<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 3" %>
Restricted Dumont Permutations
Alexander Burstein
Department of Mathematics, Iowa State University, Ames, IA 50011-2064, USA
Annals of Combinatorics 9 (3) p.269-280 September, 2005
AMS Subject Classification: 05A05, 05A15
We analyze the structure and enumerate Dumont permutations of the first and second kinds avoiding certain patterns or sets of patterns of length 3 and 4. Some cardinalities are given by Catalan numbers, powers of 2, little Schörder numbers, and other known or related sequences.
Keywords: permutation patterns, restricted permutations, Dumont permutations


1. M. Bóna, Combinatorics of Permutations, Chapman & Hall/CRC Press, 2004.

2. M. Bóna, Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, J. Combin. Theory Ser. A 80 (1997) 257--272.

3. A. Burstein, S. Elizalde, and T. Mansour, Restricted Dumont permutations and Chebyshev polynomials, preprint.

4. D. Dumont, Interpretations combinatoires des nombres de Genocchi, Duke J. Math. 41 (1974) 305--318.

5. I. Gessel, Symmetric functions and p-recursiveness, J. Combin. Theory Ser. A 53 (1990) 257--285.

6. S. Kitaev and T. Mansour, A survey of certain pattern problems, preprint.

7. D.E. Knuth, The Art of Computer Programming, Vols. 1 and 3, Addison-Wesley, NY, 1968, 1973.

8. T. Mansour, Restricted 132-Dumont permutations, Australas. J. Combin. 29 (2004) 103--117.

9. F. Ruskey, Combinatorial Object Server, http://www.theory.csc.uvic.ca/~cos/inf/ perm/GenocchiInfo.html.

10. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383--406.

11. N.J.A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York, 1995. Online at http://www.research.att.com/~njas/sequences/.

12. Z. Stankova, Forbidden subsequences, Discrete Math. 132 (1994) 291--316.

13. Z. Stankova, Classification of forbidden subsequences of length 4, Europ. J. Combin. 17 (1996) 501--517.

14. J.West, Permutation trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995) 247--262.

15. J. West, Generating trees and forbidden subsequences, Discrete Math. 157 (1996) 363--374.