The 1-Box Pattern on Pattern-Avoiding Permutations

Sergey Kitaev Department of Computer and Information Sciences University of Strathclyde Glasgow G1 1XH United Kingdom

            sergey.kitaev@cis.strath.ac.uk

Jeffrey Remmel Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112 USA

                   jremmel@ucsd.edu

Abstract

This paper is continuation of the study of the 1-box pattern in permutations introduced previously by the authors. We derive a two-variable generating function for the distribution of this pattern on 132-avoiding permutations, and then study some of its coefficients providing a link to the Fibonacci numbers. We also find the number of separable permutations with two and three occurrences of the 1-box pattern.

1 Introduction

In this paper, we study 1-box patterns, a particular case of (a, b)-rectangular patterns introduced in [7]. That is, let σ = σ_{1} ⋯ σ_{n} be a permutation written in one-line notation. Then

Figure 1: The graph of σ = 471569283.

we will consider the graph of σ, G(σ), to be the set of points (i, σ_{i}) for i = 1, …, n. For example, the graph of the permutation σ = 471569283 is pictured in Figure 1.

Then if we draw a coordinate system centered at a point (i, σ_{i}), we will be interested in the points that lie in the 2a×2b rectangle centered at the origin. That is, the (a, b)-rectangle pattern centered at (i, σ_{i}) equals the set of points (i ± r, σ_{i} ± s) such that r ∈ {0, …, a} and s ∈ {0, …, b}. Thus σ_{i} matches the (a, b)-rectangle pattern in σ if there is at least one point in the 2a × 2b-rectangle centered at the point (i, σ_{i}) in G(σ) other than (i, σ_{i}). For example, when we look for matches of the (2,3)-rectangle patterns, we would look at 4 × 6 rectangles centered at the point (i, σ_{i}) as pictured in Figure 2.

Figure 2: The 4 × 8-rectangle centered at the point (4, 5) in the graph of σ = 471569283.

We shall refer to the (k, k)-rectangle pattern as the k-box pattern. For example, if σ = 471569283, then the 2-box centered at the point (4, 5) in G(σ) is the set of circled points pictured in Figure 3. Hence, σ_{i} matches the k-box pattern in σ, if there is at least one point in the k-box centered at the point (i, σ_{i}) in G(σ) other than (i, σ_{i}). For example, σ_{4} matches the pattern k-box for all k ≥ 1 in σ = 471569283 since the point (5, 6) is present in the k-box centered at the point (4, 5) in G(σ) for all k ≥ 1. However, σ_{3} only matches the k-box pattern in σ = 471569283 for k ≥ 3 since there are no points in 1-box or 2-box centered at (3, 1) in G(σ), but the point (1, 4) is in the 3-box centered at (3, 1) in G(σ). For k ≥ 1, we let k-box(σ) denote the set of all i such that σ_{i} matches the k-box pattern in σ = σ_{1} ⋯ σ_{n}.

Figure 3: The 2-box centered at the point (4, 5) in the graph of σ = 471569283.

Note that σ_{i} matches the 1-box pattern in σ if either |σ_{i} − σ_{i+1}| = 1 or |σ_{i−1} − σ_{i}| = 1. For example, the distribution of 1-box(σ) for S_{2}, S_{3}, and S_{4} is given below, where S_{n} is the set of all permutations of length n.

\begin{matrix}σ & 1-box(σ) \\ 12 & 2 \\ 21 & 2 \end{matrix}  \begin{matrix}σ & 1-box(σ) \\ 123 & 3 \\ 132 & 2 \\ 213 & 2 \\ 231 & 2 \\ 312 & 2 \\ 321 & 3 \end{matrix}

\begin{matrix}σ & 1-box(σ) & σ & 1-box(σ) \\ 1234 & 4 & 2134 & 4 \\ 1243 & 4 & 2143 & 4 \\ 1324 & 2 & 2314 & 2 \\ 1342 & 2 & 2341 & 3 \\ 1423 & 2 & 2413 & 0 \\ 1432 & 3 & 2431 & 2 \\ 3124 & 2 & 4123 & 3 \\ 3142 & 0 & 4132 & 2 \\ 3214 & 3 & 4213 & 2 \\ 3241 & 2 & 4231 & 2 \\ 3412 & 4 & 4312 & 4 \\ 3421 & 4 & 4321 & 4 \end{matrix}

The notion of k-box patterns is related to the mesh patterns introduced by Brändén and Claesson [2] to provide explicit expansions for certain permutation statistics as, possibly infinite, linear combinations of (classical) permutation patterns. This notion was further studied in [1, 4, 5, 8, 9, 10, 14]. In particular, Kitaev and Remmel [5] initiated the systematic study of distribution of marked mesh patterns on permutations, and this study was extended to 132-avoiding permutations by Kitaev, Remmel, and Tiefenbruck in [8, 9, 10].

In this paper, we shall study the distribution of the 1-box pattern in 132-avoiding permutations and separable permutations. Given a sequence σ = σ_{1} ⋯ σ_{n} of distinct integers, let red(σ) be the permutation found by replacing the i-th largest integer that appears in σ by i. For example, if σ = 2754, then red(σ) = 1432. Given a permutation τ = τ_{1} ⋯ τ_{j} in the symmetric group S_{j}, we say that the pattern τ occurs in σ = σ_{1} … σ_{n} ∈ S_{n} provided there exists 1 ≤ i_{1} < ⋯ < i_{j} ≤ n such that red(σ_{i_{1}} ⋯ σ_{i_{j}}) = τ. We say that a permutation σ avoids the pattern τ if τ does not occur in σ. In particular, a permutation σ avoids the pattern 132 if σ does not contain a subsequence of three elements, where the first element is the smallest one, and the second element is the largest one. Let S_{n}(τ) denote the set of permutations in S_{n} which avoid τ. In the theory of permutation patterns (see [3] for a comprehensive introduction to the area), τ is called a classical pattern. The results in this paper can be viewed as another contribution to the long line of research in the literature which studies various distributions on pattern-avoiding permutations (see [3, Chapter 6.1.5] for an overview of relevant results, and [11, 12] for particular papers in this research direction).

