<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Generating Functions for Permutations Avoiding a Consecutive Pattern
Jeffrey Liese1 and Jeffrey Remmel2
1Department of Mathematics, California Polytechnic State University, San Luis Obispo, CA 93407, USA
2Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA
Annals of Combinatorics 14 (1) pp.123-141 Springer, 2010
AMS Subject Classification: 05A05, 05A15
Given a permutation τ of length j, we say that a permutation σ has a τ-match starting at position i, if the elements in positions i, i+1, …, i+ j-1 in s have the same relative order as the elements of τ. We have been able to take advantage of the results of Mendes and Remmel [1] to obtain a generating function for the number of permutations with no τ-matches for several new classes of permutations. These new classes include a large class of permutations which are shuffies of an increasing sequence 1 2…n with an arbitrary permutation s of the integers {n + 1, …, n +m}. Finally we give a formula for the generating function for the number of permutations which have no 1 3 2 4-matches.
Keywords: permutation patterns, consecutive patterns, generating functions


1. Mendes, A., Remmel, J.: Permutations and words counted by consecutive patterns. Adv. Appl. Math. 37(4), 443--–480 (2006)

2. Elizalde, S., Noy, M.: Consecutive patterns in permutations. Adv. Appl. Math. 30(1-2), 110--–125 (2003)

3. Kitaev, S.: Generalized patterns in words and permutations. Ph.D. Thesis, Chalmers University of Technology and Göteborg University, Göteborg (2003)

4. Kitaev, S.: Partially ordered generalized patterns. Discrete Math. 298, 212–--229 (2005)

5. Goulden, I.P., Jackson, D.M.: Combinatorial Enumeration. John Wiley & Sons Inc, New York (1983)