RESTRICTED PERMUTATIONS, CONTINUED

FRACTIONS, AND CHEBYSHEV POLYNOMIALS

Toufik Mansour^{∗} and Alek Vainshtein^{†}

∗ Department of Mathematics

† Department of Mathematics and Department of Computer Science

University of Haifa, Haifa, Israel 31905

     tmansur@study.haifa.ac.il, alek@mathcs.haifa.ac.il

Submitted: December 21, 1999; Accepted: February 27, 2000.

Abstract. Let f_{n}^{r}(k) be the number of 132-avoiding permutations on n letters that contain exactly r occurrences of 12 … k, and let F_{r}(x; k) and F (x, y; k) be the generating functions defined by F_{r}(x; k) = ∑_{n⩾0} f_{n}^{r}(k)x^{n} and F (x, y; k) = ∑_{r⩾0} F_{r}(x; k)y^{r}. We find an explicit expression for F (x, y; k) in the form of a continued fraction. This allows us to express F_{r}(x; k) for 1 ⩽ r ⩽ k via Chebyshev polynomials of the second kind.

2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 30B70, 42C05

Typeset by AMS-TEX

1. Introduction

Let [p] = {1, …, p} denote a totally ordered alphabet on p letters, and let α = (α_{1}, …, α_{m}) ∈ [p_{1}]^{m}, β = (β_{1}, …, β_{m}) ∈ [p_{2}]^{m}. We say that α is order-isomorphic to β if for all 1 ⩽ i < j ⩽ m one has α_{i} < α_{j} if and only if β_{i} < β_{j}. For two permutations π ∈ 𝔖_{n} and τ ∈ 𝔖_{k}, an occurrence of τ in π is 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 the pattern. We say that π avoids τ, or is τ-avoiding, if there is no occurrence of τ in π. The set of all τ-avoiding permutations of all possible sizes including the empty permutation is denoted 𝔖(τ). Pattern avoidance proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting [5] to singularities of Schubert varieties [6]. A complete study of pattern avoidance for the case τ ∈ 𝔖_{3} is carried out in [11]. For the case τ ∈ 𝔖_{4} see [14, 11, 12, 1].

A natural generalization of pattern avoidance is the restricted pattern inclusion, when a prescribed number of occurrences of τ in π is required. Papers [8] and [3] contain simple expressions for the number of permutations containing exactly one 123 and 132 patterns, respectively. The main result of [B2] is that the generating function for the number of permutations containing exactly r 132 patterns is a rational function in variables x and \sqrt{1 − 4x}. This proves a particular case of the general conjecture of Noonan and Zeilberger [9] which is that for any set T of patterns, the sequence of numbers enumerating permutations having a prescribed number of occurrences of patterns in T is P -recursive. Recent paper [10] presents the generating function for the number of 132-avoiding permutations that contain a prescribed number of 123 patterns. The generating function is given in the form of a continued fraction. In the present note we generalize the argument of [10] to get the generating function for the number of 132-avoiding permutations that contain a prescribed number of 12 … k patterns for arbitrary k ⩾ 3. The study of the obtained continued fraction allows us to recover and to generalize the result of [4] that relates the number of 132-avoiding permutations that contain no 12 … k patterns to Chebyshev polynomials of the second kind.

The authors are grateful to C. Krattenthaler, H. Wilf, and anonymous referee for useful comments concerning Theorems 4.1 and 4.2.

2. Continued fractions

Let f_{n}^{r}(k) stand for the number of 132-avoiding permutations on n letters that contain exactly r occurrences of 12 … k. We denote by F (x, y; k) the generating function of the sequence {f_{n}^{r}(k}), that is,

F (x, y; k) = ∑_{n⩾0} ∑_{r⩾0} f_{n}^{r}(k)x^{n}y^{r}.

Our first result is a natural generalization of the main theorem of [10].

Theorem 2.1. The generating function F (x, y; k) for k ⩾ 1 is given by the continued fraction

F (x, y; k) = \frac{1}{1 − \frac{xy^{d_{1}}}{1 − \frac{xy^{d_{2}}}{1 − \frac{xy^{d_{3}}}{…}}}} ,

