INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A01

RESTRICTED PERMUTATIONS, FIBONACCI NUMBERS, AND K-GENERALIZED FIBONACCI NUMBERS

Eric S. Egge

Department of Mathematics, Gettysburg College, Gettysburg, PA 17325 USA

                           eggee@member.ams.org

Toufik Mansour^{1}

Department of Mathematics, Haifa University 31905 Haifa, Israel

                          toufik@math.haifa.ac.il

Received: 5/2/04, Accepted: 1/3/05, Published: 2/1/05

Abstract

In 1985 Simion and Schmidt showed that the number of permutations in S_{n} which avoid 132, 213, and 123 is equal to the Fibonacci number F_{n+1}. We use generating function and bijective techniques to give other sets of pattern-avoiding permutations which can be enumerated in terms of Fibonacci or k-generalized Fibonacci numbers.

Keywords: Restricted permutation; pattern-avoiding permutation; forbidden subsequence; Fibonacci number

1. Introduction and Notation

Let S_{n} denote the set of permutations of {1, …, n}, written in one-line notation, and suppose π ∈ S_{n} and σ ∈ S_{k}. We say π avoids σ whenever π contains no subsequence with all of the same pairwise comparisons as σ. For example, the permutation 214538769 avoids 312 and 2413, but it has 2586 as a subsequence so it does not avoid 1243. In this context σ is called a pattern or a forbidden subsequence and π is called a restricted permutation or a patternavoiding permutation. For any permutations σ_{1}, …, σ_{k} we write S_{n}(σ_{1}, …, σ_{k}) to denote the set of permutations in S_{n} which avoid σ_{1}, …, σ_{k} and we write S(σ_{1}, …, σ_{k}) to denote the set of permutations of any length which avoid σ_{1}, …, σ_{k}. Pattern avoidance has proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting [3, Ch. 2.2.1], to singularities of Schubert varieties [5], to Chebyshev polynomials of the second kind [1, 4, 8], to rook polynomials for a rectangular board [7].

1Research financed by EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

In this paper we investigate connections pattern-avoiding permutations have with Fibonacci numbers and k-generalized Fibonacci numbers. To define the k-generalized Fibonacci numbers, first fix k ≥ 1. The sequence of k-generalized Fibonacci numbers is given by F_{k,n} = 0 for n ≤ 0, F_{k,1} = 1, and F_{k,n} = ∑_{i=1}^{k} F_{k,n−i} for n ≥ 2. We observe that F_{2,n} is the ordinary Fibonacci number F_{n} for all n ≥ 0. Moreover, the ordinary generating function for the k-generalized Fibonacci numbers is given by

∑_{n=0}^{∞} F_{k,n}x^{n} = \frac{x}{1 − x − x^{2} − … − x^{k}}  (k ≥ 1).  (1)

We will also make use of the fact, which can be verified by induction on n, that the number of tilings of a 1 × n rectangle with tiles of size 1 × 1, 1 × 2, …, 1 × k is given by F_{k,n+1} for all k ≥ 1 and all n ≥ 0.

In this paper we give families of pattern-avoiding permutations which can be enumerated in terms of Fibonacci numbers or k-generalized Fibonacci numbers. The earliest example of such a result is Simion and Schmidt’s proof [9, Prop. 15] that

|S_{n}(132, 213, 123)| = F_{n+1}  (n ≥ 0).  (2)

Somewhat later West used generating trees to show [10] that for many sets R consisting of one pattern of length three and one of length four, |S_{n}(R)| = F_{2n−1}. More recently Mansour expressed [6, Thm. 8] the ordinary generating function for |S_{n}(132, 213, τ)| as a determinant for every τ ∈ S_{k}(132, 213). Using this result, Mansour showed that

|S_{n}(132, 213, 2341)| = F_{n+2} − 1  (n ≥ 1).  (3)

One can also use [6, Thm. 8] to show that

|S_{n}(132, 213, 12 … k)| = F_{k−1,n+1} (k ≥ 2),

and that if a, b, and c are nonnegative integers with b ≥ 1 and a + c ≥ 1 then

