321-polygon-avoiding permutations and Chebyshev polynomials

Toufik Mansour

LaBRI, Université Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France

                           toufik@labri.fr

Zvezdelina Stankova

Mills College, Oakland, CA

                          stankova@mills.edu

Submitted: July 22, 2002; Accepted: January 6, 2003. MR Subject Classifications: 05A05, 05A15, 30B70, 42C05

Abstract

A 321-k-gon-avoiding permutation π avoids 321 and the following four patterns:

k(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ (k − 1)(k + 1),
k(k + 2)(k + 3) ⋯ (2k − 1)(2k)12 ⋯ (k − 1)(k + 1),
(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ k,
(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)(2k)123 ⋯ k.

The 321-4-gon-avoiding permutations were introduced and studied by Billey and Warrington [BW] as a class of elements of the symmetric group whose Kazhdan-Lusztig, Poincaré polynomials, and the singular loci of whose Schubert varieties have fairly simple formulas and descriptions. Stankova and West [SW1] gave an exact enumeration in terms of linear recurrences with constant coefficients for the cases k = 2, 3, 4. In this paper, we extend these results by finding an explicit expression for the generating function for the number of 321-k-gon-avoiding permutations on n letters. The generating function is expressed via Chebyshev polynomials of the second kind.

1 Introduction

Definition 1 Let α ∈ S_{n} and τ ∈ S_{k} be two permutations. Then α contains τ if there exists a subsequence 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n such that (α_{i_{1}}, …, α_{i_{k}}) is order-isomorphic to τ; in such a context τ is usually called a pattern; α avoids τ, or is τ-avoiding, if α does not contain such a subsequence. The set of all τ-avoiding permutations in S_{n} is denoted by S_{n}(τ). For a collection of patterns T, α avoids T if α avoids all τ ∈ T; the corresponding subset of S_{n} is denoted by S_{n}(T).

While the case of permutations avoiding a single pattern has attracted much attention (for example, see [BaWe, BWX, S, SW2]), the case of multiple pattern avoidance remains less investigated. In particular, it is natural to consider permutations avoiding pairs of patterns τ_{1}, τ_{2}. The enumeration problem was solved completely for τ_{1}, τ_{2} ∈ S_{3} (see [SS]), for τ_{1} ∈ S_{3} and τ_{2} ∈ S_{4} (see [W]). For τ_{1}, τ_{2} ∈ S_{4} the classification into Wilf classes has been completed and enumeration formulae are known for many Wilf classes exact (see [Bo1, Km] and references therein). Several recent papers [CW, MV1, Kr, MV2, MV3, MV4] deal with the case τ_{1} ∈ S_{3}, τ_{2} ∈ S_{k} for various pairs τ_{1}, τ_{2}. The tools involved in these papers include Fibonacci numbers, Catalan numbers, Chebyshev polynomials, continued fractions, and Dyck words, e.g. in [MV2]:

Theorem 2 (Mansour, Vainshtein) Let U_{m}(cos θ) = sin(m + 1)θ/ sin θ be the Chebyshev polynomial of the second kind. When 2 ≤ d + 1 ≤ k, the generating function for the number of permutations in S_{n}(321, (d + 1) ⋯ k12 ⋯ d) is given by

\frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})}·

Recently, a special class of restricted permutations has arisen in representation theory.

Definition 3 A permutation π is k-gon-avoiding if it avoids each pattern in the set P_{k}:

{k(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ (k − 1)(k + 1),
k(k + 2)(k + 3) ⋯ (2k − 1)(2k)12 ⋯ (k − 1)(k + 1),
(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ k,
(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)(2k)123 ⋯ k}.

We say that π is a 321-k-gon-avoiding permutation if it is both k-gon-avoiding and 321avoiding. The number of 321-k-gon-avoiding permutations in S_{n} is denoted by f_{k}(n). The corresponding generating function is f_{k}(x) = ∑_{n≥0} f_{k}(n)x^{n}.

Figure 1: B_{5}: all four 5-gons

Note that f_{k}(n) = \frac{1}{n+1} \binom{2n}{n} for n ∈ [0, 2k − 1], as these count the permutations in S_{n}(321) (see [Kn]).

Billey and Warrington [BW] introduced the 321-4-gon-avoiding (or 321-hexagon-avo-iding) permutations as a class in S_{n} whose Kazhdan-Lusztig and Poincaré polynomials, and the singular loci of whose Schubert varieties have fairly simple formulas and descriptions. Upon their request, Stankova and West [SW1] presented an exact enumeration for the cases k = 2, 3, 4 by using generating trees, the symmetries in the set of the P_{k}, and the structure of the 321-avoiding permutations via Schensted’s 321–subsequences decomposition.

Theorem 4 (Stankova,West) For k = 2, 3, 4, the sequences f_{k}(n) satisfy the recursive relations

f_{4}(n) = 6f_{4}(n − 1) − 11f_{4}(n − 2) + 9f_{4}(n − 3) − 4f_{4}(n − 4) − 4f_{4}(n − 5) + f_{4}(n − 6), n ≥ 6; f_{3}(n) = 4f_{3}(n − 1) − 4f_{3}(n − 2) + 3f_{3}(n − 3) + f_{3}(n − 4) − f_{3}(n − 5), n ≥ 5; f_{2}(n) = 3f_{2}(n − 1) − 3f_{2}(n − 2) + f_{2}(n − 3) = (n − 1)^{2} + 1, n ≥ 3.

In this paper we present an approach to the study of 321- k-gon- avoiding permutations in S_{n} which generalizes the methods in [SW1] and [MV3]. As a consequence, we extend the results in [SW1] to all 321-k-gon-avoiding permutations, and derive a number of other related results. The main theorem of the paper is formulated as follows.

Theorem 5 For k ≥ 3 and s ≥ 1, define L_{n}^{k}(s) = ∑_{j=0}^{s}(−1)^{j}\binom{s−j}{j}f_{k}(n − j). When n ≥ 2k,

this sequence satisfies the linear recursive relation with constant coefficients:

L_{n}^{k}(2k − 2) = L_{n−1}^{k}(2k − 2) + L_{n−3}^{k}(2k − 5) + L_{n−3}^{k}(2k − 4) + L_{n−4}^{k}(2k − 5) + L_{n−4}^{k}(2k − 4).

Corollary 6 For k ≥ 3,

f_{k}(x) = \frac{(1 + 2x^{2} + x^{3})U_{2k−3} (\frac{1}{2\sqrt{x}}) − \sqrt{x}(1 + x)U_{2k−4} (\frac{1}{2\sqrt{x}})}{\sqrt{x} [(1 + 2x^{2} + x^{3})U_{2k−2} (\frac{1}{2\sqrt{x}}) − \sqrt{x}(1 + x)U_{2k−3} (\frac{1}{2\sqrt{x}})]}·

The proofs of Theorem 5 and Corollary 6 are presented in Section 2. Note that Corollary 6 implies the previously known results for the cases k = 3, 4 (see [SW1]):

f_{3}(x) = \frac{1 − 3x + 2x^{2} − 2x^{3} − 2x^{4}}{1 − 4x + 4x^{2} − 3x^{3} − x^{4} + x^{5}} ,
f_{4}(x) = \frac{1 − 5x + 7x^{2} − 5x^{3} + x^{4} + 3x^{5}}{1 − 6x + 11x^{2} − 9x^{3} + 4x^{4} + 4x^{5} − x^{6}} ·

In Section 3, we describe several generalizations of Theorem 5 and Corollary 6, following similar arguments from their proofs.

2 Proof of Theorem 5

2.1 Refinement of the numbers f_{k}(n)

Definition 7 For m, n with 1 ≤ m ≤ n and distinct i_{1}, i_{2}, ..., i_{m} ∈ ℕ, we denote by f_{k}(n; i_{1}, …, i_{m}) the number of 321-k-gon-avoiding permutations π ∈ S_{n} which start with i_{1}i_{2} ⋯ i_{m}: π_{1}π_{2} ⋯ π_{m} = i_{1}i_{2} ⋯ i_{m}. The corresponding subset of S_{n} is denoted by

F_{k}(n; i_{1}, …, i_{m}).

Here follow basic properties of the numbers f_{k}(n; i_{1}, …, i_{m}), easily deduced from the definitions.

Lemma 8 Let n ≥ 3, 1 ≤ m ≤ n and 1 ≤ i_{1} < i_{2} < ⋯ < i_{m} ≤ n.

(a) If m ≤ n − 2 and 3 ≤ i_{1}, then f_{k}(n; i_{1}, …, i_{m}, j) = 0 for 2 ≤ j ≤ i_{m} − 1. Consequently,

f_{k}(n; i_{1}, …, i_{m}) = f_{k}(n; i_{1}, …, i_{m}, 1) + ∑_{j=i_{m}+1}^{n} f_{k}(n; i_{1}, …, i_{m}, j).

(b) If m ≤ k − 1 and 2 ≤ i_{1}, then f_{k}(n; i_{1}, …, i_{m}, 1) = f_{k}(n − 1; i_{1} − 1, …, i_{m} − 1).

(c) If i_{1} ≤ k − 1, then f_{k}(n; i_{1}, …, i_{m}) = f_{k}(n − 1; i_{2} − 1, …, i_{m} − 1).

Proof For (a), observe that if π ∈ F_{k}(n; i_{1}, …, i_{m}, j) then the entry ⟨i_{m}, j, 1⟩ gives an occurrence of 321 in π. For the second part of (a), consider the entry π_{m+1} of π. Again, avoiding 321 forces π_{m+1} = 1 or π_{m+1} > i_{m}. For (b), denote by π′ the permutation obtained from π by deleting its smallest entry and decreasing all other entries by 1 and the permutation π obtained from π′ by π = (π′_{1} + 1, …, π′_{m} + 1, 1, π′_{m+1} + 1, …, π′_{n−1} + 1). Then π ∈ F_{k}(n; i_{1}, …, i_{m}, 1) if and only if π′ ∈ F_{k}(n − 1; i_{1} − 1, …, i_{m} − 1), since entry 1 placed as in (b) cannot be used in an occurrence of 321 or τ ∈ P_{k} in π. For (c), observe that if π_{1}π_{2} ⋯ π_{m} = i_{1}i_{2} ⋯ i_{m} then the entry i_{1} cannot appear in any occurrences of τ ∈ P_{k}; further, if there is an occurrence xyz of 321 such that x = i_{1} then there is an occurrence i_{2}yx of 321 in π. □

Lemma 8 implies an explicit formula for f_{k}(n; s) for the first values of s.

Proposition 9 For 1 ≤ s ≤ min{k − 1, n},

f_{k}(n; s) = ∑_{j=0}^{s−1}(−1)^{j}\binom{s − 1 − j}{j}f_{k}(n − 1 − j).

Proof By Lemma 8(a)-(c) the proposition holds for s = 1, 2. For s ≥ 3, Lemma 8(a) says

f_{k}(n; s) = f_{k}(n; s, 1) + ∑_{j=s+1}^{n} f_{k}(n; s, j)

⇒ f_{k}(n; s) = f_{k}(n − 1; s − 1) + ∑_{j=s+1}^{n} f_{k}(n − 1; j − 1) = ∑_{j=s−1}^{n−1} f_{k}(n − 1; j).

Equivalently,

f_{k}(n; s) = f_{k}(n − 1) − ∑_{j=1}^{s−2} f_{k}(n − 1; j).  (1)

Using induction on s, we assume that the proposition holds for all 1 ≤ j ≤ s − 1. Then (1) yields

f_{k}(n; s) = f_{k}(n − 1) − ∑_{j=1}^{s−2} ∑_{i=0}^{j−1}(−1)^{i}\binom{j − 1 − i}{i}f_{k}(n − 2 − i).

Switching the summation for indices i and j, applying the familiar equality

\binom{1}{a} + \binom{2}{a} + ⋯ + \binom{b}{a} = \binom{b + 1}{a + 1},

and finally relabelling the remaining index i to j, we obtain for all 2 ≤ s ≤ k − 1

f_{k}(n; s) = f_{k}(n − 1) + ∑_{j=1}^{s−1}(−1)^{j}\binom{s − 1 − j}{j}f_{k}(n − 1 − j)

= ∑_{j=0}^{s−1}(−1)^{j}\binom{s − 1 − j}{j}f_{k}(n − 1 − j).

Next we introduce objects A_{d}(n, m) which organize suitably the information about the numbers f_{k}(n; i_{1}, i_{2}, ..., i_{m}) and play an important role in the proof of the main result. □

Definition 10 For 1 ≤ d ≤ n + 1 − m and 1 ≤ m ≤ n set

A_{d}(n, m) = ∑_{d≤i_{1}<i_{2}<···<i_{m}≤n} f_{k}(n; i_{1}, …, i_{m}).

In the following subsections 2.2–2.3 we derive two expressions for A_{k}(n, k−1), compare them in subsection 2.4, and thus complete the proof of Theorem 5.

2.2 First expression of A_{k}(n, k − 1)

The numbers A_{d}(n, m) satisfy the following recurrence. Lemma 11 For 2 ≤ d ≤ k and 1 ≤ m ≤ min{k − 1, n},

A_{d}(n, m) = A_{d−1}(n, m) − A_{d−1}(n − 1, m − 1).

Proof By Definition 4, for all 2 ≤ d ≤ k we have:

A_{d}(n, m) = A_{d−1}(n, m) − ∑_{d≤i_{2}<···<i_{m}≤n} f_{k}(n; d − 1, i_{2}, ..., i_{m}).

Lemma 8(c) and Definition 4 imply

A_{d}(n, m) = A_{d−1}(n, m) − ∑_{d−1=i_{2}<i_{3}<···<i_{m}≤n−1} f_{k}(n − 1; i_{2}, i_{3} …, i_{m})
= A_{d−1}(n, m) − A_{d−1}(n − 1, m − 1).
□

We next find an explicit expression for A_{1}(n, m) in terms of f_{k}(n). Lemma 12 Let 1 ≤ m ≤ min{k − 1, n}. Then

A_{1}(n, m) = ∑_{j=0}^{m}(−1)^{j}\binom{m − j}{j}f_{k}(n − j).

Proof For m = 1, A_{1}(n, 1) = ∑_{1≤i_{1}≤n} f_{k}(n; i_{1}) = f_{k}(n), which equals the required expression. Assume the lemma for m and all appropriate n. Comparing the (m + 1)st entry j of π with i_{m},

A_{1}(n, m) = A_{1}(n, m + 1) + ∑_{1≤i_{1}<i_{2}<...<i_{m}≤n} ∑_{j=1}^{i_{m}−1} f_{k}(n; i_{1}, i_{2}, ..., i_{m}, j).

For the summation part on the right–hand side, avoidance of (321) implies that all numbers 1, 2, ..., j − 1 appear before the entry j, and hence j ≤ m. From Lemma 8,

A_{1}(n, m) = A_{1}(n, m + 1) + ∑_{j=1}^{m} ∑_{j+1≤i_{j}<i_{j+1}<...<i_{m}≤n} f_{k}(n; 1, 2, ..., j − 1, i_{j}, i_{j+1}, ..., i_{m}, j)
= A_{1}(n, m + 1) + ∑_{j=1}^{m} ∑_{2≤i_{j}<i_{j+1}<...<i_{m}≤n−j+1} f_{k}(n − j + 1; i_{j}, i_{j+1}, ..., i_{m}, 1)
= A_{1}(n, m + 1) + ∑_{j=1}^{m} ∑_{1≤i_{j}<i_{j+1}<...<i_{m}≤n−j} f_{k}(n − j; i_{j}, i_{j+1}, ..., i_{m})
= A_{1}(n, m + 1) + ∑_{j=1}^{m} A_{1}(n − j, m − j + 1) = ∑_{j=0}^{m} A_{1}(n − j, m − j + 1)

Applying the above to A_{1}(n − 1, m − 1), subtracting the results, using the induction hypothesis and the Pascal triangle identity \binom{m−j}{j} + \binom{m−j}{j−1} = \binom{m−j+1}{j}, we arrive at

A_{1}(n, m) = A_{1}(n, m + 1) + A_{1}(n − 1, m − 1)
⇒ A_{1}(n, m + 1) = A_{1}(n, m) − A_{1}(n − 1, m − 1)
= ∑_{j=0}^{m}(−1)^{j}\binom{m − j}{j}f_{k}(n − j) − ∑_{j=0}^{m−1}(−1)^{j}\binom{m − j − 1}{j}f_{k}(n − 1 − j)

= ∑_{j=0}^{m+1}(−1)^{j}\binom{m − j + 1}{j}f_{k}(n − j).
□

Lemmas 11–12 can be combined to derive the following explicit expression for A_{d}(n, m), which is easily proven by induction on d.

Corollary 13 Let 1 ≤ d ≤ k, 1 ≤ m ≤ min{k − 1, n}. Then

A_{d}(n, m) = ∑_{j=0}^{d+m−1}(−1)^{j}\binom{d + m − 1 − j}{j}f_{k}(n − j) = L_{n}^{k}(d + m − 1).

In particular,

A_{k}(n, k − 1) = ∑_{j=0}^{2k−2}(−1)^{j}\binom{2k − 2 − j}{j}f_{k}(n − j) = L_{n}^{k}(2k − 2).

2.3 Second expression of A_{k}(n, k − 1)

We start by introducing three objects related to A_{d}(n, m).

Definition 14 For 1 ≤ d ≤ n − m + 1 and 1 ≤ m ≤ n set

B_{d}(n, m) = ∑_{d+1≤i_{1}<i_{2}<···<i_{m}≤n} f_{k}(n; d, i_{1}, …, i_{m});
C_{d}(n, m) = ∑_{d≤i_{1}<i_{2}<···<i_{m}≤n} f_{k}(n; i_{1}, …, i_{m}, 1);
D_{d}(n, m) = ∑_{d+1≤i_{1}<i_{2}<···<i_{m}≤n} f_{k}(n; d, i_{1}, …, i_{m}, 1).

Note that by Lemma 8(a), for k ≥ 2:

A_{k}(n, k − 1) = A_{k}(n, k) + C_{k}(n, k − 1).  (2)

The following Propositions 15–16 describe A_{k}(n, k) and C_{k}(n, k − 1) in terms of f_{k}(n).

Proposition 15 Let n ≥ k − 1. Then

(a) C_{k}(n, k − 1) = C_{k−1}(n − 1, k − 1) + A_{k−1}(n − 3, k − 2);

(b) C_{k}(n, k − 1) = C_{k}(n − 1, k − 1) + A_{k−2}(n − 3, k − 2) + A_{k−1}(n − 3, k − 2).

Proof For (a), similarly to Lemma 8(b) (with k ≥ 3), we have

C_{k}(n, k − 1) = ∑_{k≤i_{1}<···<i_{k−1}≤n} f_{k}(n; i_{1}, …, i_{k−1}, 1, 2) + ∑_{k≤i_{1}<···<i_{k−1}<i_{k}≤n} f_{k}(n; i_{1}, …, i_{k−1}, 1, i_{k}).

(3)

If π starts with i_{1}, …, i_{k−1}, 1, 2 as in the first sum in (3), then the entry 2 cannot participate in an occurrence of 321 or of τ ∈ P_{k}. Hence

f_{k}(n; i_{1}, …, i_{k−1}, 1, 2) = f_{k}(n − 1; i_{1} − 1, …, i_{k−1} − 1, 1).  (4)

For the second sum in (3), if π starts with i_{1}, …, i_{k−1}, 1, i_{k}, avoidance of 321 and both

\begin{matrix}(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ k, \\ k(k + 2)(k + 3) ⋯ (2k − 1)1(2k)23 ⋯ (k − 1)(k + 1), \end{matrix}

implies i_{1} = k and i_{2} = k + 1. Now, if π starts with k, k + 1, i_{3}, …, i_{k−1}, 1, i_{k} where k + 2 ≤ i_{3} < ⋯ < i_{k} ≤ n, then note that no occurrence of τ ∈ P_{k} can contain the entries k or k + 1; further, an occurrence of 321 containing k will exist in π if and only if there is such an occurrence containing k + 1. Using this and Lemma 8,

f_{k}(n; k, k + 1, i_{3}, …, i_{k−1}, 1, i_{k+1}) = f_{k}(n − 1; k, i_{3} − 1, …, i_{k−1} − 1, 1, i_{k+1} − 1)
= f_{k}(n − 2; k − 1, i_{3} − 2, …, i_{k−1} − 2, i_{k+1} − 2)
= f_{k}(n − 3; i_{3} − 3, …, i_{k−1} − 3, i_{k+1} − 3).

Combining the last equality with (3), (4) and the definitions of C_{d}(n, m) and A_{d}(n, m), we obtain the desired equality

C_{k}(n, k − 1) = C_{k−1}(n − 1, k − 1) + A_{k−1}(n − 3, k − 2).

For (b), by definitions of C_{d}(n, m) and D_{d}(n, m), we have

C_{k−1}(n − 1, k − 1) = C_{k}(n − 1, k − 1) + D_{k−1}(n − 1, k − 2).

Combining with (a), it is enough to show D_{k−1}(n − 1, k − 2) = A_{k−2}(n − 3, k − 2). To this end, note that if π ∈ F_{k}(n − 1; k − 1, i_{1}, …, i_{k−2}, 1) where k + 1 ≤ i_{1} < ⋯ < i_{k−2} ≤ n − 1, then by Lemma 8

f_{k}(n − 1; k − 1, i_{1}, …, i_{k−2}, 1) = f_{k}(n − 3; i_{1} − 2, …, i_{k−2} − 2).

By definitions of D_{d}(n, m) and A_{d}(n, m), we obtain the required equality. □

Proposition 16 Let n ≥ k − 1. The sequences A_{k}, B_{k}, C_{k} and D_{k} satisfy the relations:

(a) A_{k}(n, k) = B_{k}(n − 1, k − 2);

(b) B_{k}(n − 1, k − 2) = D_{k}(n − 1, k − 2) + B_{k}(n − 1, k − 1);

(c) B_{k}(n − 1, k − 1) = B_{k}(n − 2, k − 2);

(d) D_{k}(n − 1, k − 2) = A_{k−2}(n − 4, k − 2) + A_{k−1}(n − 4, k − 2);

(e) A_{k}(n, k) − A_{k}(n − 1, k) = A_{k−2}(n − 4, k − 2) + A_{k−1}(n − 4, k − 2).

Proof For (a), if π ∈ F_{k}(n; i_{1}, i_{2}, …, i_{k}) so that k ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n, then avoidance of 321,

(k + 1)(k + 2)(k + 3) ⋯ (2k − 1)(2k)123 ⋯ k,

and

k(k + 2)(k + 3) ⋯ (2k − 1)(2k)12 ⋯ (k − 1)(k + 1),

implies i_{1} = k and i_{2} = k+1. Since no occurrence of τ ∈ P_{k} in π can contain both entries k and k+1, it follows that f_{k}(n; k, k+1, i_{3}, …, i_{k}) = f_{k}(n−1; k, i_{3}−1, …, i_{k} −1), and hence (a). For (b), if π ∈ F_{k}(n − 1; k, i_{1}, …, i_{k−2}) so that k + 1 ≤ i_{1} < i_{2} < ⋯ < i_{k−2} ≤ n − 1, then by Lemma 8(a)-(b) we get

f_{k}(n − 1; k, i_{1}, …, i_{k−2}) = f_{k}(n − 1; k, i_{1}, …, i_{k−2}, 1) + ∑_{i_{k−1}=i_{k−2}+1}^{n−1} f_{k}(n − 1; k, i_{1}, …, i_{k−1}),

so, if summing over k + 1 ≤ i_{1} < i_{2} < ⋯ < i_{k−2} ≤ n − 1 then by Definition 5 we have (b). For (c), if π ∈ F_{k}(n − 1; k, i_{1}, …, i_{k−1}) where k + 1 ≤ i_{1} < ⋯ < i_{k−1} ≤ n − 1, then avoidance of

321 and k(k + 2)(k + 3) ⋯ (2k − 1)(2k)12 ⋯ (k − 1)(k + 1)

implies again i_{1} = k + 1. As in (a), f_{k}(n − 1; k, k + 1, i_{2}, …, i_{k−1}) = f_{k}(n − 2; k, i_{2} − 1, …, i_{k−1} − 1), and (c) follows. For (d), consider D_{k}(n − 1, k − 2) along with a similar argument to the one in Lemma 8(b):

\begin{aligned}D_{k}(n − 1, k − 2) & = ∑_{k+1≤i_{1}<···<i_{k−2}≤n}f_{k}(n; k, i_{1}, …, i_{k−2}, 1, 2) \\ & + ∑_{k+1≤i_{1}<···<i_{k−1}≤n}f_{k}(n; k, i_{1}, …, i_{k−2}, 1, i_{k−1}), \end{aligned}

Part (d) follows from here as in the proof of (4) and (5). Finally, (a)–(d) yield (e). □

2.4 Proofs of Theorem 5 and Corollary 6

Theorem 17 For k ≥ 3 and s ≥ 1, define L_{n}^{k}(s) = ∑_{j=0}^{s}(−1)^{j}\binom{s−j}{j}f_{k}(n−j). When n ≥ 2k,

this sequence satisfies the linear recursive relation with constant coefficients:

L_{n}^{k}(2k − 2) = L_{n−1}^{k}(2k − 2) + L_{n−3}^{k}(2k − 5) + L_{n−3}^{k}(2k − 4) + L_{n−4}^{k}(2k − 5) + L_{n−4}^{k}(2k − 4).

Proof By (2), A_{k}(n, k − 1) − A_{k}(n, k) = C_{k}(n, k − 1). Replacing n by n − 1 and subtracting yields

(A_{k}(n, k−1)−A_{k}(n, k))−(A_{k}(n−1, k−1)−A_{k}(n−1, k)) = C_{k}(n, k−1)−C_{k}(n−1, k−1),

⇒ A_{k}(n, k−1)−A_{k}(n−1, k−1) = A_{k}(n, k)−A_{k}(n−1, k)+C_{k}(n, k−1)−C_{k}(n−1, k−1). By Proposition 15(b) and Proposition 16(e),

A_{k}(n, k − 1) − A_{k}(n − 1, k − 1) = A_{k−2}(n − 3, k − 2) + A_{k−1}(n − 3, k − 2) (5)
+ A_{k−2}(n − 4, k − 2) + A_{k−1}(n − 4, k − 2).

The result of Corollary 13 completes the proof. □

Corollary 18 For k ≥ 3,

f_{k}(x) = \frac{(1 + 2x^{2} + x^{3})U_{2k−3} (\frac{1}{2\sqrt{x}}) − \sqrt{x}(1 + x)U_{2k−4} (\frac{1}{2\sqrt{x}})}{\sqrt{x} [(1 + 2x^{2} + x^{3})U_{2k−2} (\frac{1}{2\sqrt{x}}) − \sqrt{x}(1 + x)U_{2k−3} (\frac{1}{2\sqrt{x}})]}·

Proof Let 1 ≤ 2k − 5 ≤ s. Since f_{k}(n) = c_{n} = \frac{1}{n+1} \binom{2n}{n} for all n = 0, 1, …, 2k − 1, we have

∑_{n≥2k} L_{n}^{k}(s)x^{n} = ∑_{i=0}^{s}(−x)^{i}\binom{s − i}{i} (f_{k}(x) − ∑_{j=0}^{2k−i−1} x^{j}c_{j}) .

Recall that the Chebyshev polynomials of the second kind satisfy the relation

x^{s/2}U_{s} (\frac{1}{2\sqrt{x}}) = ∑_{i=0}^{s}(−x)^{i}\binom{s − i}{i}

(see [Ri, page 75-76]), while the Catalan numbers satisfy the relation

∑_{i=0}^{l}(−1)^{i}\binom{s − i}{i}c_{l−i} = (−1)^{l}\binom{s − 1 − l}{l}

for all l ≤ s − 1 (see [Ri, page 152-154]), and hence

∑_{i=0}^{s}(−x)^{i}\binom{s − i}{i} ∑_{j=0}^{2k−i−1} x^{j}c_{j} = ∑_{l=0}^{s−1} x^{l} ∑_{i=0}^{l}(−1)^{i}\binom{s − i}{i}c_{l−i} = ∑_{l=0}^{s−1}(−x)^{l}\binom{s − 1 − l}{l}.

Therefore, for 1 ≤ 2k − 5 ≤ s,

∑_{n≥2k} L_{n}^{k}(s)x^{n} = x^{s/2}U_{s} (\frac{1}{2\sqrt{x}}) f_{k}(x) − x^{(s−1)/2}U_{s−1} (\frac{1}{2\sqrt{x}}) .

Finally, the Chebyshev polynomials of the second kind satisfy also the relation

U_{m} (\frac{1}{2\sqrt{x}}) = \frac{1}{\sqrt{x}}U_{m−1} (\frac{1}{2\sqrt{x}}) − U_{m−2} (\frac{1}{2\sqrt{x}})

for all m ≥ 2, hence by Theorem 5 we get the desired result. □

3 Further results

In this section we describe several directions which generalize Theorem 5 by use of the same arguments as in the proofs of Theorem 5 and Corollary 6.

3.1 First generalization

For any 1 ≤ d ≤ k − 2, let X_{k,d}^{1} be the set of all patterns

(d + 1, d + 2, …, k − 1, 1, 2, …, j, k, j + 1, j + 2, …, d)

for j = 0, 1, 2, ..., d, plus the pattern 321. For example, X_{3,1}^{1} = {321, 213, 231}. Denote the number of permutations in S_{n}(321, X_{k,d}^{1}) by x_{k,d}^{1}(n).

Theorem 19 Let k ≥ 3 and 1 ≤ d ≤ k − 2. For all n ≥ k,

∑_{j=0}^{k−1}(−1)^{j}\binom{k − 1 − j}{j}x_{k,d}^{1}(n − j) = \binom{n − d − 1}{k − d − 2},

and for all 0 ≤ n ≤ k − 1, x_{k,d}^{1}(n) = \frac{1}{n+1} \binom{2n}{n}. Thus, the generating function for {x_{k,d}^{1}(n)}_{n≥0} is

∑_{n≥0} x_{k,d}^{1}(n)x^{n} = \frac{U_{k−2} (\frac{1}{2\sqrt{x}}) + \frac{x^{k/2}}{(1−x)^{k−d−1}}}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})} ·