where d_{i} = \binom{i−1}{k−1}, and \binom{a}{b} is assumed 0 whenever a < b or b < 0.

Proof. Following [10] we define η_{j}(π), j ⩾ 1, as the number of occurrences of 12 … j in π. Define η_{0}(π) = 1 for any π, which means that the empty pattern occurs exactly once in each permutation. The weight of a permutation π is a monomial in k independent variables q_{1}, …, q_{k} defined by

w_{k}(π) = ∏_{j=1}^{k} q_{j}^{η_{j}(π)}.

The total weight is a polynomial

W_{k}(q_{1}, …, q_{k}) = ∑_{π∈𝔖(132)} w_{k}(π).

The following proposition is implied immediately by the definitions.

Proposition 2.1. F (x, y; k) = W_{k}(x, 1, …, 1, y) for k ⩾ 2, and F (x, y; 1) = W_{1}(xy).

We now find a recurrence relation for the numbers η_{j}(π). Let π ∈ 𝔖_{n}, so that π = (π′, n, π′′).

Proposition 2.2. For any j ⩾ 1 and any nonempty π ∈ 𝔖(132)

η_{j}(π) = η_{j}(π′) + η_{j}(π′′) + η_{j−1}(π′).

Proof. Let l = π^{−1}(n). Since π avoids 132, each number in π′ is greater than any of the numbers in π′′. Therefore, π′ is a 132-avoiding permutation of the numbers {n−l+1, n−l+2, …, n−1}, while π′′ is a 132-avoiding permutation of the numbers {1, 2, …, n − l}. On the other hand, if π′ is an arbitrary 132-avoiding permutation of the numbers {n − l + 1, n − l + 2, …, n − 1} and π′′ is an arbitrary 132-avoiding permutation of the numbers {1, 2, …, n − l}, then π = (π′, n, π′′) is 132-avoiding. Finally, if (i_{1}, …, i_{j}) is an occurrence of 12 … j in π then either i_{j} < l, and so it is also an occurrence of 12 … j in π′, or i_{1} > l, and so it is also an occurrence of 12 … j in π′′, or i_{j} = l, and so (i_{1}, …, i_{j−1}) is an occurrence of 12 … j − 1 in π′. The result follows. □

Now we are able to find the recurrence relation for the total weight W. Indeed, by Proposition 2.2,

W_{k}(q_{1}, …, q_{k}) = 1 + ∑_{∅≠π∈𝔖(132)} ∏_{j=1}^{k} q_{j}^{η_{j}(π′)+η_{j}(π′′)+η_{j−1}(π′)}

= 1 + ∑_{π′∈𝔖(132)} ∑_{π′′∈𝔖(132)} ∏_{j=1}^{k} q_{j}^{η_{j}(π′′)} · q_{1} ∏_{j=1}^{k−1}(q_{j}q_{j+1})^{η_{j}(π′)} · q_{k}^{η_{k}(π′)}

= 1 + q_{1}W_{k}(q_{1}, …, q_{k})W_{k}(q_{1}q_{2}, q_{2}q_{3}, …, q_{k−1}q_{k}, q_{k}).  (1)

For any d ⩾ 0 and 1 ⩽ m ⩽ k define

q^{d,m} = ∏_{j=1}^{k} q\binom{d}{j−m}_{j};

recall that \binom{a}{b} = 0 if a < b or b < 0. The following proposition is implied immediately by the well-known properties of binomial coefficients.

Proposition 2.3. For any d ⩾ 0 and 1 ⩽ m ⩽ k

q^{d,m}q^{d,m+1} = q^{d+1,m}.

Observe now that W_{k}(q_{1}, …, q_{k}) = W_{k}(q^{0,1}, …, q^{0,k}) and that by (1) and Proposition 2.3

W_{k}(q^{d,1}, …, q^{d,k}) = 1 + q^{d,1}W_{k}(q^{d,1}, …, q^{d,k})W_{k}(q^{d+1,1}, …, q^{d+1,k}),

