Pattern Popularity in Multiply Restricted Permutations

Alina F. Y. Zhao School of Mathematical Sciences and Institute of Mathematics Nanjing Normal University Nanjing 210023 PR China

                     alinazhao@njnu.edu.cn

Abstract We derive explicit formulae or generating functions for the popularity of all the length-3 patterns in multiply restricted permutations, and provide combinatorial interpretations for some non-trivial equipopular patterns as well.

1 Introduction

Let σ = σ_{1}σ_{2} ⋯ σ_{n} be a permutation in the symmetric group S_{n}. We say that σ contains a pattern q = q_{1}q_{2} ⋯ q_{k} ∈ S_{k} if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that the entries σ_{i_{1}}σ_{i_{2}} ⋯ σ_{i_{k}} have the same relative order as the entries of q, i.e., q_{j} < q_{l} if and only if σ_{i_{j}} < σ_{i_{l}} whenever 1 ≤ j, l ≤ k. We say that σ avoids q if σ does not contain q as a pattern. A permutation may contain multiple copies of a pattern. For example, permutation 43512 contains two copies of pattern 321, namely 431 and 432, but avoids pattern 123.

For a pattern q, let S_{n}(q) denote the set of all permutations in S_{n} that avoid the pattern q, and for R ⊆ S_{k}, let S_{n}(R) = ⋂_{q∈R} S_{n}(q) be the set of permutations in S_{n} that avoid every pattern contained in R. For two permutations σ and q, we set f_{q}(σ) to be the number of copies of q in σ as a pattern. The popularity of pattern q in S_{n}(R) is defined as

f_{q}(S_{n}(R)) = ∑_{σ∈S_{n}(R)} f_{q}(σ).

f_{213}(n) = (n − 3)2^{n−2} + 1  ∑ f_{231}(n)x^{n} = ∑ f_{312}(n)x^{n} = \frac{x3(1+2x)}{(1−x−x2)3}
S_{n}(123, 132)  f_{231}(n) = f_{312}(n) = (n^{2} − 5n + 8)2^{n−3} − 1  S_{n}(123, 132, 213)  ∑ f_{321}(n)x^{n} = \frac{x3(1+6x+12x2+8x3)}{(1−x−x2)4}
f_{321}(n) = (n^{3}/3 − 2n^{2} + 14n/3 − 5)2^{n−2} + 1  f_{213}(n) = f_{312}(n) = \binom{n}{3}
f_{123}(n) = (n − 4)2^{n−1} + n + 2  S_{n}(123, 132, 231)  f_{321}(n) = (n − 2)\binom{n}{3}
S_{n}(132, 213)  f_{231}(n) = f_{312}(n) = ( \frac{n2}{4} − \frac{7n}{4} + 4)2^{n} − n − 4  f_{123}(n) = f_{312}(n) = \binom{n+1}{4}
f_{321}(n) = ( \frac{1}{12} n^{3} − \frac{3}{4} n^{2} + \frac{38}{12} n − 6)2^{n} + n + 6  S_{n}(132, 213, 231)  f_{321}(n) = \frac{1}{12} n(n − 2)(n − 1)^{2}
S_{n}(132, 231)  f_{123}(n) = f_{213}(n) = f_{312}(n) = f_{321}(n) = \frac{2n}{8} \binom{n}{3}  f_{213}(n) = f_{231}(n) = \binom{n}{3}
S_{n}(132, 312)  f_{123}(n) = f_{213}(n) = f_{231}(n) = f_{321}(n) = \frac{2n}{8} \binom{n}{3}  S_{n}(123, 132, 312)  f_{321}(n) = (n − 2)\binom{n}{3}
f_{213}(n) = f_{231}(n) = f_{312}(n) = \binom{n+2}{5}  f_{132}(n) = f_{213}(n) = \binom{n+1}{4}
S_{n}(132, 321)  f_{123}(n) = \frac{7n5}{120} − \frac{n4}{3} + \frac{17n3}{24} − \frac{2n2}{3} + \frac{7}{30}  S_{n}(123, 231, 312)  f_{321}(n) = \frac{1}{12} n(n − 2)(n − 1)^{2}

Table 1: Pattern popularity in doubly and triply restricted permutations.

We say that p and q are equipopular if f_{p}(S_{n}(R)) = f_{q}(S_{n}(R)) for all n.

The complement of σ is given by σ^{c} = (n + 1 − σ_{1})(n + 1 − σ_{2}) ⋯ (n + 1 − σ_{n}), its reverse is defined as σ^{r} = σ_{n} ⋯ σ_{2}σ_{1} and the inverse σ^{−1} is the regular group-theoretic inverse permutation. For any set of permutations R, let R^{c} be the set obtained by complementing each element of R, and the sets R^{r} and R^{−1} are defined analogously. It is well known that

Lemma 1. Let R ⊆ S_{k} be any set of permutations in S_{k}, and σ ∈ S_{n}, we have

σ ∈ S_{n}(R) ⇔ σ^{c} ∈ S_{n}(R^{c}) ⇔ σ^{r} ∈ S_{n}(R^{r}) ⇔ σ^{−1} ∈ S_{n}(R^{−1}).

Cooper [6] first raised the problem of determining the total number f_{q}(S_{n}(r)), and Bóna [2] derived the generating function of the sequence (f_{q}(S_{n}(132)))_{n≥1} for monotone pattern, i.e., q = 12 ⋯ k or q = k(k − 1) ⋯ 21. Further, Bóna [3] studied the generating functions for other length-3 patterns in S_{n}(132), and showed both algebraically and bijectively that

f_{231}(S_{n}(132)) = f_{312}(S_{n}(132)) = f_{213}(S_{n}(132)).

According to the correspondence between 132-avoiding permutations and binary plane trees, Rudolph [13] showed that patterns of equal length are equipopular if their associated binary plane trees have identical spine structure. For the converse direction, Chua and Sankar [4] gave a complete classification of 132-avoiding permutations into equipopularity classes. Moreover, Homberger [9] presented exact formulae for the occurrences of each length-3 pattern in S_{n}(123). From Lemma 1 and the existing results on S_{n}(123) and S_{n}(132), we can obtain the popularity of each length-3 pattern for the singly restricted permutations S_{n}(r) with r = 213, 231, 312, 321. Therefore, it is well-studied for the popularity of length-3 patterns in singly restricted permutations, whereas it remains open for multiply restricted permutations.

In this paper, we focus on counting the number of occurrences of length-3 patterns in multiply restricted permutations S_{n}(R) for R ⊂ S_{3}, especially for double and triple restrictions.

We obtain exact formulae or generating functions for popularity of each length-3 pattern, and the detailed results are summarized in Table 1. Moreover, we present combinatorial proofs for non-trivial equalities between the number of occurrences of different patterns. It is routine to consider the restricted permutations of higher multiplicity since there are only finite permutations, as shown in [14, Proposition 17]. Therefore, this work gives a complete study on the popularity of length-3 patterns in the multiply restricted permutations. For the distributions of other statistics in multiply restricted permutations, see [7, 8, 10, 11, 12].

2 Doubly restricted permutations

This section deals with the enumeration of the popularity for length-3 patterns in the doubly restricted permutations, i.e., permutations avoiding two different patterns in S_{3}. For doubly restricted permutations, we have the following proposition from [14].

Proposition 2. ([14, Lemma 5]) For every symmetric group S_{n},

1. |S_{n}(123, 132)| = |S_{n}(123, 213)| = |S_{n}(231, 321)| = |S_{n}(312, 321)| = 2^{n−1};

2. |S_{n}(132, 213)| = |S_{n}(231, 312)| = 2^{n−1};

3. |S_{n}(132, 231)| = |S_{n}(213, 312)| = 2^{n−1};

4. |S_{n}(132, 312)| = |S_{n}(213, 231)| = 2^{n−1};

5. |S_{n}(132, 321)| = |S_{n}(123, 231)| = |S_{n}(123, 312)| = |S_{n}(213, 321)| = \binom{n}{2} + 1;

