{"entities":{"Q2344818":{"pageid":2355561,"ns":120,"title":"Item:Q2344818","lastrevid":57866787,"modified":"2026-04-02T21:06:07Z","type":"item","id":"Q2344818","labels":{"en":{"language":"en","value":"Permutations generated by a depth 2 stack and an infinite stack in series are algebraic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6436278"}},"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":"Q2344818$037D04B7-6E07-4122-8655-462BAA0A5699","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cacb92cfc8ed6ab785fcd8722019fee5b6ebb43d","datavalue":{"value":{"text":"Permutations generated by a depth 2 stack and an infinite stack in series are algebraic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2344818$CCEF11C4-2F46-4ED4-8873-4D2DF0BC19D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7e25ae9da7fa3d4a28ad485c03ffed00a58f0a0","datavalue":{"value":"1311.05005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$8CFB6EEB-36DC-43F5-9DF2-CA7C98720F25","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"70ab787c9073b134ad5dbc9157f7bc83a250ba96","datavalue":{"value":{"entity-type":"item","numeric-id":1863082,"id":"Q1863082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$DE5B4346-9CD2-4D0E-8D6C-4FB500511FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"df5d7eeb6bae375a2867529849c1d527f4df9acc","datavalue":{"value":{"entity-type":"item","numeric-id":617950,"id":"Q617950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$C2705FCE-08A2-473E-8167-33A3DD6FBE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5cd304afac648773f4c0d09fedadc5ee13e0f9c","datavalue":{"value":{"entity-type":"item","numeric-id":188708,"id":"Q188708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$8FD7366E-6FA6-47E1-9933-79B945331264","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":"Q2344818$0B1AAEFF-721A-48E2-973C-560D5B94AE5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d4eb1898e7e9f37f96fc2bc2b93f3d306019019","datavalue":{"value":{"time":"+2015-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2344818$286C4F01-A8D2-4521-802D-A3794E4DAC91","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"91736fe0b39449e4dd45b54b5481833789fe7336","datavalue":{"value":"https://arxiv.org/abs/1407.4248","type":"string"},"datatype":"url"},"type":"statement","id":"Q2344818$56895743-5D67-476B-86A2-49EB82288C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6c89e758c6979b44881d691b8cf6e2365276e93","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p16","type":"string"},"datatype":"url"},"type":"statement","id":"Q2344818$109B9852-8237-4985-B2B0-F6EF06F2A89D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6db4b68ae6af3d34b44b15d068e474be4c41aae2","datavalue":{"value":"Summary: We prove that the class of permutations generated by passing an ordered sequence \\(12\\ldots n\\) through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length \\(n\\) is encoded by a string of length \\(3n\\). It follows that the sequence counting the number of permutations of each length has an algebraic generating function. We use the explicit context-free grammar to compute the generating function:  \\[  \\sum_{n\\geqslant 0} c_n t^n = \\frac{(1+q)\\bigg(1+5q-q^2-q^3-(1-q)\\sqrt{(1-q^2)(1-4q-q^2)}\\bigg)}{8q} \\]  where \\(c_n\\) is the number of permutations of length \\(n\\) that can be generated, and \\(q \\equiv q(t) = \\frac{1-2t-\\sqrt{1-4t}}{2t}\\) is a simple variant of the Catalan generating function. This in turn implies that \\(c_n^{1/n} \\to 2+2\\sqrt{5}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344818$D2917B65-E0FE-40A7-923A-C43768C91785","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$137C6D60-8E26-43B4-B129-E331FFD5960A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$FE2EF176-F65D-4826-B047-D7C5903E9477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$FB61BDB7-A1D4-4EBA-A8F4-4F4E7497FF7C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"350ef3339b3634d6bab0e8aaec323e0fc821bbcb","datavalue":{"value":"6436278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$E7A48582-0322-483F-B53F-D4053492AC36","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70ee8fd2a028d8d8b7799cfb8b748b195392e2b1","datavalue":{"value":"pattern avoiding permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344818$28201C41-5FA5-47E6-82A7-87E0B07E6A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52b2d29a06adc2ecb379f579c108a9b490aa9f69","datavalue":{"value":"algebraic generating function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344818$B969E720-AF4E-42F4-9A42-955218C9935A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d75d448735778f46c4e9667e177539a844422b26","datavalue":{"value":"context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344818$756045B4-8BE1-4333-89F4-4F472E7EF682","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":"Q2344818$440F175D-48DF-4581-AA51-ED2F4B7873C2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1306afc2a7243f06154716bc100ead6ea2f27f38","datavalue":{"value":{"entity-type":"item","numeric-id":1426439,"id":"Q1426439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$332C0A82-0B9E-4633-ADEE-EE2ACB716599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5adf81fca8e354372c8511635fbb4ee49c46f1","datavalue":{"value":{"entity-type":"item","numeric-id":2490021,"id":"Q2490021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$3EAE2561-78ED-4ECC-9A33-B76FF151CD56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e38803483b6182b945d63425c51df2e3b0961ca","datavalue":{"value":{"entity-type":"item","numeric-id":458593,"id":"Q458593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$450559CB-B3F1-4A96-BB2D-1EC688318895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"881c882d3deb57353540496a971b6ea0fe33c8bf","datavalue":{"value":{"entity-type":"item","numeric-id":2380302,"id":"Q2380302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$B4CE8092-197E-4FC2-BDAB-EFF056069AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"270a36152f3a85c7b7e52b90124be3bdbbf2ca17","datavalue":{"value":{"entity-type":"item","numeric-id":2571290,"id":"Q2571290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$19E08552-1094-4E9A-B2D3-B24F34A2AA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06692efc1679a3763702937e5587a435e19646a7","datavalue":{"value":{"entity-type":"item","numeric-id":1391529,"id":"Q1391529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$1BED7967-A6E7-4E7C-AD4E-9776CCF0E867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97f05915ad9caec5e52e4d39c0c3eac95d0798f8","datavalue":{"value":{"entity-type":"item","numeric-id":1853525,"id":"Q1853525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$538E2A48-3AE3-4DB7-B126-61E92C49D17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb34e780119c0b638e5db17ad752577fcf82cacb","datavalue":{"value":{"entity-type":"item","numeric-id":1374188,"id":"Q1374188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$CA4240A7-8970-41E9-A03A-B7AAD0EF845A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffcf74453560a7faa36d6b3d0f2f62b38133c103","datavalue":{"value":{"entity-type":"item","numeric-id":2254999,"id":"Q2254999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$761D91A4-834D-4FE7-82A8-56BD6F32E7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17445752731ab63ba64205bdc31486f1ef385180","datavalue":{"value":{"entity-type":"item","numeric-id":2500987,"id":"Q2500987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$A739D0FA-07FF-411E-AA45-ADEAA1598E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ef8fac80d379bd80260f843138869332bd9384","datavalue":{"value":{"entity-type":"item","numeric-id":3549563,"id":"Q3549563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$AE5414FF-4F41-4E76-88F8-DF4A6259BB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25c630bd26c81455ea04b41e0046994ab243252a","datavalue":{"value":{"entity-type":"item","numeric-id":916659,"id":"Q916659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$C564C2EE-CD5E-45E2-A863-A23D9385E895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$86D1D353-9F77-4E04-AAED-3571A9977FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$01B06249-DD8F-4667-A1E5-68A95A95D5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"948fce0699519e804c8e909c4a792a15007f88eb","datavalue":{"value":{"entity-type":"item","numeric-id":2965521,"id":"Q2965521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$4ED48249-410C-4EFB-B92D-78E4FA1C9AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b449c1fa7cfb7efa1bf3e42ea7c8a97fdaca20b","datavalue":{"value":{"entity-type":"item","numeric-id":5916426,"id":"Q5916426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344818$D38486A2-DC6A-46B6-9B67-44D36BC91565","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a7e1d2ec0971d86a5f1b293503d9d0da9b2afaa1","datavalue":{"value":"bafkreiayzj2jc4ooiwszxdvlitv5l2buvtvwwp7sf4wl7g7r6xoqluxl3i","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344818$50F4D32D-A244-40C1-AAD9-AD6EA15F5DFF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b77609dc549638d632bb28ba5d07592e10bafe57","datavalue":{"value":{"entity-type":"item","numeric-id":2500987,"id":"Q2500987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16cd3d02162389423ee7c34452de7a991088960e","datavalue":{"value":{"amount":"+0.8302034139633179","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":"Q2344818$D782AE16-F056-4793-BA68-FD7798D9A9D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36a3160327be10a9285fa7788f1f440cedce7f0c","datavalue":{"value":{"entity-type":"item","numeric-id":343835,"id":"Q343835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22f19a6527979d9d2a942276672f57f2dc30e1de","datavalue":{"value":{"amount":"+0.7650306224822998","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":"Q2344818$60DBE1C8-ED67-4FD9-9BD7-942C0004A759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f7c1e658a6db39519b377c9d36a77df5269d078","datavalue":{"value":{"entity-type":"item","numeric-id":1747767,"id":"Q1747767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46325ac401f5a8ab55710327463d61618ec9543e","datavalue":{"value":{"amount":"+0.7612074613571167","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":"Q2344818$802726C5-2B13-4186-BAD1-388201C85257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093f0adb8e69b7cd07b91c7be8837c4b5de32aba","datavalue":{"value":{"entity-type":"item","numeric-id":1383515,"id":"Q1383515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"349ef0ea3763347061ae210650b9243ca2870031","datavalue":{"value":{"amount":"+0.7524553537368774","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":"Q2344818$9C9FB1CB-5541-49DD-A334-C64C8EF71010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"872d4f65c9562fdc1cba352314095a2ce1632df2","datavalue":{"value":{"entity-type":"item","numeric-id":1853525,"id":"Q1853525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"349ef0ea3763347061ae210650b9243ca2870031","datavalue":{"value":{"amount":"+0.7524553537368774","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":"Q2344818$306E4A5A-4D3C-441D-9112-4EE73BB86009","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2344818","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2344818"}}}}}