The outline of this paper is as follows. In Section 2 we shall study the distribution of the 1-box pattern in 132-avoiding permutations. In particular, we shall derive explicit formulas for the generating functions

A(t, x) = ∑_{n≥0} A_{n}(x)t^{n},

B(t, x) = ∑_{n≥1} B_{n}(x)t^{n}, and

E(t, x) = ∑_{n≥1} E_{n}(x)t^{n},

where A_{0}(x) = 1 and for n ≥ 1,

A_{n}(x) = ∑_{σ∈S_{n}(132)} x^{1-box(σ)}
B_{n}(x) = ∑_{σ=σ_{1}···σ_{n}∈S_{n}(132) and σ_{1}=n} x^{1-box(σ)}, and
E_{n}(x) = ∑_{σ=σ_{1}···σ_{n}∈S_{n}(132) and σ_{n}=n} x^{1-box(σ)}.

In Section 3, we shall study the coefficients of x^{k} in the polynomials A_{n}(x), B_{n}(x), and E_{n}(x) for k ∈ {0, 1, 2, 3, 4} as well as the coefficient of the highest power of x in these polynomials. Many of these coefficients can be expressed in terms of the Fibonacci numbers F_{n}. For example, for n ≥ 2, the coefficient of x^{2} in A_{n}(x) is F_{n} and the coefficient of x^{2} in B_{n}(x) and E_{n}(x) is F_{n−2}. Finally, in Section 4, we shall study the 1-box pattern on separable permutations.

2 Distribution of the 1-box pattern on 132-avoiding permutations

In this section, we shall study the generating functions A(t, x), B(t, x), and E(t, x). Clearly, A_{1}(x) = B_{1}(x) = E_{1}(x) = 1. One can see from our tables for S_{2}, S_{3}, and S_{4} that A_{2}(x) = 2x^{2}, A_{3}(x) = 3x^{2} + 2x^{3}, and A_{4}(x) = 5x^{2} + 3x^{3} + 6x^{4}. Similarly, one can check that B_{2}(x) = E_{2}(x) = x^{2}, B_{3}(x) = E_{3}(x) = x^{2} + x^{3}, and B_{4}(x) = E_{4}(x) = 2x^{2} + x^{3} + 2x^{4}.

We shall classify the 132-avoiding permutations σ = σ_{1} ⋯ σ_{n} by position of n in σ. That is, let S_{n}^{(i)}(132) denote the set of σ ∈ S_{n}(132) such that σ_{i} = n. Clearly each σ ∈ S_{n}^{(i)}(132) has the structure pictured in Figure 4. That is, in the graph of σ, the elements to the left of n, A_{i}(σ), have the structure of a 132-avoiding permutation, the elements to the right of n, B_{i}(σ), have the structure of a 132-avoiding permutation, and all the elements in A_{i}(σ) lie above all the elements in B_{i}(σ). Note that the number of 132-avoiding permutations in S_{n} is the Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}, which is a well-known fact, and the generating function for the C_{n}’s is given by

C(t) = ∑_{n≥0} C_{n}t^{n} = \frac{1 − \sqrt{1 − 4t}}{2t} = \frac{2}{1 + \sqrt{1 − 4t}}.

Figure 4: The structure of 132-avoiding permutations.

The following lemma establishes relations among A_{n}(x), B_{n}(x), and E_{n}(x).

Lemma 1. For all n ≥ 1, B_{n}(x) = E_{n}(x) and for n ≥ 4,

B_{n}(x) = x^{n} + (A_{n−1}(x) − B_{n−1}(x)) + ∑_{i=2}^{n−2} x^{n−i}(A_{i}(x) − B_{i}(x)).  (1)

For n ≥ 2,

A_{n}(x) = B_{n}(x) + ∑_{i=2}^{n} B_{i}(x)A_{n−i}(x).  (2)

Proof. We begin with deriving relationships for B_{n}(x) and E_{n}(x). Any 132-avoiding permutation π = π_{1} ⋯ π_{n} beginning with the largest letter n is of one of the three forms described below:

1. the decreasing permutation n(n − 1) ⋯ 1;

2. nℓπ_{3}π_{4} ⋯ π_{n} where ℓ < n − 1 and ℓπ_{3}π_{4} ⋯ π_{n} is a 132-avoiding permutation on {1, …, n − 1};

3. n(n−1) ⋯ (n−i+1)ℓπ_{i+2}π_{i+3} ⋯ π_{n}, where 2 ≤ i ≤ n−2, ℓ < n−i and ℓπ_{i+2}π_{i+3} ⋯ π_{n} is a 132-avoiding permutation on {1, …, n − i}.

This structural observation implies immediately (1). Indeed, in the decreasing permutation each element is an occurrence of the 1-box pattern thus giving a contribution of x^{n} to the function B_{n}(x). Also, in the second case, n is not an occurrence of the 1-box pattern in π and it does not effect whether any of the remaining elements in π are occurrences of the 1box pattern in π. Thus, in this case we have a contribution of (A_{n−1}(x)−B_{n−1}(x)) to B_{n}(x). Finally, in the last case, for any i, 2 ≤ i ≤ n−2, each of the elements n−i+1, n−i+2, …, n is an occurrence of the 1-box pattern in π and these elements do not effect whether any of the remaining elements in π are occurrences of the 1-box pattern in π. Thus, in this case we have a contribution of ∑_{i=2}^{n−2} x^{n−i}(A_{i}(x) − B_{i}(x)) to B_{n}(x).

We can use similar methods to prove that for all n ≥ 4,

E_{n}(x) = x^{n} + (A_{n−1}(x) − E_{n−1}(x)) + ∑_{i=2}^{n−2} x^{n−i}(A_{i}(x) − E_{i}(x)).  (3)

That is, if π is a 132-avoiding permutation in S_{n} that ends in n, we have the following three cases:

1. π is the increasing permutation 1 ⋯ n;