6. |S_{n}(123, 321)| = 0 for n ≥ 5.

Thus it is sufficient to consider the pattern popularity for the first set from class 1 to class 5, and the pattern popularity for the other sets can be derived by taking complement, reverse or inverse.

A composition of n is an expression of n as an ordered sum of positive integers, and we say that c has k parts or c is a k-composition if there are exactly k summands appeared in composition c. Let C_{n} and C_{n,k} denote the set of all compositions of n and the set of k-compositions of n, respectively. It is known that |C_{0}| = 1, and for n ≥ 1, 1 ≤ k ≤ n, |C_{n}| = 2^{n−1} and |C_{n,k}| = \binom{n−1}{k−1}. For more details on compositions, see [16]. It is helpful to introduce a lemma as follows:

Lemma 3. For n ≥ 1, we have

a(n) := ∑_{c_{1}+c_{2}+···+c_{k}=n} c_{k} = 2^{n} − 1,
b(n) := ∑_{c_{1}+c_{2}+···+c_{k}=n} c_{k}(c_{k} − 1) = 2^{n+1} − 2n − 2,
c(n) := ∑_{c_{1}+c_{2}+···+c_{k}=n} k = (n + 1)2^{n−2},
d(n) := ∑_{c_{1}+c_{2}+···+c_{k}=n} k(k − 1) = (n^{2} + n − 2)2^{n−3},

where the sums are taken over all compositions of n.

Proof. For c_{k} = m , we can regard c_{1} + c_{2} + ⋯ + c_{k−1} as a composition of n − m. Since the number of compositions of n − m is 2^{n−m−1} for 1 ≤ m ≤ n − 1 and the number of compositions of n with k parts is \binom{n−1}{k−1}, we have

a(n) = n + ∑_{m=1}^{n−1} m2^{n−m−1}, b(n) = n(n − 1) + ∑_{m=1}^{n−1} m(m − 1)2^{n−m−1},

and

c(n) = ∑_{k=1}^{n} k\binom{n − 1}{k − 1}, d(n) = ∑_{k=1}^{n} k(k − 1)\binom{n − 1}{k − 1}.

Let g(x) = ∑_{i=0}^{n−1} x^{i} = \frac{1−x^{n}}{1−x} and h(x) = x ∑_{i=1}^{n} \binom{n−1}{i−1}x^{i−1} = x(1 + x)^{n−1}. We have

g′(x) = ∑_{i=1}^{n−1} ix^{i−1} = \frac{(n − 1)x^{n} − nx^{n−1} + 1}{(1 − x)^{2}},

g′′(x) = ∑_{i=1}^{n−1} i(i − 1)x^{i−2} = \frac{(3n − n^{2} − 2)x^{n} + (2n^{2} − 4n)x^{n−1} + (n − n^{2})x^{n−2} + 2}{(1 − x)^{3}},

h′(x) = ∑_{i=1}^{n} i\binom{n − 1}{i − 1}x^{i−1} = (nx + 1)(1 + x)^{n−2},

h′′(x) = ∑_{i=1}^{n} i(i − 1)\binom{n − 1}{i − 1}x^{i−2} = [n^{2}x + n(2 − x) − 2] (1 + x)^{n−3}.

It follows that

a(n) = 2^{n−2}g′(1/2) + n, b(n) = 2^{n−3}g′′(1/2) + n(n − 1),

and

c(n) = h′(1), d(n) = h′′(1).

Lemma 3 holds by simple computations.

2.1 Pattern popularity in (123, 132)-avoiding permutations

In this subsection, we calculate the popularity of all length-3 patterns in S_{n}(123, 132). For a permutation σ = σ_{1}σ_{2} ⋯ σ_{n}, σ_{i} is said to be a left-to-right maximum (resp., right-to-left maximum) if σ_{i} > σ_{j} for all j < i (resp., j > i). We first recall a correspondence between S_{n}(123, 132) and C_{n} as implicitly shown in [10].

Lemma 4. ([10, Theorem 3]) There is a bijection φ_{1} between S_{n}(123, 132) and C_{n}.

Proof. Given σ ∈ S_{n}(123, 132), let σ_{i_{1}}, σ_{i_{2}}, …, σ_{i_{k}} be the k right-to-left maxima with i_{1} < i_{2} < ⋯ < i_{k}. Then c = i_{1} + (i_{2} − i_{1}) + ⋯ + (i_{k−1} − i_{k−2}) + (i_{k} − i_{k−1}) is a composition of n since i_{k} = n. On the converse, let m_{i} = n − (c_{1} + ⋯ + c_{i−1}) for any given composition n = c_{1} + c_{2} + ⋯ + c_{k} ∈ C_{n}. Set τ_{i} = m_{i} − 1, m_{i} − 2, …, m_{i} − c_{i} + 1, m_{i} for 1 ≤ i ≤ k. It is easy to check that σ = τ_{1} τ_{2} ⋯ τ_{k} ∈ S_{n}(123, 132).

For example, σ = 8 9 7 5 4 3 6 1 2 corresponds to the composition 9 = 2 + 1 + 4 + 2.

Given a pattern q, for simplicity, let f_{q}(n) := ∑_{σ∈S_{n}(123,132)} f_{q}(σ) be the number of occurrences of pattern q in S_{n}(123, 132), and we will use this notation in subsequent sections when the set in question is unambiguous. A factor of σ is a subsequence consisting of contiguous letters in σ. From Lemma 4, we have

Proposition 5. For n ≥ 3,

f_{213}(n) = ∑_{c_{1}+c_{2}+···+c_{k}=n} ∑_{i=1}^{k} \binom{c_{i} − 1}{2},  (1)

f_{231}(n) = ∑_{c_{1}+c_{2}+···+c_{k}=n} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}(c_{i} − 1).  (2)

Proof. For each permutation σ ∈ S_{n}(123, 132) with φ_{1}(σ) = c_{1} + c_{2} + ⋯ + c_{k}, we can rewrite σ as σ = τ_{1} τ_{2} ⋯ τ_{k} from Lemma 4. We say that τ_{i} > τ_{j} if all the elements in τ_{i} are larger than that in τ_{j}. We see that the pattern 213 can only occur in every factor τ_{i} since the elements except the last one are decreasing in τ_{i} and τ_{i} > τ_{j} for j > i. Thus, there are \binom{c_{i}−1}{2} choices to select two elements in τ_{i} to play the role of “21”, and the last element of τ_{i} plays the role of “3”. If c_{i} ≤ 2, then there is no copy of the pattern 213 in τ_{i}, this coincides with the value \binom{c_{i}−1}{2} = 0 for c_{i} = 1 or 2. Summing up all the number of 213-patterns in factors τ_{1}, τ_{2}, …, τ_{k} yields formula (1).

For pattern 231, we have c_{i} −1 choices in factor τ_{i} to select one element to play the role of “2” and one choice (always the last element of τ_{i}) for “3”. After this, we have c_{i+1} + ⋯ + c_{k} choices to select one element in τ_{i+1}, …, τ_{k} for the role of “1” since all the elements after τ_{i} are smaller than those in τ_{i}. Summing up all the number of 231-patterns according to the position of “3” gives formula (2).

Theorem 6. For n ≥ 3, in the set S_{n}(123, 132), we have

f_{213}(n) = (n − 3)2^{n−2} + 1,  (3)
f_{231}(n) = f_{312}(n) = (n^{2} − 5n + 8)2^{n−3} − 1,  (4)
f_{321}(n) = (n^{3}/3 − 2n^{2} + 14n/3 − 5)2^{n−2} + 1.  (5)

Proof. From S_{3}(123, 132) = {213, 231, 312, 321}, we have

f_{213}(3) = f_{231}(3) = 1.

To prove formula (3), Proposition 5 gives that, for n ≥ 3,

f_{213}(n + 1) = ∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i} − 1}{2} + ∑_{{c_{k}≥2 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i} − 1}{2}.

If c_{k} = 1, then k ≥ 2, and we have

∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i} − 1}{2} = ∑_{c_{1}+c_{2}+···+c_{k−1}=n} ∑_{i=1}^{k−1} \binom{c_{i} − 1}{2} = f_{213}(n).

If c_{k} ≥ 2, then we set c_{k} = 1 + r_{k} with r_{k} ≥ 1. From Lemma 3, we find that

∑_{{c_{k}≥2 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i} − 1}{2} = ∑_{c_{1}+···+c_{k−1}+r_{k}=n} [∑_{i=1}^{k−1} \binom{c_{i} − 1}{2} + \binom{r_{k} − 1}{2} + (r_{k} − 1)]

= f_{213}(n) + ∑_{c_{1}+···+c_{k−1}+r_{k}=n}(r_{k} − 1)

= f_{213}(n) + a(n) − 2^{n−1}.

Combining the above two cases, we have

f_{213}(n + 1) = 2f_{213}(n) + 2^{n−1} − 1,

which proves formula (3) by solving the recurrence with initial value f_{213}(3) = 1.

For formula (4), we first have f_{231}(n) = f_{312}(n) from 231^{−1} = 312 and σ ∈ S_{n}(123, 132) ⇔ σ^{−1} ∈ S_{n}(123, 132). Using the same method as in the proof of formula (3), we can show

∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}(c_{i} − 1) = f_{231}(n) − c(n) + n2^{n−1},

and

∑_{{c_{k}≥2 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}(c_{i} − 1) = f_{231}(n) − a(n) − c(n) + (n + 1)2^{n−1}.

It follows that, from Lemma 3,

f_{231}(n + 1) = 2f_{231}(n) + (n − 2)2^{n−1} + 1.

Formula (4) is proved by solving this recurrence using f_{231}(3) = 1.

Since the total number of all length-3 patterns in a permutation σ ∈ S_{n} is \binom{n}{3}, we have

f_{213}(n) + 2f_{231}(n) + f_{321}(n) = \binom{n}{3}2^{n−1},

and formula (5) holds.

The first few values of f_{q}(S_{n}(123, 132)) for q of length 3 are shown below. Moreover, we observe that they appear in the On-Line Encyclopedia of Integer Sequences [15] as follows: (f_{213}(n))_{n≥3} form sequence \underline{A000337}, (f_{231}(n))_{n≥3} form sequence \underline{A055580}.

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 0 & 0 & 1 & 1 & 1 & 1 & 6 & 0 & 0 & 49 & 111 & 111 & 369 \\ 4 & 0 & 0 & 5 & 7 & 7 & 13 & 7 & 0 & 0 & 129 & 351 & 351 & 1409 \\ 5 & 0 & 0 & 17 & 31 & 31 & 81 & 8 & 0 & 0 & 321 & 1023 & 1023 & 4801 \end{matrix}

2.2 Pattern popularity in (132, 213)-avoiding permutations

We first recall a correspondence between S_{n}(132, 213) and C_{n} as follows:

Lemma 7. ([10, Theorem 8]) There is a bijection φ_{2} between S_{n}(132, 213) and C_{n}.

Proof. Given σ ∈ S_{n}(132, 213), let σ_{i_{1}}, σ_{i_{2}}, …, σ_{i_{k}} be the k right-to-left maxima with i_{1} < i_{2} < ⋯ < i_{k}. It follows that c = i_{1} +(i_{2} −i_{1})+⋯+(i_{k−1} −i_{k−2})+(i_{k} −i_{k−1}) is a composition of n since i_{k} = n. On the converse, given a composition n = c_{1} + c_{2} + ⋯ + c_{k} ∈ C_{n}, let m_{i} = n − (c_{1} + ⋯ + c_{i−1}) and τ_{i} = m_{i} − c_{i} + 1, m_{i} − c_{i} + 2, …, m_{i} − 1, m_{i} for 1 ≤ i ≤ k. Set σ = τ_{1} τ_{2} ⋯ τ_{k}, and it is easy to check that σ ∈ S_{n}(132, 213).

For example, for the composition 9 = 3 + 3 + 1 + 2, we get σ = 7 8 9 4 5 6 3 1 2. From this lemma, we have Proposition 8. For n ≥ 3,

f_{123}(n) = ∑_{c_{1}+c_{2}+···+c_{k}=n} ∑_{i=1}^{k} \binom{c_{i}}{3},  (6)

f_{231}(n) = ∑_{c_{1}+c_{2}+···+c_{k}=n} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}\binom{c_{i}}{2}.  (7)

Proof. For a permutation σ ∈ S_{n}(132, 213) with φ_{2}(σ) = c_{1} + c_{2} + ⋯ + c_{k}, we rewrite σ as σ = τ_{1} τ_{2} ⋯ τ_{k}. The pattern 123 can only occur in every factor τ_{i} as τ_{i} > τ_{j} for j > i and the elements in τ_{i} are increasing. Thus, we have \binom{c_{i}}{3} choices to select three elements in τ_{i} to play the role of “123”, and formula (6) follows by summing up all 123-patterns in factors τ_{1}, τ_{2}, …, τ_{k}.

For the pattern 231, we have \binom{c_{i}}{2} choices in factor τ_{i} to select two elements to play the role of “23”. After this, we have c_{i+1} + ⋯ + c_{k} choices to select one element in τ_{i+1}, …, τ_{k} for the role of “1” since τ_{j} < τ_{i} for all j > i. Summing up all the number of 231-patterns according to the position of “23” gives formula (7).

Theorem 9. For n ≥ 3, in the set S_{n}(132, 213), we have

f_{123}(n) = (n − 4)2^{n−1} + n + 2,  (8)
f_{231}(n) = f_{312}(n) = (n^{2} − 7n + 16)2^{n−2} − n − 4,  (9)
f_{321}(n) = (n^{3}/3 − 3n^{2} + 38n/3 − 24)2^{n−2} + n + 6.  (10)

Proof. From Proposition 8, it follows that

