{"entities":{"Q2628258":{"pageid":2639001,"ns":120,"title":"Item:Q2628258","lastrevid":57965499,"modified":"2026-04-03T06:41:40Z","type":"item","id":"Q2628258","labels":{"en":{"language":"en","value":"Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6729621"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$16D8420F-2F7E-4D50-AC20-575AFC679BE0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fdb54c7901fa064da96d0d1fc7790fb17b0cb956","datavalue":{"value":{"text":"Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2628258$639E9B39-D7B0-42E7-A6BD-8E2442C7356D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7773736a77007d71939848029f6be88d5c611ddd","datavalue":{"value":"1366.05119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$C13D0DBA-4D43-4F09-8CCF-66D7AAFD5782","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9358371eb481c5669d7e6cbbb165b81613fb2ecd","datavalue":{"value":{"entity-type":"item","numeric-id":432755,"id":"Q432755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$709229C9-4595-47D4-918D-84D9BD2F3E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"561bc5db4c2a98c2dcd18d83b7f7bb593fb08544","datavalue":{"value":{"entity-type":"item","numeric-id":491960,"id":"Q491960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$06A86788-B779-49AC-8FC1-E2D7BA723CB6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$F7449B65-F480-4909-BE1F-8F1A88975A98","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9fb82429bb4ba602ab7d5caf04c575952ba3fb53","datavalue":{"value":{"time":"+2017-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2628258$BDBF049F-6EE4-4C26-9ED4-AF7F07E97E77","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02dc5bf41e2133db7ea30809bcb8adf0844f151e","datavalue":{"value":"https://arxiv.org/abs/1606.07597","type":"string"},"datatype":"url"},"type":"statement","id":"Q2628258$AAE7863A-395B-40D3-9D17-546A5666F05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"728a384c7df3c209b8c003a3a1d0da6cb5a2d338","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p28","type":"string"},"datatype":"url"},"type":"statement","id":"Q2628258$8B12642C-71C6-4090-AC78-3C501A7414F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de10860ca1fea19093ef1e30c7404415bc8f602c","datavalue":{"value":"Summary: The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and M\u00fcller.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$4EF29210-77BE-4479-B6B8-531E252423EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8cf2f692eb0d5c2fc2ce5b2154318999029c1c1b","datavalue":{"value":"05E10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$1F61A07B-AD16-49A4-AE60-1B1C3BEABD76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"42de9321ec9bffe9bd1dcf8c8689a504914f3754","datavalue":{"value":"33F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$9C67D8B1-AE07-40F8-88B7-C7A6A9050FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$74D84D61-8297-447D-9A05-8DB8047392FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35126e60302ea2da644622f203c170dccc114af1","datavalue":{"value":"6729621","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$CB190192-3118-423E-83BE-E4AD0BCA535A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b7dc3979cbd6cf698808b000da38b139059fcf0","datavalue":{"value":"Novelli-Pak-Stoyanovskii algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$CF011F09-7474-43FC-BC3B-3C34915802B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3c60d808f53ee18d5e34eff3ac95456d981e7db","datavalue":{"value":"standard Young tableau","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$5062D01A-D6DA-43FA-970F-408ED5D8EEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c20bbfabf47d9537f910ea1878414a01b1370624","datavalue":{"value":"hook-length formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$B8BA4F66-2338-4033-8A56-F3884C1E4936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"553fdd7868ccf0d19550ee87a05ea6ab73e29844","datavalue":{"value":"average case and worst case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$C8938488-C25E-46BF-A40B-F30FF9DC44E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b56e395a462378e6a23bcf12f58c58bde072f4af","datavalue":{"value":"symbolic summation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2628258$2EF07E24-5C21-42F6-9B26-0A6F8ED77C7C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"085133077efa217e4777f2824e2f6681884891f1","datavalue":{"value":{"entity-type":"item","numeric-id":23579,"id":"Q23579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$F4C3ACEE-1CE2-4E35-8DB2-59A92AA0E7A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c66446f9cd4a7290c9edd2514c3e5936a8d3bae3","datavalue":{"value":{"entity-type":"item","numeric-id":26177,"id":"Q26177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$65917BFC-7DD5-4142-9CBB-50EB597743E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"99bab8cc7e3d0482fe74192a712cfb8a04059eff","datavalue":{"value":{"entity-type":"item","numeric-id":18971,"id":"Q18971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$567275C5-15CA-4DDD-BEC6-59020C2DE276","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$3E8A9E67-3100-4909-A138-701C1BF8EA1B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeddb77a3ef4cad4a2b8aa07dcda364a07fac202","datavalue":{"value":{"entity-type":"item","numeric-id":339379,"id":"Q339379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$DBA2A3B5-1F7C-4EB1-A56F-17697BC98F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebb9c3f2e440e80830ccab93ece5ffb5a1f889b2","datavalue":{"value":{"entity-type":"item","numeric-id":4234305,"id":"Q4234305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$165CFD66-2E86-4B0C-A114-C4683C11450C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6dcd7c871b2c3db2fd9d865b595d9250aeac0aa","datavalue":{"value":{"entity-type":"item","numeric-id":5841616,"id":"Q5841616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$B61D4CD0-CE06-4D81-9A7F-8E5C93284E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e16080b6ae9dcdc7ef7313eb63dcf1d58b18fc68","datavalue":{"value":{"entity-type":"item","numeric-id":5826959,"id":"Q5826959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$615FF0B0-0767-4DB6-8998-D7FDC00756B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f89a6e69ca8bd1033b672532eff3510a04642b4","datavalue":{"value":{"entity-type":"item","numeric-id":3957938,"id":"Q3957938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$5065F30B-0E2F-4DA9-8CD6-E58BC3C8A75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bf8a388a8b7a344206e6b05f995568a5a24c176","datavalue":{"value":{"entity-type":"item","numeric-id":1806214,"id":"Q1806214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$3643C8BB-72AE-44A9-931E-35251E809A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f28c269329b95a99d792f6efe0146cde9c720d22","datavalue":{"value":{"entity-type":"item","numeric-id":1240509,"id":"Q1240509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$9DAE31CE-359D-4307-AB37-B5D153E0A646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6e03c4234ea22b70208fd3a10be66495c831031","datavalue":{"value":{"entity-type":"item","numeric-id":491961,"id":"Q491961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$E299457D-64C3-45FF-8653-657417F3BE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62ba02d8d7b47b98b69ee66cb12d952c0c011633","datavalue":{"value":{"entity-type":"item","numeric-id":3836512,"id":"Q3836512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$51948BD5-AE51-4048-BB0D-A1AD60079212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e00ba7d03a470ce43f8b1440f8d2f240d4fa40f","datavalue":{"value":{"entity-type":"item","numeric-id":1918487,"id":"Q1918487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$68F284DE-10D2-4688-841C-C35E625B29EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c4ec75eb1df7410ececc1deecb107ec91c8a62","datavalue":{"value":{"entity-type":"item","numeric-id":4875364,"id":"Q4875364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$2C8BCF15-5D5F-42A5-891B-7BB127CE5FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e70b685cdc53828a965dc466ebc1734d138a940","datavalue":{"value":{"entity-type":"item","numeric-id":2716065,"id":"Q2716065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$455B1A3F-7842-4968-822F-407F39482482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f515454bb1e63239657166fc6a2b9bae052166fb","datavalue":{"value":{"entity-type":"item","numeric-id":2654601,"id":"Q2654601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$CEA691E5-F077-44A9-8CE4-C55F2874C071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afc9744a4c4aaf4865625e9967177499464b3c14","datavalue":{"value":{"entity-type":"item","numeric-id":5244928,"id":"Q5244928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$F3D6CC86-10E4-430B-9ADA-B14828AE1DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45e29ac01bbce7a408399c21a4b5037401fb64ac","datavalue":{"value":{"entity-type":"item","numeric-id":492025,"id":"Q492025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$89F4176F-97AB-4FAA-BACE-B0F65FB4B4D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62804a0cccd0b4476a3013373a0ce9c1c0ad477e","datavalue":{"value":{"entity-type":"item","numeric-id":1711991,"id":"Q1711991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2628258$1D3BC197-8217-4FB4-B922-06A8063D83D1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"72dca7a555c36cb8dde961df72c5dafacb993bd7","datavalue":{"value":"bafkreiagtzewqojdopcoyatm3hpkpgkwtecakkaodpmmp5vna4kvqsbgde","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2628258$A07C0464-BD8C-4387-B60A-70437813B92F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b52244ed0a494a803d1efd8cc250c5d86f5fe6d","datavalue":{"value":{"entity-type":"item","numeric-id":491961,"id":"Q491961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b68b2686910951d98cf7c14938b53d04052530e9","datavalue":{"value":{"amount":"+0.8881813287734985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2628258$6409A887-181E-4BCB-B21B-973A6E800207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"193315e3bd7d15bf674bb00be9b01e3ea4dddacb","datavalue":{"value":{"entity-type":"item","numeric-id":4584101,"id":"Q4584101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4fc09bb54ff297574339ed048c6688db3f25cc4","datavalue":{"value":{"amount":"+0.8723040223121643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2628258$08C7DCE2-04DF-47F6-8FA7-E579C5305B10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17955a0bf198a8c18efa44f0ac2e3e47404c8aa0","datavalue":{"value":{"entity-type":"item","numeric-id":3836512,"id":"Q3836512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bf471c62cb951328fe390322366555312815c85","datavalue":{"value":{"amount":"+0.6773356795310974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2628258$0A9DBBA1-9547-434A-92F3-C62584BD1DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd6a9f2de34557d2432fc7387ce7ef0e055dcffc","datavalue":{"value":{"entity-type":"item","numeric-id":1806214,"id":"Q1806214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57262a34c8e11f7e25c78518d671da75a16957ab","datavalue":{"value":{"amount":"+0.6771343946456909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2628258$C082788D-7065-4252-9A87-588C7C8FF06B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05665e8b56149e25f12fc58eaeccb4b99711849f","datavalue":{"value":{"entity-type":"item","numeric-id":1310601,"id":"Q1310601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"085abcb2db146ec775f2bea7644b0ce4c08787d1","datavalue":{"value":{"amount":"+0.671009361743927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2628258$30B013A4-11EE-4495-A125-56DF10712712","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2628258","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2628258"}}}}}