2. π = π_{1} ⋯ π_{n−2}ℓn where ℓ < n − 1 and π_{1} ⋯ π_{n−2}ℓ is a 132-avoiding permutation on {1, …, n − 1};

3. π_{1} ⋯ π_{n−i−1}ℓ(n−i+1)(n−i+2) ⋯ n, where 2 ≤ i ≤ n−2, ℓ < n−i and π_{1} ⋯ π_{n−i−1}ℓ is a 132-avoiding permutation on {1, …, n − i}.

Arguing as above, we see that the identity permutations contributes x^{n} to E_{n}(x), the elements in case (2) contribute A_{n−1}(x) − E_{n−1}(x) to E_{n}(x), and the elements in case (3) contribute ∑_{i=2}^{n−2} x^{n−i}(A_{i}(x) − E_{i}(x)) to E_{n}(x).

Given that we have computed that B_{n}(x) = E_{n}(x) for 1 ≤ n ≤ 3, one can easily use (1) and (3) to prove that B_{n}(x) = E_{n}(x) for all n ≥ 1 by induction.

To prove (2), note that S_{n}(132) = S_{n}^{(1)}(132) ∪ S_{n}^{(n)}(132) ∪_{2≤i≤n−1} S_{n}^{(i)}(132). Clearly, the permutations in S_{n}^{(1)}(132) contribute B_{n}(x) to A_{n}(x) and the permutations in S_{n}^{(n)}(132) contribute E_{n}(x) to A_{n}(x). Now suppose that 2 ≤ i ≤ n and π = π_{1} ⋯ π_{n} ∈ S_{n}^{(i)}(132). Then all the elements in π_{1} ⋯ π_{i−1} are strictly greater than all the elements in π_{i+1} ⋯ π_{n}. It follows that π_{i+1} ≤ n − 2. Hence the elements π_{1} ⋯ π_{i−1}n have no effect as to whether any of the elements in π_{i+1} ⋯ π_{n} are occurrences of the 1-box pattern in π. Hence the elements S_{n}^{(i)}(132) contribute E_{i}(x)A_{n−i}(x) to A_{n}(x). Thus for all n ≥ 2,

A_{n}(x) = B_{n}(x) + E_{n}(x) + ∑_{i=2}^{n} E_{i}(x)A_{n−i}(x).  (4)

It is easy to see that since B_{n}(x) = E_{n}(x) for all n ≥ 1, (4) implies (2).

The following theorem gives the generating function for the entire distribution of the 1-box pattern over 132-avoiding permutations.

Theorem 2. We have

A(t, x) = \frac{1 + t + t^{2} − tx − t^{2}x − t^{3}x + t^{3}x^{2} − \sqrt{F (t, x)}}{2(t(1 − xt) + x^{2}t^{2})}  (5)

where F (t, x) = (1+t+t^{2} −tx−t^{2}x−t^{3}x+t^{3}x^{2})^{2} +4((1+t)(1−xt)+x^{2}t^{2})(t(1−xt)+x^{2}t^{2}). Also,

B(t, x) = E(t, x) = \frac{t(1 − xt) + x^{2}t^{2}}{(1 + t)(1 − xt) + x^{2}t^{2}} A(t, x).

Proof. Multiplying both parts of (2) by t^{n} and summing over all n ≥ 2 we obtain

A(t, x) − (1 + t) = (B(t, x) − t) + (B(t, x) − t)A(t, x).

Solving for A(t, x), we obtain that

A(t, x) = \frac{1 + B(t, x)}{1 + t − B(t, x)}.  (6)

Now multiplying both parts of (1) by t^{n} and summing over all n ≥ 2 we obtain

B(t, x) − (t + x^{2}t^{2} + (x^{2} + x^{3})t^{3}) = \frac{x^{4}t^{4}}{1 − xt} + t(A(t, x) − (1 + t + 2x^{2}t^{2}))

−t(B(t, x) − (t + x^{2}t^{2})) + \frac{x^{2}t^{2}}{1 − xt} ((A(t, x) − (1 + t)) − (B(t, x) − t)) .

Solving for B(t, x), we obtain that

B(t, x) = \frac{t(1 − xt) + x^{2}t^{2}}{(1 + t)(1 − xt) + x^{2}t^{2}} A(t, x).  (7)

Combining (6) and (7), we see that A(t, x) satisfies the following quadratic equation

(t(1−xt)+x^{2}t^{2})A^{2}(t, x)−(1+t+t^{2} −tx−t^{2}x−t^{3}x+t^{3}x^{2})A(t, x)+(1+t)(1−xt)+x^{2}t^{2} = 0

which can be solved to yield (5).

We used Mathematica to find the first few terms of A(t, x) and B(t, x) = E(t, x). That is, we have that

A(t, x) = 1 + t + 2x^{2}t^{2} + x^{2}(3 + 2x)t^{3} + x^{2} (5 + 3x + 6x^{2}) t^{4} + x^{2} (8 + 5x + 19x^{2} + 10x^{3}) t^{5} +
x^{2} (13 + 8x + 50x^{2} + 35x^{3} + 26x^{4}) t^{6} + x^{2} (21 + 13x + 119x^{2} + 95x^{3} + 127x^{4} + 54x^{5}) t^{7} +
x^{2} (34 + 21x + 265x^{2} + 230x^{3} + 451x^{4} + 295x^{5} + 134x^{6}) t^{8} +
x^{2} (55 + 34x + 564x^{2} + 517x^{3} + 1373x^{4} + 1118x^{5} + 895x^{6} + 306x^{7}) t^{9} +
x^{2} (89 + 55x + 1160x^{2} + 1107x^{3} + 3790x^{4} + 3548x^{5} + 4010x^{6} + 2283x^{7} + 754x^{8}) t^{10} + · · · .

and