f_{123}(n + 1) = ∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i}}{3} + ∑_{{c_{k}≥2 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k} \binom{c_{i}}{3}.

An argument similar to the proof of Theorem 6 shows that

f_{123}(n + 1) = 2f_{123}(n) + 2^{n} − n − 1.

Solving this recurrence with initial value f_{123}(3) = 1 leads to formula (8).

From Lemma 1, we see that σ ∈ S_{n}(132, 213) ⇔ σ^{−1} ∈ S_{n}(132, 213), which implies f_{231}(n) = f_{312}(n) as 231^{−1} = 312.

To calculate f_{231}(n), by Proposition 8, we arrive at

f_{231}(n + 1) = ∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}\binom{c_{i}}{2} + ∑_{{c_{k}≥2 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}\binom{c_{i}}{2}.

If c_{k} = 1, then k ≥ 2, and we have

∑_{{c_{k}=1 \atop c_{1}+c_{2}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}\binom{c_{i}}{2} = f_{231}(n) + α(n),

where

α(n) = ∑_{c_{1}+···+c_{k}=n} ∑_{i=1}^{k} \binom{c_{i}}{2} = ∑_{c_{1}+···+c_{k}=n} ∑_{i=1}^{k} [\binom{c_{i} − 1}{2} + c_{i} − 1]
= f_{213}(S_{n}(123, 132)) + ∑_{c_{1}+···+c_{k}=n}(n − k)
= f_{213}(S_{n}(123, 132)) − c(n) + n2^{n−1}.

Here we have used the deduced expression (1). If c_{k} ≥ 2, then we can derive that

∑_{{c_{k}≥2 \atop c_{1}+···+c_{k}=n+1}} ∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{j}\binom{c_{i}}{2} = f_{231}(n) + β(n),

where

β(n) = ∑_{c_{1}+···+c_{k}=n} ∑_{i=1}^{k−1} \binom{c_{i}}{2}

= ∑_{c_{1}+···+c_{k}=n} ∑_{i=1}^{k} \binom{c_{i}}{2} − ∑_{c_{1}+···+c_{k}=n} \frac{c_{k}(c_{k} − 1)}{2} = α(n) − b(n)/2.

From Lemma 3, we get

f_{231}(n + 1) = 2f_{231}(n) + (2n − 6)2^{n−1} + n + 3.

Formula (9) holds by solving this recurrence with initial condition f_{213}(3) = 1. Finally, formula (10) follows from f_{123}(n) + 2f_{231}(n) + f_{321}(n) = \binom{n}{3}2^{n−1}.

The first few values of f_{q}(S_{n}(132, 213)) for q of length 3 are shown below. They appear in [15] as follows: (f_{123}(n))_{n≥3} form sequence \underline{A045618}, (f_{231}(n))_{n≥3} form sequence \underline{A055581} and (f_{321}(n))_{n≥3} form sequence \underline{A055586}.

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 1 & 0 & 0 & 1 & 1 & 1 & 6 & 72 & 0 & 0 & 150 & 150 & 268 \\ 4 & 6 & 0 & 0 & 8 & 8 & 10 & 7 & 201 & 0 & 0 & 501 & 501 & 1037 \\ 5 & 23 & 0 & 0 & 39 & 39 & 59 & 8 & 522 & 0 & 0 & 1524 & 1524 & 3598 \end{matrix}

For each σ ∈ S_{n}(132, 231), we observe that n must lie in the beginning or the end of σ, and n − 1 must lie in the beginning or the end of σ\{n},..., and so on. Here σ\{n} denotes the sequence obtained from σ by deleting the element n. In view of such special structure, we can derive the pattern popularity in (132, 231)-avoiding permutations directly.

Theorem 10. For n ≥ 3, in the set S_{n}(132, 231), we have

f_{123}(n) = f_{213}(n) = f_{312}(n) = f_{321}(n) = \binom{n}{3}2^{n−3}.  (11)

Proof. Suppose that q is a length-3 pattern in {123, 213, 312, 321}, and abc is a copy of the pattern q. Set

[n]\{a, b, c} := {r_{1} > r_{2} > ⋯ > r_{n−4} > r_{n−3}}.

We will construct a permutation in the set S_{n}(132, 231) which contains abc as a copy of the pattern q. Start with the subsequence σ^{0} := abc, and for i from 1 to n − 3, σ^{i} is obtained by inserting r_{i} into σ^{i−1} such that

• If there are at least two elements in σ^{i−1} that are smaller than r_{i}, then choose the two elements A and B such that A is the leftmost one and B is the rightmost one. We put r_{i} immediately to the left of A or immediately to the right of B;

• If there is only one element A in σ^{i−1} such that A < r_{i}, then we put r_{i} immediately to the left or to the right of A;

• If all the elements in σ^{i−1} are larger than r_{i}, then choose A the smallest one, and put r_{i} immediately to the left or to the right of A.

Finally, we set σ := σ^{n−3} and σ ∈ S_{n}(132, 231) from the above construction. It can be seen that, the number of permutations having a copy abc is 2^{n−3} since each r_{i} has 2 choices in the inserting procedure. Moreover, there are \binom{n}{3} choices to select three elements a, b, c as an appearance of the pattern q in \{123, 213, 312, 321\}. Hence we deduce f_{q}(n) = \binom{n}{3}2^{n−3}.

Here we give an illustration for constructing a permutation in S_{8}(132, 231) which contains abc = 256 as a copy of the pattern 123. Set σ^{0} := 2 5 6, we may have σ^{1} = 8 2 5 6, σ^{2} = 8 7 2 5 6, σ^{3} = 8 7 2 4 5 6, σ^{4} = 8 7 3 2 4 5 6, σ := σ^{5} = 8 7 3 2 1 4 5 6.

We can also give a combinatorial proof for Theorem 10. Since σ ∈ S_{n}(132, 231) ⇔ σ^{r} ∈ S_{n}(132, 231), it is easy to show f_{123}(n) = f_{321}(n) and f_{213}(n) = f_{312}(n) from 123^{r} = 321 and 213^{r} = 312. It remains to give a bijection for f_{213}(n) = f_{123}(n), and our construction is motivated from Bóna [3].

We first introduce some notation about trees. A binary plane tree is a rooted unlabelled tree in which each vertex has at most two children, and each child is a left child or a right child of its parent. For each σ ∈ S_{n}(132), we can construct a binary plane tree T (σ) as follows: the root of T (σ) corresponds to the entry n of σ, the left subtree of the root corresponds to the string of entries of σ on the left of n, and the right subtree of the root corresponds to the string of entries of σ on the right of n. Both subtrees are constructed recursively by the same rule. For more details, see [1, 3, 13].

A left descendant (resp., right descendant) of a vertex x in a binary plane tree is a vertex in the left (resp., right) subtree of x. Similarly, an ascendant of a vertex x in a binary plane tree is a vertex whose subtree contains x. Given a tree T and a vertex v ∈ T, let T_{v} be the subtree of T rooted at v. Let R be an occurrence of the pattern 123 in σ ∈ S_{n}(132), and let R_{1}, R_{2}, R_{3} be the three vertices of T (σ) that correspond to R, going left to right. Then, R_{1} is a left descendant of R_{2}, and R_{2} is a left descendant of R_{3}.

According to the correspondence between 132-avoiding permutations and binary plane trees, we see that for σ ∈ S_{n}(132, 231), T (σ) is a binary plane tree on n vertices such that each vertex has at most one child from the forbiddance of the pattern 231. For simplicity, let T_{n} be the set of such binary plane trees on n vertices. Let Q be an occurrence of the pattern 213 in σ ∈ S_{n}(132, 231), and let Q_{2}, Q_{1}, Q_{3} be the three vertices of T (σ) that correspond to Q, going left to right. From the characterization of trees in T_{n}, Q_{2} is a left descendant of Q_{3}, and Q_{1} is a right descendant of Q_{2}.

Combinatorial proof for f_{213}(n) = f_{123}(n). Let A_{n} be the set of binary plane trees in T_{n} where three vertices forming a 213-pattern are colored black. Let B_{n} be the set of all binary plane trees in T_{n} where three vertices forming a 123-pattern are colored black. We define a map ρ : A_{n} → B_{n} as follows.

Given a tree T ∈ A_{n} with Q_{2}, Q_{1}, Q_{3} being the three black vertices as a 213-pattern, we define ρ(T) be the tree obtained from T by changing the right subtree of Q_{2} to be its left subtree. See Figure 1 for an illustration.

[figure: Q_{1}; Q_{2}; Q_{3}; ⇌; Q_{1}; Q_{2}; Q_{3}; right subtree of Q_{2}; left subtree of Q_{2}]

Figure 1: The bijection ρ.

In the tree ρ(T), the relative positions of Q_{2} and Q_{3} keep the same, and Q_{1} is a left descendant of Q_{2}. Therefore, points Q_{1}Q_{2}Q_{3} form a 123-pattern in ρ(T), and ρ(T) ∈ B_{n}. On the converse, it is routine to verify that changing left subtree of Q_{2} to be its right subtree is the desired reverse map. Therefore, ρ is a bijection between A_{n} and B_{n}.

The initial values for f_{q}(S_{n}(132, 231)) are

1, 8, 40, 160, 560, 1792, …,

and this is essentially the sequence \underline{A001789} in [15].

2.4 Pattern popularity in (132, 312)-avoiding permutations

We first present a lemma as follows:

Lemma 11. There is a bijection φ_{4} between S_{n}(132, 312) and C_{n}.

Proof. For σ ∈ S_{n}(132, 312), let σ_{i_{1}}, σ_{i_{2}}, …, σ_{i_{k}} be the k left-to-right maxima with i_{1} < i_{2} < ⋯ < i_{k}. Then c = (i_{2}−i_{1})+(i_{3}−i_{2})+⋯+(i_{k} −i_{k−1})+(n+1−i_{k}) is a composition of n since i_{1} = 1. On the converse, let n = c_{k} +c_{k−1} +⋯+c_{2} +c_{1} ∈ C_{n}. For 1 ≤ i ≤ k, if c_{i} = 1 then set τ_{i} = n−i+1; otherwise, set m_{i} = c_{1}+⋯+c_{i−1}−i+2 and τ_{i} = n−i+1, m_{i}+c_{i}−2, …, m_{i}+1, m_{i}. It is easy to get σ = τ_{k} τ_{k−1} ⋯ τ_{2} τ_{1} ∈ S_{n}(132, 312).

For example, if 9 = 3 + 1 + 2 + 3, then σ = 6 5 4 7 8 3 9 2 1.

Proposition 12. For n ≥ 3,

f_{123}(n) = ∑_{c_{1}+c_{2}+···+c_{k}=n} ∑_{i=1}^{k−2} c_{i}\binom{k − i}{2}.  (12)

Proof. Let σ = τ_{k} ⋯ τ_{2} τ_{1} be a permutation in S_{n}(132, 312) whose composition is given by n = c_{k} + c_{k−1} + ⋯ + c_{2} + c_{1}. It is evident that, for i + 1 ≤ j ≤ k, the first element in τ_{i} is larger than all the elements in τ_{j}, whereas the other elements in τ_{i} are smaller than that in τ_{j}. Furthermore, the left-to-right maxima form an increasing subsequence and the other elements form a decreasing subsequence. Thus we have c_{i} choices to select one element in τ_{i} to play the role of “1”, and then \binom{i−1}{2} choices to select two left-to-right maxima after τ_{i} to paly the role of “23”. Summing up all the number of 123-patterns in factors τ_{k}, …, τ_{2}, τ_{1} yields that

f_{123}(n) = ∑_{c_{k}+···+c_{2}+c_{1}=n} ∑_{i=3}^{k} c_{i}\binom{i − 1}{2}.

By setting i := k − i + 1 and using the symmetry of the summands in compositions, it is equivalent to formula (12).

Theorem 13. For n ≥ 3, in the set S_{n}(132, 312), we have

f_{123}(n) = f_{321}(n) = \binom{n}{3}2^{n−3},  (13)
f_{213}(n) = f_{231}(n) = \binom{n}{3}2^{n−3}.  (14)

Proof. From Lemma 1, we know that σ ∈ S_{n}(132, 312) ⇔ σ^{c} ∈ S_{n}(132, 312). Hence it is obvious that f_{123}(n) = f_{321}(n) and f_{213}(n) = f_{231}(n) as 123^{c} = 321 and 213^{c} = 231.

To calculate f_{123}(n), by using Proposition 12 and the similar argument in the proof of Theorem 6, we have

f_{123}(n + 1) = 2f_{123}(n) + (n^{2} − n)2^{n−3}.

Formula (13) holds by solving the recurrence with initial value f_{123}(3) = 1, and formula (14) is a direct computation of 2f_{123}(n) + 2f_{213}(n) = \binom{n}{3}2^{n−1}.

We will give a combinatorial interpretation for f_{231}(n) = f_{123}(n). For each σ ∈ S_{n}(132, 312), we construct a binary plane tree T (σ) on n vertices such that each vertex with a right descendant of some vertex does not have a left descendant from the forbiddance of the pattern 312. Let 𝒯_{n} denote the set of such trees on n vertices. Let Q be an occurrence of the pattern 231 in σ ∈ S_{n}(132, 312), and let Q_{2}, Q_{3}, Q_{1} be the three vertices of T (σ) that correspond to Q, going left to right. Then, Q_{2} is a left descendant of Q_{3}, and there exists a lowest ascendant x of Q_{3} or x = Q_{3} so that Q_{1} is a right descendant of x.

Combinatorial proof for f_{231}(n) = f_{123}(n). Let 𝒜_{n} be the set of binary plane trees in 𝒯_{n} in which three vertices forming a 231-pattern are colored black. Let ℬ_{n} be the set of all binary plane trees in 𝒯_{n} in which three vertices forming a 123-pattern are colored black. We define a map ϱ : 𝒜_{n} → ℬ_{n} as follows.

Given a tree T ∈ 𝒜_{n} with Q_{2}, Q_{3}, Q_{1} being the three black vertices forming a 231-pattern, let y be the parent of x if it exists. We can see that x is the left child of y from T ∈ 𝒜_{n}. Let T^{u} := T − T_{x} be the tree obtained from T by deleting the subtree T_{x}, and T^{d} := T_{x} − T_{Q_{1}} be the tree obtained from T_{x} by deleting T_{Q_{1}}. Now we define ϱ(T) to be the tree obtained from T by first adjoining T_{Q_{1}} to the vertex y as its left subtree, then adjoining T^{d} to Q_{1} as its left subtree and keeping all three black vertices the same if y exits; otherwise, we adjoin T^{d} to Q_{1} as its left subtree directly. An illustration is given in Figure 2.

[figure: Q_{2}; Q_{3}; Q_{1}; x; y; ⇒; Q_{2}; Q_{3}; Q_{1}; x; y; T_{u}; ↗; T_{u}; →; T_{d}; ↘; T_{d}; →]

Figure 2: The bijection ϱ.

In the tree ϱ(T), the relative positions of Q_{2} and Q_{3} are unchanged, and Q_{3} is a left descendant of Q_{1}, thus the three black points Q_{2}Q_{3}Q_{1} form a 123-pattern in ϱ(T), and ϱ(T) ∈ ℬ_{n}. It is easy to describe the inverse map and we omit here.

We first introduce a lemma as follows:

Lemma 14. [14, Proposition 13] There is a bijection φ_{5} between S_{n}(132, 321)\{id} and the set of 2-element subsets of [n].

Proof. For a permutation σ ∈ S_{n}(132, 321)\{id}, suppose σ_{k} = m (k < m) and define φ_{5}(σ) = {k, m}. On the converse, given two elements 1 ≤ k < m ≤ n, set τ_{1} = m − k + 1, m − k + 2, …, m − 1, m, τ_{2} = 1, 2, …, m − k and τ_{3} = m + 1, m + 2, …, n − 1, n. We have σ = φ_{5}^{−1}(k, m) = τ_{1} τ_{2} τ_{3}.

For example, if k = 4, m = 6, then σ = 3 4 5 6 1 2 7 8.

Proposition 15. For n ≥ 3,

f_{213}(n) = ∑_{1≤k<m≤n} k(m − k)(n − m),  (15)

f_{312}(n) = ∑_{1≤k<m≤n} k\binom{m − k}{2}.  (16)

Proof. Given a permutation σ = τ_{1} τ_{2} τ_{3} in S_{n}(132, 321) with φ_{5}(σ) = {k, m}, we see that the elements in each τ_{i} (1 ≤ i ≤ 3) are increasing, and τ_{2} < τ_{1} < τ_{3}. Hence we have k choices to select one element in τ_{1} to play the role of “2”, m − k choices to select one element in τ_{2} to play the role of “1”, and n − m choices to select one element in τ_{3} to play the role of “3”. Summing up all possible k and m gives formula (15).

For the pattern 312, we have k choices to select one element in factor τ_{1} to play the role of “3”, and then have \binom{m−k}{2} choices to select two elements in factor τ_{2} to play the role of “12”. Summing up all k and m proves formula (16).

We now derive the exact formulae for the popularity of patterns in S_{n}(132, 321) as follows.

Theorem 16. For n ≥ 3, in the set S_{n}(132, 321), we have

f_{213}(n) = f_{231}(n) = f_{312}(n) = \binom{n + 2}{5},  (17)
f_{123}(n) = n(7n^{4} − 40n^{3} + 85n^{2} − 80n + 28)/120.  (18)

Proof. It is simple to prove f_{312}(n) = f_{231}(n) from Lemma 1 and 312^{−1} = 231. By Proposition 15, we have

f_{312}(n) = ∑_{1≤k<m≤n} k\binom{m − k}{2}

= ∑_{k=1}^{n−1} k ∑_{m=k+1}^{n} \binom{m − k}{2} = ∑_{k=1}^{n−1} k\binom{n − k + 1}{3}

= ∑_{k=1}^{n−1} [(n^{3} − n)k + (1 − 3n^{2})k^{2} + 2nk^{3} − k^{4}] ,

and

f_{213}(n) = ∑_{1≤k<m≤n} k(m − k)(n − m) = ∑_{k=1}^{n−1} ∑_{m=k+1}^{n} k(m − k)(n − m)

= ∑_{k=1}^{n−1} ∑_{m′=1}^{n−k} km′(n − m′ − k) = ∑_{k=1}^{n−1} k(n − k) ∑_{m′=1}^{n−k} m′ − ∑_{k=1}^{n−1} k ∑_{m′=1}^{n−k} m^{′2}

= ∑_{k=1}^{n−1} [(\frac{n^{3}}{6} − \frac{n}{6}) k + (\frac{1}{6} − \frac{n^{2}}{2} ) k^{2} + \frac{n}{2}k^{3} − \frac{1}{6}k^{4}] .

We get formula (17) by substituting the closed forms of ∑_{k=1}^{n} k^{p} (p = 1, 2, 3, 4) into the above expressions, and this theorem holds from 2f_{231}(n) + f_{213}(n) + f_{123}(n) = \binom{n}{3} [\binom{n}{2} + 1].

Notice that f_{213}(n) = f_{231}(n) can be proved by Bóna’s bijection [3] on the set of binary plane trees on n vertices such that the vertex which is a right descendant of some node has no right descendant.

The first few values of f_{q}(S_{n}(132, 321)) for q of length 3 are shown below, and (f_{213}(n))_{n≥3} form sequence \underline{A000389} in [15].

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 1 & 0 & 1 & 1 & 1 & 0 & 6 & 152 & 0 & 56 & 56 & 56 & 0 \\ 4 & 10 & 0 & 6 & 6 & 6 & 0 & 7 & 392 & 0 & 126 & 126 & 126 & 0 \\ 5 & 47 & 0 & 21 & 21 & 21 & 0 & 8 & 868 & 0 & 252 & 252 & 252 & 0 \end{matrix}

3 Triply restricted permutations

This section studies the pattern popularity in the permutations which avoid simultaneously any three patterns of length 3. We begin with the following proposition from [14].

Proposition 17. ([14, Lemma 6]) The numbers of triply restricted permutations in S_{n} satisfy the following equalities:

1. |S_{n}(123, 132, 213)| = |S_{n}(231, 312, 321)| = F_{n+1};

2. |S_{n}(123, 132, 231)| = |S_{n}(123, 213, 312)| = |S_{n}(132, 231, 321)| = |S_{n}(213, 312, 321)| = n;

3. |S_{n}(132, 213, 231)| = |S_{n}(132, 213, 312)| = |S_{n}(132, 231, 312)| = |S_{n}(213, 231, 312)| = n;

4. |S_{n}(123, 132, 312)| = |S_{n}(123, 213, 231)| = |S_{n}(132, 312, 321)| = |S_{n}(213, 231, 321)| = n;

5. |S_{n}(123, 231, 312)| = |S_{n}(132, 213, 321)| = n;

6. |S_{n}(R)| = 0 for all R ⊃ {123, 321} if n ≥ 5, where F_{n} is the Fibonacci number given by F_{0} = 0, F_{1} = 1 and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2.

An argument similar to the one used for doubly restricted permutations shows that we only need to consider the pattern popularity for the first set of class 1 to class 5.

3.1 Pattern popularity in (123, 132, 213)-avoiding permutations

It is well-known that Fibonacci number F_{n+1} counts the number of 0-1 sequences of length n − 1 in which there are no consecutive ones, see [5]. We call such a sequence a Fibonacci binary word for convenience. Let B_{n} denote the set of all Fibonacci binary words of length n. Simion and Schmidt [14] showed that

Lemma 18. ([14, Proposition 15^{∗}]) There is a bijection ψ_{1} between S_{n}(123, 132, 213) and B_{n−1}.

Proof. For w = w_{1}w_{2} ⋯ w_{n−1} ∈ B_{n−1}, we construct the permutation σ as follows. For 1 ≤ i ≤ n − 1, let X_{i} = [n] − {σ_{1}, …, σ_{i−1}}, and set

σ_{i} = {

largest element in X_{i},  if w_{i} = 0,
second largest element in X_{i}, if w_{i} = 1.

Finally, σ_{n} is the unique element in X_{n}.

For example, if w = 01001010, then ψ_{1}(w) = 9 7 8 6 4 5 2 3 1.

Given a word w = w_{1}w_{2} ⋯ w_{n} ∈ B_{n}, the index i (1 ≤ i < n) is an ascent of w if w_{i} < w_{i+1}. Let asc(w) = {i |w_{i} < w_{i+1}} be the set of ascents of w, and let maj(w) = ∑_{i∈asc(w)} i.

Proposition 19. For n ≥ 3,

f_{312}(n) = ∑_{w∈B_{n−1}} maj(w).  (20)

Proof. Suppose σ ∈ S_{n}(123, 132, 213) and ψ_{1}(σ) = w_{1}w_{2} ⋯ w_{n−1}. If k is an ascent of w, then w_{k}w_{k+1} = 01 and σ_{k} > σ_{k+1}. From bijection ψ_{1}, we see that for all i ∈ [n − 1], there is at most one j > i such that σ_{j} > σ_{i}. This implies that σ_{i} > σ_{k+1} for all i < k. Since σ_{k} is the largest element in X_{k}, we have σ_{i} > σ_{j} for all i < k + 1 and j > k + 1. On the other hand, since σ_{k+1} is the second largest element in X_{k+1}, there exists a unique l > k + 1 such that σ_{l} > σ_{k+1}. Thus, we find that σ_{i}σ_{k+1}σ_{l} forms a 312-pattern for all i ≤ k, that is the ascent k will produce k’s copies of 312-pattern in which σ_{k+1} plays the role of “1”. Summing up all the ascents, we derive that the number of copies of 312-pattern in σ is maj(ψ_{1}(σ)).

Recall that the generating function of the Fibonacci number F_{n} is given by

∑_{n≥0} F_{n}x^{n} = \frac{x}{1 − x − x^{2}} .

Hence we can deduce that

∑_{n≥3} F_{n+1}x^{n} = x ∑_{n≥2} F_{n+2}x^{n} = \frac{1}{x} (\frac{x}{1 − x − x^{2}} − x − x^{2} − 2x^{3}) = \frac{x^{3}(3 + 2x)}{1 − x − x^{2}},  (21)

∑_{n≥2} nF_{n+2}x^{n} = x (\frac{x^{2}(3 + 2x)}{1 − x − x^{2}})′ = \frac{x^{2}(6 + 3x − 4x^{2} − 2x^{3})}{(1 − x − x^{2})^{2}},  (22)

∑_{n≥3} \binom{n}{3}F_{n+1}x^{n} = \frac{x^{3}}{6} (∑_{n≥3} F_{n+1}x^{n})′′′ = \frac{x^{3}(3 + 8x + 6x^{2} + 4x^{3})}{(1 − x − x^{2})^{4}}.  (23)

Theorem 20. For n ≥ 3, in the set S_{n}(123, 132, 213), we have

∑_{n≥3} f_{231}(n)x^{n} = ∑_{n≥3} f_{312}(n)x^{n} = \frac{x^{3}(1 + 2x)}{(1 − x − x^{2})^{3}} ,  (24)

∑_{n≥3} f_{321}(n)x^{n} = \frac{x^{3}(1 + 6x + 12x^{2} + 8x^{3})}{(1 − x − x^{2})^{4}}.  (25)

Proof. From Lemma 1, we have f_{231}(n) = f_{312}(n) as σ ∈ S_{n}(123, 132, 213) ⇔ σ^{−1} ∈ S_{n}(123, 132, 213) and 231^{−1} = 312. By Proposition 19, we can write

∑_{n≥3} f_{312}(n)x^{n} = ∑_{n≥3} x^{n} ∑_{w∈B_{n−1}} maj(w) = x ∑_{n≥3} ∑_{w∈B_{n−1}} maj(w)x^{n−1} = xu(x),

where u(x) = ∑_{n≥2} ∑_{w∈B_{n}} maj(w)x^{n}. To calculate u(x), we set

M_{n}(q) = ∑_{w∈B_{n}} q^{maj(w)} and M(x, q) = ∑_{n≥2} M_{n}(q)x^{n}.

It is easy to get

u(x) = \frac{∂M(x, q)}{∂q} |_{q=1} .

Given a word w = w_{1}w_{2} ⋯ w_{n} ∈ B_{n}, if w_{n} = 0, then maj(w) = maj(w_{1}w_{2} ⋯ w_{n−1}); otherwise, w_{n−1}w_{n} = 01 and maj(w) = maj(w_{1}w_{2} ⋯ w_{n−2}) + n − 1. Hence, we have

M_{n}(q) = M_{n−1}(q) + q^{n−1}M_{n−2}(q) for n ≥ 4,

with M_{2}(q) = 2 + q and M_{3}(q) = 2 + q + 2q^{2}. Multiplying the recursion by x^{n} and summing over n ≥ 4 yields that

M(x, q) − (2 + q)x^{2} − (2 + q + 2q^{2})x^{3} = x [M(x, q) − (2 + q)x^{2}] + qx^{2}M(xq, q).

Therefore

(1 − x)M(x, q) = qx^{2}M(xq, q) + (2 + q)x^{2} + 2q^{2}x^{3}.

Differentiate both sides with respect to q, we get

(1 − x)\frac{∂M(x, q)}{∂q} = x^{2} [M(xq, q) + q \frac{∂M(xq, q)}{∂q}] + x^{2} + 4qx^{3}.

Setting q = 1 gives

(1 − x)u(x) = x^{2} [M(x, 1) + \frac{∂M(xq, q)}{∂q} |_{q=1}] + x^{2} + 4x^{3}.

Notice that

M(x, 1) = ∑_{n≥2} |B_{n}|x^{n} = ∑_{n≥2} F_{n+2}x^{n},

and

\frac{∂M(xq, q)}{∂q} |_{q=1} = (∑_{n≥2} ∑_{w∈B_{n}}(n + maj(w))q^{n+maj(w)−1}x^{n}) |_{q=1}

= ∑_{n≥2} x^{n} ∑_{w∈B_{n}}(n + maj(w))

= ∑_{n≥2} nF_{n+2}x^{n} + u(x).

Invoking formulae (21) and (22), this implies that

(1 − x)u(x) = x^{2} [\frac{x^{2}(3 + 2x)}{1 − x − x^{2}} + \frac{x^{2}(6 + 3x − 4x^{2} − 2x^{3})}{(1 − x − x^{2})^{2}} + u(x)] + x^{2} + 4x^{3}.

Therefore, u(x) = x^{2}(1 + 2x)/(1 − x − x^{2})^{3}. Multiplying u(x) by x, we arrive at formula (24). As for formula (25), we notice that

∑_{n≥3} f_{321}(n)x^{n} = ∑_{n≥3} \binom{n}{3}F_{n+1}x^{n} − 2 ∑_{n≥3} f_{312}(n)x^{n}  (26)

from the observation 2f_{312}(n) + f_{321}(n) = \binom{n}{3}F_{n+1}. Thus formula (25) is obtained by substituting equation (23) and the generating function of f_{312}(n) into formula (26).

The first few values of f_{q}(S_{n}(123, 132, 213)) for q of length 3 are shown below, and (f_{231}(n))_{n≥3} form sequence \underline{A152881} in [15].

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 0 & 0 & 0 & 1 & 1 & 1 & 6 & 0 & 0 & 0 & 40 & 40 & 180 \\ 4 & 0 & 0 & 0 & 5 & 5 & 10 & 7 & 0 & 0 & 0 & 95 & 95 & 545 \\ 5 & 0 & 0 & 0 & 15 & 15 & 50 & 8 & 0 & 0 & 0 & 213 & 213 & 1478 \end{matrix}

3.2 Pattern popularity in other triply restricted permutations

This subsection deals with the popularity of length-3 patterns in the other four classes of triply restricted permutations. We begin with a helpful lemma from [14] as follows:

Lemma 21. ([14, Proposition 16^{∗}])We have

σ ∈ S_{n}(123, 132, 231) ⇔ σ = n, n − 1, …, k + 1, k − 1, k − 2, …, 2, 1, k for some k. (27)
σ ∈ S_{n}(132, 213, 231) ⇔ σ = n, n − 1, …, k + 1, 1, 2, 3, …, k − 1, k for some k.  (28)
σ ∈ S_{n}(123, 132, 312) ⇔ σ = n − 1, n − 2, …, k + 1, n, k, k − 1, …, 1 for some k. (29)
σ ∈ S_{n}(123, 231, 312) ⇔ σ = k − 1, k − 2, …, 3, 2, 1, n, n − 1 …, k for some k.  (30)

Appealing to the above structural characterizations, we can derive the pattern popularity in those classes as follows.

Theorem 22. For n ≥ 3, in the set S_{n}(123, 132, 231), we have

f_{213}(n) = f_{312}(n) = \binom{n}{3},  (31)
f_{321}(n) = (n − 2)\binom{n}{3}.  (32)

Proof. According to the structural formula (27), the identity f_{213}(n) = f_{312}(n) can be proved by a direct bijection.

Let q = abc (b < a < c) be a copy of 213-pattern in σ ∈ S_{n}(123, 132, 231). We have σ(n) = c since b < c and σ ∈ S_{n}(123, 132, 231) has only one ascent at position n − 1. Therefore, q is a 213-pattern in the sole permutation

σ = n, n − 1, …, c + 1, c − 1, …, \underline{a}, …, \underline{b}, …, 2, 1, \underline{c}.

For the sake of clarity, we underline the occurrence of the assumed pattern.

For q′ = cba (312-pattern), we find similarly that q′ is a 312-pattern in

σ′ = n, n − 1, …, \underline{c}, …, a + 1, a − 1, …, \underline{b}, …, 2, 1, \underline{a}.

For example, if n = 7 and q = 326, then σ = 7 5 4 \underline{3} \underline{2} 1 \underline{6}, q′ = 623 and σ′ = 7 \underline{6} 5 4 \underline{2} 1 \underline{3}.

Hence, for every copy of 213-pattern (q, σ), there is a unique copy of 312-pattern (q′, σ′), and the converse is also true. This implies that f_{213}(n) = f_{312}(n).

To calculate f_{312}(n), we suppose σ = n, n − 1, …, k + 1, k − 1, k − 2, …, 2, 1, k for some k. We construct a 312-pattern as follows: Choose one element from the first n − k elements to play the role of “3”, then choose one element from the next k − 1 elements to play the role of “1”, and the last element plays the role of “2”. Thus, summing up k gives

f_{312}(n) = ∑_{k=1}^{n}(n − k)(k − 1) = −n^{2} + (n + 1) ∑_{k=1}^{n} k − ∑_{k=1}^{n} k^{2} = \frac{n(n − 1)(n − 2)}{6} = \binom{n}{3}.

The proof is completed by the relation f_{213}(n) + f_{312}(n) + f_{321}(n) = n\binom{n}{3}.

The first few values of f_{q}(S_{n}(123, 132, 231)) for q of length 3 are shown below, and (f_{213}(n))_{n≥3} form sequence \underline{A000292}, (f_{321}(n))_{n≥3} form sequence \underline{A002417} in [15].

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 0 & 0 & 1 & 0 & 1 & 1 & 6 & 0 & 0 & 20 & 0 & 20 & 80 \\ 4 & 0 & 0 & 4 & 0 & 4 & 8 & 7 & 0 & 0 & 35 & 0 & 35 & 175 \\ 5 & 0 & 0 & 10 & 0 & 10 & 30 & 8 & 0 & 0 & 56 & 0 & 56 & 336 \end{matrix}

Theorem 23. For n ≥ 3, in the set S_{n}(132, 213, 231), we have

f_{123}(n) = f_{312}(n) = \binom{n + 1}{4},  (33)
f_{321}(n) = \frac{n(n − 2)(n − 1)^{2}}{12} .  (34)

Proof. Based on structural formula (28), we could also prove f_{123}(n) = f_{312}(n) directly. Let abc be a 123-pattern in

σ = n, n − 1, …, k + 1, 1, …, \underline{a}, a + 1, …, \underline{b}, b + 1, …, c − 1, \underline{c}, c + 1, …, k − 1, k.

Set

σ′ = n, n − 1, …, \underline{n − k + c}, …, c, 1, 2, …, \underline{a}, a + 1, …, \underline{b}, b + 1, …, c − 1.

It is easy to check that (n−k+c) a b is a 312-pattern of σ′. For example, if σ = 9 8 7 1 \underline{2} \underline{3} 4 \underline{5} 6, then σ′ = 9 \underline{8} 7 6 5 1 \underline{2} \underline{3} 4.

To calculate f_{123}(n), we suppose σ = n, n − 1, …, k + 1, 1, 2, …, k − 1, k for some k. A 123-pattern can be obtained by picking three elements from the last k elements to play the role of “123”. Thus, summing up all possible k gives

f_{123}(n) = ∑_{k=1}^{n} \binom{k}{3} = \binom{n + 1}{4}.

We complete the proof from f_{123}(n) + f_{312}(n) + f_{321}(n) = n\binom{n}{3}.

The first few values of f_{q}(S_{n}(132, 213, 231)) for q of length 3 are shown below, and (f_{123}(n))_{n≥3} form sequence \underline{A000332}, (f_{321}(n))_{n≥3} form sequence \underline{A002415} in [15].

\begin{matrix}n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} & n & f_{123} & f_{132} & f_{213} & f_{231} & f_{312} & f_{321} \\ 3 & 1 & 0 & 0 & 0 & 1 & 1 & 6 & 35 & 0 & 0 & 0 & 35 & 50 \\ 4 & 5 & 0 & 0 & 0 & 5 & 6 & 7 & 70 & 0 & 0 & 0 & 70 & 105 \\ 5 & 15 & 0 & 0 & 0 & 15 & 20 & 8 & 126 & 0 & 0 & 0 & 126 & 196 \end{matrix}

Theorem 24. For n ≥ 3, in the set S_{n}(123, 132, 312), we have

f_{213}(n) = f_{231}(n) = \binom{n}{3},  (35)
f_{321}(n) = (n − 2)\binom{n}{3}.  (36)

Proof. In view of the structural formula (29), the equality f_{213}(n) = f_{231}(n) can be proved by a direct correspondence. Let abn be a copy of 213-pattern in

σ = n − 1, …, \underline{a}, a + 1, …, \underline{b}, b + 1, …, k + 1, \underline{n}, k, k − 1, …, 2, 1.

Set

σ′ = n − 1, …, \underline{n − a + b}, …, n − a + k + 1, \underline{n}, n − a + k, n − a + k − 1, …, \underline{n − a}, …, 2, 1.

Then n − a + b, n, n − a is a 231-pattern of σ′. For example, if σ = 8 \underline{7} 6 \underline{5} 4 \underline{9} 3 2 1, then σ′ = σ = 8 \underline{7} 6 \underline{9} 5 4 3 \underline{2} 1.

To calculate f_{213}(n), we suppose that σ = n − 1, n − 2, …, k + 1, n, k, k − 1, …, 2, 1 for some k. A 213-pattern can be obtained by choosing two elements from the first n − k − 1 elements to play the role of “21”, and let n play the role of “3”. Thus, summing up all possible k, we have

f_{213}(n) = ∑_{k=0}^{n−1} \binom{n − k − 1}{2} = \binom{n}{3}.

The proof is completed by using the relation f_{213}(n) + f_{231}(n) + f_{321}(n) = n\binom{n}{3}.

Theorem 25. For n ≥ 3, in the set S_{n}(123, 231, 312), we have

f_{132}(n) = f_{213}(n) = \binom{n + 1}{4},  (37)
f_{321}(n) = \frac{n(n − 2)(n − 1)^{2}}{12} .  (38)

Proof. From Lemma 1, we see that

σ ∈ S_{n}(123, 231, 312) ⇔ σ^{r} ∈ S_{n}(321, 132, 213) ⇔ (σ^{r})^{c} ∈ S_{n}(123, 231, 312).

As a consequence, we have f_{213}(n) = f_{132}(n) from (213^{r})^{c} = 312^{c} = 132.

For f_{213}(n), we will employ the structure in formula (30). Suppose σ = k − 1, k − 2, …, 3, 2, 1, n, n − 1 …, k for some k. A 213-pattern can be obtained as follows: Choose two elements from the first k − 1 elements to play the role of “21”, and choose one element from the last n − k + 1 elements to play the role of “3”. Thus, summing up all possible k, we have

f_{213}(n) = ∑_{k=1}^{n} \binom{k − 1}{2}(n − k + 1) = ∑_{k=0}^{n−1} \binom{k}{2}(n − k) = \binom{n + 1}{4}.

The formula for f_{321}(n) is obtained by the relation 2f_{213}(n) + f_{321}(n) = n\binom{n}{3}.

4 Acknowledgments

The author thanks the anonymous referee and the editor for their helpful comments. This work was supported by the National Natural Science Foundation of China (No. 11401316), the Natural Science Foundation of Jiangsu Province (No. BK20131393) and Program of Natural Science Research of Jiangsu Higher Education Institutions of China (No. 13KJB110019).

References

[1] M. Bóna, A Walk Through Combinatorics, 3rd edition, World Scientific, 2011.

[2] M. Bóna, The absence of a pattern and the occurrences of another, Discrete Math. Theor. Comput. Sci. 12 (2010), 89–102.

[3] M. Bóna, Surprising symmetries in objects counted by Catalan numbers, Electron. J. Combin. 19 (2012), P62.

[4] L. Chua and K. R. Sankary, Equipopularity classes of 132-avoiding permutations, Electron. J. Combin. 21 (2014), P1.59.

[5] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[6] J. Cooper, Combinatorial Problems I like, available at

    http://www.math.sc.edu/~cooper/combprob.html.

[7] T. Dokosa, T. Dwyer, B. P. Johnson, B. E. Sagan, and K. Selsor, Permutation patterns and statistics, Discrete Math. 312 (2012), 2760–2775.

[8] S. Elizalde, Multiple pattern avoidance with respect to fixed points and excedances, Electron. J. Combin. 11 (2004), R51.

[9] C. Homberger, Expected patterns in permutation classes, Electron. J. Combin. 19 (2012), P43.

[10] T. Mansour, Permutations avoiding a pattern from S_{k} and at least two patterns from S_{3}, Ars Combin. 62 (2001), 227–239.

[11] T. Mansour, Permutations containing a pattern exactly once and avoiding at least two patterns of three letters, Ars Combin. 72 (2004), 213–222.

[12] T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Ann. Combin. 6 (2003), 407–418.

[13] K. Rudolph, Pattern popularity in 132-avoiding permutations, Electron. J. Combin. 20 (2013), P8.

[14] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[15] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[16] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15; 05A19. Keywords: permutation, pattern, composition, binary plane tree, Fibonacci number.

(Concerned with sequences \underline{A000292}, \underline{A000332}, \underline{A000337}, \underline{A000389}, \underline{A001789}, \underline{A002415}, \underline{A002417}, \underline{A045618}, \underline{A055580}, \underline{A055581}, \underline{A055586}, and \underline{A152881}.)

Received April 8 2014; revised versions received August 30 2014; September 19 2014; September 22 2014. Published in Journal of Integer Sequences, November 2 2014.

Return to Journal of Integer Sequences home page.