Proof As in Subsection 2.1, we define

A_{s}(n, m) = ∑_{s≤i_{1}<i_{2}<···<i_{m}≤n} f_{k,d}^{1}(n; i_{1}, …, i_{m})

where f_{k,d}^{1}(n; i_{1}, …, i_{m}) is the number of permutations π ∈ S_{n}(321, X_{k,d}^{1}) which start with i_{1}i_{2} ⋯ i_{m}: π_{1}π_{2} ⋯ π_{m} = i_{1}i_{2} ⋯ i_{m}. Using the same arguments in the proof of Lemma 12 and Corollary 13 we obtain that

A_{d+1}(n, k − d − 1) = ∑_{j=0}^{k−1}(−1)^{j}\binom{k − 1 − j}{j}x_{k,d}^{1}(n − j)  (6)

On the other hand, it is easy to verify that

A_{d+1}(n, k − d − 1) = ∑_{d+1≤i_{1}<i_{2}<···<i_{k−d−1}≤n} x_{k,d}^{1}(n; i_{1}, …, i_{k−d−1}, 1).

Since our permutations avoid X_{d,k}^{1}, we set i_{k−d−1} = n. Thus, if π ∈ X_{k,d}^{1}(n; i_{1}, …, i_{k−d−2}, n, 1) with d + 1 ≤ i_{1} < ⋯ < i_{k−d−2} ≤ n − 1, then π_{k−d+1} < ⋯ < π_{n}. This means

