{"entities":{"Q2194083":{"pageid":2204826,"ns":120,"title":"Item:Q2194083","lastrevid":57775467,"modified":"2026-04-02T11:48:43Z","type":"item","id":"Q2194083","labels":{"en":{"language":"en","value":"Sorting with pattern-avoiding stacks: the \\(132\\)-machine"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7239395"}},"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":"Q2194083$A90FF7D9-1ECB-45D3-B13D-1CF26971CCAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"878a425ca15b6e26bfb95abf212b69e301dd714c","datavalue":{"value":{"text":"Sorting with pattern-avoiding stacks: the \\(132\\)-machine","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2194083$0E695B61-9E2F-4E1A-83FA-EA2EF0654B86","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca78b559104f760281bfb79ca7aa4f6617bc0dad","datavalue":{"value":"1446.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$8B8ACBAB-E4A6-4E97-AF5B-0437E87CFF38","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"db0e544fc11934f669b88d9fcd20a3c428c92200","datavalue":{"value":"10.37236/9642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$B8E0C75D-F4F0-44B4-89F2-950F532EC120","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f81ffd483374754372447effb6b91dac3128074","datavalue":{"value":{"entity-type":"item","numeric-id":2032177,"id":"Q2032177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$EC497FEE-753A-43A8-BE82-894F390465B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2382c533b3737aef603ccad663a1f72ceff60c73","datavalue":{"value":{"entity-type":"item","numeric-id":215139,"id":"Q215139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$31C41A05-BAAA-4FCC-94C4-EDC0E6AC2D04","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":"Q2194083$8E04E358-C4EB-44B3-944F-86D40EEFBFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8162a0a79feed12486e672d5e000bfb3b1b08d3","datavalue":{"value":{"entity-type":"item","numeric-id":222131,"id":"Q222131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$2C0E8982-4F91-4A0C-878F-651ABF29241C","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":"Q2194083$DBA2F4C1-199E-42CF-BCE7-2FD9C6023D1D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"40d6298d979cc5fe8f26a1cea0e2ec254982529e","datavalue":{"value":{"time":"+2020-08-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2194083$9AB50A6F-8419-410F-8EE0-D1CDAAEB1328","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36a289f9f6194ab36bb8e5e2c9153902d45807d6","datavalue":{"value":"https://arxiv.org/abs/2006.05692","type":"string"},"datatype":"url"},"type":"statement","id":"Q2194083$B57CCA4B-9813-4BB0-92DD-E5FAD69BE8AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ae0e749b4baf9e48b448ebaee09a7f34b5706a3","datavalue":{"value":"Summary: This paper continues the analysis of the pattern-avoiding sorting machines recently introduced by \\textit{G. Cerbai} et al. [J. Comb. Theory, Ser. A 173, Article ID 105230, 19 p. (2020; Zbl 1435.05004)]. These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is \\(132\\)-avoiding, solving one of the open problems proposed by the above mentioned authors. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2194083$78BD6989-2A58-4FFA-B57C-712B1543D5AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$57120057-CF30-4CCB-8A3D-3EB20B98C1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"880665e99fe5de07999ef2f74a810b36dd3dabed","datavalue":{"value":"05A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$C632564A-B4FF-4C22-9690-62E052A66154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$15F4124C-A12D-47A2-B1BA-09C46DD61C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"16a41880afbd8630e6acc78be050f90ea5608911","datavalue":{"value":"05A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$B67B0766-9DDE-4FA5-939A-39A380FF2EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fe20c11270a022ced6b6a582d87c0ca73a689567","datavalue":{"value":"05A19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$3C6E660F-967B-4371-A485-BC9BD0B082A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$058F6025-ED4C-4411-9DFC-3572E99F19E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9bb9d8e8e21f7120c5968207f48285c29ee9d301","datavalue":{"value":"7239395","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$55A9EBC1-D91D-494A-B630-6B96417FB42E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74d868cacd89e78f43921be39affd7e0b951bc95","datavalue":{"value":"pattern-avoiding sorting machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q2194083$9BBFAC18-79A1-418C-9BAB-D8056A72C241","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"650e761a5f418c574655712b35b1fe882f756011","datavalue":{"value":{"entity-type":"item","numeric-id":19297,"id":"Q19297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$04096576-547F-4F5B-ADDE-CF495BC3B4CC","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":"Q2194083$17EB87AE-B518-4A25-9E1D-BB36D4A76A00","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d852ec40a4554618e864129830e35bd9dfa5f32d","datavalue":{"value":"W3083001871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2194083$2BF400EB-191D-4DFB-886E-B4DF70B7A4D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fd72b62c8d9cf7fc18a11558352322e258a53f4","datavalue":{"value":{"entity-type":"item","numeric-id":4700083,"id":"Q4700083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$6E8A724F-78A8-4B30-84A5-E19DD2C03223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10576f833cedc2830eb813cb9cc434ab7c488c08","datavalue":{"value":{"entity-type":"item","numeric-id":5962493,"id":"Q5962493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$B5939E67-FB47-455A-95E2-22A35E2152CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad24d3e4e955aaf6d16737a7884623678248390","datavalue":{"value":{"entity-type":"item","numeric-id":540135,"id":"Q540135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$7E9F3DA0-85F6-461F-832B-283E6EE4C4D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efffe6c3918dd737042bf73cadb96594cfc3ff1c","datavalue":{"value":{"entity-type":"item","numeric-id":2306002,"id":"Q2306002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$E08C1600-A849-4B44-8C37-EAB6E5C3B42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00a4472638997290e9671b67d50c888fa2d2557e","datavalue":{"value":{"entity-type":"item","numeric-id":1661480,"id":"Q1661480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$4C23E4B8-A973-40FD-9757-2600A665B832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8df2c4e809e862bb2208623f4f9f8b17a39554a2","datavalue":{"value":{"entity-type":"item","numeric-id":1704103,"id":"Q1704103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$D001994E-9796-4209-8EA2-72034261494A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ab21df4e953ebb8c841888ee56d2fe32bb31732","datavalue":{"value":{"entity-type":"item","numeric-id":1300974,"id":"Q1300974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$E93175B5-BE1A-4655-953D-E774456D69C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9fce0d48b5758fbb9b79953def7348fcc6c444","datavalue":{"value":{"entity-type":"item","numeric-id":1145147,"id":"Q1145147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$75AA26E5-15BA-4874-9A7B-383CB8E02463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94f4bee54a164951f9f2258c14c7ae9aaaa2f9cc","datavalue":{"value":{"entity-type":"item","numeric-id":1010749,"id":"Q1010749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$CB663525-62BC-4647-9FFC-A297123F8771","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":"Q2194083$8ACAD515-FEB6-4696-8266-8DECD8B75766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbfe8b3db045c3af5bd936077fb2e74b1125b562","datavalue":{"value":{"entity-type":"item","numeric-id":4443440,"id":"Q4443440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$3D87F9E1-8556-4AC4-9B02-209D130D9822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3688421d8b6ce74e2cd080265886a5a7a274ffc","datavalue":{"value":{"entity-type":"item","numeric-id":404476,"id":"Q404476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$2EC362B1-F23C-493A-867D-0DC267A5D256","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"588924571bfb72bc5d29e3770590077281afefd0","datavalue":{"value":{"entity-type":"item","numeric-id":2306002,"id":"Q2306002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c810fa06f24406075d1c4ddf5e7af5ab00a642d","datavalue":{"value":{"amount":"+0.8812749981880188","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":"Q2194083$285EA7AD-062D-4E4C-B9B8-A39C9DCE1113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"047fabb3c233aa30135968a24f8305668d663303","datavalue":{"value":{"entity-type":"item","numeric-id":2032179,"id":"Q2032179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c0c0c230d219564849e556f25d1c0eb11aa98e7","datavalue":{"value":{"amount":"+0.8748552203178406","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":"Q2194083$CA8B2DA5-AEEC-4581-A649-D49D44A7553C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced1499ca778f23b6440efcd2bfef2bdbf69a6eb","datavalue":{"value":{"entity-type":"item","numeric-id":5000313,"id":"Q5000313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cb0c24dd40c31c5df82dd088ef8b027b3020562","datavalue":{"value":{"amount":"+0.8576163649559021","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":"Q2194083$D72473F4-2CA7-4CDA-B3BA-F06B5C15080E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a99044df64817afcb0be4410c686bcc14b1b5c53","datavalue":{"value":{"entity-type":"item","numeric-id":5197592,"id":"Q5197592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"243ee0fb505079433f455e55ae5ea84da190385c","datavalue":{"value":{"amount":"+0.8049869537353516","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":"Q2194083$15EEE7BC-FED3-4575-8EB9-47B7B0985228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f49b6fd853d9d0d032b5bef31c64b2ef45f0376","datavalue":{"value":{"entity-type":"item","numeric-id":404476,"id":"Q404476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b74d3f49880225e5dd866b91b3b5e831ea540b5e","datavalue":{"value":{"amount":"+0.8046303391456604","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":"Q2194083$950892DB-2B4A-4999-B203-5800AF347FD1","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2194083$94C802BA-AD2C-4D03-8822-32FAA962AF68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2194083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2194083"}}}}}