therefore

W_{k}(q_{1}, …, q_{k}) = \frac{1}{1 − \frac{q^{0,1}}{1 − \frac{q^{1,1}}{1 − \frac{q^{2,1}}{…}}}} .

To obtain the continued fraction representation for F (x, y; k) it is enough to use Proposition 2.1 and to observe that

q^{d,1}|_{q_{1}=x,q_{2}=···=q_{k−1}=1,q_{k}=y} = xy^{\binom{d}{k−1}}. □

Remark. For k = 1 one recovers from Theorem 2.1 the well-known generating function for the Catalan numbers, (1 − \sqrt{1 − 4z})/2z. This result also follows immediately from Proposition 2.1 and equation (1), which for k = 1 is reduced to W_{1}(q) = 1 + qW_{1}^{2}(q).

3. Chebyshev polynomials

Let us denote by F_{r}(x; k) the generating function of the sequence {f_{n}^{r}(k)} for a given r, that is,

F_{r}(x; k) = ∑_{n⩾0} f_{n}^{r}(k)x^{n}.

Recall that F (x, y; k) = ∑_{r⩾0} F_{r}(x; k)y^{r}. In this section we find explicit expressions for F_{r}(x; k) in the case 0 ⩽ r ⩽ k.

Consider a recurrence relation

T_{j} = \frac{1}{1 − xT_{j−1}} , j ⩾ 1.  (2)

The solution of (2) with the initial condition T_{0} = 0 is denoted by R_{j}(x), and the solution of (2) with the initial condition

T_{0} = G(x, y; k) = \frac{y}{1 − \frac{xy^{\binom{k}{1}}}{1 − \frac{xy^{\binom{k+1}{2}}}{1 − \frac{xy^{\binom{k+2}{3}}}{…}}}}

is denoted by S_{j}(x, y; k), or just S_{j} when the value of k is clear from the context. Our interest in (2) is stipulated by the following relation, which is an easy consequence of Theorem 2.1:

F (x, y; k) = S_{k}(x, y; k).  (3)

First of all, we find an explicit formula for the functions R_{j}(x). Let U_{j}(cos θ) = sin(j + 1)θ/ sin θ be the Chebyshev polynomials of the second kind.

Lemma 3.1. For any j ⩾ 1

R_{j}(x) = \frac{U_{j−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{j} (\frac{1}{2\sqrt{x}})}.  (4)

Proof. Indeed, it follows immediately from (2) that R_{j}(x) is the jth approximant for the continued fraction

\frac{1}{1 − \frac{x}{1 − \frac{x}{1 − \frac{x}{…}}}} .

Hence, by [7, Theorem 2, p. 194], for any j ⩾ 1 one has R_{j}(x) = A_{j}(x)/A_{j+1}(x), where

A_{j}(x) = (\frac{1 + \sqrt{1 − 4x}}{2})^{j} − (\frac{1 − \sqrt{1 − 4x}}{2})^{j} .

Using substitution x → 1/4t^{2} one gets (2t)^{j}A_{j}(1/4t^{2}) = 2\sqrt{t^{2} − 1}U_{j−1}(t), which gives A_{j}(x) = \sqrt{1/x − 4} x^{j/2}U_{j−1}(1/2\sqrt{x}), and the result follows. □

Next, we find an explicit expression for S_{j} in terms of G and R_{j}.

Lemma 3.2. For any j ⩾ 1 and any k ⩾ 1

S_{j}(x, y; k) = R_{j}(x)\frac{1 − xR_{j−1}(x)G(x, y; k)}{1 − xR_{j}(x)G(x, y; k)}.  (5)

Proof. Indeed, from (2) and S_{0} = G we get S_{1} = 1/(1 − xG). On the other hand, R_{0} = 0, R_{1} = 1, so (5) holds for j = 1. Now let j > 1, then by induction

S_{j} = \frac{1}{1 − xS_{j−1}} = \frac{1}{1 − xR_{j−1}} · \frac{1 − xR_{j−1}G}{1 − \frac{x(1 − xR_{j−2})R_{j−1}G}{1 − xR_{j−1}}} .

Relation (2) for R_{j} and R_{j−1} yields (1 − xR_{j−2})R_{j−1} = (1 − xR_{j−1})R_{j} = 1, which together with the above formula gives (5). □

As a corollary from Lemma 3.2 and (3) we get the following expression for the generating function F (x, y; k).

Corollary.

F (x, y; k) = R_{k}(x) + (R_{k}(x) − R_{k−1}(x)) ∑_{m⩾1} (xR_{k}(x)G(x, y; k))^{m}.

Now we are ready to express the generating functions F_{r}(x; k), 0 ⩽ r ⩽ k, via Chebyshev polynomials.

Theorem 3.1. For any k ⩾ 1, F_{r}(x; k) is a rational function given by

F_{r}(x; k) = \frac{x^{\frac{r−1}{2}} U_{k−1}^{r−1} (\frac{1}{2\sqrt{x}})}{U_{k}^{r+1} (\frac{1}{2\sqrt{x}})}, 1 ⩽ r ⩽ k,

F_{0}(x; k) = \frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})},

