{"entities":{"Q640846":{"pageid":642694,"ns":120,"title":"Item:Q640846","lastrevid":57083970,"modified":"2026-03-26T13:06:28Z","type":"item","id":"Q640846","labels":{"en":{"language":"en","value":"The M\u00f6bius function of separable and decomposable permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960839"}},"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":"Q640846$4B38F958-0555-4DAB-B2D7-4A83A655DF3D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"58fe96b9eab1e401ab3532bdfe5e4245234c0dc6","datavalue":{"value":{"text":"The M\u00f6bius function of separable and decomposable permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640846$B16BE50B-C11A-4765-A3D9-F9F840F45A2F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9193946198b8fa193d2fb76e2225f20be1acf739","datavalue":{"value":"1228.05008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$EA27B25B-3D27-4B90-BF12-604B7B1B32E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9372ee6e007bb83636a15cc03262adeb34501fb8","datavalue":{"value":{"entity-type":"item","numeric-id":640472,"id":"Q640472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$067A3123-17CB-48E4-9117-93DB32C61B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c697b46636e11de2b7931fa0f06412c01aef6dc","datavalue":{"value":{"entity-type":"item","numeric-id":354439,"id":"Q354439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$9C73D59B-42AF-4684-8854-6C85A68707C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f03af25ea55d3e83db9d0b3e5cf6385684bbabdc","datavalue":{"value":{"entity-type":"item","numeric-id":215091,"id":"Q215091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$3C0FA510-BB9E-4A4F-AC67-44FEF4511783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba44d81108b51c5e74dc72de0b9e3e5a20a1b0f0","datavalue":{"value":{"entity-type":"item","numeric-id":354440,"id":"Q354440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$0352EF31-FE91-445B-9C12-28DAC51DCAAF","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":"Q640846$A7880216-85A4-4C0D-A76C-D2B86A031240","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5412e51208588a3303ff1411a4274ccfb0b7d7d6","datavalue":{"value":{"time":"+2011-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640846$3238ECA1-7E45-470D-9DCE-15C99FE6CDFA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"45e4fc0c587c25afef65027c20923ec874d34c21","datavalue":{"value":"https://arxiv.org/abs/1102.1611","type":"string"},"datatype":"url"},"type":"statement","id":"Q640846$3E17B67B-54B9-4439-AD1D-F1DD641F8C95","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a91e9faa32c14e0b30c61ef19a104f3d71c34947","datavalue":{"value":"Let \\(S_n\\) denote the permutations of \\(\\{1,\\dots,n\\}\\); the union of all \\(S_n\\) (\\(n \\in \\mathbb{N}\\)) forms a poset with respect to pattern containment (also called permutation involvement). The paper is concerned with the M\u00f6bius function of this poset: first mentioned by \\textit{H. Wilf} [``The patterns of permutations,'' Discrete Math. 257, No.\\,2--3, 575--583 (2002; Zbl 1028.05002)], and studied by \\textit{B. Sagan} and \\textit{V. Vatter} for the case of layered permutations [``The M\u00f6bius function of a composition poset,'' J. Algebr. Comb. 24, No.\\,2, 117--136 (2006; Zbl 1099.68081)]. Here, the authors consider the case of decomposable permutations (those expressible as direct sums of smaller permutations). They provide a recursive formula for the M\u00f6bius function of an interval \\([\\sigma,\\pi]\\) when \\(\\pi\\) is decomposable. In the special case when \\(\\pi\\) is separable (obtainable from \\(1\\) by successive sums and skew sums), the authors obtain a polynomial-time algorithm to compute the M\u00f6bius function. This leads to an alternative combinatorial interpretation for the M\u00f6bius function of separable permutations in terms of ''normal embeddings''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$B6825243-1C4E-4108-B206-8868F4C63721","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"efee8ef63d883794313ed3dd20fed2e78849a325","datavalue":{"value":{"entity-type":"item","numeric-id":405097,"id":"Q405097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$6AF2570D-A26E-4DFF-8EDF-76C997D41E0A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$7874CAA4-DA79-432C-8BAD-7E1DD07AF53F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fef85b4976949ebfc814b255ad5593167b00286f","datavalue":{"value":"5960839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$5871694F-5DEF-4521-87F3-329490FC86D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"379272f926eea761941679f116e9dbee4c3f3d1e","datavalue":{"value":"M\u00f6bius function","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$D14CAB8B-A260-4D0B-8132-1C67E3542DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22f497f9da6d36ef1491eb21ef89ccee11b7643c","datavalue":{"value":"pattern poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$8CFCDB36-DB3A-4F86-B521-A4F28DEDF685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac0ec0763db849a8eec9dfae6413048e7c949cae","datavalue":{"value":"decomposable permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$A6DD63CC-91B2-4CBC-A137-A9CF2E9DC45D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bc7be76c309e1927868270256a0feeb4b7b9ac6","datavalue":{"value":"separable permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$E2C86A86-6558-4C3D-844F-69B4432EE3E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eab912622162cba806a3f8bb54a33f224081c51f","datavalue":{"value":"pattern containment","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$A2E41F49-9C10-4366-A8D9-0270856BD6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"340c32fdf01e6ba7f42b510b81b5416905afdbbc","datavalue":{"value":"permutation involvement","type":"string"},"datatype":"string"},"type":"statement","id":"Q640846$257EF2D9-698F-400A-A27A-708C707F6B77","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"118c5a24e00a009b96a0fa54e3bc81ede562620b","datavalue":{"value":"Q60638486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$F98FCF3C-0817-4CE7-A845-D23E907951AA","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":"Q640846$9C61B4A6-8494-4198-8B95-A25AF831834E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6c87148e2a6ae433a1864a0861a7ae067668139c","datavalue":{"value":"W2053601698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$7741C7C2-2CEA-4927-863E-6D80E0E8AE15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2f7d30e460cbfd6e9c3311db7d2128487aac767","datavalue":{"value":{"entity-type":"item","numeric-id":3023983,"id":"Q3023983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$5D9C5E29-947A-4972-986B-9639D864E846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ba439f1813ee045229b0e6e83c630cba997c61","datavalue":{"value":{"entity-type":"item","numeric-id":293263,"id":"Q293263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$5A5640FE-9775-4F3C-9B47-B31E4F099725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"425480b5d1b5f832287871fb0e3e914f8bf3a232","datavalue":{"value":{"entity-type":"item","numeric-id":3487448,"id":"Q3487448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$32EF2E82-1BF2-448D-A13C-6D3323891572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e960a50f625942e3c292fc701d149a4ef835d8be","datavalue":{"value":{"entity-type":"item","numeric-id":688683,"id":"Q688683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$7D80E309-2345-4C92-9399-9B503FC58D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"444f703e684bdcfe492fad91f5f8c2017580f8b7","datavalue":{"value":{"entity-type":"item","numeric-id":2504997,"id":"Q2504997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$271FB090-03D4-4D74-932B-D69FB219C3B2","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":"Q640846$1425FBBF-AE4F-4F15-8D82-3092F9CC5A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f3b8b1fade8497bd8f83fb0657dd00709878939","datavalue":{"value":{"entity-type":"item","numeric-id":989228,"id":"Q989228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$5971F264-2E45-4FB6-94CD-E416A767C4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e16ea4c1768b7af503e5c7532b6c5ea83afab25d","datavalue":{"value":{"entity-type":"item","numeric-id":1850035,"id":"Q1850035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$9037A01E-0C13-4FD1-AF20-1966605ECCB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88812a2c7b6d826ff4be7890cc5f546980739a60","datavalue":{"value":{"entity-type":"item","numeric-id":1763485,"id":"Q1763485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640846$09ABFB42-662D-4261-8F6B-1BABAA0905CE","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"3531d3635f74173901a277f4c4e0742699bce0a7","datavalue":{"value":"journals/jct/BursteinJJS11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$83079FF9-264D-4C8F-964F-8B34EB08E9ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a11bc6c9b259f15640feca57515552fbd4bf72f7","datavalue":{"value":"10.1016/J.JCTA.2011.06.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640846$A1AE4D2B-21CD-4659-8E72-AF47506E35AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"586d3b6d319a4fa75525b23d9c25386ac4edb7f9","datavalue":{"value":{"entity-type":"item","numeric-id":4591341,"id":"Q4591341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8bb0f93a0e5cbcecab66121eb9a1ff699117396","datavalue":{"value":{"amount":"+0.951201319694519","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":"Q640846$81F2E5D6-BC45-4E8C-848E-EC5654A8770E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d4ef67497e994c7b216e78d5e6e74aaf35ff8b1","datavalue":{"value":{"entity-type":"item","numeric-id":989228,"id":"Q989228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b5092881f1451e78a1ef3ba05d6b5d2ef1e8bd9","datavalue":{"value":{"amount":"+0.8521823883056641","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":"Q640846$1E2ADCD0-4067-4A6D-ADCE-5F6974A7B78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"235bf1267051c904805561c2d683fa8711dfddf8","datavalue":{"value":{"entity-type":"item","numeric-id":2399888,"id":"Q2399888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec0d6d82518cb3ebe25dc08fb354fec72f166b62","datavalue":{"value":{"amount":"+0.8485755324363708","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":"Q640846$32B632C5-6882-4C0C-8790-529FD5675199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30fe45658f6971890f41a3927906960e57444bac","datavalue":{"value":{"entity-type":"item","numeric-id":1709541,"id":"Q1709541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f5d19402718e9dc05533fefecc83d9a3c74521c","datavalue":{"value":{"amount":"+0.843275249004364","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":"Q640846$7AE8B54E-8E86-42E3-A6A3-18C4B2AE876D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7fe6a00a55380a2ee20a2522397c7e6cfb0616a","datavalue":{"value":{"entity-type":"item","numeric-id":5111034,"id":"Q5111034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29b2957e8e669a0e8098d53280ad0349f3fc96f6","datavalue":{"value":{"amount":"+0.8306759595870972","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":"Q640846$A47E4BE1-E85F-4B99-B88C-EA8798B4C900","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:640846","badges":[]}}}}}