<%@ 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
jliese@calpoly.edu
2Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA
remmel@math.ucsd.edu
Annals of Combinatorics 14 (1) pp.123-141 Springer, 2010
AMS Subject Classification: 05A05, 05A15
Abstract:
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

References:

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)