{"entities":{"Q556857":{"pageid":558624,"ns":120,"title":"Item:Q556857","lastrevid":62724249,"modified":"2026-04-11T08:01:41Z","type":"item","id":"Q556857","labels":{"en":{"language":"en","value":"The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2181974"}},"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":"Q556857$97687986-69F1-458E-9903-185D0F5B6CB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"977ae309d5946f36a2e2b1971ee7639d5321aee3","datavalue":{"value":{"text":"The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q556857$3924D901-5F45-4CDE-8353-AF60EBFD9640","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"46c475380610d5642d5f8fbd33e12d5841a6fb80","datavalue":{"value":"1067.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q556857$F9E58B10-48D6-410A-9EE0-729A3477242C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ec23f34bfcc389574096d79ab6ba4481139b927","datavalue":{"value":{"entity-type":"item","numeric-id":395244,"id":"Q395244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$3AC22564-3072-496C-895B-EA8C43A6FA9A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$6768FA8D-4959-4992-A160-2AD88C6A6C44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"248c1efd530ae2f9901b8ca831703cab8c4ba528","datavalue":{"value":{"time":"+2005-06-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q556857$8EFDE49E-78BF-4CE9-B279-79F309138A02","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92f522721a75f126a54c934e3983531420a5a8e6","datavalue":{"value":"https://arxiv.org/abs/math/0403502","type":"string"},"datatype":"url"},"type":"statement","id":"Q556857$4E554BDA-B772-457F-BCD5-45A378B5D950","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd056f865c5c3ba578a17870d6a0e8c6d7c222a9","datavalue":{"value":"If \\(p=p_1p_2\\dots p_n\\) and \\(q\\) are permutations of \\(\\{ 1,2,\\dots,n\\}\\) and \\(\\{ 1,2,\\dots,k\\}\\) for \\(k\\leq n\\), respectively, then \\(p\\) is said to contain the pattern \\(q\\) if \\(q\\) and \\(p_{i_1}p_{i_2}\\dots p_{i_k}\\) are order isomorphic for some \\(1\\leq i_1<i_2<\\dots<i_k\\leq n\\), i.e. the terms are ordered in the same relative way. Let \\(S_n(q)\\) denote the number of permutations of \\(\\{ 1,2,\\dots,n\\}\\) that do not contain a pattern \\(q\\). It follows from a recent result of Marcus and Tardos that the limit \\(L(q)=\\lim_{n\\to\\infty}(S_n(q))^{1/n}\\) exists. In the present paper the author proves that \\(L(12453)=9+4\\sqrt{2}\\) providing the first example of a pattern \\(q\\) for which \\(L(q)\\) is not an integer. He also determines \\(L(q_k)\\) for \\(q_k=12\\dots(k-3)(k-1)k(k-2)\\) as \\((k-4+\\sqrt{8})^2\\). Finally, he proves that \\(L(q)\\geq L(12\\dots k)=(k-1)^2\\) for so-called layered patterns \\(q\\) of length \\(k\\) which supports a conjecture from 1997 stating that \\(S_n(q)\\geq S_n(12\\dots k)\\) for such patterns \\(q\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q556857$1804950D-9826-48B1-AFDE-6BC0F8B5ABF0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c21cb54e7c2c469712a9307e52fa5ab7414ba5da","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$C93AF9A6-97C7-4BFE-A0EB-E28116AD2E04","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q556857$CC5233AD-59C2-43C7-B2F5-D74B36E553E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7e639fbccb1428bf014fc16efc57fb6fd1471c0","datavalue":{"value":"2181974","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q556857$BA8B7542-6254-40BC-BB53-4C85066776BA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q556857$04A99A75-4610-4E5C-88BF-A84800E0C4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a650f15583af62d1827b2ebb16e134294cf5840","datavalue":{"value":"pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q556857$CFEB9A0D-48AB-411E-ABAC-55C7171300A6","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":"Q556857$B33CDB63-4397-451B-9E83-D5CC173C0CF7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"545f47d76edfba4498818bc0981e7cad09cc1826","datavalue":{"value":"W2105493981","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q556857$B0188E96-0EB8-4EAB-A91D-DB85ED82B970","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d28b2cf44fef9ef108fad5c71b0fb6b6131a36fd","datavalue":{"value":{"entity-type":"item","numeric-id":1305174,"id":"Q1305174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$9240EFBF-7302-4CDC-91A2-D02B0D7D505D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60d5d5364f76220c9d4a7f65ceaad746c44020dd","datavalue":{"value":{"entity-type":"item","numeric-id":2643864,"id":"Q2643864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$9A8D27A2-0A64-4BA3-9369-F1738B99DBE1","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":"Q556857$35558A1A-EAF5-4E96-BDC2-F57C13D9F606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3096c229b1a3bfa3a25283738f258865fb9d543","datavalue":{"value":{"entity-type":"item","numeric-id":3148849,"id":"Q3148849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$D83F0415-CD76-4870-BD24-2652A1FA7B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fbc06056ab860c3fe5529345ab39aeea542dcf3","datavalue":{"value":{"entity-type":"item","numeric-id":4821520,"id":"Q4821520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$AC2E2FB9-9DC7-44FD-B427-22C841FEFED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d98e6e23d79c7beb237f494a6118d8fb7ddb02bd","datavalue":{"value":{"entity-type":"item","numeric-id":1377745,"id":"Q1377745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$0D5A1EB5-ACEC-40A1-BA0F-6F8BE6BC3A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0c94cd4a96fc7dec5471f770b1a7fa40188ac05","datavalue":{"value":{"entity-type":"item","numeric-id":1871365,"id":"Q1871365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$3EB9F8B5-43C3-48FE-B08A-80645D255B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50240b068b2f4e66fb8cd75d033da96637e75bdc","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$5EE52058-B64D-4135-824B-A7013DCABC88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01c0c13e7aff2aab90eeacee5f7719d3db6fcf8d","datavalue":{"value":{"entity-type":"item","numeric-id":1838567,"id":"Q1838567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$F62F08E3-5D33-4A59-B151-6C90220064AC","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":"Q556857$21572806-9A3A-43FD-BCBC-8636009E7B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d825095afe6e2215dbc5ab36153017eec07800e3","datavalue":{"value":{"entity-type":"item","numeric-id":4344108,"id":"Q4344108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q556857$970DBCDD-9D38-48AF-BA5C-61DAF49BC033","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8ad7e92b1671dd490dfc36edfeffcb9001c71ed3","datavalue":{"value":"10.1016/J.JCTA.2004.07.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q556857$9A13E69F-044A-4F02-A313-BA80C6D77622","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e450ce237e87c367a82a5bd52f5eddf4d262abd4","datavalue":{"value":{"entity-type":"item","numeric-id":444905,"id":"Q444905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6edb2bad103922e1ce52c400d68e0b2a46697618","datavalue":{"value":{"amount":"+0.8897269368171692","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":"Q556857$038042A6-CAA2-4459-AE8F-2FAAE23510A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4abef1b3c1263e6978939dbc624f3ca1749839ad","datavalue":{"value":{"entity-type":"item","numeric-id":1279660,"id":"Q1279660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcf6f2cdf921e220b1496299a2eea259f94caa5d","datavalue":{"value":{"amount":"+0.850191056728363","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":"Q556857$1976C069-69B6-457C-859E-2CD150460E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b628f30e35497108b952bcfff28136f4f1323c4a","datavalue":{"value":{"entity-type":"item","numeric-id":854808,"id":"Q854808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7660538c79036ea95bae2ca9590815415a1ec98","datavalue":{"value":{"amount":"+0.835091233253479","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":"Q556857$55146466-3AC2-4190-A7FF-DF0CAA217C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b81d8d39533cce54992f52338a151d1ccc163cc6","datavalue":{"value":{"entity-type":"item","numeric-id":1305174,"id":"Q1305174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d159094ea96b014284813caa55209c8eb595079e","datavalue":{"value":{"amount":"+0.8298795819282532","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":"Q556857$9839EFCD-996F-4CEA-8957-D0AD97AD7D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb3c07c259afdb952994e0e04cb3fda2ced39bab","datavalue":{"value":{"entity-type":"item","numeric-id":2490021,"id":"Q2490021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3c9104196e17ae338aa292d542c4361776fe7d9","datavalue":{"value":{"amount":"+0.825689435005188","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":"Q556857$CE7F7E1F-A388-4230-892B-CC6C32100129","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_limit_of_a_Stanley-Wilf_sequence_is_not_always_rational,_and_layered_patterns_beat_monotone_patterns"}}}}}