×

Passing through a stack \(k\) times. (English) Zbl 1404.05007

Summary: 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 \(\pi\) to be \(k\)-pass sortable if \(\pi\) is sortable using \(k\) passes through the stack. Permutations that are 1-pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of 2-pass sortable permutations in terms of their basis. We also show all \(k\)-pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer \(k\). Finally, we define the notion of tier of a permutation \(\pi\) to be the minimum number of passes after the first pass required to sort \(\pi\). We then give a bijection between the class of permutations of tier \(t\) and a collection of integer sequences studied by S. Parker [The combinatorics of functional composition and inversion. Waltham, MA: Brandeis University. (PhD Thesis) (1993)]. This gives an exact enumeration of tier \(t\) permutations of a given length and thus an exact enumeration for the class of \((t + 1)\)-pass sortable permutations. Finally, we give a new derivation for the generating function in [loc. cit.] and an explicit formula for the coefficients.

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
06A07 Combinatorics of partially ordered sets

Software:

OEIS; SageMath

References:

[1] Albert, M. H., Atkinson, M. and Linton, S., Permutations generated by stacks and deques, Ann. Comb.14(1) (2010) 3-16. · Zbl 1233.05003
[2] Atkinson, M. D., Murphy, M. M. and Rukuc, N., Sorting with two ordered stacks in series, Theoret. Comput. Sci.289(1) (2002) 205-223. · Zbl 1061.68037
[3] Babson, E. and Steingrímsson, E., Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin.44 (2000), Article B44b. · Zbl 0957.05010
[4] Bóna, M., Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, J. Combin. Theory Ser. A80(2) (1997) 257-272. · Zbl 0887.05004
[5] Bóna, M., A survey of stack-sorting disciplines, Electron. J. Combin.9(2) (2003), Article 1. · Zbl 1028.05003
[6] Claesson, A., Generalized pattern avoidance, European J. Combin.22(7) (2001) 961-971. · Zbl 0994.05004
[7] Developers, T. S. SageMath, the sage mathematics software system (Version 6.1.1), 2014, http://www.sagemath.org.
[8] Elder, M., Permutations generated by a stack of depth 2 and an infinite stack in series, Electron. J. Combin.13 (2006), Research paper 68. · Zbl 1097.05002
[9] Even, S. and Itai, A., Queues, stacks, and graphs, in Theory of Machines and Computations(Proc. Internat. Sympos., Technion, Haifa, 1971) (Academic Press, New York, 1971), pp. 71-86.
[10] Kitaev, S., Patterns in Permutations and Words, (Springer-Verlag, 2011). · Zbl 1257.68007
[11] Knuth, D. E., The art of computer programming, in Sorting and Searching, Vol. 3 (Addison-Wesley Publishing Co., Reading, Massachusetts, 1973). · Zbl 0302.68010
[12] Knuth, D. E., The art of computer programming, in Fundamental Algorithms, Vol. 1 (Addison-Wesley Publishing Co., Reading, Massachusetts, 1969). · Zbl 0191.17903
[13] Kremer, D., Permutations with forbidden subsequences and a generalized Schröder number, Discr. Math.218(1-3) (2000) 121-130. · Zbl 0949.05003
[14] Kremer, D., Postscript: Permutations with forbidden subsequences and a generalized Schröder number, Discr. Math.270(1-3) (2003) 333-334. · Zbl 1025.05001
[15] M. M. Murphy, Restricted permutations, antichains, atomic classes, and stack sorting, PhD thesis, University of St Andrews (2002).
[16] S. Parker, The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993).
[17] Pratt, V. R., Computing permutations with double-ended queues, parallel stacks and parallel queues, In Proc. Fifth Annual ACM Symp. Theory of Computing (ACM Press, New York, NY, USA, 1973), pp. 268-277. · Zbl 0314.94030
[18] Schroeder, M. and Smith, R., A bijection on classes enumerated by the Schröder numbers, Discr. Math. Theoret. Comput. Sci.18(2) (2017) 15. · Zbl 1400.05015
[19] N. J. Sloane, The online encyclopedia of integer sequences, http://oeis.org. · Zbl 1044.11108
[20] Smith, R., Two stacks in series: A decreasing stack followed by an increasing stack, Ann. Comb.18 (2014) 359-363. · Zbl 1297.05011
[21] E. Steingrímsson, Generalized permutation patterns — a short survey, in Permutation Patterns, London Mathematical Society Lecture Note Series (Cambridge University Press, 2010), pp. 137-152. · Zbl 1217.05017
[22] Tarjan, R., Sorting using networks of queues and stacks, J. Assoc. Comput. Mach.19 (1972) 341-346. · Zbl 0243.68004
[23] West, J., Sorting twice through a stack, Theoret. Comput. Sci.117(1-2) (1993) 303-313. · Zbl 0797.68041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.