A_{d+1}(n, k − d − 1) = \binom{n − d − 1}{k − d − 2}  (7)

Combining (6) and (7) yields the desired recursive relation. The rest of the theorem is easy to derive by use of the same argument as in the proofs of Corollary 6. □

Example 20 For d = 1 and k = 3, Theorem 19 yields

x_{3,1}^{1}(n) − x_{3,1}^{1}(n − 1) = 1, and x_{3,1}^{1}(0) = x_{3,1}^{1}(1) = 1, x_{3,1}^{1}(2) = 2.

Hence, x_{3,1}^{1}(n) = n for all n ≥ 1 (see [SS]). For d = 1, k = 4 and n ≥ 0, Theorem 19 yields

x_{4,1}^{1}(n) = |S_{n}(321, 2341, 2314)| = 2^{n} − n,

while for d = 2, k = 4 and n ≥ 2:

x_{4,2}^{1}(n) = |S_{n}(321, 3412, 3142, 3124)| = 3 · 2^{n−2} − 1.

3.2 Second generalization

Let X_{k,d}^{2} consist of the three patterns 321, (d + 1)(d + 2) ⋯ (k − 1)1k23 ⋯ d, and (d + 1)(d + 2) ⋯ (k − 1)k12 ⋯ d. The number of X_{k,d}^{2}-avoiding permutations in S_{n} is denoted by x_{k,d}^{2}(n).

