Permutation Patterns and Continued Fractions

Aaron Robertson Colgate University, Hamilton, NY 13346

              <aaron@math.colgate.edu>

Herbert S. Wilf

University of Pennsylvania, Philadelphia, PA 19104-6395

               <wilf@math.upenn.edu>

Doron Zeilberger Temple University, Philadelphia, PA 19122

          <zeilberg@euclid.math.temple.edu>

Abstract

We find, in the form of a continued fraction, the generating function for the number of (132)-avoiding permutations that have a given number of (123) patterns, and show how to extend this to permutations that have exactly one (132) pattern. We also find some properties of the continued fraction, which is similar to, though more general than, those that were studied by Ramanujan.

A (132) pattern (resp. a (123) pattern) in a permutation π of |π| letters is a triple 1 ≤ i < j < k ≤ n of indices for which π(i) < π(k) < π(j) (resp. π(i) < π(j) < π(k)). Let f_{r}(n) denote the number of permutations π of n letters that have no (132) patterns and exactly r (123) patterns. Our main result is the following.

Theorem 1 The generating function for the {f_{r}(n)} is

∑_{r,n≥0} f_{r}(n)z^{n}q^{r} = \frac{1}{1 − \frac{z}{1 − \frac{z}{1 − \frac{zq}{1 − \frac{zq^{3}}{1 − \frac{zq^{6}}{…}}}}}}  (1)

in which the nth numerator is zq^{\binom{n−1}{2}}.

We think it is remarkable that such a continued fraction encodes information about (132)-avoiding permutations. We will first prove the theorem, and then study some consequences and generalizations.

1 The patterns

Let the weight of a permutation π of |π| letters be z^{|π|}q^{|123(π)|}t^{|12(π)|}, in which |123(π)| is the number of (123) patterns (rising triples) in π, and |12(π)| is the number of rising pairs in π. Let

P (q, z, t) = ∑′_{π}weight(π),  (2)

where the sum extends over all (132)-avoiding permutations π.

If π is a (132)-avoiding permutation on {1, 2, …, n}, (n > 0) and the largest element, n, is at the kth position, i.e., π(k) = n, then by letting π_{1} := {π(i)}_{1}^{k−1} and π_{2} := {π(i)}_{k+1}^{n}, we have that every element in π_{1} must be larger than every element of π_{2}, or else a (132) would be formed, with the n serving as the ‘3’ of the (132). Hence, π_{1} is a permutation of the set {n − k + 1, …, n − 1}, and π_{2} is a permutation of the set {1, …, n − k}. Furthermore, π_{1} and π_{2} are each (132)-avoiding. Conversely, if π_{1} and π_{2} are (132)-avoiding permutations on {n−k +1, …, n−1} and {1, …, n−k} respectively (for some k, 1 ≤ k ≤ n), then (π_{1}nπ_{2}) is a nonempty (132)-avoiding permutation.

Thus we have

|123(π)| = |123(π_{1})| + |123(π_{2})| + |12(π_{1})|,

since a (123) pattern in π =^{def} (π_{1}nπ_{2}) may either be totally immersed in the π_{1} part, or wholly immersed in the π_{2} part, or may be due to the n serving as the ‘3’ of the (123), the number of which is the number of (12) patterns in π_{1}.

We also have

|12(π)| = |12(π_{1})| + |12(π_{2})| + |π_{1}|,

and, of course

|π| = |π_{1}| + |π_{2}| + 1.

Hence,

weight(π)(q, z, t) := q^{|123(π)|}z^{|π|}t^{|12(π)|}
= q^{|123(π_{1})|+|123(π_{2})|+|12(π_{1})|}z^{|π_{1}|+|π_{2}|+1}t^{|12(π_{1})|+|12(π_{2})|+|π_{1}|}
= zq^{|123(π_{1})|}(qt)^{|12(π_{1})|}(zt)^{|π_{1}|}q^{|123(π_{2})|}t^{|12(π_{2})|}z^{|π_{2}|}
= z weight(π_{1})(q, zt, tq) weight(π_{2})(q, z, t).

Now sum over all possible (132)-avoiding permutations π, to get the functional equation

P (q, z, t) = 1 + zP (q, zt, tq)P (q, z, t),  (3)

in which the 1 corresponds to the empty permutation.

Next let Q(q, z, t) be the sum of all the weights of all permutations with exactly one (132) pattern. By adapting the argument from Miklós Bóna’s paper [1] we easily see that Q(q, z, t) satisfies

