231-Avoiding Involutions and Fibonacci Numbers^{∗}

Eric S. Egge Department of Mathematics Gettysburg College Gettysburg, PA 17325 USA eggee@member.ams.org

Toufik Mansour Department of Mathematics Chalmers University of Technology 412 96 Göteborg Sweden toufik@math.chalmers.se

May 6, 2003

Abstract We use combinatorial and generating function techniques to enumerate various sets

of involutions which avoid 231 or contain 231 exactly once.

Interestingly, many of these enumerations can be given in terms of k-generalized Fibonacci numbers.

Keywords: Restricted permutation; restricted involution; 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}. We say π is an involution whenever π(π(i)) = i for all i, 1 ≤ i ≤ n, and we write I_{n} to denote the set of involutions in S_{n}. Now 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. If π avoids σ then σ is sometimes called a pattern or a forbidden subsequence and π is sometimes called a restricted permutation or a patternavoiding permutation.

∗2000 Mathematics Subject Classification: 05A15

In this paper we will be interested in permutations which avoid several patterns, so for any set R of permutations we write S_{n}(R) to denote the elements of S_{n} which avoid every element of R. For any set R of permutations we take S_{n}(R) to be the empty set whenever n < 0 and we take S_{0}(R) to be the set containing only the empty permutation. When R = {π_{1}, π_{2}, …, π_{r}} we often write S_{n}(R) = S_{n}(π_{1}, π_{2}, …, π_{r}). We will also be interested in involutions which avoid several patterns, so for any set R of permutations we write I_{n}(R) to denote the set of involutions in S_{n}(R).

For all k ≥ 1 and all n, we write F_{k,n} to denote the number of tilings of a 1 × (n − 1) rectangle with tiles of size 1×1, 1×2, …, 1×k. Observe that F_{k,n} = 0 for all n ≤ 0, F_{k,1} = 1, and F_{k,n} = ∑_{i=1}^{k} F_{k,n−i} for all n ≥ 2. It follows that the ordinary generating function for F_{k,n} is given by

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

Since F_{2,n} is the ordinary Fibonacci number F_{n} for all n ≥ 0, we refer to the numbers F_{k,n} as the k-generalized Fibonacci numbers. (cf. [3])

Restricted permutations were first connected with Fibonacci numbers by Simion and Schmidt, who showed in [11, Prop. 15] that

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

The present authors generalized this result extensively in [2], where they gave several families of sets of restricted permutations which can be counted in terms of k-generalized Fibonacci numbers. For example, the present authors showed in [2] that

|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},  (2)

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

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

In fact, |S_{n}(132, 213, τ)| can be expressed in terms of k-generalized Fibonacci numbers for every τ ∈ S_{n}(132, 213), as Mansour demonstrated in [8, Thm. 8] by expressing the generating function for |S_{n}(132, 213, τ)| as a determinant of a matrix of generating functions for various k-generalized Fibonacci numbers.

Although they were initially studied through the Robinson-Schensted correspondence, restricted involutions have recently begun to receive attention as objects of study in their own right. In [10] Regev provided an asymptotic formula for |I_{n}(12 … k)| and showed that |I_{n}(1234)| = M_{n}, where M_{n} is the nth Motzkin number, which may be defined by M_{0} = 1 and M_{n} = M_{n−1}+∑_{i=0}^{n−2} M_{i}M_{n−i−2} for n ≥ 1. In [4] Gessel enumerated I_{n}(12 … k), and Gouyou– Beauchamps [5] has given bijective proofs of exact formulas for |I_{n}(12345)| and |I_{n}(123456)|. Guibert [6] has established bijections between 1-2 trees with n edges and several sets of restricted involutions, including I_{n}(3412) and I_{n}(4321). This latter bijection leads, by way of the Robinson-Schensted correspondence, to a bijection between 1-2 trees with n edges and I_{n}(1234). Guibert has also given [6] a bijection between vexillary involutions of length n (that is, I_{n}(2143)) and I_{n}(1243). More recently, Guibert, Pergola and Pinzani [7] gave a bijection between 1-2 trees with n edges and vexillary involutions of length n. Combining all of these results, we find that |I_{n}(1234)| = |I_{n}(3412)| = |I_{n}(4321)| = |I_{n}(2143)| = |I_{n}(1243)| = M_{n}. At this writing it is an open problem to prove the conjecture of Guibert [6] that |I_{n}(1432)| = M_{n}.