Theorem 21 Let k ≥ 4 and 2 ≤ d ≤ k − 2. Then for all n ≥ k,

\begin{aligned}∑_{j=0}^{k−1}(−1)^{j}\binom{k−1−j}{j}x_{k,d}^{2}(n − j) & = ∑_{j=0}^{k−1}(−1)^{j}\binom{k−1−j}{j}x_{k,d}^{2}(n − 1 − j) \\ & + ∑_{j=0}^{k−4}(−1)^{j}\binom{k−4−j}{j}x_{k,d}^{2}(n − 3 − j), \end{aligned}

and x_{k,d}^{2}(n) = \frac{1}{n+1} \binom{2n}{n} for all 0 ≤ n ≤ k−1. Thus, the generating function for \{x_{k,d}^{2}(n)\}_{n≥0} is

∑_{n≥0} x_{k,d}^{2}(n)x^{n} = \frac{U_{k−1} (\frac{1}{2\sqrt{x}}) + xU_{k−3} (\frac{1}{2\sqrt{x}})}{\sqrt{x} [U_{k} (\frac{1}{2\sqrt{x}}) + xU_{k−2} (\frac{1}{2\sqrt{x}})]}·

Proof As in Subsection 2.1, we define

A_{s}(n, m) = ∑_{s≤i_{1}<i_{2}<···<i_{m}≤n} f_{k,d}^{2}(n; i_{1}, …, i_{m})

