{"entities":{"Q2680951":{"pageid":2691694,"ns":120,"title":"Item:Q2680951","lastrevid":47795620,"modified":"2026-01-02T17:27:52Z","type":"item","id":"Q2680951","labels":{"en":{"language":"en","value":"Stack-sortable permutations and beyond"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7638505"}},"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":"Q2680951$9CFBB408-F920-43DF-AA72-DB0A858A6E57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"364ea2a59c875df8904081d0a679e62de17f045d","datavalue":{"value":{"text":"Stack-sortable permutations and beyond","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2680951$2C03ACDD-913B-4FCF-B449-65F64B35D176","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf105631058b5d0d01f9860e2652b9984a0f15de","datavalue":{"value":{"entity-type":"item","numeric-id":322054,"id":"Q322054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$D1F5980F-DCA4-4934-ABF3-1476E5C01548","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"56f073f9ab604f3c0237b36ea8964cdfa0d52193","datavalue":{"value":{"entity-type":"item","numeric-id":161489,"id":"Q161489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$3629EDA1-208C-40BB-8CCD-879BF33D7148","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"66522f081101ad6908ea306f633c717cb55b5bc6","datavalue":{"value":{"time":"+2023-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2680951$B18DC30C-D75D-49AB-9DEE-0BC6AA366ED2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4c25f753315109785f716c8d4852b6936ded790b","datavalue":{"value":"https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2021/7.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2680951$70942B16-5DE7-485E-8914-0D5A004B18A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f922d48eb1036a5beee6f74685af975f3d33b5c","datavalue":{"value":"\\textit{D. E. Knuth} [The art of computer programming. Vol. 1: Fundamental algorithms. 3rd ed. Reading, MA: Addison-Wesley (1997; Zbl 0895.68055)] classified and counted permutations which can be sorted using a stack data structure. This was later generalized to permutations sorted by two iterations of the stack, also known as 2-stack-sortable. \\textit{J. West} [Permutations with restricted subsequences and stack-sortable permutations. MIT (PhD thesis) (1990)] conjectured a formula for the number of 2-stack-sortable permutations and \\textit{D. Zeilberger} [Discrete Math. 102, No. 1, 85--93 (1992; Zbl 0754.05006)] proved this formula. In this expository article, the author surveys the state-of-the-art in the theory of \\(t\\)-stack-sortable permutations for \\(t \\geq 2\\).  The key result is a decomposition lemma due to the author, which he successfully uses to establish asymptotic bounds on the number of 3-stack-sortable permutations, thereby disproving a conjecture of B\u00f3na (see [\\textit{C. Defant}, J. Comb. Theory, Ser. A 172, Article ID 105209, 26 p. (2020; Zbl 1433.05005)]). He also gives a new proof of the number of 2-stack-sortable permutations and gives nontrivial lower bounds for the number of \\(t\\)-stack-sortable permutations when \\(t \\geq 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680951$0B8CE41D-2D01-489E-9AFD-AFCDE162B3A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cfbe408652dc68b442b302f036cbffeb02b678b2","datavalue":{"value":{"entity-type":"item","numeric-id":255725,"id":"Q255725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$549DC826-4B07-4C7A-B1A6-DC724E116CED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680951$B2CFE8D6-CA05-4CB7-915D-8DCDBA358518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680951$F7061622-9470-45CC-80A2-6A01667DC59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680951$C7F9987A-6AA9-446E-91E9-73DCD6FD373B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90f8bc5814ba9298726b73fe227e1ad68e3cdb95","datavalue":{"value":"7638505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680951$1B3F9B7F-C837-42D1-A2DA-7CDF5AFB6254","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680951$7FB178E4-84B2-482C-8CEE-8E0C8A8D1987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6552ce75a4cc0b914792de02a4115af1fb45a794","datavalue":{"value":"stack-sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680951$F4483A69-4FA5-437F-BB17-6AC4A47CE7A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680951$F2CB5612-C383-4D86-98B4-015D07305AB0","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":"Q2680951$EBECBD39-5C26-420A-9A3E-11EB27CFCC2E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c58b0f18f9e24e07b7955cf2c2fdb1be6efafd0f","datavalue":{"value":{"entity-type":"item","numeric-id":2498737,"id":"Q2498737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$53F6202B-3A4B-46C2-829A-1A5E7B388D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a179d0e86c1d45a54aa017d7fd5ab868cce7718","datavalue":{"value":{"entity-type":"item","numeric-id":2361080,"id":"Q2361080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$4FE6ED9D-9C4E-4EE0-92D7-37D06CBB2160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d910a6895719902f0d981b57066fef38aa7e6a90","datavalue":{"value":{"entity-type":"item","numeric-id":5074765,"id":"Q5074765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$59D20813-DF38-4D2D-A942-78A1178AF7DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a5cef112e92964b887e107ebc28c223105b0ef2","datavalue":{"value":{"entity-type":"item","numeric-id":2299650,"id":"Q2299650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$D5923B42-B7DA-4E7E-A6DB-25EA498CE490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b71a697f094bbab27e70f692ea02ff0269608df8","datavalue":{"value":{"entity-type":"item","numeric-id":6161642,"id":"Q6161642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$75EADF62-CE8E-4C13-A348-B2D64CA0B145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97ee44f21ec24bf6083a38edff92bf01b30b3f80","datavalue":{"value":{"entity-type":"item","numeric-id":2225458,"id":"Q2225458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$BA0BE959-2BA8-4563-8967-90F4A320983C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d20f866a2342812edd0e11764cf6dcc5df0df2b","datavalue":{"value":{"entity-type":"item","numeric-id":2034079,"id":"Q2034079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$5AF45CC3-0F83-44CB-B63A-6DB9522E4B0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$F03E718C-3086-4147-A572-03D2BBA218AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e32e2ff3cf4a4b94496203a3edd1d841d00822b0","datavalue":{"value":{"entity-type":"item","numeric-id":1978151,"id":"Q1978151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$0F52F41F-1A5F-4DC0-8B0A-AF0EC9F54F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26944629180b1a25cfe4ea517e321fb7b95152f3","datavalue":{"value":{"entity-type":"item","numeric-id":1889895,"id":"Q1889895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$352D136B-EE0C-4D22-918E-A276ACA72BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe322fffe6cd39ce712705296c2f3ff9471fea65","datavalue":{"value":{"entity-type":"item","numeric-id":715231,"id":"Q715231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$643B7524-1F0A-4F96-B83B-2AC7F2453D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972eb69b01d9cc3ca7efe885df6a69dd861bcbd4","datavalue":{"value":{"entity-type":"item","numeric-id":1193435,"id":"Q1193435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680951$095AA734-A93B-41D4-A10B-DA7AF7128DC1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"85c64c6b1df10b73d227d50b8c5e09498409d986","datavalue":{"value":"bafkreia6eckn6ijzc6ixsvhn55lguarkmnkocwr2jdvzklcbr6353omjj4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680951$AACF9D58-E31E-44D5-8DC9-B9E45E675BAC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1c564b350eae0a32a7538f8e27690ac5faebd6d","datavalue":{"value":{"entity-type":"item","numeric-id":2299650,"id":"Q2299650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14ed18cad8df1a92bf45e98c8a26e1742bba019b","datavalue":{"value":{"amount":"+0.9346486330032348","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":"Q2680951$B5102B68-B5C6-49C7-92D6-701B9B167472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e41e3fd51b2803a1b9322955b8604b56917a280","datavalue":{"value":{"entity-type":"item","numeric-id":2361080,"id":"Q2361080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b432675ee65816c9c71cf7fa91ab7e16d3b9bb12","datavalue":{"value":{"amount":"+0.846767783164978","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":"Q2680951$CA6C6A84-8BBA-4DCB-B8E7-63823A28ECDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"824a999a3e2be7cdc9b9dfb516754e8abec166ca","datavalue":{"value":{"entity-type":"item","numeric-id":5074765,"id":"Q5074765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c33288b3d6fa97ecb04095ef05edf98d58f8ad2a","datavalue":{"value":{"amount":"+0.8392106890678406","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":"Q2680951$BA1837E3-721E-41BC-8E27-3968C0E13EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9de4adea14b7631cb364952096f38be3f132ebcc","datavalue":{"value":{"entity-type":"item","numeric-id":2199801,"id":"Q2199801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aada142c1a1411b2a12e95392ea6e7920f9274b7","datavalue":{"value":{"amount":"+0.8363126516342163","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":"Q2680951$53627294-8C73-48F4-8185-6DB6A7AD1E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ce0752adc68489cd9fe4237cdc39f370a131fa1","datavalue":{"value":{"entity-type":"item","numeric-id":5377411,"id":"Q5377411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"354e8253c1b6e682e40a207660bb15c13c461f65","datavalue":{"value":{"amount":"+0.8344569802284241","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":"Q2680951$AD7057EB-262F-4C43-A0E5-04C91EEFFFB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2680951","badges":[]}}}}}