{"entities":{"Q1305174":{"pageid":1315924,"ns":120,"title":"Item:Q1305174","lastrevid":46846011,"modified":"2025-12-25T17:20:26Z","type":"item","id":"Q1305174","labels":{"en":{"language":"en","value":"On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1345966"}},"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":"Q1305174$34F64EF8-21F5-490A-B8C1-56A07BAD108D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e55de372a181fccfce457d4da13d1bfaaa7ca71","datavalue":{"value":{"text":"On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1305174$9CBC9670-8B8D-4D83-96C4-FBF5712E557A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fdf21d446179e68518c24697f8930174b1755788","datavalue":{"value":"0922.05002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305174$68939089-859B-4C22-807D-5A71E45C7902","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac21bf7a04a815c2e3aeb34521257315899f8b6e","datavalue":{"value":{"entity-type":"item","numeric-id":360355,"id":"Q360355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1305174$8968AEA9-554E-4536-9B7E-F942D2582BFB","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":"Q1305174$AEA4AE4D-F467-42D5-952D-E2EFE2279EB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"731546a283254539a298569c79a55f8744c07659","datavalue":{"value":{"time":"+1999-10-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1305174$026ECF39-7378-4FB1-8E0A-BF4B4CD0DD17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dc8d71311cf822c8ccd2e4c54d3fc7905992751","datavalue":{"value":"https://eudml.org/doc/119939","type":"string"},"datatype":"url"},"type":"statement","id":"Q1305174$4E78870B-0D43-4390-9F38-59FBC0491585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"50e59fb34f9e209a2c511dde33b7968c499b30de","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_6/Abstracts/v6i1n1.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1305174$3A79BD03-0FA1-45CA-A04C-F2D55F8C645A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81002445839a72777d254b7e40ab6e72881b2713","datavalue":{"value":"Summary: Consider, for a permutation \\(\\sigma \\in {\\mathcal S}_k\\), the number \\(F(n,\\sigma)\\) of permutations in \\({\\mathcal S}_n\\) which avoid \\(\\sigma\\) as a subpattern. The conjecture of Stanley and Wilf is that for every \\(\\sigma\\) there is a constant \\(c(\\sigma)< \\infty\\) such that for all \\(n\\), \\(F(n,\\sigma) \\leq c(\\sigma)^n\\). All the recent work on this problem also mentions the ``stronger conjecture'' that for every \\(\\sigma\\), the limit of \\(F(n,\\sigma)^{1/n}\\) exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity. We also discuss \\(n\\)-permutations, containing all \\(\\sigma \\in {\\mathcal S}_k\\) as subpatterns. We prove that this can be achieved with \\(n=k^2\\), we conjecture that asymptotically \\(n \\sim (k/e)^2\\) is the best achievable, and we present Noga Alon's conjecture that \\(n \\sim (k/2)^2\\) is the threshold for random permutations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305174$ECFBDBA4-18E6-48C9-B4AC-5CA03CEBA465","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305174$CF7E7751-8658-44DD-9530-08E4EF2CFF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305174$07C98E7B-8F93-4660-8B2D-2BA210E5933B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ad59534d36ce143dcd34f8ecbb3945be9e33ae3f","datavalue":{"value":"1345966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305174$0A81711D-52CD-4EB6-B137-3AE793420A85","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c21e36790e451ae11a7a8e36f33f82d43b990ec6","datavalue":{"value":"Stanley-Wilf conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305174$127133FA-FC0A-4CF0-902E-067C38C43E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a650f15583af62d1827b2ebb16e134294cf5840","datavalue":{"value":"pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305174$7F7EC42F-F441-4591-8E27-99A6EA951A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"550ae3a4e873095c636a72a92d90f5f407809b16","datavalue":{"value":"Alon conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305174$644FA9CD-DAF4-47BD-B0C6-A3F9635F5605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1305174$3DE84187-5671-46CA-8667-7B564722AEFF","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":"Q1305174$EC689189-EC8A-40B8-B52D-AF04C4BE1F22","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"44a2c87b0265d95179c611af9c0f5e95790d8c38","datavalue":{"value":"bafkreih44imgvefiwaelaqfei6ninuc5dy5ry2hbr4pdxm6gc6trljqdx4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1305174$597A4E71-0078-4FE8-9568-401B7F640A31","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52608567094097828b47e0cc96c31ae318b070ed","datavalue":{"value":{"entity-type":"item","numeric-id":1971017,"id":"Q1971017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e92b8e639efdf5a246ad4af26f1426747d5ed8af","datavalue":{"value":{"amount":"+0.9019700884819032","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":"Q1305174$0AFB2B33-3933-4603-86E4-D7A0C85BD544","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":"d2d9042b2d996651acbfc8da1b0bc9d23fb02611","datavalue":{"value":{"amount":"+0.8776844143867493","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":"Q1305174$FA608177-EEE9-4F79-B10C-4D958192441F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e37e54ebe61fd450019ad0769057f9aee8da8965","datavalue":{"value":{"entity-type":"item","numeric-id":2490025,"id":"Q2490025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b8471fd2932f0a504553affe73b5bbbb1131a10","datavalue":{"value":{"amount":"+0.852142870426178","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":"Q1305174$03305935-9F17-4310-8A80-E74346532E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c84f0a09cb28fb840b9c681242bfc8f0d9f6150","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c198a937d1d12188db7105f003c51332a5f00f70","datavalue":{"value":{"amount":"+0.851108193397522","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":"Q1305174$BF7B6982-B1AC-4F47-BB5F-C79627AC732C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1305174","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1305174"}}}}}