where f_{k,d}^{2}(n; i_{1}, …, i_{m}) is the number of permutations π ∈ S_{n}(321, X_{k,d}^{2}) which start with i_{1}i_{2} ⋯ i_{m}: π_{1}π_{2} ⋯ π_{m} = i_{1}i_{2} ⋯ i_{m}. Using the same arguments as in the proof of Corollary 13 we arrive at

A_{d+1}(n, m) = ∑_{j=0}^{d+m−1}(−1)^{j}\binom{d + m − 1 − j}{j}x_{k,d}^{2}(n − j),

for all m ≤ k − d − 1. On the other hand, the same arguments as in the proof of Proposition 16 yield

A_{d+1}(n, k − d − 1) = A_{d+1}(n − 1, k − d − 1) + A_{d−1}(n − 3, k − d − 2).

Hence,

\begin{aligned}∑_{j=0}^{k−1}(−1)^{j}\binom{k−1−j}{j}x_{k,d}^{2}(n − j) & = ∑_{j=0}^{k−1}(−1)^{j}\binom{k−1−j}{j}x_{k,d}^{2}(n − 1 − j) \\ & + ∑_{j=0}^{k−4}(−1)^{j}\binom{k−4−j}{j}x_{k,d}^{2}(n − 3 − j). \end{aligned}