B(t, x) = E(t, x)
= t + x^{2}t^{2} + x^{2}(1 + x)t^{3} + x^{2} (2 + x + 2x^{2}) t^{4} +
x^{2} (3 + 2x + 6x^{2} + 3x^{3}) t^{5} + x^{2} (5 + 3x + 16x^{2} + 11x^{3} + 7x^{4}) t^{6} +
x^{2} (8 + 5x + 39x^{2} + 30x^{3} + 36x^{4} + 14x^{5}) t^{7} +
x^{2} (13 + 8x + 88x^{2} + 75x^{3} + 131x^{4} + 81x^{5} + 33x^{6}) t^{8} +
x^{2} (21 + 13x + 190x^{2} + 171x^{3} + 410x^{4} + 319x^{5} + 233x^{6} + 73x^{7}) t^{9} +
x^{2} (34 + 21x + 395x^{2} + 372x^{3} + 1156x^{4} + 1044x^{5} + 1087x^{6} + 579x^{7} + 174x^{8}) t^{10} + · · · .

3 Properties of coefficients of A_{n}(x) and B_{n}(x) = E_{n}(x)

In this section, we shall explain several of the coefficients of the polynomials A_{n}(x) and B_{n}(x) = E_{n}(x) and show their connections with the Fibonacci numbers.

In Subsection 3.1, we study the coefficients of x^{k} in the the polynomials A_{n}(x) and B_{n}(x) = E_{n}(x) for k ∈ {0, 1, 2, 3, 4} and, in Subsection 3.2, we derive the generating functions for the highest coefficients for these polynomials.

3.1 The four smallest coefficients and the Fibonacci numbers

Clearly the coefficient of x in either A_{n}(x), B_{n}(x), or E_{n}(x) is 0 by the definition of an occurrence of the 1-box pattern. The following theorem states that for n ≥ 2, each 132avoiding permutation of length n has at least two occurrences of the 1-box pattern. In what follows, we need the notion of the celebrated n-th Fibonacci number F_{n} defined as F_{0} = F_{1} = 1 and, for n ≥ 2, F_{n} = F_{n−1} + F_{n−2}. Also, for a polynomial P (x), we let P (x)|_{x^{m}} denote the coefficient of x^{m}.

Theorem 3. For n ≥ 2, A_{n}(x)|_{x^{0}} = B_{n}(x)|_{x^{0}} = E_{n}(x)|_{x^{0}} = 0.

Proof. Clearly, it is enough to prove the claim for A_{n}(x). We proceed by induction on n. The claim is clearly true for n = 2. Next suppose that n ≥ 3 and σ = S_{n}(132). From the structure of 132-avoiding permutations presented in Figure 4, either A_{i}(σ) is empty in which case B_{i}(σ) has at least two elements and it contains an occurrence of the 1-box pattern by the induction hypothesis, or A_{i}(σ) has a single element n − 1 leading to two occurrence of the pattern formed by n and n − 1, or A_{i}(σ) has at least two elements and we apply the induction hypothesis to it.

Theorem 4. For n ≥ 2, A_{n}(x)|_{x^{2}} = F_{n} and B_{n}(x)|_{x^{2}} = E_{n}(x)|_{x^{2}} = F_{n−2}.

Proof. We proceed by induction on n. Note that A_{2}(x)|_{x^{2}} = 2 = F_{2} and B_{2}(x)|_{x^{2}} = E_{2}(x)|_{x^{2}} = 1 = F_{0}. Similarly, A_{3}(x)|_{x^{2}} = 3 = F_{3} and B_{3}(x)|_{x^{2}} = E_{3}(x)|_{x^{2}} = 1 = F_{1}. Thus our claim holds for n = 2 and n = 3.

For n ≥ 4, it follows from (1) and Theorem 3 that

B_{n}(x)|_{x^{2}} = x^{n}|_{x^{2}} + (A_{n−1}(x)|_{x^{2}} − B_{n−1}(x)|_{x^{2}}) + ∑_{i=2}^{n−2}(x^{n−i}(A_{i}(x) − B_{i}(x)))|_{x^{2}}
= A_{n−1}(x)|_{x^{2}} − B_{n−1}(x)|_{x^{2}} + (A_{n−2}(x) − B_{n−2}(x))|_{x^{0}}
= F_{n−1} − F_{n−3} = F_{n−2}.

But then by (2), we have that

A_{n}(x)|_{x^{2}} = B_{n}(x)|_{x^{2}} + ∑_{i=2}^{n}(B_{i}(x)A_{n−i}(x))|_{x^{2}}.  (8)

Note that since n ≥ 4 and 2 ≤ i ≤ n

(B_{i}(x)A_{n−i}(x))|_{x^{2}} = (B_{i}(x)|_{x^{0}})(A_{n−i}(x))|_{x^{2}}) + (B_{i}(x)|_{x^{1}})(A_{n−i}(x))|_{x^{1}}) +
(B_{i}(x)|_{x^{2}})(A_{n−i}(x))|_{x^{0}})
= (B_{i}(x)|_{x^{2}})(A_{n−i}(x))|_{x^{0}})

since B_{i}(x)|_{x^{1}} = A_{n−i}(x)|_{x^{1}} = 0 for i ≥ 1 and B_{i}(x)|_{x^{0}} = 0 for i ≥ 2. But then since A_{i}(x)|_{x^{0}} = 0 for i ≥ 2 and A_{i}(x)|_{x^{0}} = 1 for i = 0, 1, it follows that (8) reduces to

A_{n}(x)|_{x^{2}} = B_{n}(x)|_{x^{2}} + B_{n}(x)|_{x^{2}} + B_{n−1}(x)|_{x^{2}}
= F_{n−2} + F_{n−2} + F_{n−3} = F_{n−2} + F_{n−1} = F_{n}.

Corollary 5. For n ≥ 2, the number of 132-avoiding permutations of length n that do not begin (resp. end) with n and contain exactly two occurrences of the 1-box pattern is F_{n−1}.

Proof. A proof is straightforward from Theorem 4, since

A_{n}(x)|_{x^{2}} − B_{n}(x)|_{x^{2}} = A_{n}(x)|_{x^{2}} − E_{n}(x)|_{x^{2}} = F_{n−1}.