In this paper we use combinatorial and generating function techniques to enumerate various sets of involutions which avoid 231 or contain 231 exactly once. It turns out that many of these enumerations can be given in terms of k-generalized Fibonacci numbers. In section 2 we use results of Simion and Schmidt [11], Mansour [8], and the current authors [2] to explain how to enumerate involutions which avoid 231 and another pattern. In section 3 we enumerate involutions which avoid 231 and contain a given pattern. In section 4 we enumerate involutions which contain 231 exactly once and avoid another pattern. In section 5 we enumerate involutions which contain 231 exactly once and contain another pattern.

2 Involutions Which Avoid 231 and Avoid Another Pattern

In this section we briefly consider I_{n}(231, τ), where τ ∈ S_{k}. Our consideration will be brief because these sets of permutations have already been extensively studied in a slightly different guise. To describe this different guise, we begin with some notation. Definition 2.1 Fix n ≥ 1 and let l_{1}, l_{2}, …, l_{m} denote a sequence such that l_{i} ≥ 1 for 1 ≤ i ≤ m and ∑_{i=1}^{m} l_{i} = n. We write [l_{1}, l_{2}, …, l_{m}] to denote the permutation given by

[l_{1}, l_{2}, …, l_{m}] = l_{1}, l_{1} − 1, …, 1, l_{2} + l_{1}, l_{2} + l_{1} − 1, …, l_{1} + 1, …, n, n − 1, …, n − l_{m} + 1.

We call a permutation layered whenever it has the form [l_{1}, …, l_{m}] for some sequence l_{1}, …, l_{m}. We remark that layered permutations have also been studied in [1] and [9]. Associating the layered permutation [l_{1}, …, l_{m}] with the tiling 1×l_{1}, 1×l_{2}, 1×l_{3}, …, 1×l_{m}

of a rectangle of size 1 × n, we obtain a natural bijection between layered permutations of length n and tilings of a 1 × n rectangle with rectangles of size 1 × 1, 1 × 2, 1 × 3, . . ..

Since 231 and 312 are (group-theoretic) inverses of each other, and since every involution is its own inverse, the number of subsequences of type 231 in an involution π is equal to the number of subsequences of type 312 in π. In particular, I_{n}(231) = I_{n}(312) for all n ≥ 0. As Simion and Schmidt explain in the remarks following the proofs of [11, Prop. 6] and [11, Prop. 12], the set I_{n}(231) = I_{n}(312) is also connected with layered permutations, as follows. Proposition 2.2 For all n ≥ 0, the sets I_{n}(231), I_{n}(312), and S_{n}(231, 312) are all equal to the set of layered permutations of length n.

It follows that I_{n}(231, τ) = S_{n}(231, 312, τ) = I_{n}(312, τ) for any permutation τ. Writing τ^{r} to denote the permutation obtained by writing the entries of τ in reverse order, we find that S_{n}(231, 312, τ) = S_{n}(132, 213, τ^{r}) for any permutation τ. These observations allow us to translate results such as (2) into enumerations of I_{n}(213, τ) for various permutations τ.

3 Involutions Which Avoid 231 and Contain Another Pattern

In this section we consider those involutions in I_{n}(231) which contain a given pattern τ. We begin by setting some notation. Definition 3.1 For all n ≥ 0, all r ≥ 0, and all permutations τ, we write I_{n}^{r}(231; τ) to denote the set of involutions in I_{n}(231) which contain exactly r subsequences of type τ. We write I_{231;τ}^{r}(x) to denote the generating function given by

I_{231;τ}^{r}(x) = ∑_{n=0}^{∞} |I_{n}^{r}(231; τ)|x^{n}.

We often abbreviate I_{231;τ}^{0}(x) by I_{231;τ}(x). We write I_{231;τ}(x, y) to denote the generating function given by

I_{231;τ}(x, y) = ∑_{n=0}^{∞} ∑_{r=0}^{∞} |I_{n}^{r}(231; τ)|x^{n}y^{r}.

In view of Proposition 2.2, if τ is not layered then I_{231;τ}(x, y) = 0, so it is reasonable to ask for a closed form expression for I_{231;τ}(x, y) for any layered permutation τ. Such an expression appears to be difficult to obtain, so we content ourselves here with a closed form expression for I_{231;k...21}(x, y). Theorem 3.2 For all k ≥ 1, we have

I_{231;k...21}(x, y) = \frac{1}{1 − ∑_{j≥1} x^{j}y^{\binom{j}{k}}} .  (3)

Proof. To obtain (3), we count tilings of a 1×n rectangle with tiles of size 1×1, …, 1×(k−1) according to the length of the right-most tile. The generating function for the empty tiling is 1. The generating function for those tilings whose right-most tile has length j ≥ 1 is x^{j}y^{\binom{j}{k}}I_{231;k...21}(x, y). Combining these observations, we find that

