{"entities":{"Q1383515":{"pageid":1394255,"ns":120,"title":"Item:Q1383515","lastrevid":46968492,"modified":"2025-12-25T23:16:16Z","type":"item","id":"Q1383515","labels":{"en":{"language":"en","value":"Multi-static enumeration of two-stack sortable permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1144300"}},"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":"Q1383515$4DD1E544-EAE0-47C4-BD38-B900380A2890","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7cfc7403b6c6f19545b9a0033cb8f0e99506ae2d","datavalue":{"value":{"text":"Multi-static enumeration of two-stack sortable permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1383515$C771DD6C-25DC-43D9-AE5F-3D30BF9016A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"839fce7af35970f34dba8dd1019aa79daa84bef4","datavalue":{"value":"0890.05004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$BCA8D1B5-ED96-4626-BADC-B4D8F2C555C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a89011941c7adc41dcc256aa01bc422f77f57e49","datavalue":{"value":{"entity-type":"item","numeric-id":232252,"id":"Q232252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383515$8AB6B64A-FC26-4433-B80F-0CA0CDCF2BCB","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":"Q1383515$CB9B8185-99A6-4C59-B0B7-B4C0A8E55908","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"50be06f6d092f252de9c2eaf3f0ef4dc9d82808c","datavalue":{"value":{"time":"+1998-04-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1383515$8428153A-6553-4585-99D8-AF63682B45FA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fdac65ebc8aae6419fca8b6ccd3d59c42611cf40","datavalue":{"value":"https://eudml.org/doc/119439","type":"string"},"datatype":"url"},"type":"statement","id":"Q1383515$3D79979F-9E76-4B60-BE61-CBFC48EEE9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fc53d35aea404a8aeee095a45ec973c5ec75d8c9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_5/Abstracts/v5i1r21.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1383515$F9CE18AC-93DC-4BC7-8782-7456AF568666","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e9b70ad1e36e6bd59446590d4df603f5e02ee6e0","datavalue":{"value":"The permutations being counted are words of length \\(n\\) \\((n\\geq0)\\) in the alphabet \\(\\{1,2,\\dots,n\\}\\), no symbol being repeated. The mapping \\(T\\) is defined recursively: the empty word is mapped onto itself; if \\(\\sigma=\\sigma^{(\\ell)}n\\sigma^{(r)}\\) is such a word, then \\(T(\\sigma)=T(\\sigma^{(\\ell)}) T(\\sigma^{(r)})n\\). A permutation \\(\\sigma\\) is \\(k\\)-stack-sortable if \\(k\\) successive applications of \\(T\\) yield \\(123\\dots n\\). The numbers of 1-stack-sortable and 2-stack-sortable permutations have been determined by \\textit{D. Knuth} [The art of computer programming, Volume 1, Fundamental algorithms, Addison-Wesley, Reading, Mass. (1958) p. 238] and \\textit{D. Zeilberger} [A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \\(n\\) is \\(2(3n)!/((n+1)!(2n+1)!)\\), Discrete Math. 102, No. 1, 85-93 (1992; Zbl 0754.05006)] respectively. ``In this paper we shall enumerate two-stack-sortable permutations \\(\\sigma=\\sigma_1\\sigma_2\\dots\\sigma_n\\) according to the following classic statistics: the length \\(n\\); i.e. the number of \\(i\\in\\{1,2,\\dots,n\\}\\) such that \\(\\sigma(i)>\\sigma(i+1)\\) \\dots; the number of right-to-left maxima, i.e. the number of \\(i\\in\\{1,2,\\dots,n\\}\\) such that \\(\\sigma(i)>\\sigma(j)\\) for all \\(j>i\\); the number of left-to-right maxima, i.e. the number of \\(i\\in\\{1,2,\\dots,n\\}\\) such that \\(\\sigma(i)>\\sigma(j)\\) for all \\(j<i\\). Moreover, using Zeilberger's factorization requires (us) to introduce another statistic \\(\\ell(\\sigma)= \\max\\{\\ell:\\sigma^{-1}(n)<\\sigma^{-1}(n-1)<\\cdots< \\sigma^{-1}(n-\\ell+1)\\}\\dots\\). We \\(\\dots\\) prove that our five-variable generating function for two-stack-sortable permutations is algebraic of degree 20''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383515$99C23B6C-564F-4BED-A9F0-3A5BACCB3114","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$789B7171-D11E-4DE9-8269-E110E7266FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$60CD1EF3-56DB-4A4C-ABE9-7557E6B80204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$A7A2C39B-51EC-4E74-911A-6BACABA6F2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$0CF80712-5481-4944-B3EE-23BFD2203648","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab76907be8e309a7c2b11e9b58c3f18342bd0f50","datavalue":{"value":"1144300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$AE9D8BB0-7652-44A1-8905-9FC0CB88F346","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383515$930F2D7D-2606-4843-A7B5-A986887A1058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16e37fe13d140ec8b9ab008d123de408b1b91520","datavalue":{"value":"two-stack-sortable permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383515$656A7E02-6256-458D-81A1-16963FE14EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fac2114354ca7f6c05a9e13ecf75f42fae7e6874","datavalue":{"value":"statistics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383515$170AC068-3668-4948-B188-9FAD75A2EF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cd04b2cc505cb409797e572750d2f2642129dfb","datavalue":{"value":"generating function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1383515$77F873D1-5628-4E99-B3AE-F314439AE6CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1383515$A40FB5F4-C211-40FA-8E7B-356F4D9D6F95","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":"Q1383515$79F153E6-4EDC-4CBD-AEC6-C76EC6FD711A","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fd7eaafc113f2cd61b5d23d005e12358db32465b","datavalue":{"value":"bafkreibp4epi4bycojqhkwweizqrthnk7tke7zm67o43qzz7hqsxzp7amu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1383515$1941D54B-C0B6-4302-98B7-EF50FC96424D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f1fc3f527844c39dfb830f1256d1ea469c8b6f3","datavalue":{"value":{"entity-type":"item","numeric-id":2680951,"id":"Q2680951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ebd070e52622263d96dccdb6f4b2a784b775094","datavalue":{"value":{"amount":"+0.8347892165184021","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":"Q1383515$952D4185-086A-4EE8-B1BF-183B1810D1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56de5f3fd6e6803216bf318d2feb6b9b87969ffb","datavalue":{"value":{"entity-type":"item","numeric-id":688711,"id":"Q688711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11c3735ed51d76e30176afcd8011b3163dafa0dc","datavalue":{"value":{"amount":"+0.8185736536979675","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":"Q1383515$21F93D9F-1AA0-46AD-A6AF-154D2D23C372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c723d5803714f2d2d423d6511bfbe6fe770c995","datavalue":{"value":{"entity-type":"item","numeric-id":5947480,"id":"Q5947480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12d966660f2e36f89f098800bc5d10a4682e52a2","datavalue":{"value":{"amount":"+0.8135532140731812","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":"Q1383515$C82D696C-F5F0-403C-B8E2-FC2D71A7DCCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccaff5af6f2150270a858ade7f0cb1290cc3f88b","datavalue":{"value":{"entity-type":"item","numeric-id":458593,"id":"Q458593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"284f41ab77e7c2844da7ef91947e7b82aaa049e5","datavalue":{"value":{"amount":"+0.802529513835907","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":"Q1383515$76C8FB8B-4009-40B2-9A00-92031F0BE465","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1383515","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1383515"}}}}}