Theorem 6. For n ≥ 3, A_{n}(x)|_{x^{3}} = F_{n−1} and B_{n}(x)|_{x^{3}} = E_{n}(x)|_{x^{3}} = F_{n−3}.

Proof. We proceed by induction on n, the length of permutations, and the formulas (1) and (2). Note that we have computed that A_{3}(x)|_{x^{3}} = 2 = F_{2}, A_{4}(x)|_{x^{3}} = 3 = F_{3}, B_{3}(x)|_{x^{3}} = E_{3}(x)|_{x^{3}} = 1 = F_{0}, and B_{4}(x)|_{x^{3}} = E_{4}(x)|_{x^{3}} = 1 = F_{1}. Thus our claim holds for n = 3 and n = 4.

For n ≥ 5, it follows from (1) and Theorem 3 that

B_{n}(x)|_{x^{3}} = x^{n}|_{x^{3}} + (A_{n−1}(x)|_{x^{3}} − B_{n−1}(x)|_{x^{3}}) + ∑_{i=2}^{n−2}(x^{n−i}(A_{i}(x) − B_{i}(x)))|_{x^{3}}
= A_{n−1}(x)|_{x^{3}} − B_{n−1}(x)|_{x^{3}} + (A_{n−2}(x) − B_{n−2}(x))|_{x^{1}} + (A_{n−3}(x) − B_{n−3}(x))|_{x^{0}}
= F_{n−2} − F_{n−4} = F_{n−3}.

But then by (2), we have that

A_{n}(x)|_{x^{3}} = B_{n}(x)|_{x^{3}} + ∑_{i=2}^{n}(B_{i}(x)A_{n−i}(x))|_{x^{3}}.  (9)

Note that since n ≥ 5 and 2 ≤ i ≤ n,

(B_{i}(x)A_{n−i}(x))|_{x^{3}} = (B_{i}(x)|_{x^{0}}) + (A_{n−i}(x)|_{x^{3}})(B_{i}(x)|_{x^{1}})(A_{n−i}(x)|_{x^{2}}) +
(B_{i}(x)|_{x^{2}})(A_{n−i}(x)|_{x^{1}}) + (B_{i}(x)|_{x^{3}})(A_{n−i}(x)|_{x^{0}})
= (B_{i}(x)|_{x^{3}})(A_{n−i}(x)|_{x^{0}})

since B_{i}(x)|_{x^{1}} = A_{n−i}(x)|_{x^{1}} = 0 for i ≥ 1 and B_{i}(x)|_{x^{0}} = 0 for i ≥ 2. But then since A_{i}(x)|_{x^{0}} = 0 for i ≥ 2 and A_{i}(x)|_{x^{0}} = 1 for i = 0, 1, it follows that (9) reduces to

A_{n}(x)|_{x^{3}} = B_{n}(x)|_{x^{3}} + B_{n}(x)|_{x^{3}} + B_{n−1}(x)|_{x^{3}}
= F_{n−3} + F_{n−3} + F_{n−4} = F_{n−3} + F_{n−2} = F_{n−1}.

Corollary 7. For n ≥ 3, the number of 132-avoiding permutations of length n that do not begin (resp. end) with n and contain exactly three occurrences of the 1-box pattern is F_{n−2}.

Proof. A proof is straightforward from Theorem 6, since

A_{n}(x)|_{x^{3}} − B_{n}(x)|_{x^{3}} = A_{n}(x)|_{x^{3}} − E_{n}(x)|_{x^{3}} = F_{n−2}.

Regarding the number of 132-avoiding permutations with exactly four occurrences of the 1-box pattern, we can derive the following recurrence relations involving the Fibonacci numbers.

Theorem 8. We have that for n ≤ 3, A_{n}(x)|_{x^{4}} = B_{n}(x)|_{x^{4}} = E_{n}(x)|_{x^{4}} = 0, B_{4}(x)|_{x^{4}} = 2, B_{5}(x)|_{x^{4}} = 6, and for n ≥ 4,

A_{n}(x)|_{x^{4}} = 2B_{n}(x)|_{x^{4}} + B_{n−1}(x)|_{x^{4}} + ∑_{i=2}^{n−2} F_{i−2}F_{n−i};  (10)

while for n ≥ 6,

B_{n}(x)|_{x^{4}} = B_{n−1}(x)|_{x^{4}} + B_{n−2}(x)|_{x^{4}} + F_{n−1} + ∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}.  (11)

Proof. The initial conditions follow from the expansions of A(t, x) and B(t, x) given above. By (2), we have that

A_{n}(x)|_{x^{4}} = B_{n}(x)|_{x^{4}} + ∑_{i=2}^{n}(B_{i}(x)A_{n−i}(x))|_{x^{4}}.  (12)

Note that since n ≥ 4 and 2 ≤ i ≤ n,

(B_{i}(x)A_{n−i}(x))|_{x^{4}} = (B_{i}(x)|_{x^{0}})(A_{n−i}(x)|_{x^{4}}) + (B_{i}(x)|_{x^{1}})(A_{n−i}(x)|_{x^{3}}) +
(B_{i}(x)|_{x^{2}})(A_{n−i}(x)|_{x^{2}}) + (B_{i}(x)|_{x^{3}})(A_{n−i}(x)|_{x^{1}}) +
(B_{i}(x)|_{x^{4}})(A_{n−i}(x)|_{x^{0}})
= (B_{i}(x)|_{x^{2}})(A_{n−i}(x)|_{x^{2}}) + (B_{i}(x)|_{x^{4}})(A_{n−i}(x)|_{x^{0}})

since B_{i}(x)|_{x^{1}} = A_{n−i}(x)|_{x^{1}} = 0 for i ≥ 1 and B_{i}(x)|_{x^{0}} = 0 for i ≥ 2. But then since A_{i}(x)|_{x^{0}} = 0 for i ≥ 2 and A_{i}(x)|_{x^{0}} = 1 for i = 0, 1, (12) reduces to