Q(q, z, t) = zP (q, zt, qt)Q(q, z, t) + zQ(q, zt, qt)P (q, z, t) + t^{2}z^{2}P (q, zt, qt)(P (q, z, t) − 1).

(4)

This holds since our sole (132) pattern can either appear in the elements

(a) before n,

(b) after n, or

(c) with n as the ‘3’ in the (132) pattern.

The term zP (q, zt, qt)Q(q, z, t) corresponds to (a), zQ(q, zt, qt)P (q, z, t) corresponds to (b), and t^{2}z^{2}P (q, zt, qt)(P (q, z, t) − 1) corresponds to (c). We see that case (c) follows since π = (π_{1}, n − k, n, π_{2}), where π_{1} is a permutation of [n − k + 2, …, n − 1], π_{2} is a permutation of [1, …, n − k − 1] ∪ {n − k + 1}, and k ≠ n.

2 The fractions

Here we study this generating function P (q, z, t) further, finding that it is a pretty continued fraction, and deriving a fairly explicit form for its numerator and denominator.

First, from (3) we have that

P (q, z, t) = \frac{1}{1 − zP (q, zt, tq)},  (5)

the electronic journal of combinatorics 6 (1999), #R38 4 and so by iteration we have the continued fraction,

P (q, z, t) = \frac{1}{1 − \frac{z}{1 − \frac{zt}{1 − \frac{zt^{2}q}{1 − \frac{zt^{3}q^{3}}{1 − \frac{zt^{4}q^{6}}{…}}}}}} .  (6)

Now let

P (q, z, t) = \frac{A(q, z, t)}{B(q, z, t)}.

Then substitution in (5) shows that A(q, z, t) = B(q, zt, tq), and therefore

P (q, z, t) = \frac{B(q, zt, tq)}{B(q, z, t)},  (7)

where B satisfies the functional equation

B(q, z, t) = B(q, zt, tq) − zB(q, t^{2}qz, tq^{2}).  (8)

To find out more about the form of B we write

B(q, z, t) = ∑_{m≥0} ϕ_{m}(q, t)z^{m}.

Then ϕ_{0} = 1, and

ϕ_{m}(q, t) = t^{m}ϕ_{m}(q, qt) − t^{2m−2}q^{m−1}ϕ_{m−1}(q, tq^{2}),

for m = 1, 2, 3, . . .. It is easy to see by induction that

ϕ_{m}(q, t) = − ∑_{j≥2} t^{jm−2}q^{m\binom{j}{2}−2j+3}ϕ_{m−1}(q, tq^{j}). (m ≥ 1; ϕ_{0} = 1)

For example, we have

ϕ_{1}(q, t) = − ∑_{j≥0} t^{j}q^{\binom{j}{2}},

and

ϕ_{2}(q, t) = ∑_{j,ℓ≥2} t^{ℓ+2j−4}q^{\frac{1}{2} ℓ^{2}+j^{2}+ℓj− \frac{5}{2} ℓ−5j+6}.

In general, the exponent of t in ϕ_{m}(q, t) will be a linear form in the m summation indices, plus a constant, and the exponent of q will be an affine form in these indices, i.e., a quadratic form plus a linear form plus a constant. Let’s find all of these forms explicitly.

Hence suppose in general that

ϕ_{m}(t) = (−1)^{m} ∑_{j≥0} t^{a_{m}·j+b_{m}}q^{(j,Q_{m}j)+c_{m}·j+d_{m}},

in which j is the m-vector of summation indices, Q_{m} is a real symmetric m × m matrix to be determined, a_{m}, c_{m} are m-vectors, and b_{m}, d_{m} are scalars. Inductively we find that

a_{m} = {r}_{r=1}^{m},
b_{m} = −2m,
c_{m} = {−5r/2}_{r=1}^{m} ,
d_{m} = 3m.

The m × m matrix Q_{m} is {min (r, s)/2}_{r,s=1}^{m}. Thus we have the following formula for B.

Theorem 2 The denominator B(q, z, t) of the grand generating function P (q, z, t) is explicitly given by

B(q, z, t) = 1 + ∑_{m=1}^{∞}(−zq^{3}t^{−2})^{m} ∑_{j_{1},...,j_{m}≥2} t^{∑_{r=1}^{m} rj_{r}}q^{^{\frac{1}{2}}\{∑_{r,s=1}^{m} min (r,s)j_{r}j_{s}−5 ∑_{r=1}^{m} rj_{r}\}}. (9)

3 The series computations