Now, using the same arguments as in the proof of Corollary 6 we obtain the desired result.

□

Example 22 For d = 2, k = 4 and n ≥ 3, Theorem 21 yields

x_{4,2}^{2}(n) = 3x_{4,2}^{2}(n − 1) − 2x_{4,2}^{2}(n − 2) + x_{4,2}^{2}(n − 3), and x_{4,2}^{2}(0) = x_{4,2}^{2}(1) = 1, x_{4,2}^{2}(2) = 2.

A comparison of Theorem 21 for different cases suggests that there should exist a bijection between the sets S_{n}(X_{k,2}^{2}) and S_{n}(132, X_{k,d}^{2}) for any d such that 2 ≤ d ≤ k − 2. Producing such a bijection remains yet an open question.

3.3 Third generalization

Let X_{k,d}^{3} consist of the two patterns 321 and (d + 1)(d + 2) ⋯ (k − 1)1k23 ⋯ d. The number of X_{k,d}^{3}-avoiding permutations in S_{n} is denoted by x_{k,d}^{3}(n). Similarly as in the argument proofs of the main theorem in [MV3] and Theorem 5, we obtain

Theorem 23 Let k ≥ 4 and 2 ≤ d ≤ k − 2. Then for all n ≥ k,

∑_{i=0}^{k}(−1)^{j}\binom{k − j}{j}x_{k,d}^{3}(n − j) = 0,

and x_{k,d}^{3}(n) = \frac{1}{n+1} \binom{2n}{n} for all 0 ≤ n ≤ k−1. Thus, the generating function for \{x_{k,d}^{3}(n)\}_{n≥0} is