∑_{n=0}^{∞} |S_{n}(132, 213, β_{a,b,c})|x^{n} = \frac{(1 − x)^{a+c} + x^{b} ( ∑_{i=0}^{a+c−1}(1 − x)^{i}x^{a+c−i+1})}{(1 − x)^{a+c}(1 − x − … − x^{b−1})},

where β_{a,b,c} is the permutation in S_{a+b+c} given by

β_{a,b,c} = c + b + a, c + b + (a − 1), …, c + b + 1, c + 1, c + 2, …, b + c, c, c − 1, …, 2, 1.

Moreover, it is apparent from Mansour’s description of the elements of S_{n}(132, 213) in [6, Thm. 8] that there is a constructive bijection between S_{n}(132, 213) and the set of tilings of a 1 × n rectangle with tiles of size 1 × i, where i ≥ 1. One can show that the restriction of this map to S_{n}(132, 213, 12 … k) is a bijection between S_{n}(132, 213, 12 … k) and the set of tilings of a 1 × n rectangle with tiles of size 1 × 1, 1 × 2, …, 1 × (k − 1). One can also show that the restriction of this map to S_{n}(132, 213, β_{a,b,c}) is a bijection between S_{n}(132, 213, β_{a,b,c}) and the set of tilings of a 1 × n rectangle in which all but the leftmost a tiles and the rightmost c tiles have length at most b − 1. It follows that for n ≥ 1,

|S_{n}(132, 213, β_{a,b,c})| = ∑_{k=1}^{a+c−1} \binom{n − 1}{k − 1} + ∑_{k=a+c}^{n} \binom{k − 1}{a + c − 1}F_{b−1,n−k+1}.

Mansour has also expressed [6, Thm. 3] the ordinary generating function for |S_{n}(123, 132, τ)| as a determinant for certain τ ∈ S_{k}(123, 132). Using this result, Mansour showed that

|S_{n}(123, 132, 3241)| = F_{n+2} − 1  (n ≥ 1).  (4)

One can also use Mansour’s description of the elements of S_{n}(123, 132) in [6, Thm. 3] to give a bijective proof that

|S_{n}(123, 132, (k − 1)(k − 2) … 21k)| = F_{k−1,n+1} (k ≥ 2).

We begin our results with an extension of [6, Thm. 3] in which we give recurrence relations for the generating function for |S_{n}(123, 132, τ)| which apply for all τ ∈ S(123, 132). Using these recurrence relations, we give an explicit enumeration of S_{n}(123, 132, τ) in terms of k-generalized Fibonacci numbers for all τ of the form

τ = k + (l − 1), k + (l − 2), …, k + 1, k + l, k, k − 1, …, 2, 1.

We also give a bijective proof of this enumeration. We then turn our attention to generalizations of (3) and (4). To generalize (3) we give a recurrence relation for the generating function for |S_{n}(132, 2341, ω_{k})|, where ω_{k} is the permutation in S_{k} given by ω_{k} = k, k −1, …, 4, 2, 1, 3. Using this relation we give explicit enumerations of S_{n}(132, 2341, ω_{k}) in terms of Fibonacci numbers and binomial coefficients for several small values of k. To generalize (4) we give recurrence relations for the generating function for |S_{n}(132, 3241, μ_{a,b})|, where μ_{a,b} is the permutation in S_{a+b} given by μ_{a,b} = b+a, b+a−1, …, b+1, 1, 2, …, b. Using these relations we give explicit enumerations of S_{n}(132, 3241, μ_{a,b}) in terms of k-generalized Fibonacci numbers for several small values of a and b.

2. Avoiding 123, 132, and Another Pattern

For any permutation π, let F_{π}(x) denote the generating function given by

F_{π}(x) = ∑_{n=0}^{∞} |S_{n}(123, 132, π)|x^{n}.

In this section we give recurrence relations for F_{π}(x) for all π ∈ S_{n}(123, 132). We begin by setting some notation.

Definition 2.1 For all k ≥ 1, we write [k] to denote the permutation in S_{k} given by

[k] = k(k − 1) … 21.

For notational convenience we let [0] denote the empty permutation. For all k ≥ 2, we write ⟨k⟩ to denote the permutation in S_{k} given by

⟨k⟩ = (k − 1)(k − 2) … 21k.