where U_{j} is the jth Chebyshev polynomial of the second kind.

Proof. Observe that G(x, y; k) = y + y^{k+1}P (x, y), so from Corollary we get

F (x, y; k) = R_{k}(x) + (R_{k}(x) − R_{k−1}(x)) ∑_{m=1}^{k} (xR_{k}(x))^{m}y^{m} + y^{k+1}P′(x, y),

where P (x, y) and P′(x, y) are formal power series. To complete the proof, it suffices to use (4) together with the identity U_{n−1}^{2}(z) − U_{n}(z)U_{n−2}(z) = 1, which follows easily from the trigonometric identity sin^{2} nθ − sin^{2} θ = sin(n + 1)θ sin(n − 1)θ. □

For the case r = 0 this result was proved by a different method in [4].

4. Further results

There are several ways to generalize the results of the previous sections. First, one can try to get exact formulas for F_{r}(x; k) in the case r > k. The method described in Section 3 allows, in principle, to obtain such formulas, though they become more and more complicated. For example, the following theorem gives an explicit expression for F_{r}(x; k) when r ⩽ k(k + 3)/2.

Theorem 4.1. For any k ⩾ 1 and 1 ⩽ r ⩽ k(k + 3)/2, F_{r}(x; k) is a rational function given by

F_{r}(x; k) = \frac{x^{\frac{r−1}{2}} U_{k−1}^{r−1} (\frac{1}{2\sqrt{x}})}{U_{k}^{r+1} (\frac{1}{2\sqrt{x}})} ∑_{j=0}^{⌊(r−1)/k⌋} \binom{r − kj + j − 1}{j} (\frac{U_{k} (\frac{1}{2\sqrt{x}})}{x^{\frac{k−2}{2k}} U_{k−1} (\frac{1}{2\sqrt{x}})})^{kj} ,

where U_{j} is the jth Chebyshev polynomial of the second kind.

Proof. Indeed, the explicit expression for G(x, y; k) gives

G(x, y; k) = y(1 + xy^{k} + ⋯ + x^{s}y^{ks}) + y^{t}P (x, y),

where s = ⌈(k + 1)/2⌉, t = 1 + k(k + 3)/2, and P (x, y) is a formal power series. Hence, by Corollary,

\frac{F (x, y; k) − R_{k}(x)}{R_{k}(x) − R_{k−1}(x)} = ∑_{m⩾1} (xR_{k}(x))^{m}y^{m}(1 + xy^{k} + ⋯ + x^{s}y^{ks})^{m} + y^{t}P′(x, y)

= ∑_{m⩾1} (xR_{k}(x))^{m}y^{m} ∑_{j=0}^{ms} \binom{m + j − 1}{j}x^{j}y^{kj} + y^{t}P′(x, y)

= ∑_{r⩾1} y^{r}(xR_{k}(x))^{r} ∑_{j=0}^{⌊(r−1)/k⌋} \frac{\binom{r−kj+j−1}{j}x^{j}}{(xR_{k}(x))^{kj}} + y^{t}P′′(x, y),