I_{231;k...21}(x, y) = 1 + ∑_{j≥1} x^{j}y^{\binom{j}{k}}I_{231;k...21}(x, y).

Solve this equation for I_{231;k...21}(x, y) to obtain (3). □

For r ≤ k one can now obtain I_{231;k...21}^{r}(x) from (3) by expanding the right side in powers of y and finding the coefficient of y^{r}. In lieu of this calculation, we use a combinatorial approach to obtain I_{231;k...21}^{r}(x). Theorem 3.3 For all k and r such that 0 ≤ r ≤ k and all n ≥ 0 we have

|I_{n}^{r}(231; k … 21)| = ∑_{s_{0},...,s_{r}} ∏_{i=0}^{r} F_{k−1,s_{i}+1},  (4)

where the sum on the right is over all sequences s_{0}, …, s_{r} of nonnegative integers such that ∑_{i=0}^{r} s_{i} = n − kr. Moreover,

I_{231;k...21}^{r}(x) = \frac{x^{kr}}{(1 − x − … − x^{k−1})^{r+1}} .  (5)

Proof. Since r ≤ k, the tilings which correspond to the permutations in I_{n}^{r}(231; k … 21) are exactly those tilings of a 1 × n rectangle which contain precisely r tiles of size 1 × k and no tiles of length k + 1 or more. To build such a tiling, first order the tiles of size 1 × k; there is one way to do this. Now fix the sizes s_{0}, …, s_{r} of the gaps between these tiles; observe that we must have ∑_{i=0}^{r} s_{i} = n − kr. Finally, tile each of these gaps with tiles of length at most k − 1; there are ∏_{i=0}^{r} F_{k−1,s_{i}+1} ways to do this. Combine these observations to obtain (4).

The proof of (5) is similar to the proof of (4). □

Using the same combinatorial techniques, we now compute I_{231;τ}^{1}(x) for any layered permutation τ. Theorem 3.4 Fix a layered permutation [l_{1}, …, l_{m}]. Set k_{0} = l_{1} − 1, k_{m} = l_{m} − 1, and k_{i} = min(l_{i} − 1, l_{i+1} − 1) for 1 ≤ i ≤ m − 1. Then we have

|I_{n}^{1}(231; [l_{1}, …, l_{m}])| = ∑_{s_{0},...,s_{m}} ∏_{i=0}^{m} F_{k_{i},s_{i}+1},  (6)

where the sum is over all sequences of nonnegative integers such that ∑_{i=0}^{m} s_{i} = n − ∑_{i=1}^{m} l_{i}. Moreover,

I_{231;[l_{1},...,l_{m}]}^{1}(x) = x^{∑_{i=1}^{m} l_{i}} ∏_{i=0}^{m} \frac{1}{1 − x − x^{2} − … − x^{k_{i}}} .  (7)

Proof. This is similar to the proof of Theorem 3.3. □

Using Theorem 3.4, we now highlight a family of involutions which are enumerated by k-generalized Fibonacci numbers. Corollary 3.5 For all k ≥ 1, all l ≥ 1, and all n ≥ 0, the number of involutions in I_{n}(231) which contain exactly one subsequence of type [1^{k}, l] is given by F_{l−1,n−k−l+1}.

Proof. Set m = k + 1, l_{i} = 1 for 1 ≤ i ≤ k, and l_{k+1} = l in Theorem 3.4 and observe that F_{0,1} = 1 and F_{0,n} = 0 whenever n ≠ 1. □

4 Involutions Which Contain 231 Once and Avoid Another Pattern

In this section we consider those involutions in I_{n} which contain exactly one subsequence of type 231 and avoid an additional pattern. We begin by setting some notation.

Definition 4.1 For all n ≥ 0 and any permutation τ, we write J_{n}(τ) to denote the set of involutions in I_{n} which avoid τ and which contain exactly one subsequence of type 231. We write J_{231;τ}(x) to denote the generating function given by

J_{231;τ}(x) = ∑_{n=0}^{∞} |J_{n}(τ)|x^{n}.

As we did for I_{n}(231) in Section 2, we give a constructive bijection between the set of involutions of length n which contain exactly one subsequence of type 231 and a certain set of tilings of a rectangle of size 1 × n. Proposition 4.2 Fix n ≥ 0. Then there exists a constructive bijection between the set of involutions in I_{n} which contain exactly one subsequence of type 231 and the set of tilings of a 1×n rectangle using exactly one red rectangle of size 1×4 and blue rectangles of size 1×1, 1 × 2, . . ..