A_{n}(x)|_{x^{4}} = B_{n}(x)|_{x^{4}} + B_{n}(x)|_{x^{4}} + B_{n−1}(x)|_{x^{4}} + ∑_{i=2}^{n−2} (B_{i}(x)|_{x^{2}}) (A_{n−i}(x)|_{x^{2}}) .

Then we can apply Theorem 4 to obtain (10).

Let n ≥ 6. From (1),

B_{n}(x)|_{x^{4}} = (A_{n−1}(x)|_{x^{4}} − B_{n−1}(x)|_{x^{4}}) + (A_{n−2}(x)|_{x^{2}} − B_{n−2}(x)|_{x^{2}}) ,

since only the term corresponding to i = n − 2 from the sum contributes to x^{4}. Applying (10) and Theorem 4, we obtain

B_{n}(x)|_{x^{4}} = (2B_{n−1}(x)|_{x^{4}} + B_{n−2}(x)|_{x^{4}} + ∑_{i=2}^{n−3} F_{i−2}F_{n−1−i}) − B_{n−1}(x)|_{x^{4}} + F_{n−2} − F_{n−4}

= B_{n−1}(x)|_{x^{4}} + B_{n−2}(x)|_{x^{4}} + F_{n−3} + F_{n−4} + F_{n−2} − F_{n−4} + ∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}

= B_{n−1}(x)|_{x^{4}} + B_{n−2}(x)|_{x^{4}} + F_{n−1} + ∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}.

Note that B_{5}(x)|_{x^{4}} = 6, B_{4}(x)|_{x^{4}} = 2, B_{3}(x)|_{x^{4}} = 0, and F_{4} = 5 so that (11) does not hold for n = 5.

We can use Theorem 8 to find the generating functions for A_{n}(x)|_{x^{4}} and B_{n}(x)|_{x^{4}}. That is, let

𝔸_{4}(t) = ∑_{n≥4}(A_{n}(x)|_{x^{4}})t^{n}

and

𝔹_{4}(t) = ∑_{n≥4}(B_{n}(x)|_{x^{4}})t^{n}.

Then we have the following theorem.

Theorem 9.

𝔸_{4}(t) = \frac{t^{4}(6 + t − 7t^{2} − t^{3} + 3t^{4} + t^{5})}{(1 − t − t^{2})^{3}}  (13)

and

𝔹_{4}(t) = \frac{t^{4}(2 − t^{2} + t^{3} + t^{4})}{(1 − t − t^{2})^{3}}.  (14)

Proof. First observe that

∑_{n≥7} (∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}) t^{n} = t^{3} ∑_{n≥7} (∑_{j=2}^{n−5} F_{j}F_{n−3−j}) t^{n−3}

= t^{3} ∑_{n≥4} (∑_{j=2}^{n−2} F_{j}F_{n−j}) t^{n}

= t^{3} (∑_{j≥2} F_{j}t^{j})^{2} .

Using the fact that ∑_{n≥0} F_{n}t^{n} = \frac{1}{1−t−t^{2}} , it follows that

∑_{n≥7} (∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}) t^{n} = t^{3} (\frac{1}{1 − t − t^{2}} − (1 + t))^{2}

= t^{3} \frac{(t^{2}(2 + t))^{2}}{(1 − t − t^{2})^{2}} = \frac{(2 + t)^{2}t^{7}}{(1 − t − t^{2})^{2}} .

Next observe that

∑_{n≥6} F_{n−1}t^{n} = t (\frac{1}{1 − t − t^{2}} − (1 + t + 2t^{2} + 3t^{3} + 5t^{4})) = \frac{(8 + 5t)t^{5}}{1 − t − t^{2}} .

Let H(t) = ∑_{n≥6} H_{n}t^{n}, where H_{n} = ∑_{n≥6} F_{n−1}t^{n} + ∑_{n≥7} (∑_{i=4}^{n−3} F_{i−2}F_{n−1−i}) t^{n}. Then

H(t) = \frac{(2 + t)^{2}t^{7}}{(1 − t − t^{2})^{2}} + \frac{(8 + 5t)t^{5}}{1 − t − t^{2}}
= \frac{(8 + t − 9t^{2} − 4t^{3})t^{6}}{(1 − t − t^{2})^{2}} .

Here we use Mathematica to simplify the last expression.

We can now rewrite (11) as

B_{n}(x)|x^{4} = B_{n−1}(x)|_{x^{4}} + B_{n−2}(x)|_{x^{4}} + H_{n}  (15)

for n ≥ 6. Multiplying both sides of (15) by t^{n} and summing for n ≥ 6, we see that

𝔹_{4}(t) − 2t^{4} − 6t^{5} = t(𝔹_{4}(t) − 2t^{4}) + t^{2}𝔹_{4}(t) + H(t).

Solving for 𝔹_{4}(t) and using Mathematica, we obtain that

𝔹_{4}(t) = \frac{t^{4}(2 − t^{2} + t^{3} + t^{4})}{(1 − t − t^{2})^{3}}.

Next observe that

∑_{n≥4} (∑_{i=2}^{n−2} F_{i−2}F_{n−i}) t^{n} = ∑_{n≥4} (∑_{j=0}^{n−4} F_{j}F_{n−2−j}) t^{n}

= t^{2} ∑_{n≥4} (∑_{j=0}^{n−4} F_{j}F_{n−2−j}) t^{n−2}

= t^{2} (∑_{j≥0} F_{j}t^{j}) (∑_{j≥0} F_{j}t^{j} − (1 + t))

= \frac{(2 + t)t^{4}}{(1 − t − t^{2})^{2}} .

Thus

G(t) = ∑_{n≥5} G_{n}t^{n} = ∑_{n≥5} (∑_{i=2}^{n−2} F_{i−2}F_{n−i}) t^{n}

= \frac{(2 + t)t^{4}}{(1 − t − t^{2})^{2}} − 2t^{4}
= \frac{(5 + 2t − 4t^{2} − 2t^{3})t^{5}}{(1 − t − t^{2})^{2}} .

We can now rewrite (10) as