If f_{r}(n) denotes the number of permutations of n letters that contain no pattern (132) and have exactly r (123)’s, we write A_{1}(r, z) := ∑_{n} f_{r}(n)z^{n}. Then A_{1}(r, z) is the coefficient of q^{r} in the series development of P (q, z, 1) of (2). That is, we have

\frac{1}{1 − \frac{z}{1 − \frac{z}{1 − \frac{zq}{1 − \frac{zq^{3}}{1 − \frac{zq^{6}}{…}}}}}} = ∑_{r≥0} A_{1}(r, z)q^{r}.  (10)

From (10) we see that if we terminate the fraction P (q, z, 1) at the numerator q^{N}, say, then we’ll know all of the {A_{1}(r, z)}_{r=0}^{N} exactly.

Further, if we know the denominator B(q, z, t) in (7) exactly through terms of order q^{N}, then by carrying out the division in (7) and keeping the same accuracy, we will, after setting t = 1, again obtain all of the generating functions {A_{1}(r, z)}_{r=0}^{N} exactly.

Finally, to find the denominator B(q, z, t) in (7) exactly through terms of order q^{N}, it is sufficient to carry out the iteration that is implicit in (8) N times, since further iteration will affect only the terms involving powers of q higher than the Nth.

In that way we computed the A_{1}(r, z)’s for 0 ≤ r ≤ 15 in a few seconds, as is shown below in the initial section of the series (10):

\frac{1−z}{1−2 z} + \frac{z^{3}}{(1−2 z)^{2}} q + \begin{matrix}(1−z) & z^{4} \\ (1−2 z) & ^{3} \end{matrix} q^{2} + \begin{matrix}(1−z)^{2} & z^{5} \\ (1−2 z) & ^{4} \end{matrix} q^{3} + \begin{matrix}z^{4} & (−1+6 z−13 z^{2}+11 z^{3}−3 z^{4}+z^{5}) \\ (−1+2 z) & ^{5} \end{matrix}q^{4}

+ \begin{matrix}z^{5} & (2−14 z+37 z^{2}−44 z^{3}+22 z^{4}−4 z^{5}+z^{6}) \\ (1−2 z) & ^{6} \end{matrix}q^{5} + \begin{matrix}(1−z)^{2} & z^{6} & (−3+18 z−37 z^{2}+27 z^{3}−3 z^{4}+z^{5}) \\ (−1+2 z) & ^{7} \end{matrix}q^{6}

+ \begin{matrix}z^{5} & (1−12 z+64 z^{2}−196 z^{3}+373 z^{4}−450 z^{5}+343 z^{6}−164 z^{7}+47 z^{8}−6 z^{9}+z^{10}) \\ (1−2 z) & ^{8} \end{matrix}q^{7} + …

If g_{r}(n) denotes the number of permutations of n letters that contain one (132) pattern and have exactly r (123)’s, we write A_{2}(r, z) := ∑_{n} g_{r}(n)z^{n}. Then A_{2}(r, z) is the coefficient of q^{r} in the series development of Q(q, z, 1) of (4). Since we have a very quick method to compute P (q, z, 1), we can iterate equation (4) to compute the A_{2}(r, z)’s. Shown below are the A_{2}(r, z)’s for 0 ≤ r ≤ 6, that were computed in a few minutes.

\frac{z^{3}}{(1−2z)^{2}} + \frac{2z^{5}}{(1−2z)^{3}} q + \frac{z^{4}(z^{3}−6z^{2}+4z−1)}{(1−2z)^{4}}q^{2} + \frac{2z^{5}(z−1)(5z^{2}−4z+1)}{(1−2z)^{5}}q^{3}
+ \frac{z^{6}(z^{5}+12z^{4}−55z^{3}+65z^{2}−30z+5)}{(1−2z)^{6}}q^{4} + \frac{−2z^{7}(z^{6}+6z^{5}−40z^{4}+80z^{3}−69z^{2}+27z−4)}{(1−2z)^{7}}q^{5}
+ \frac{−z^{6}(z−1)(3z^{8}+13z^{7}−77z^{6}+240z^{5}−329z^{4}+231z^{3}−91z^{2}+20z−2)}{(1−2z)^{8}}q^{6} + ….

References

[1] Miklós Bóna, Permutations with one or two 132-subsequences. Discrete Math. 181 (1998), no. 1-3, 267–274.

[2] Aaron Robertson, Permutations containing and avoiding 123 and 132 patterns. Discrete Math. and Theoretical Computer Science, 3 (1999), no. 4, 119-122.