Proof. Suppose we are given such a tiling; we construct the corresponding involution as follows. First number the squares 1, 2, …, n from left to right. In each blue tile, reverse the order of the entries. If the left-most entry of the red tile is a, then put the entries of the red tile in the order a + 3, a + 1, a + 2, a. It is routine to verify that the resulting permutation is an involution which contains exactly one subsequence of type 231 and that the given map is injective. Therefore it is sufficient to show that the given map is surjective. To do this, fix π ∈ I_{n}; we argue by induction on n. It is routine to verify the result when n ≤ 4, so we assume n ≥ 5 and that the result holds for all k ≤ n − 1. Fix j such that π(j) = n; since π is an involution we also have π(n) = j. We consider two cases: either n appears in the subsequence of type 231 or n does not appear in the subsequence of type 231.

If n does not appear in the subsequence of type 231 then there exist permutations π_{1} and π_{2}, exactly one of which contains exactly one subsequence of type 231, such that π = π_{1}, n, π̃_{2}. Here π̃_{2} is the sequence obtained by adding j − 1 to every entry of π_{2}. In this case the result follows from our bijection involving I_{n}(231) and induction.

Now suppose the subsequence given by π(a), n, π(b) has type 231. If π(b) > j then π(a) > π(b) > j and the subsequence π(a), n, j of π is a second subsequence of type 231, which is a contradiction. If π(b) = j then π(a) > j. Therefore, since π is an involution, a appears to the right of n and a < π(a). It follows that π(a), n, a is a second subsequence of type 231, which is a contradiction. If π(b) < j then b appears to the left of n, since π is an involution. It follows that b, n, j is a second subsequence of type 231, which is a contradiction. Combining these observations, we find that n does not appear in the subsequence of type 231.

It follows that the given map is surjective, as desired. □

Using Proposition 4.2, we now enumerate those involutions in I_{n} which contain exactly one subsequence of type 231. Theorem 4.3 The number of the involutions in S_{n} which contain exactly one subsequence of type 231 is given by (n − 1)2^{n−6} for all n ≥ 5.

Proof. Count the corresponding tilings in three cases: the red tile is at the far left, the red tile is at the far right, or there are blue tiles on both sides of the red tile. There are 2^{n−5} tilings of the first type, 2^{n−5} tilings of the second type, and ∑_{i=1}^{n−5} 2^{i−1}2^{n−i−5} = (n − 5)2^{n−6} tilings of the third type. Combine these observations to obtain the desired result. □

We now use Proposition 4.2 to enumerate J_{n}(k … 21). We observe that every involution in S_{n} which contains exactly one pattern of type 231 contains a pattern of type 4231, and therefore a pattern of type 321. With this in mind, we consider J_{n}(k … 21) for k ≥ 4. Theorem 4.4 Fix k ≥ 4. Then for all n ≥ 0 we have

|J_{n}(k … 21)| = ∑_{i=0}^{n−4} F_{k−1,i+1}F_{k−1,n−i−3}.  (8)

Moreover,

J_{231;k...21}(x) = \frac{x^{4}}{(1 − x − … − x^{k−1})^{2}} .  (9)

Proof. This is similar to the proof of Theorem 3.3, using Proposition 4.2. □

We conclude this section by giving a recursive procedure for computing J_{231;τ}(x) when τ is a layered permutation. Theorem 4.5 Fix positive integers l_{1}, …, l_{m} and l. If l ≤ 3 then we have

J_{231;[l_{1},...,l_{m},l]}(x) = \frac{1}{1 − x − … − x^{l−1}} (\frac{x^{l}}{1 − x}J_{231;[l_{1},...,l_{m}]}(x) + x^{4}I_{231;[l_{1},...,l_{m}]}(x)) . (10)

If l ≥ 4 then we have

J_{231;[l_{1},...,l_{m},l]}(x) = \frac{1}{1 − x − … − x^{l−1}} (\frac{x^{l}}{1 − x}J_{231;[l_{1},...,l_{m}]}(x) + x^{4}I_{231;[l_{1},...,l_{m},l]}(x)) . (11)

Proof. This is similar to the proof of Theorem 3.2, using Proposition 4.2. □

We remark that it is clear from results given in [8] and (9) – (11) that for any layered permutation τ, the set J_{n}(τ) can be enumerated in terms of k-generalized Fibonacci numbers.

5 Involutions Which Contain 231 Once and Contain Another Pattern