A_{n}(x)|_{x^{4}} = 2A_{n}(x)|_{x^{4}} + B_{n−1}(x)|_{x^{4}} + G_{n}  (16)

for n ≥ 5. Multiplying both sides of (16) by t^{n} and summing for n ≥ 5, we obtain that

𝔸_{4}(t) − 6t^{4} = 2(𝔹_{4}(t) − 2t^{4}) + t𝔹_{4}(t) + G(t).

Solving for 𝔸_{4}(t) then gives

𝔸_{4}(t) = \frac{t^{4}(6 + t − 7t^{2} − t^{3} + 3t^{4} + t^{5})}{(1 − t − t^{2})^{3}}.

3.2 The highest coefficient of x in A(t, x) and B(t, x) = E(t, x)

Let a_{n} = A_{n}(x)|_{x^{n}}, b_{n} = B_{n}(x)|_{x^{n}}, and e_{n} = E_{n}(x)|_{x^{n}}. Thus, for example, a_{n} is the number of permutations π ∈ S_{n}(132) such that every element of π is an occurrence of the 1-box pattern in π. The identity element in S_{n} and its reverse show that a_{n}, b_{n}, and e_{n} are nonzero for all n ≥ 1. Moreover, the fact that B_{n}(x) = E_{n}(x) for all n ≥ 1 implies b_{n} = e_{n} for all n ≥ 1. In this section, we shall compute the generating functions

A(t) = ∑_{n≥0} a_{n}t^{n} and B(t) = ∑_{n≥1} b_{n}t^{n}.

Theorem 10.

A(t) = \frac{1 − t + 2t^{3} − \sqrt{1 − 2t − 3t^{2} + 4t^{3} − 4t^{4}}}{2t^{2}}

and

B(t) = \frac{1 + t − 2t^{2} + 2t^{3} − \sqrt{1 − 2t − 3t^{2} + 4t^{3} − 4t^{4}}}{2(1 − t + t^{2})} .

The initial values for a_{n} are

1, 1, 2, 2, 6, 10, 26, 54, 134, 306, 754, …

and the initial values for b_{n} are

0, 1, 1, 1, 2, 3, 7, 14, 33, 73, 174, ….

Proof. Our proof of the theorem is very similar to the proofs of Lemma 1 and Theorem 2. First we claim that for n ≥ 4,

b_{n} = 1 + ∑_{k=2}^{n−2}(a_{k} − b_{k}).  (17)

Here 1 corresponds to the decreasing permutation n(n − 1) ⋯ 1, and the sum counts permutations of the form π_{1} ⋯ π_{n−k−1}ℓ(n − k + 1)(n − k + 2) ⋯ n, where 2 ≤ k ≤ n − 2, ℓ < n − k and π_{1} ⋯ π_{n−k−1}ℓ is a 132-avoiding permutation on {1, …, n − k} with the maximum number of occurrences of the 1-box pattern. There are no other permutations counted by b_{n}. Multiplying both parts of (17) by t^{n}, summing over all n ≥ 4, and using the fact that b_{1} = b_{2} = b_{3} = 1, we obtain

B(t) − (t + t^{2} + t^{3}) = \frac{t^{4}}{1 − t} + \frac{t^{2}}{1 − t} ((A(t) − (1 + t)) − (B(t) − t)) ,

from where we get

B(t) = \frac{t − t^{2} + t^{2}A(t)}{1 − t + t^{2}}.  (18)

Using the fact that S_{n}(132) = S_{n}^{(1)}(132) ∪ S_{n}^{(n)}(132) ∪_{2≤i≤n−1} S_{n}^{(i)}(132), it is easy to see that for n ≥ 4,

a_{n} = b_{n} + e_{n} + ∑_{k=2}^{n−2} e_{k}a_{n−k} = 2b_{n} + ∑_{k=2}^{n−2} b_{k}a_{n−k}.  (19)

Multiplying both sides of (19) by t^{n} and using the facts that a_{0} = a_{1} = 1 and a_{2} = a_{3} = 2, we see that

A(t) − (1 + t + 2t^{2} + 2t^{3}) = 2(B(t) − (t + t^{2} + t^{3})) + (B(t) − t)(A(t) − (1 + t)).

This leads to

A(t) = \frac{1 + t^{2} + (1 − t)B(t)}{1 + t − B(t)}.  (20)

Solving the system of equations given by (18) and (20) for A(t) and B(t) we get the desired result.

4 The 1-box pattern on separable permutations

In this section we enumerate separable permutations with m, 0 ≤ m ≤ 3, occurrences of the 1-box pattern.

For two non-empty words, A and B, we write A < B to indicate that any element in A is less than each element in B. We say that π′ = π_{i}π_{i+1} ⋯ π_{j} is an interval in a permutation π_{1} ⋯ π_{n} if π′ is a permutation of {k, k + 1, …, k + j − i} for some k, that is, if π′ consists of consecutive values.

A permutation is separable if it avoids simultaneously the patterns 2413 and 3142. It is known and is not difficult to see that any separable permutation π of length n has the following structure (also illustrated in Figure 5):

π = L_{1}L_{2} ⋯ L_{m}nR_{m}R_{m−1} ⋯ R_{1}  (21)

where

Figure 5: The structure of a separable permutation.

• for 1 ≤ i ≤ m, L_{i} and R_{i} are non-empty, with possible exception of L_{1} and R_{m}, separable permutations which are intervals in π, and

• L_{1} < R_{1} < L_{2} < R_{2} < ⋯ < L_{m} < R_{m}. In particular, L_{1}, if it is non-empty, contains the element 1.

For example, if π = 215643 then L_{1} = 21, L_{2} = 5 R_{1} = 43 and R_{2} = ∅.

The following theorem is similar to the case of 132-avoiding permutations.

Theorem 11. Apart from the empty permutation and the permutation 1, there are no separable permutations avoiding the 1-box pattern.

