<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The X-Class and Almost-Increasing Permutations
Sergi Elizalde
Department of Mathematics, Dartmouth College, Hanover, NH 03755, USA
Annals of Combinatorics 15 (1) pp.51-68 January, 2011
AMS Subject Classification: 05A05, 05A15
In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in Knuth [4] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almostincreasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions.
Keywords: cycle diagram, pattern-avoiding permutation, picture class, X-class


1. Atkinson, M.D.: Some equinumerous pattern-avoiding classes of permutations. Discrete Math. Theor. Comput. Sci. 7(1), 71--–73 (2005)

2. Flajolet, P.: Combinatorial aspects of continued fractions. Discrete Math. 306(10-11), 992--–1021 (2006)

3. Foata, D., Schätzenberger, M.-P.: Théorie géométrique des polynˆomes Euériens. Springer, Berlin (1970)

4. Knuth, D.: The Art of Computer Programming, Vol. III. Addison-Wesley, Reading, MA (1973)

5. Waton, S.: On permutation classes defined by token passing networks, gridding matrices and pictures: three flavours of involvement. Ph.D. thesis, University of St Andrews, St Andrews (2007)