<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Permutations Generated by Stacks and Deques
Michael Albert1, Mike Atkinson1 and Steve Linton2
1Department of Computer Science, University of Otago, PO Box 56, Dunedin 9054, New Zealand
{mike, malbert}@cs.otago.ac.nz
2School of Computer Science, University of St Andrews, North Haugh, St. Andrews, Fife, KY169SX, Scotland
Annals of Combinatorics 14 (1) pp.3-16 Springer, 2010
AMS Subject Classification: 05A05, 05A16, 68Q45
Lower and upper bounds are given for the the number of permutations of length n generated by two stacks in series, two stacks in parallel, and a general deque.
Keywords: deque, parallel stacks, serial stacks, permutation, enumeration, growth rate


1. Albert, M.H., Atkinson, M.D., Ruskuc, N.: Regular closed sets of permutations. Theoret. Comput. Sci. 306(1-3), 85--–100 (2003)

2. Arratia, R.: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin. 6, #N1 (1999)

3. Atkinson, M.D., Tulley, D., Livesey, M.J.: Permutations generated by token passing in graphs. Theoret. Comput. Sci. 178(1-2), 103--–118 (1997)

4. Atkinson, M.D., Murphy, M.M., Ruskuc, N.: Sorting with two ordered stacks in series. Theoret. Comput. Sci. 289(1), 205--–223 (2002)

5. Even, S., Itai, A.: Queues, stacks and graphs. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 71–--86. Academic Press, New York (1971)

6. Knuth, D.E.: Fundamental Algorithms, The Art of Computer Programming Vol. 1 (First Edition). Addison-Wesley, Massachusetts (1968)

7. Knuth, D.E.: Sorting and Searching, The Art of Computer Programming Vol. 3 (First Edition). Addison-Wesley, Massachusetts (1973)

8. Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A 107(1), 153--–160 (2004)

9. Pratt, V.R.: Computing permutations with double-ended queues, parallel stacks and parallel queues. In: Annual ACM Symposium on Theory of Computing, Proceedings of the fifth annual ACM symposium on Theory of computing, pp. 268–--277. ACM, New York (1973)

10. Simion, R., Schmidt, F.W.: Restricted permutations. European J. Combin. 6, 383–--406 (1985)

11. Rosenstiehl, P., Tarjan, R.E.: Gauss codes, planar Hamiltonian graphs, and Stack-Sortable permutations. J. Algorithms 5(3), 375--–390 (1984)

12. R.E. Tarjan: Sorting using networks of queues and stacks. J. ACM 19(2), 341--–346 (1972)