Proof. Our proof is straightforward by induction on n, the length of permutations and is similar to the proof of Theorem 3. Indeed, the base cases for n ≤ 2 are easy to check. Now assume that n ≥ 3 and R_{m} is non-empty (the case when R_{m} is empty can be considered similarly substituting R_{m} with L_{m} in our arguments). If R_{m} has only one element, n − 1, then n and n − 1 give two occurrences of the 1-box pattern; otherwise, R_{m} contains an occurrence of the pattern by the inductive hypothesis.

By definition of an occurrence of the 1-box pattern, we cannot have any permutations with exactly one occurrence of the 1-box pattern.

Theorem 12. The number c_{n} of separable permutations of length n with exactly two occurrences of the 1-box pattern is given by c_{0} = c_{1} = 0, c_{2} = 2, and for n ≥ 3, c_{n} = 2c_{n−1} + c_{n−2}. The generating function for this sequence is

∑_{n≥0} c_{n}t^{n} = \frac{2t^{2}}{1 − 2t − t^{2}} .

The initial values for c_{n}s, for n ≥ 0, are 0, 0, 2, 4, 10, 24, 58, 140, 338, 816, 1970, …, and this is essentially the sequence \underline{A052542} in [13]. Apart from the initial 0s, the sequence of c_{n}s is simply twice the Pell numbers.

Proof. Suppose that n ≥ 3 and π is a separable permutation in S_{n} which is counted by c_{n}. Thus π either contains a consecutive sequence of the form a(a + 1) or (a + 1)a. If we remove a from π and decrease all the elements that are greater than or equal to a + 1 by one, we will obtain a separable permutation π′ in S_{n−1}. By Theorem 11, we must have at least two occurrences of the pattern in the obtained permutation π′. In fact, it is easy to see that we will either get two occurrences or three occurrences of the 1-box pattern in π′.

By Theorem 13 below the number of possibilities to get π′ with three occurrences of the 1-box pattern (necessarily formed by either a consecutive subword of the form a(a+1)(a+2) or by (a+2)(a+1)a) is given by c_{n−2}. This is indeed the case because we can reverse removing the element in this case by turning a(a + 1)(a + 2) to a(a + 2)(a + 1)(a + 3) or (a + 2)(a + 1)a to (a + 3)(a + 1)(a + 2)a and increasing by 1 each element of π that is larger than (a + 2). On the other hand, the number of possibilities to get π′ with two occurrences of the 1-box pattern (formed by either a consecutive elements of the form a(a + 1) or by (a + 1)a) is given by 2c_{n−1}. Indeed, to reverse removing the element in this case we need either to turn a(a+1) to either (a + 1)a(a + 2) or to a(a + 2)(a + 1), or to turn (a + 1)a to either (a + 2)a(a + 1) or to (a + 1)(a + 2)a. In each of these cases the suggested substitutions create, in an injective way, separable permutations with exactly two occurrences of the 1-box pattern.

Our considerations above justify the recursion c_{n} = 2c_{n−1} + c_{n−2} (the initial values for it are easy to see). Finally, using the standard technique, it is straightforward to derive the generating function based on the recursion above.

Theorem 13. For n ≥ 1, the number of separable permutations of length n with exactly three occurrences of the 1-box pattern is equal to the number of separable permutations of length n − 1 with exactly two occurrences of this pattern.

Proof. It is easy to see that if a separable permutation has exactly three occurrences of the 1-box pattern, then these occurrences are necessarily formed by either a consecutive subword of the form a(a + 1)(a + 2) or by (a + 2)(a + 1)a. In either case, removing the middle element and reducing by 1 all elements that are larger than (a + 1), we get a separable permutation with exactly two occurrences of the 1-box pattern. This operation is obviously reversible.

Even though we shall not derive formulas for separable permutations with other number of occurrences of the 1-box pattern, we provide initial values for the number of separable permutations with exactly four occurrences of the 1-box pattern (not in [13]):

0, 0, 0, 0, 8, 42, 178, 664, 2288, …,

and with the maximum number of occurrences of this pattern on separable permutations (again, not in [13]):

0, 0, 2, 2, 8, 14, 54, 128, 466, ….

References

[1] S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Avoidance of boxed mesh patterns on permutations, Discrete Appl. Math. 161 (2013), 43–51.

[2] P. Brändén and A. Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Elect. J. Comb. 18 (2) (2011), #P5.

[3] S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011.

[4] S. Kitaev and J. Liese, Harmonic numbers, Catalan triangle and mesh patterns, J.

Discr. Math. 313 (2013), 1515–1531.

[5] S. Kitaev and J. Remmel, Quadrant marked mesh patterns, J. Integer Sequences, 12 (2012), Article 12.4.7.

[6] S. Kitaev and J. Remmel, Quadrant marked mesh patterns in alternating permutations, Sem. Lothar. Combin. B68a (2012); available at

http://www.emis.de/journals/SLC/wpapers/s68kitaremm.html.

[7] S. Kitaev and J. Remmel, (a, b)-rectangular patterns in permutations and words,

preprint, http://arxiv.org/abs/1304.4286.

[8] S. Kitaev, J. Remmel, and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, Pure Mathematics and Applications, to appear.

[9] S. Kitaev, J. Remmel, and M. Tiefenbruck, Marked mesh patterns in 132-avoiding

permutations II, preprint, http://arxiv.org/abs/1302.2274.

[10] S. Kitaev, J. Remmel, and M. Tiefenbruck, Marked mesh patterns in 132-avoiding

permutations III, preprint, http://arxiv.org/abs/1303.0854.

[11] T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Ann. Comb. 6 (2002), 65–76.

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

[13] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically

at http://oeis.org.

[14] H. Úlfarsson, A unification of permutation patterns related to Schubert varieties, Pure Mathematics and Applications, to appear.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: 1-box pattern, 132-avoiding permutation, separable permutation, Fibonacci number, Pell number, distribution.

(Concerned with sequence \underline{A052542}.)

Received September 22 2013; revised version received February 11 2014. Published in Journal of Integer Sequences, February 15 2014.

Return to Journal of Integer Sequences home page.