{"entities":{"Q1971017":{"pageid":1981759,"ns":120,"title":"Item:Q1971017","lastrevid":46910097,"modified":"2025-12-25T20:21:04Z","type":"item","id":"Q1971017","labels":{"en":{"language":"en","value":"On the number of permutations avoiding a given pattern"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1421336"}},"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":"Q1971017$45BDB285-C370-46AD-B2C4-4BCFCD61674D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02e1e11e3cffdc7b94a38f13523a4dad64c6b234","datavalue":{"value":{"text":"On the number of permutations avoiding a given pattern","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1971017$2DD91455-4A1B-4797-A058-A57D1480CED2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c58b20442a6b3a7ae8aad971e5678ba1561b3945","datavalue":{"value":"0948.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$925924FB-BF0F-4F54-8D92-39E0274D3651","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$9AEF9C00-5A7F-4E34-93BF-C29276F695B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4c1f35623768681f408e62bdd351d6201b9df65","datavalue":{"value":{"entity-type":"item","numeric-id":220703,"id":"Q220703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$9A8047FB-1ECF-4506-9E3E-EFA89C37C5F4","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":"Q1971017$EC2F812C-4C80-48C0-B144-A5FC05D92AFC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f75721fa752c9123eb70187b9a711f89662b7df4","datavalue":{"value":{"time":"+2000-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1971017$384056C8-DDF3-47A9-B32F-43994833D4F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"79585330b75bb67944b12c6d72816fdecba1c752","datavalue":{"value":"R. P. Stanley and H. Wilf [see, e.g., \\textit{M. B\u00f3na}, J. Comb. Theory, Ser. A 85, No. 1, 96-104 (1999; Zbl 0919.05002)] conjectured that for the number \\(F(n,\\sigma)\\) of \\(n\\)-permutations avoiding (not containing) a given permutation \\(\\sigma\\) there exists a constant \\(c= c(\\sigma)\\) such that \\(F(n,\\sigma)\\leq c^n\\) for all \\(n\\). Using results about generalized Davenport-Schinzel sequences, the authors prove a slightly weaker statement: \\(F(n,\\sigma)\\leq c^{n\\gamma^*(n)}\\), where \\(\\gamma^*(n)\\) is an extremaly slowly growing function, related to the Ackermann hierarchy. They also prove that the conjecture holds for every permutation which consists of an increasing subsequence followed by a decreasing one, or vice versa.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971017$22DCF640-FB10-498C-8E23-D1D4D42EC215","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7de453d68e14befc7166d5beda28632878de9dca","datavalue":{"value":{"entity-type":"item","numeric-id":751623,"id":"Q751623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$E8DAACD5-FE9C-437F-90B0-A8D2B57A88F8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$F7B79DA5-1717-4A9E-BE12-E81054782200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff9d350acea12ffd75e7ed8da6f45c48ff041eef","datavalue":{"value":"05A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$292D4AB8-D138-4B17-B2AB-63631F106498","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d94563573d710fa59e4ba8090506f46ca8d7736","datavalue":{"value":"1421336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$EF2071F8-C635-4CAF-8EAA-53C6BCCB1B91","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a650f15583af62d1827b2ebb16e134294cf5840","datavalue":{"value":"pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971017$8360C7E9-40A5-44F6-816F-DBC39ACE0D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971017$621A2944-DE91-4F75-81E5-5611A1F3F885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900572492ff0b9c514cba808fa7fe3539b0c1cb0","datavalue":{"value":"Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971017$3B9D8E8C-DFD5-4223-9FF7-00AE0A69A53E","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":"Q1971017$ECB29CA0-ABCE-425E-B71F-98A40CC329AE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ae832001f072d9ac9cecd0b96499afc66c22d34","datavalue":{"value":"https://doi.org/10.1006/jcta.1999.3002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1971017$C56341CF-3953-4D9A-8041-96EA741046A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb4211dbe731fb39b48704af3166be417ef8f5cd","datavalue":{"value":"W2021480278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$EF451FE2-32F6-4B51-BE48-1972B7E411FC","rank":"normal"}],"P223":[{"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":"Q1971017$5E53249B-CD91-4564-BECE-4D2F5EDF5199","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":"Q1971017$804B231F-183A-4D05-B899-C21A72B439D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4462fd8670ad9c283a2e41b02aef503375ab1d4","datavalue":{"value":{"entity-type":"item","numeric-id":1279660,"id":"Q1279660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$FE13A8B9-CE5E-4E29-8F40-6ABEA4A88493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201f81637d81b2a961cfae9f81bf87bee08d6a66","datavalue":{"value":{"entity-type":"item","numeric-id":3137399,"id":"Q3137399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$275BC2BF-A907-45A2-8ED7-49DB7DEA578C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58f225bc4e91b43f52f369f98d6074e8fc6d4bf7","datavalue":{"value":{"entity-type":"item","numeric-id":1343170,"id":"Q1343170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$1CAD4952-D8CE-4502-BF8B-5952D1D3E087","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":"Q1971017$4645377C-0CC3-48E7-B599-BE5DEBA209E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf78f24dc9967d0a6148cbfe129076e5e338f2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4325546,"id":"Q4325546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971017$45AD4A2B-415C-4FB7-947D-84617A59CB70","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":"Q1971017$BF36A379-580F-41C8-8532-2FB8152E4D25","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b793f4683cbbb1c9dba88601a6a438261709813c","datavalue":{"value":"10.1006/JCTA.1999.3002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971017$AB0F7E94-71EC-4725-A5BE-BC7294FBAF2A","rank":"normal"}],"P1643":[{"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":"44511d670bc6ca5898b45ca2d412e133b299041c","datavalue":{"value":{"amount":"+0.9019699096679688","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":"Q1971017$24809188-7E96-40C4-9504-7BAAE6853BE5","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":"29e9911d048d9fed14b199e29bf113a6511e08d3","datavalue":{"value":{"amount":"+0.8654193878173828","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":"Q1971017$7BEAECCA-3904-4D36-B971-BA643341B21E","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":"9482dced299d97d22146e29bbf1ad1308b1d7f52","datavalue":{"value":{"amount":"+0.8600648045539856","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":"Q1971017$499B986B-F60A-41A0-B0FA-A7E63512246D","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":"12ef3ed0b6455ae64ce5ababad8843f73c9bf1fe","datavalue":{"value":{"amount":"+0.8427435755729675","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":"Q1971017$9931C1F1-D09D-44D1-BE37-38B63F5A9C68","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":"f5c7b22ed4071fdc48bbfc8cf4189055980fea4b","datavalue":{"value":{"amount":"+0.8387277722358704","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":"Q1971017$A0B2B2D8-B4FC-4AC3-8C35-4C8F19A3C7C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1971017","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1971017"}}}}}