For notational convenience we set ⟨1⟩ = 1 and we let ⟨0⟩ denote the empty permutation.

Definition 2.2 For all π_{1} ∈ S_{m} and all π_{2} ∈ S_{n}, we write π_{1} ⊖π_{2} to denote the permutation in S_{m+n} which is given by

(π_{1} ⊖ π_{2})(i) = \{ \begin{matrix}n + π_{1}(i) & 1 ≤ i ≤ m \\ π_{2}(i − m) & m + 1 ≤ i ≤ m + n \end{matrix} .

We refer to π_{1} ⊖ π_{2} as the skew sum of π_{1} and π_{2}.

Mansour has shown [6, Thm. 3] that π ∈ S_{n}(123, 132) if and only if π is a skew sum of permutations of the forms [k], k ≥ 1, and ⟨l⟩, l ≥ 2. In the same theorem Mansour expresses F_{π}(x) as a determinant when π is a skew sum of permutations of the form ⟨l⟩, l ≥ 2. It is clear from the form of this determinant that for these π, the set S_{n}(123, 132, π) can always be enumerated in terms of k-generalized Fibonacci numbers. Here we give recurrence relations which enable one to compute F_{π}(x) for any permutation π. We then find simple formulas for |S_{n}(123, 132, π)| in terms of k-generalized Fibonacci numbers for a variety of π which are not handled by [6, Thm. 3]. We begin by examining F_{[k]}(x).

Theorem 2.3 For all k ≥ 1 we have

F_{[k]}(x) = 1 + xF_{[k−1]}(x) + ∑_{i=2}^{k+1} x^{i}F_{[k−i+1]}(x).  (5)

Proof. First observe that S(123, 132, [k]) may be partitioned into the sets A_{0}, A_{1}, …, A_{k}, where A_{0} is the set containing only the empty permutation, and for 1 ≤ i ≤ k the set A_{i} consists of those permutations π ∈ S(123, 132, [k]) such that π(i) is π’s largest entry. Now observe that the set A_{1} consists of those permutations of the form 1 ⊖ τ, where τ ∈ S(123, 132, [k − 1]). Similarly, for 2 ≤ i ≤ k the set A_{i} consists of those permutations of the form ⟨i⟩ ⊖ τ, where τ ∈ S(123, 132, [k − i + 1]). The generating function for A_{0} is 1, the generating function for A_{1} is xF_{[k−1]}(x), and the generating function for A_{i}, 2 ≤ i ≤ k, is x^{i}F_{[k−i+1]}(x). Add these generating functions to obtain (5). □

Next we consider the case in which π has the form [k] ⊖ π_{1}, where π_{1} is not the empty permutation. Observe that in this case we may assume π_{1} = ⟨l⟩ ⊖ π_{2} for l ≥ 2, since [r] ⊖ [s] = [r + s] and ⟨1⟩ = [1].

Theorem 2.4 For any permutation π, any k ≥ 1, and any l ≥ 2 we have

F_{[k]⊖⟨l⟩⊖π}(x) = 1 + xF_{[k−1]⊖⟨l⟩⊖π}(x) + ∑_{i=2}^{k} x^{i}F_{[k−i+1]⊖⟨l⟩⊖π}(x) + \frac{x^{k+1}}{1 − x}F_{⟨l⟩⊖π}(x). (6)

Proof. This is similar to the proof of (5). □

Next we consider the case in which π has the form ⟨k⟩ ⊖ π_{1}.

Theorem 2.5 For any permutation π and any k ≥ 2 we have

F_{⟨k⟩⊖π}(x) = \frac{1 − x + x^{k}F_{π}(x)}{1 − 2x + x^{k}}.  (7)

Proof. This is similar to the proof of (5). □

To illustrate our recurrence relations for F_{π}(x), we now use them to find |S_{n}(123, 132, π)| for various π. In each case, |S_{n}(123, 132, π)| is given by a simple formula involving Fibonacci numbers or k-generalized Fibonacci numbers. We begin with π = ⟨3⟩ ⊖ [2] = 43521.

Proposition 2.6 For all n ≥ 3,

|S_{n}(123, 132, ⟨3⟩ ⊖ [2])| = F_{n+2} + F_{n} − 3.  (8)

Moreover,

F_{⟨3⟩⊖[2]}(x) = 3 + x + x^{2} + \frac{x^{2} + 4x − 2}{1 − 2x + x^{3}}.  (9)

Proof. To obtain (9), set k = 3 and π = [2] in (7) and use the fact that F_{[2]}(x) = 1 + x + x^{2} to simplify the result. To obtain (8), observe that

\frac{x^{2} + 4x − 2}{1 − 2x + x^{3}} = \frac{−3}{1 − x} + \frac{2x + 1}{1 − x − x^{2}} .

Now (8) is immediate in view of (1). □

We now use (5), (6), and (7) to obtain explicit enumerations of S_{n}(123, 132, ⟨l⟩ ⊖ [2]) for l ≥ 4.

Proposition 2.7 Fix l ≥ 4. Then for all n ≥ 3,

|S_{n}(123, 132, ⟨l⟩ ⊖ [2])|= (\frac{1}{l − 2})(3F_{l−1,n+1}+(l−5)F_{l−1,n−1}+3 ∑_{i=3}^{l−2}(l−i−1)F_{l−1,n−i+1}−3) .

Alternatively, for all n ≥ 3,

|S_{n}(123, 132, ⟨l⟩ ⊖ [2])| = ∑_{k=1}^{n−1} F_{l−1,k} + 2 ∑_{k=1}^{n−2} F_{l−1,k}.  (11)

Moreover,

∑_{n=0}^{∞} |S_{n}(123, 132, ⟨l⟩ ⊖ [2])|x^{n} = 1 + x + x^{2} + \frac{x^{2} + 2x^{3}}{1 − 2x + x^{l}} .  (12)

Proof. To obtain (12), set k = l and π = [2] in (7) and use the fact that F_{[2]}(x) = 1+x+x^{2}. To obtain (10), observe that if l ≥ 4 then

\frac{x^{2} + 2x^{3}}{1 − 2x + x^{l}} = (\frac{1}{l − 2}) (\frac{−3}{1 − x} + \frac{3 + (l − 5)x^{2} + 3 ∑_{i=3}^{l−2}(l − i − 1)x^{i}}{1 − x − … − x^{l−1}} ) .

Now (10) is immediate in view of (1). To obtain (11), observe that

\frac{x^{2} + 2x^{3}}{(1 − x)(1 − x − … − x^{l−1})} = (∑_{n=0}^{∞} x^{n}) (∑_{n=0}^{∞} (F_{l−1,n−1} + 2F_{l−1,n−2}) x^{n})
= ∑_{n=0}^{∞} (∑_{k=0}^{n−1} F_{l−1,k} + 2 ∑_{k=0}^{n−2} F_{l−1,k}) x^{n}.

Now (11) is immediate in view of (1). □

We also give a bijective proof of (8) and (11).

Theorem 2.8 Let l ≥ 3. For all n ≥ 1, let B_{n} denote the set of tilings of a 1 × n rectangle in which there is at most one tile with length greater than l − 1, and this tile has at most one tile, of length 1 or 2, to its right. Then there exists a constructive bijection between B_{n} and S_{n}(123, 132, ⟨l⟩ ⊖ [2]).

Proof. Suppose we are given such a tiling. We construct its corresponding permutation as follows. Let m denote the length of the rightmost tile. Fill this tile with the numbers 1, 2, …, m from left to right in the order m − 1, m − 2, …, 1, m. Fill the tile immediately to the left of the rightmost tile in the same way, using the smallest available numbers. Repeat this process until every tile is filled. It is routine to verify that this map is invertible, and that the permutation constructed avoids 123, 132, and ⟨l⟩ ⊖ [2]. □

Lines (5), (6) and (7) yield many additional enumerations involving k-generalized Fibonacci numbers. We summarize some of these in the following table.

k l m  |S_{n}(123, 132, [k] ⊖ ⟨l⟩ ⊖ [m])|  valid for
1 2 2  F_{n+3} + F_{n+1} − 3n + 2  n ≥ 3
2 2 2  5F_{n+1} − 9n + 21  n ≥ 5
3 2 2  3F_{n+2} + 3F_{n} − 24n + 91  n ≥ 7
1 3 2  \frac{1}{2} (F_{3,n+2} + 2F_{3,n} + F_{3,n−1} − 3n + 5)  n ≥ 3
2 3 2  \frac{1}{2} (4F_{3,n+1} + F_{3,n} − 3F_{3,n−1} − 9n + 30)  n ≥ 5
3 3 2 \frac{1}{2} (3F_{3,n} + 10F_{3,n−1} − 3F_{3,n−2} − 24n + 115) n ≥ 7

Table 1

3. Avoiding 132 and Two Longer Permutations

In this section we generalize Mansour’s results (3) and (4) by lengthening some of the forbidden subsequences. We begin with (3).

Definition 3.9 For all k ≥ 3 we write ω_{k} to denote the permutation in S_{k} given by ω_{k} = [k − 3] ⊖ 213. We write G_{k}(x) to denote the generating function

G_{k}(x) = ∑_{n=0}^{∞} |S_{n}(132, 2341, ω_{k})|x^{n}.

In [6, Thm. 8] Mansour uses generating function techniques to find G_{3}(x), from which he proves (3). We give a bijective proof of (3).

Proposition 3.10 For all n ≥ 1, there exists a constructive bijection between the set S_{n}(132, 213, 2341) and the set of tilings of a 1 × (n + 1) rectangle with tiles of size 1 × 1 and 1 × 2 using at least one 1 × 2 tile.

Proof. Suppose we are given such a tiling. We construct its corresponding permutation as follows. Replace the rightmost 1 × 2 tile with a 1 and fill the (necessarily 1 × 1) tiles to the right of the 1 with 2, 3, … from left to right. Now fill the rightmost empty tile with the smallest numbers available, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled. It is routine to verify that this map is invertible and that the permutation constructed avoids 132, 213, and 2341, as desired. □

We now give a recurrence relation for G_{k}(x).

Proposition 3.11 We have

G_{3}(x) = \frac{x^{3} − x + 1}{(1 − x)(1 − x − x^{2})}.  (13)

Moreover, for all k > 3,

G_{k}(x) = (\frac{1}{1 − x}) (1 + x(G_{k−1}(x) − 1) + ∑_{r=2}^{k−2} x^{r}(G_{k−r+1}(x) − 1) + \frac{x^{k−1}}{1 − x}(G_{3}(x) − 1)) . (14)

Proof. Line (13) is immediate from (3), since ω_{3} = 213. The proof of (14) is similar to the proof of (5). □

The table below gives |S_{n}(132, 2341, ω_{k})| for several small values of k. Observe that in each case |S_{n}(132, 2341, ω_{k})| is given by a simple formula involving Fibonacci numbers and binomial coefficients.

k  |S_{n}(132, 2341, ω_{k})|  valid for
4  F_{n+5} − \binom{n + 1}{2} − 2\binom{n + 1}{1} − 2  n ≥ 1
5  3F_{n+5} − 2\binom{n + 1}{3} − 4\binom{n + 1}{2} − 3\binom{n + 1}{1} − 14  n ≥ 2
6 5F_{n+6} + F_{n+4} − 4\binom{n + 1}{4} − 7\binom{n + 1}{3} − 5\binom{n + 1}{2} − 27\binom{n + 1}{1} − 8 n ≥ 2

Table 2

We now turn our attention to a generalization of (4).

Definition 3.12 For all k ≥ 1, let [k]^{r} denote the permutation 12 … k. For notational convenience, let [0]^{r} denote the empty permutation. For all k ≥ 0 and all l ≥ 0 we write H_{k,l}(x) to denote the generating function

H_{k,l}(x) = ∑_{n=0}^{∞} |S_{n}(132, 3241, [k] ⊖ [l]^{r})|x^{n}.

In [6, Thm. 3] Mansour uses generating function techniques to find H_{0,3}(x), from which he proves (4). We give a bijective proof of (4).

Proposition 3.13 For all n ≥ 1 there exists a constructive bijection between S_{n}(132, 3241, [3]^{r}) and the set of tilings of a 1 × (n + 1) rectangle with tiles of size 1 × 1 and 1 × 2 using at least one 1 × 2 tile.

Proof. Suppose we are given such a tiling. To construct the corresponding permutation, we consider two cases: the rightmost tile is 1 × 2 or the rightmost tile is 1 × 1.

If the rightmost tile is 1 × 2, then first place a 1 in the rightmost tile. Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled.

If the rightmost tile is 1 × 1, then let m denote the number of 1 × 1 tiles to the right of the rightmost 1 × 2 tile. Place an m in the rightmost 1 × 2 tile. Fill the (necessarily 1 × 1) tiles to the right of the rightmost 1 × 2 with the numbers m − 1, m − 2, …, 1, m + 1, in this order. Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled.

It is routine to verify that this map is invertible, and that the permutation constructed avoids 132, 3241, and μ_{0,3}. □

We now give recurrence relations for H_{0,l}(x) and H_{k,l}(x).

Proposition 3.14 Let k and l denote positive integers. Then H_{0,1}(x) = 1,

H_{0,l}(x) = 1 + \frac{xH_{0,l−1}(x)}{1 − x − … − x^{l−1}}  (l ≥ 2),  (15)

and

H_{k,l}(x) = \frac{1 − 2x + xH_{k−1,l}(x)}{(1 − x)^{2}}  (k ≥ 1).  (16)

Proof. This is similar to the proof of (5). □

Specializing k and l in (16) yields many explicit enumerations. We summarize some of these in the table below. The enumerations in this table are valid for n ≥ 1.

\begin{matrix}k & l & |S_{n}(132, 3241, [k] ⊖ [l]^{r})| \\ 0 & 4 & \frac{1}{2} (2F_{3,n+3} + F_{3,n+2} + F_{3,n} − 2F_{n+4} + 1) \\ 0 & 5 & \frac{1}{6} (14F_{4,n+4} + 8F_{4,n+3} + 4F_{4,n+2} + 2F_{4,n} − 6F_{3,n+6} − 3F_{3,n+5} − 3F_{3,n+3} + 6F_{n+5} − 1) \\ 1 & 3 & F_{n+5} − \binom{n + 1}{2} − 2\binom{n + 1}{1} − 2 \\ 2 & 3 & F_{n+8} − \binom{n + 1}{4} − 3\binom{n + 1}{3} − 4\binom{n + 1}{2} − 9\binom{n + 1}{1} − 11 \\ 1 & 4 & \frac{1}{2} (F_{3,n+5} + 2F_{3,n+4}) − F_{n+7} + \frac{1}{2}\binom{n + 1}{2} + \frac{3}{2}\binom{n + 1}{1} + 5 \end{matrix}

Table 3

Observe that for n ≥ 1 we have |S_{n}(132, 3241, [1] ⊖ [3]^{r})| = |S_{n}(132, 2341, ω_{4})|. This is no surprise, however, since S_{n}(132, 2341, ω_{4}) is precisely the set of group-theoretic inverses of the elements of S_{n}(132, 3241, [1] ⊖ [3]^{r}).

4. Extended Restrictions

Let R denote a set of permutations. In this section we describe a method of building sets of forbidden subsequences from R for which the associated sets of restricted permutations can be easily enumerated in terms of |S_{n}(R)|. We then use this method to produce some specific enumerations, several of which involve Fibonacci numbers or k-generalized Fibonacci numbers. We begin by describing our technique for building on R.

Definition 4.15 Suppose α ∈ S_{n−1} and β ∈ S_{n}. We say β is an extension of α whenever α is the permutation obtained by removing n from β. We observe that every permutation in S_{n} has exactly n + 1 extensions.

Definition 4.16 Let R denote a set of permutations. We write E(R) to denote the set of permutations π such that π is an extension of an element of R, and we refer to E(R) as the extension of R. More generally, we write E^{0}(R) = R and for any k ≥ 2 we define E^{k}(R) inductively, so that E^{k}(R) = E(E^{k−1}(R)).

Our results in this section are based on the following observation.

Theorem 4.17 Let R denote a set of permutations. Then for all n ≥ 1,

S_{n}(E(R)) = E(S_{n−1}(R)).  (17)

Moreover, for all k ≥ 0,

|S_{n}(E^{k}(R))| = \frac{n!}{(n − k)!}|S_{n−k}(R)|  (n ≥ k)  (18)

and

|S_{n}(E^{k}(R))| = n!  (0 ≤ n < k).  (19)

Proof. To obtain (17), suppose π′ ∈ S_{n−1}, π is an extension of π′, and σ′ is a permutation. Observe that π′ contains a subsequence of type σ′ if and only if there exists an extension σ of σ′ such that π contains a subsequence of type σ. Now (17) is immediate.

To obtain (18), we argue by induction on k. Since E^{0}(R) = R, the result is immediate for k = 0. Now observe that every permutation in S_{n} has exactly n+1 extensions, and every permutation in S_{n+1} is the extension of exactly one permutation in S_{n}. Therefore, using (17) and induction we find

|S_{n}(E^{k}(R))| = |E(S_{n−1}(E^{k−1}(R)))|
= n|S_{n−1}(E^{k−1}(R))|
= \frac{n!}{(n − k)!}|S_{n−k}(R)|,

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A01 11

as desired.

To obtain (19), observe that every permutation in E^{k}(R) has length at least k, so S_{n}(E^{k}(R)) = S_{n} when n < k. □

We now give several applications of this theorem. Proposition 4.18 For all k ≥ 0 and all n ≥ k,

|S_{n}(E^{k}(123, 132, 213))| = \frac{n!}{(n − k)!}F_{n+1−k}.

In particular, for all n ≥ 1,

|S_{n}(1234, 1243, 1423, 4123, 1324, 1342, 1432, 4132, 2134, 2143, 2413, 4213)| = nF_{n}. Proof. Set R = {123, 132, 213} in (18) and use (2) to simplify the result. □ Proposition 4.19 Let R denote one of the following sets of permutations.

\begin{matrix}\{123, 1432\}; \{123, 2143\}; \{123, 2413\}; \{132, 1234\}; \{132, 2134\}; \\ \{132, 2314\}; \{132, 2341\}; \{132, 3241\}; \{132, 3412\} \end{matrix}

For all k ≥ 0 and all n ≥ k,

|S_{n}(E^{k}(R))| = \frac{n!}{(n − k)!}F_{2(n−k)−1}.  (20)

Proof. In [10] West shows that for each of the sets listed, S_{n}(R) = F_{2n−1}. Combine this with (18) to obtain (20). □ Proposition 4.20 (see also [2]) Fix τ ∈ S_{3}. For all k ≥ 0 and all n ≥ k,

|S_{n}(E^{k}(τ))| = \frac{n!}{(n − k + 1)!}\binom{2n − 2k}{n − k}.  (21)

Proof. It is well known that for all τ ∈ S_{3} we have S_{n}(τ) = C_{n}, where C_{n} = \frac{1}{n + 1}\binom{2n}{n} is the nth Catalan number. Combine this with (18) to obtain (21). □

References

[1] T. Chow and J. West. Forbidden subsequences and Chebyshev polynomials. Discrete Math., 204(1– 3):119–128, 1999.

[2] O. Guibert. Permutations sans sous-séquence interdite. PhD thesis, Université Bordeaux I, 1992.

[3] D. E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, 3rd edition, 1997.

[4] C. Krattenthaler. Permutations with restricted patterns and Dyck paths. Adv. in Appl. Math., 27(2/3):510–530, 2001.

[5] V. Lakshmibai and M. Song. A criterion for smoothness of Schubert varieties in Sp_{2n}/B. J. Algebra, 189(2):332–352, 1997.

[6] T. Mansour. Permutations avoiding a pattern from S_{k} and at least two patterns from S_{3}. Ars Combin., 62, 2002.

[7] T. Mansour and A. Vainshtein. Avoiding maximal parabolic subgroups of S_{k}. Discrete Math. Theor. Comput. Sci., 4(1):67–75, 2000.

[8] T. Mansour and A. Vainshtein. Restricted 132-avoiding permutations. Adv. in Appl. Math., 26(3):258– 269, 2001.

[9] R. Simion and F. Schmidt. Restricted permutations. Europ. J. Combin., 6:383–406, 1985.

[10] J. West. Generating trees and forbidden subsequences. Discrete Math., 157:363–374, 1996.