where P′(x, y) and P′′(x, y) are formal power series. The rest of the proof follows the proof of Theorem 3.1. □

Another possibility is to analyze the case of permutations containing exactly one 132 pattern and r 12 … k patterns. Introducing the modified total weight Ω_{k}(q_{1}, …, q_{k}) as the sum of the weights w_{k}(π) over all permutations containing exactly one 132 pattern, we get the following equation:

Ω_{k}(q_{1}, …, q_{k}) = q_{1}W_{k}(q_{1}q_{2}, …, q_{k−1}q_{k}, q_{k})Ω_{k}(q_{1}, …, q_{k})
+ q_{1}W_{k}(q_{1}, …, q_{k})Ω_{k}(q_{1}q_{2}, …, q_{k−1}q_{k}, q_{k})
+ q_{1}^{2}q_{2}^{2}W_{k}(q_{1}q_{2}, …, q_{k−1}q_{k}, q_{k})(W_{k}(q_{1}, …, q_{k}) − 1);

for the case k = 3 see [10]. By (1) and Proposition 2.3 this is equivalent to

Ω_{k}(q^{d,1}, …, q^{d,k}) = q^{d,1} (q^{d,2})^{2} (W_{k}(q^{d,1}, …, q^{d,k}) − 1)^{2}
+ q^{d,1}W_{k}^{2}(q^{d,1}, …, q^{d,k})Ω_{k}(q^{d+1,1}, …, q^{d+1,k}).

(6)

Let now φ_{n}^{r}(k) be the number of permutations on n letters that contain exactly one 132 pattern and r 12 … k patterns, and Φ_{r}(x; k) be the generating function of the sequence {φ_{n}^{r}(k)} for a given r. In general, equation (6) allows us to find explicit expressions for Φ_{r}(x; k). However, they are rather cumbersome, so we restrict ourselves to the case r = 0.

Theorem 4.2. For any k ⩾ 3, Φ_{0}(x; k) is a rational function given by

Φ_{0}(x; k) = \frac{x}{U_{k}^{2} (\frac{1}{2\sqrt{x}})} ∑_{j=1}^{k−2} U_{j}^{2} (\frac{1}{2\sqrt{x}})

= \frac{1}{16 sin^{2}(k + 1)t cos^{2} t} (2k − 5 + 4 cos^{2} t − \frac{sin(2k − 1)t}{sin t}) ,

where U_{j} is the jth Chebyshev polynomial of the second kind and cos t = 1/2\sqrt{x}.

References

1. M. Bona, Permutations avoiding certain patterns: the case of length 4 and some generalizations, Discr. Math. 175 (1997), 55–67.

2. M. Bona, The number of permutations with exactly r 132-subsequences is P -recursive in the size!, Adv. Appl. Math. 18 (1997), 510–522.

3. M. Bona, Permutations with one or two 132-subsequences, Discr. Math. 181 (1998), 267–274.

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

5. D. Knuth, The Art of Computer Programming, vol. 3, Addison Wesley, Reading, MA, 1973.

6. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)/B, Proc. Indian Acad. Sci. 100 (1990), no. 1, 45–52.

7. L. Lorentzen and H. Waadeland, Continued fractions with applications, North-Holland, 1992.

8. J. Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discr. Math. 152 (1996), 307–313.

9. J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of “forbidden” patterns, Adv. Appl. Math. 17 (1996), 381–407.

10. A. Robertson, H. Wilf, and D. Zeilberger, Permutation patterns and continuous fractions, Elec. J. Comb. 6 (1999), no. 1, R38.

11. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Comb. 6 (1985), 383-406.

12. Z. Stankova, Classification of forbidden subsequences of length 4, Eur. J. Comb. 17 (1996), 501–517.

13. Z. Stankova, Forbidden subsequences, Discr. Math. 132 (1994), 291–316.

14. J. West, Generating trees and the Catalan and Schröder numbers, Discr. Math. 146 (1995), 247–262.