∑_{n≥0} x_{k,d}^{3}(n)x^{n} = \frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})}·

Proof Again, we define

\begin{aligned}A_{s}(n, m) & = ∑_{s≤i_{1}<i_{2}<···<i_{m}≤n} f_{k,d}^{3}(n; i_{1}, …, i_{m}), \\ C_{s}(n, m) & = ∑_{s≤i_{1}<i_{2}<···<i_{m}≤n} f_{k,d}^{3}(n; i_{1}, …, i_{m}, 1) \end{aligned}

where f_{k,d}^{3}(n; j_{1}, …, j_{p}) is the number of permutations π ∈ S_{n}(321, X_{k,d}^{3}) which start with j_{1}j_{2} ⋯ j_{p}: π_{1}π_{2} ⋯ π_{p} = j_{1}j_{2} ⋯ j_{p}. Using the same arguments as in the proof of Proposition 16 we obtain

A_{d+1}(n, m) − A_{d+1}(n, m + 1) = C_{d+1}(n, m) and C_{d+1}(n, m) = C_{d}(n − 1, m),

for all m ≥ k − d − 1. So, for all m ≥ k − d − 1:

A_{d+1}(n, m) − A_{d+1}(n, m + 1) = A_{d}(n − 1, m) − A_{d}(n − 1, m + 1).

Adding over all m ≥ k − d − 1 yields

A_{d+1}(n, k − d − 1) = A_{d}(n − 1, k − d − 1).

On the other hand, using the same arguments as in the proof of Corollary 13 we arrive at

A_{d+1}(n, m) = ∑_{j=0}^{d+m−1}(−1)^{j}\binom{d + m − 1 − j}{j}x_{k,d}^{2}(n − j),

for all m ≤ k − d − 1. Hence,

∑_{j=0}^{k−1}(−1)^{j}\binom{k − 1 − j}{j}x_{k,d}^{3}(n − j) = ∑_{j=0}^{k−2}(−1)^{j}\binom{k − 2 − j}{j}x_{k,d}^{3}(n − 1 − j),

or equivalently,

∑_{j=0}^{k}(−1)^{j}\binom{k − j}{j}x_{k,d}^{3}(n − j) = 0.

Now, using the same arguments as in the proof of Corollary 6 we obtain the desired result. □

Again, finding a direct bijection between the sets S_{n}(X_{k,d}^{3}) and S_{n}(132, (d+1) ⋯ k1 ⋯ d) for any k ≥ 4 and 2 ≤ d ≤ k − 2 is, as of now, an open question.

Acknowledgments. The authors are grateful to the referees for the careful reading of the manuscript and to M. Atkinson for his remarks. The final version of the paper was written during the first author’s (T.M.) stay at Chalmers University of Technology in Göteborg, Sweden. T.M. want to express his gratitude to Chalmers University of Technology for the support.

References

[BaWe] E. Babson and J. West, The permutations 123p_{4} … p_{t} and 321p_{4} … p_{t} are Wilfequivalent, Graphs Comb. 16 (2000) 373–380.

[BWX] E. Babson, J. West, and G. Xin, Wilf–equivalence for singelton classes, in Proc. 13th Conf. in Formal Power Series and Algebraic Combinatorics, Tempe 2001.

[Bo1] M. Bóna, The permutation classes equinumerous to the smooth class, Electron. J. Combin. 5 (1998) #R31.

[Bo2] M. Bóna, The solution of a conjecture of Stanley and Wilf for all layered patterns, J. Combin. Theory Ser. A, 85 (1999) 96–104.

[BW] S. C. Billey and G. S. Warrington, Kazhdan-lusztig polynomials for 321-hexagon-avoiding permutations,

[CW] T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discr. Math. 204 (1999) 119–128.

[Kn] D.E. Knuth, The Art of Computer Programming, 2nd ed. Addison Wesley, Reading, MA (1973).

[Km] D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discr. Math. 218 (2000) 121–130.

[Kr] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Applied Math. 27 (2001) 510–530.

[MV1] T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials Electron. J. Combin. 7 (2000) #R17.

[MV2] T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 126 (2001) 258–269.

[MV3] T. Mansour and A. Vainshtein, Layered restrictions and Chebychev polynomials (2000), Annals of Combinatorics 5 (2001) 451–458.

[MV4] T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Séminaire Lotharingien de Combinatoire 47 (2002) Article B47c.

[R] A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Mathematics and Theoretical Computer Science, 3 (1999) 151–154.

[Ri] Th. Rivlin, Chebyshev polynomials. From approximation theory to algebra and number theory, John Wiley, New York (1990).

[RWZ] A. Robertson, H. Wilf, and D. Zeilberger, Permutation patterns and continuous fractions, Electron. J. Combin. 6 (1999) #R38.

[SS] R. Simion, F.W. Schmidt, Restricted Permutations, Europ. J. of Combinatorics 6 (1985) 383–406.

[S] Z. Stankova, Classification of forbidden subsequences of length 4, Europ. J. Comb. 17 (1996) 501–517.

[SW1] Z. Stankova and J. West, Explicit enumeration of 321-hexagon-avoiding permutations, Disc. Math., to appear.

[SW2] Z. Stankova and J. West, A new class of Wilf–equivalent Permutations, J. Alg. Comb. 15 (2002) 271–290.

[W] J. West, Generating trees and forbidden subsequences, Discr. Math. 157 (1996) 363–372.