{"entities":{"Q1336669":{"pageid":1347408,"ns":120,"title":"Item:Q1336669","lastrevid":47277034,"modified":"2026-01-01T05:19:25Z","type":"item","id":"Q1336669","labels":{"en":{"language":"en","value":"Forbidden subsequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 681673"}},"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":"Q1336669$D8F1F6D7-E261-4429-B2F7-0172E00CF7DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ebf7e4f1a0b33aed1d60b75f36387d9f221e38a7","datavalue":{"value":{"text":"Forbidden subsequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1336669$28F7DBD0-C094-424B-8548-875E5EF9E4A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a24f1a53988c900507e6571bded372e0544ff959","datavalue":{"value":"0810.05011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$5E4F9DB0-0A81-481C-808D-43167901155B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e356b21996ac7318d392240d03c8b392a1994e97","datavalue":{"value":"10.1016/0012-365X(94)90242-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$14987C1F-9494-40BB-8B1E-9F786C148D9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9728b3115d308c63aebb4d7f50174d6b08e6486","datavalue":{"value":{"entity-type":"item","numeric-id":1336668,"id":"Q1336668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$30844676-F9BA-46B7-A5D9-D446E6EF5BCD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$511907D9-97E2-4CCF-AD68-060DE111A9F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82bd72124ae9a1c309abc4c30d0c3523c1c49e97","datavalue":{"value":{"time":"+1994-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1336669$68D6FC93-1D7F-40F6-A47C-60AFDD435D53","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11d15d320b190a720d3dd73ef66b7a0278efdf81","datavalue":{"value":"A permutation \\(\\tau\\) of length \\(k\\) is denoted by \\((a_ 1,a_ 2,\\dots, a_ k)\\) so that \\(\\tau(i)= a_ i\\), \\(i=1,2,3,\\dots, k\\). Consider two permutations \\(\\tau\\) and \\(\\pi\\) of lengths \\(k\\) and \\(n\\) respectively. \\(\\pi\\) is said to be \\(\\tau\\)-avoiding if no subsequence \\(i_{\\tau(1)},i_{\\tau(2)},\\dots, i_{\\tau(k)}\\) of \\([n]= \\{1,2,\\dots,n\\}\\) exists such that \\(\\pi(i_ 1)< \\pi(i_ 2)<\\cdots< \\pi(i_ k)\\). In case there is such a subsequence, we say that the subsequence \\(\\pi(i_{\\tau(1)}),\\dots,\\pi(i_{\\tau(k)})\\) is of type \\(\\tau\\). Let \\(S_ n(\\tau)\\) denote the set of \\(\\tau\\)-avoiding permutations in \\(S_ n\\), the symmetric group on \\([n]\\). The general question addressed here refers to the number of permutations of a certain length avoiding a given permutation of length 4. In this paper it is shown that \\(| S_ n(4132)|= | S_ n(3142)|\\) by proving the stronger theorem for the corresponding permutation trees: \\(T(4132)\\cong T(3142)\\). A new proof of the so-called Schr\u00f6der result is given, and some conjectures concerning the sort of permutations \\(\\tau\\) and \\(\\sigma\\) for which \\(| S_ n(\\tau)|= | S_ n(\\sigma)|\\) for all \\(n\\in N\\) are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336669$7105A63E-6E14-4798-94C2-9C23311F7F0C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d36e3867d5946e3717838aa146c58da76ecefaf","datavalue":{"value":"05A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$114B2C33-6B4C-4B67-A7BB-7EF03D021414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$4BEBB8ED-58E2-4E16-91FC-D1FFB899FBFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$F61D0E96-398B-4165-A06F-A1374743B72E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"caeac05afcb930c582cb79ac45b69706acc5601a","datavalue":{"value":"681673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$5F5FB603-F2C0-4E23-870E-B7A6EFCD6F27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336669$5F3CBF73-0174-409A-BC37-CE29DAC27570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e422c878f3869d10d601341fdceec81e20986e5f","datavalue":{"value":"subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336669$F49BF00C-64E2-45A8-BC92-4DFBD6DA9464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38d830dae6f5ce906f6d20604a81e37d7574c069","datavalue":{"value":"symmetric group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336669$4C8E1623-4543-4DD4-8F58-04F243C21AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e33540a03b4186a2f48fc29492af6ad4872225e","datavalue":{"value":"Schr\u00f6der result","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336669$9EB925D1-3492-4981-AD8E-EF31905A7D15","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5966bacba611d16b7c796cf01c056e7b12d67d6","datavalue":{"value":{"entity-type":"item","numeric-id":607023,"id":"Q607023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$AFB16C47-0CCC-48CE-8C52-3877DF36ADE2","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":"Q1336669$3DC5270E-ABF7-4D97-ADEC-C0DDF5D7B1A7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5b2ca2d71ec1c060bb19b8cdb086a71379e47815","datavalue":{"value":"Q60638467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$F5427DA6-6077-4482-BDDB-60DB3FEA5F37","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24598a45cfbd4c9e1d327e90e9fd53c445e4fcb9","datavalue":{"value":{"entity-type":"item","numeric-id":2533026,"id":"Q2533026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$0DFD697D-5880-40D7-AC9D-14E7EE73A356","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":"Q1336669$38A4AB59-C1E1-4734-A5CF-CA6989CBDBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffe11abc22e68ae906332024cf889b115d7224f","datavalue":{"value":{"entity-type":"item","numeric-id":2540557,"id":"Q2540557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$45F4F9AC-366C-41E8-B96F-DB8BCA8359C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$A28CE6F9-5945-4136-AE18-EE652AC07264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$1C19A7C3-1B64-47BB-97A7-FC542DD4C8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ee167693eeec71c841affda1c51ad1e59bc6d7","datavalue":{"value":{"entity-type":"item","numeric-id":3975127,"id":"Q3975127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$A9B42740-6A76-40B1-9C3C-5D6AB660269F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e73c6f16c7317f2c5db4af33a45ca57e3869ab2e","datavalue":{"value":{"entity-type":"item","numeric-id":3495358,"id":"Q3495358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$021FE4A7-BECA-4AAB-A5B4-724BC040051B","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":"Q1336669$07F2AC9E-78BA-4583-B847-02A2BA534A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"975acad29d2640f68d4c8acf61d0628a829a30ee","datavalue":{"value":{"entity-type":"item","numeric-id":1224099,"id":"Q1224099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336669$000E7F6F-CA3D-4F3C-90B0-D77E55426C94","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9ac202edc538f135e638c3c43b29601f69e1127e","datavalue":{"value":"https://doi.org/10.1016/0012-365x(94)90242-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1336669$A0AFA575-4949-4A25-804D-A39754F15C7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5dbed294baecc3527e267eb56502cbc8fa92d18c","datavalue":{"value":"W2912910446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336669$DE8F14B6-7D23-4818-849E-297EE73CF2E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a05e3150247bc7c9f47903322b70500cffd32866","datavalue":{"value":{"entity-type":"item","numeric-id":1922878,"id":"Q1922878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72afe16717bb0f33bf746ef6fd9a6826d0992ff0","datavalue":{"value":{"amount":"+0.8805153965950012","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":"Q1336669$801185D9-32CC-462B-9C7C-7826E27BAC56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15695a6f9284cad5bec74210a75eb5992a502819","datavalue":{"value":{"entity-type":"item","numeric-id":5187290,"id":"Q5187290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e634dd18caadfcbaec8f78c6bd558e5c876589a","datavalue":{"value":{"amount":"+0.8778400421142578","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":"Q1336669$3FCB8541-1A20-4494-9B37-3CC2199F7011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13b14fb37e8b0b45af950ea5617f3eb9998b6892","datavalue":{"value":{"entity-type":"item","numeric-id":4954008,"id":"Q4954008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93b40bd4ed9bb054006d46b6044cf4595a1911dc","datavalue":{"value":{"amount":"+0.8711919188499451","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":"Q1336669$FE6514F2-8AEA-4A29-A2FE-5C9A23C2F0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10e2edc4448a3278f6f84765e89f09099cae9362","datavalue":{"value":{"entity-type":"item","numeric-id":1903733,"id":"Q1903733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91edd7e9530b873e8f5b5b26af7b6ed146ed1660","datavalue":{"value":{"amount":"+0.8337618112564087","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":"Q1336669$5C4688E0-E78F-4BC1-A032-0AB9C32E0BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa0be6336aa07c8e3aa5334ed75ec1c70b6d054","datavalue":{"value":{"entity-type":"item","numeric-id":5916426,"id":"Q5916426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68eca63733795182bf4970375904c39b10a7b418","datavalue":{"value":{"amount":"+0.8334295153617859","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":"Q1336669$639F31EC-01B6-493E-95E9-9EFD6900BC48","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1336669","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1336669"}}}}}