{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:22:43Z","timestamp":1759335763659},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2019,2]]},"abstract":"<jats:p>We consider the number of passes a permutation needs to take through a stack if we only pop the appropriate output values and start over with the remaining entries in their original order. We define a permutation [Formula: see text] to be [Formula: see text]-pass sortable if [Formula: see text] is sortable using [Formula: see text] passes through the stack. Permutations that are [Formula: see text]-pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of [Formula: see text]-pass sortable permutations in terms of their basis. We also show all [Formula: see text]-pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer [Formula: see text]. Finally, we define the notion of tier of a permutation [Formula: see text] to be the minimum number of passes after the first pass required to sort [Formula: see text]. We then give a bijection between the class of permutations of tier [Formula: see text] and a collection of integer sequences studied by Parker [The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)]. This gives an exact enumeration of tier [Formula: see text] permutations of a given length and thus an exact enumeration for the class of [Formula: see text]-pass sortable permutations. Finally, we give a new derivation for the generating function in [S. Parker, The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)] and an explicit formula for the coefficients.<\/jats:p>","DOI":"10.1142\/s1793830919500034","type":"journal-article","created":{"date-parts":[[2018,11,8]],"date-time":"2018-11-08T02:44:50Z","timestamp":1541645090000},"page":"1950003","source":"Crossref","is-referenced-by-count":1,"title":["Passing through a stack k times"],"prefix":"10.1142","volume":"11","author":[{"given":"Toufik","family":"Mansour","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Haifa, 3498838 Haifa, Israel"}]},{"given":"Howard","family":"Skogman","sequence":"additional","affiliation":[{"name":"Department of Mathematics, SUNY Brockport, Brockport, New York, USA"}]},{"given":"Rebecca","family":"Smith","sequence":"additional","affiliation":[{"name":"Department of Mathematics, SUNY Brockport, Brockport, New York, USA"}]}],"member":"219","published-online":{"date-parts":[[2019,2,8]]},"reference":[{"key":"S1793830919500034BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-010-0042-9"},{"key":"S1793830919500034BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00270-5"},{"key":"S1793830919500034BIB003","volume":"44","author":"Babson E.","year":"2000","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"S1793830919500034BIB004","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2800"},{"issue":"2","key":"S1793830919500034BIB005","doi-asserted-by":"crossref","DOI":"10.37236\/1693","volume":"9","author":"B\u00f3na M.","year":"2003","journal-title":"Electron. J. Combin."},{"key":"S1793830919500034BIB006","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2001.0515"},{"key":"S1793830919500034BIB008","doi-asserted-by":"crossref","DOI":"10.37236\/1094","volume":"13","author":"Elder M.","year":"2006","journal-title":"Electron. J. Combin."},{"key":"S1793830919500034BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"key":"S1793830919500034BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17333-2"},{"key":"S1793830919500034BIB011","volume-title":"Sorting and Searching","volume":"3","author":"Knuth D. E.","year":"1973"},{"key":"S1793830919500034BIB012","volume-title":"Fundamental Algorithms","volume":"1","author":"Knuth D. E.","year":"1969"},{"key":"S1793830919500034BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00302-7"},{"key":"S1793830919500034BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00124-9"},{"issue":"2","key":"S1793830919500034BIB018","first-page":"15","volume":"18","author":"Schroeder M.","year":"2017","journal-title":"Discr. Math. Theoret. Comput. Sci."},{"key":"S1793830919500034BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-014-0227-8"},{"key":"S1793830919500034BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321704"},{"key":"S1793830919500034BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90321-J"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830919500034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T21:55:24Z","timestamp":1605390924000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830919500034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2]]},"references-count":17,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,2,8]]},"published-print":{"date-parts":[[2019,2]]}},"alternative-id":["10.1142\/S1793830919500034"],"URL":"https:\/\/doi.org\/10.1142\/s1793830919500034","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2]]}}}