In this section we consider those involutions in I_{n} which contain exactly one subsequence of type 231 and which also contain a given pattern. We begin by setting some notation. Definition 5.1 For all n ≥ 0, all r ≥ 0, and any permutation τ, we write J_{n}^{r}(τ) to denote the set of involutions in I_{n} which contain exactly one subsequence of type 231 and exactly r subsequences of type τ. We write J_{231;τ}^{r}(x) to denote the generating function given by

J_{231;τ}^{r}(x) = ∑_{n=0}^{∞} |C_{n}^{r}(τ)|x^{n}.

We write J_{231;τ}(x, y) to denote the generating function given by

J_{231;τ}(x, y) = ∑_{n=0}^{∞} ∑_{r=0}^{∞} |C_{n}^{r}(τ)|x^{n}y^{r}.

As with I_{231;τ}(x, y), finding a closed form expression for J_{231;τ}(x, y) appears to be difficult for general τ, so we content ourselves here with a closed form expression for J_{231;k...21}(x, y). Theorem 5.2 For all k ≥ 4 we have

J_{231;k...21}(x, y) = \frac{x^{4}}{(1 − ∑_{j≥1} x^{j}y^{\binom{j}{k}})^{2}} .  (12)

Proof. This is similar to the proof of Theorem 3.2, using Proposition 4.2. □

For r ≤ k one can now obtain J_{231;k...21}^{r}(x) from (12) by expanding the right side in powers of y and finding the coefficient of y^{r}. In lieu of this calculation, we use a combinatorial approach to obtain J_{231;k...21}^{r}(x). Theorem 5.3 For all k and r such that 0 ≤ r ≤ k and all n ≥ 0 we have

|J_{n}^{r}(k … 21)| = (r + 1) ∑_{s_{0},...,s_{r+1}} ∏_{i=0}^{r+1} F_{k−1,s_{i}+1},  (13)

where the sum on the right is over all sequences s_{0}, …, s_{r+1} of nonnegative integers such that ∑_{i=0}^{r+1} s_{i} = n − kr − 4. Moreover,

J_{231;k...21}^{r}(x) = \frac{(r + 1)x^{kr+4}}{(1 − x − x^{2} − … − x^{k−1})^{r+2}} .  (14)

Proof. This is similar to the proof of Theorem 3.3, using Proposition 4.2. □

We conclude the paper by giving a recursive procedure for computing J_{231;τ}^{1}(x) for any layered permutation τ. Theorem 5.4 Fix positive integers l_{1}, …, l_{m} and l. If l ≤ 3 then we have

J_{231;[l_{1},...,l_{m},l]}^{1}(x) = \frac{x^{l}}{1 − x − … − x^{l−1}} J_{231;[l_{1},...,l_{m}]}^{1}(x).  (15)

If l ≥ 4 then we have

J_{231;[l_{1},...,l_{m},l]}^{1}(x) = \frac{1}{1 − x − … − x^{l−1}} (x^{l}J_{231;[l_{1},...,l_{m}]}^{1}(x) + x^{4}I_{231;[l_{1},...,l_{m},l]}^{1}(x)) . (16)

Proof. This is similar to the proof of Theorem 3.2, using Proposition 4.2. □

We remark that it is clear from (7) and (14) – (16) that for any layered permutation τ, the set J_{n}^{r}(τ) can be enumerated in terms of k-generalized Fibonacci numbers.

Acknowledgement The authors thank the anonymous referee, whose suggestions

improved both the content and exposition of this paper.

References

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

[2] E. S. Egge and T. Mansour. Restricted permutations, Fibonacci numbers, and kgeneralized Fibonacci numbers. arXiv:math.CO/0203226.

[3] I. Flores. Direct calculation of k-generalized Fibonacci numbers. Fibonacci Quart., 5:259–266, 1967.

[4] I. M. Gessel. Symmetric functions and P-recursiveness. J. Combin. Theory, Series A, 53:257–285, 1990.

[5] D. Gouyou-Beauchamps. Standard Young tableaux of height 4 and 5. Europ. J. Combin., 10:69–82, 1989.

[6] O. Guibert. Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young. PhD thesis, Université Bordeaux I, 1995.

[7] O. Guibert, E. Pergola, and R. Pinzani. Vexillary involutions are enumerated by Motzkin numbers. Ann. Comb., 5:153–174, 2001.

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

[9] T. Mansour and A. Vainshtein. Layered restrictions and Chebyshev polynomials. Ann. Comb., 5(3–4):451–458, 2001.

[10] A. Regev. Asymptotic values for degrees associated with strips of Young diagrams. Adv. Math., 41:115–136, 1981.

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