Quadrant Marked Mesh Patterns

Sergey Kitaev University of Strathclyde Livingstone Tower, 26 Richmond Street Glasgow G1 1XH United Kingdom

                sergey.kitaev@gmail.com

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

                 remmel@math.ucsd.edu

Abstract

In this paper we begin the first systematic study of distributions of quadrant marked mesh patterns. Mesh patterns were introduced recently by Brändén and Claesson in connection with permutation statistics. Quadrant marked mesh patterns are based on how many elements lie in various quadrants of the graph of a permutation relative to the coordinate system centered at one of the points in the graph of the permutation. We study the distribution of several quadrant marked mesh patterns in a symmetric group and in certain subsets of the symmetric group. We find explicit formulas for the generating function of such distributions in several general cases and develop recursions to compute the numbers in question in other cases. In addition, certain q-analogues of our results are discussed.

1 Introduction

The notion of mesh patterns was introduced by Brändén and Claesson [1] to provide explicit expansions for certain permutation statistics as, possibly infinite, linear combinations of (classical) permutation patterns. This notion was further studied in [2, 10]. In particular, the notion of a mesh pattern was extended to that of a marked mesh pattern by Úlfarsson in [10].

In this paper, we study the number of occurrences of what we call quadrant marked mesh patterns. Let ℕ = {0, 1, 2, …} denote the set of natural numbers and S_{n} denote the symmetric group of permutations of 1, …, n. If σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, then 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 four quadrants I, II, III, and IV of that coordinate system as pictured in Figure 1. For any a, b, c, d ∈ ℕ and any σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we say that σ_{i} matches the quadrant marked mesh pattern MMP (a, b, c, d) in σ if in G(σ) relative to the coordinate system which has the point (i, σ_{i}) as its origin, there are ≥ a points in quadrant I, ≥ b points in quadrant II, ≥ c points in quadrant III, and ≥ d points in quadrant IV. For example, if σ = 471569283, the point σ_{4} = 5 matches the quadrant marked mesh pattern MMP (2, 1, 2, 1) since relative to the coordinate system with origin (4, 5), there are 3 points in G(σ) in quadrant I, there is 1 point in G(σ) in quadrant II, there are 2 points in G(σ) in quadrant III, and there are 2 points in G(σ) in quadrant IV. Note that if a coordinate in MMP (a, b, c, d) is 0, then there is no condition imposed on the points in the corresponding quadrant. In addition, we shall consider patterns MMP (a, b, c, d) where a, b, c, d ∈ ℕ ∪ {∅}. Here when one the parameters a, b, c, or d in MMP (a, b, c, d) is the empty set, then for σ_{i} to match MMP (a, b, c, d) in σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, it must be the case that there are no points in G(σ) relative to the coordinate system with origin (i, σ_{i}) in the corresponding quadrant. For example, if σ = 471569283, the point σ_{3} = 1 matches the marked mesh pattern MMP (4, 2, ∅, ∅) since relative to the coordinate system with origin (3, 1), there are 6 points in G(σ) in quadrant I, 2 points in G(σ) in quadrant II, no points in G(σ) in quadrant III, and no points in G(σ) in quadrant IV. We let mmp^{(a,b,c,d)}(σ) denote the number of i such that σ_{i} matches the marked mesh pattern MMP (a, b, c, d) in σ.

Figure 1: The graph of σ = 471569283.

Note how the (two-dimensional) notation of Úlfarsson [10] for marked mesh patterns corresponds to our (one-line) notation for quadrant marked mesh patterns. For example,

MMP (0, 0, k, 0) = _{k}  , MMP (k, 0, 0, 0) = _{k}  ,

MMP (0, a, b, c) = _{a}_{b}_{c}  and MMP (0, 0, ∅, k) = _{k}  .

In Section 2 we will consider MMP (=k, 0, 0, 0), another type of quadrant marked mesh patterns, which requires presence of exactly k elements in quadrant I. This type of patterns is expressed in the terminology of Úlfarsson [10] as follows:

MMP (=k, 0, 0, 0) = _{=k} .

Also, in Section 5 we define and study MMP (k≤ max, ∅, 0, 0), yet another type of quadrant marked mesh patterns, which is equivalent to the following pattern in the terminology of Úlfarsson [10]:

MMP (k≤ max, ∅, 0, 0) = _{k−1} .

Given a sequence σ = σ_{1} ⋯ σ_{n} of distinct integers, let red(σ) be the permutation found by replacing the i-th smallest integer that appears in σ by i. For example, if σ = 2754, then red(σ) = 1432. Given a permutation τ = τ_{1} ⋯ τ_{j} ∈ S_{j}, we say that the pattern τ occurs in σ = σ_{1} ⋯ σ_{n} ∈ S_{n} provided there exist 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 σ. Let S_{n}(τ) denote the set of permutations in S_{n} which avoid τ. In the theory of permutation patterns, τ is called a classical pattern. See [3] for a comprehensive introduction to permutation patterns.

Given a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we say that σ_{j} is a right-to-left maximum of σ if σ_{j} > σ_{i} for all i > j. We let RLmax(σ) denote the number of right-to-left maxima of σ.

The main goal of this paper is to study the generating functions

R^{(a,b,c,d)}(t, x) = 1 + ∑_{n≥1} \frac{t^{n}}{n!} ∑_{σ∈S_{n}} x^{mmp^{(a,b,c,d)}(σ)}.

For any a, b, c, d ∈ {∅} ∪ ℕ, let

R_{n}^{(a,b,c,d)}(x) = ∑_{σ∈S_{n}} x^{mmp^{(a,b,c,d)}(σ)}.

Note that there is a natural action of the symmetries of the square on the graphs of permutations. That is, one can identify each permutation σ ∈ S_{n} with a permutation matrix P (σ) and it is clear that rotating such matrices counter-clockwise by 90 degrees counterclockwise or reflecting permutation matrices about any central axis or any diagonal axis preserves the property of being a permutation matrix. For any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let σ^{r} = σ_{n} ⋯ σ_{1} be the reverse of σ and σ^{c} = (n + 1 − σ_{1}) ⋯ (n + 1 − σ_{n}) be the complement of σ. Then it is easy to see that the map σ → σ^{r} corresponds to reflecting a permutation matrix about its central vertical axis and the map σ → σ^{c} corresponds to reflecting a permutation matrix about its central horizontal axis. It is also easy to see that rotating a permutation matrix by 90 degrees corresponds to replacing σ by (σ^{−1})^{r}. It follows that the map σ → (σ^{−1})^{r} shows that R_{n}^{(a,b,c,d)}(x) = R_{n}^{(d,a,b,c)}(x), the map σ → σ^{r} shows that for R_{n}^{(a,b,c,d)}(x) = R_{n}^{(b,a,d,c)}(x) and the map σ → σ^{c} shows that for R_{n}^{(a,b,c,d)}(x) = R_{n}^{(d,c,b,a)}(x). Moreover, taking the inverse of permutations shows that R_{n}^{(a,b,c,d)}(x) = R_{n}^{(a,d,c,b)}(x), applying the composition of reverse and complement shows that R_{n}^{(a,b,c,d)}(x) = R_{n}^{(c,d,a,b)}(x), applying the composition of reverse and inverse shows that R_{n}^{(a,b,c,d)}(x) = R_{n}^{(b,c,d,a)}(x), and finally, applying the composition of reverse, complement and inverse, that is, the map σ → (σ^{rc})^{−1}, shows that R_{n}^{(a,b,c,d)}(x) = R_{n}^{(c,b,a,d)}(x). Any other composition of the three trivial bijections on S_{n} will not give us any new symmetries. Thus we have the following lemma:

Lemma 1. For any a, b, c, d ∈ {∅} ∪ ℕ,

R_{n}^{(a,b,c,d)}(x) = R_{n}^{(d,a,b,c)}(x) = R_{n}^{(c,b,a,d)}(x) =
R_{n}^{(b,a,d,c)}(x) = R_{n}^{(d,c,b,a)}(x) = R_{n}^{(a,d,c,b)}(x) = R_{n}^{(c,d,a,b)}(x) = R_{n}^{(b,c,d,a)}(x).

2 R_{n}^{(k,0,0,0)}(x) = R_{n}^{(0,k,0,0)}(x) = R_{n}^{(0,0,k,0)}(x) = R_{n}^{(0,0,0,k)}(x) and R_{n}^{(=k,0,0,0)}(x)

The equalities in the section title are true by Lemma 1. Thus we only need to consider the quadrant marked mesh pattern MMP (k, 0, 0, 0).

First assume that k ≥ 1. It is easy to see that R_{n}^{(k,0,0,0)}(x) = n! if n ≤ k. For n > k, suppose that we start with a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n} and then we let σ^{(i)} denote the permutation of S_{n+1} that is produced by adding 1 to each element of σ and inserting 1 before the element σ_{i} + 1 if 1 ≤ i ≤ n and inserting 1 at the end if i = n + 1. Then it is easy to see that

mmp^{(k,0,0,0)}(σ^{(i)}) = \begin{cases}mmp^{(k,0,0,0)}(σ), & if i > n − k + 1; \\ 1 + mmp^{(k,0,0,0)}(σ), & if i ≤ n − k + 1. \end{cases}

That is, clearly the placement of 1 in position i in σ^{(i)} cannot effect the elements in quadrant I relative to any pair (j, σ_{j} + 1) for any j < i or relative to any pair (j + 1, σ_{j} + 1) for any j ≥ i. In addition, the 1 in position i can contribute to mmp^{(k,0,0,0)}(σ^{(i)}) if and only if i ≤ n + 1 − k. It then follows that for n ≥ k,

R_{n+1}^{(k,0,0,0)}(x) = (k + x(n + 1 − k))R_{n}^{(k,0,0,0)}(x).  (1)

Iterating this recursion, we see that

R_{k+s}^{(k,0,0,0)}(x) = k! ∏_{i=1}^{s}(k + ix)  (2)

for all s ≥ 1. In this case, we can form a simple generating function. That is, let

P^{(k,0,0,0)}(t, x) = ∑_{n≥k} \frac{t^{n−k}}{(n − k)!} ∑_{σ∈S_{n}} x^{mmp^{(k,0,0,0)}(σ)}.

Then we know that

P^{(k,0,0,0)}(t, x) = k! + ∑_{n>k} R_{n}^{(k,0,0,0)}(x)\frac{t^{n−k}}{(n − k)!}

= k! + ∑_{n>k} (kR_{n−1}^{(k,0,0,0)}(x) + (n − k)xR_{n−1}^{(k,0,0,0)}(x)) \frac{t^{n−k}}{(n − k)!}

= k! + tx ∑_{n>k} R_{n−1}^{(k,0,0,0)}(x)\frac{t^{n−k−1}}{(n − k − 1)!} + k ∑_{n>k} R_{n−1}^{(k,0,0,0)}(x)\frac{t^{n−k}}{(n − k)!}.

Hence

(1 − tx)P^{(k,0,0,0)}(t, x) = k! + k ∑_{n>k} R_{n−1}^{(k,0,0,0)}(x)\frac{t^{n−k}}{(n − k)!}.

Taking the derivative of both sides with respect to t, we see that

\frac{∂}{∂t}((1 − tx)P^{(k,0,0,0)}(t, x)) = kP^{(k,0,0,0)}(t, x) = \frac{k}{1 − tx}(1 − tx)P^{(k,0,0,0)}(t, x).

Thus

\frac{\frac{∂}{∂t}((1 − tx)P^{(k,0,0,0)}(t, x))}{(1 − tx))P^{(k,0,0,0)}(t, x)} = \frac{k}{1 − tx}.

It then follows that

ln((1 − tx)P^{(k,0,0,0)}(t, x)) = −\frac{k}{x} ln(1 − tx) + c.

Hence, using the fact that P^{(k,0,0,0)}(0, x) = k!, we obtain the following theorem.

Theorem 2. For all k ≥ 1,

P^{(k,0,0,0)}(t, x) = ∑_{n≥k} \frac{t^{n−k}}{(n − k)!} ∑_{σ∈S_{n}} x^{mmp^{(k,0,0,0)}(σ)} = k! (\frac{1}{1 − tx})^{\frac{k}{x} +1} .

Next, we consider another type of quadrant marked mesh pattern. That is, given a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we say that σ_{i} matches the marked mesh pattern MMP (=k, 0, 0, 0) in σ if and only if, relative to the coordinate system with origin at (i, σ_{i}), there are exactly k points in G(σ) in quadrant I. Let mmp^{(=k,0,0,0)}(σ) denote the number of i such that σ_{i} matches MMP (=k, 0, 0, 0) and

R_{n}^{(=k,0,0,0)}(x) = ∑_{σ∈S_{n}} x^{mmp^{(=k,0,0,0)}(σ)}.

Then we can use the same reasoning to show that

R_{n}^{(=k,0,0,0)}(x) = n!

if n ≤ k, and, for n ≥ k,

R_{n+1}^{(=k,0,0,0)}(x) = (n + x)R_{n}^{(=k,0,0,0)}(x).

The difference in this case is that insertion of 1 will contribute to mmp^{(=k,0,0,0)}(σ^{(i)}) if and only if i = n + 1 − k. Iterating this recursion, we see that

R_{k+s}^{(=k,0,0,0)}(x) = k! ∏_{i=1}^{s}(k + i − 1 + x)

for all s ≥ 1. It is then easy to see using the same reasoning as above that if we let

P^{(=k,0,0,0)}(t, x) = ∑_{n≥k} \frac{t^{n−k}}{(n − k)!} ∑_{σ∈S_{n}} x^{mmp^{(=k,0,0,0)}(σ)},

then

P^{(=k,0,0,0)}(t, x) = k! (\frac{1}{1 − t})^{x+k} .

It is also known [1] and is easy to see that a point σ_{i} matches the pattern MMP (∅, 0, 0, 0) in σ = σ_{1} ⋯ σ_{n} ∈ S_{n} if and only if σ_{i} is a right-to-left maximum of σ. It is well-known that the number of permutations σ ∈ S_{n} such that RLmax(σ) = k is equal to the signless Stirling number of the first kind c(n, k) which is the number of permutations τ ∈ S_{n} such that τ has k cycles. Thus

R_{n}^{(∅,0,0,0)}(x) = ∑_{σ∈S_{n}} x^{RLmax(σ)} = ∑_{k=1}^{n} c(n, k)x^{k}
= x(x + 1) ⋯ (x + n − 1).

It is well-known that ∑_{n≥0} \frac{t^{n}}{n!} ∑_{k=1}^{n} c(n, k)x^{k} = (\frac{1}{1−t})^{x}. Thus

R^{(∅,0,0,0)}(t, x) = 1 + ∑_{n≥1} R_{n}^{(∅,0,0,0)}(x)\frac{t^{n}}{n!} = (\frac{1}{1 − t})^{x} .

3 R_{n}^{(a,b,0,0)}(x) and some other cases of two non-zero parameters

Note that it follows from Lemma 1 that R_{n}^{(a,b,0,0)}(x) equals

R_{n}^{(b,0,0,a)}(x) = R_{n}^{(0,0,a,b)}(x) = R_{n}^{(0,a,b,0)}(x) = R_{n}^{(b,a,0,0)}(x) =

R_{n}^{(0,b,a,0)}(x) = R_{n}^{(0,0,b,a)}(x) = R_{n}^{(a,0,0,b)}(x).

First, we consider the case where a, b ≥ 1. It is easy to see that R_{n}^{(a,b,0,0)}(x) = n! if n ≤ a + b. For n ≥ a + b, it is easy to see that if σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, then

mmp^{(a,b,0,0)}(σ^{(i)}) = \begin{cases}mmp^{(a,b,0,0)}(σ), & if i ≤ b or i > n − a + 1; \\ 1 + mmp^{(a,b,0,0)}(σ), & if b + 1 ≤ i ≤ n − a + 1. \end{cases}  (3)

That is, clearly the placement of 1 in position i in σ^{(i)} cannot effect the elements in quadrant I or II relative to any pair (j, σ_{j} + 1) for any j < i or relative to any pair (j + 1, σ_{j} + 1) for any j ≥ i, and the 1 in position i can contribute to mmp^{(k,0,0,0)}(σ^{(i)}) if and only if b + 1 ≤ i ≤ n − a + 1. It then follows that for n ≥ a + b,

R_{n+1}^{(a,b,0,0)}(x) = (a + b)R_{n}^{(a,b,0,0)}(x) + (n + 1 − (a + b))xR_{n}^{(a,b,0,0)}(x).  (4)

Note this is the same recursion as the recursion for R_{n+1}^{(k,0,0,0)}(x) if a + b = k. Thus it follows that

R_{a+b+s}^{(a,b,0,0)}(x) = (a + b)! ∏_{i=1}^{s}((a + b) + ix)  (5)

for all s ≥ 1 and that

P^{(a,b,0,0)}(t, x) = ∑_{n≥a+b} \frac{t^{n−a−b}}{(n − a − b)!}R_{n}^{(a,b,0,0)}(x) = (a + b)! (\frac{1}{1 − tx})^{\frac{a+b}{x} +1}  (6)

for all a, b ≥ 1.

Next we consider the case R_{n}^{(1,∅,0,0)}(x). Clearly, R_{1}^{(1,∅,0,0)}(x) = 1. For n ≥ 1 and any σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we again consider the permutations σ^{(i)} in S_{n+1}. For i = 1, mmp^{(1,∅,0,0)}(σ^{(1)}) = 1 + mmp^{(1,∅,0,0)}(σ) and, for i > 1, mmp^{(1,∅,0,0)}(σ^{(i)}) = mmp^{(1,∅,0,0)}(σ). It follows that for all n ≥ 1,

R_{n+1}^{(1,∅,0,0)}(x) = (x + n)R_{n}^{(1,∅,0,0)}(x)

so that for n > 1,

R_{n}^{(1,∅,0,0)}(x) = (x + 1) ⋯ (x + n − 1).

It then easily follows that

R^{(1,∅,0,0)}(t, x) = 1 + \frac{(1 − t)^{−x} − 1}{x}.  (7)

Next fix k ≥ 2. Clearly, R_{n}^{(k,∅,0,0)}(x) = n! for n ≤ k. For n ≥ k and σ ∈ S_{n}, it is easy to see that for i = 1, mmp^{(k,∅,0,0)}(σ^{(1)}) = 1 + mmp^{(k,∅,0,0)}(σ) and that for i > 1, mmp^{(k,∅,0,0)}(σ^{(i)}) = mmp^{(k,∅,0,0)}(σ). Hence, for all n ≥ k,

R_{n+1}^{(k,∅,0,0)}(x) = (x + n)R_{n}^{(k,∅,0,0)}(x).

Thus for n > k,

R_{n}^{(k,∅,0,0)}(x) = k!(x + k) ⋯ (x + n − 1).

It follows that for k ≥ 2,

P^{(k,∅,0,0)}(t, x) = ∑_{n≥k} R_{n}^{(k,∅,0,0)}(x)\frac{t^{n−k}}{(n − k)!} = k! (\frac{1}{1 − t})^{x+k}

and that

R^{(k,∅,0,0)}(t, x) = 1 + ∑_{n≥1} R_{n}^{(k,∅,0,0)}(x)\frac{t^{n}}{n!}

= ∑_{j=0}^{k} t^{j} + \frac{k!}{∏_{i=1}^{k−1}(x + i)} (R^{(1,∅,0,0)}(t, x) − 1 − t − ∑_{j=2}^{k} \frac{t^{j}}{j!} ∏_{i=1}^{j−1}(x + i)) . (8)

4 q-analogues to marked mesh patterns considered above

We let

[n]_{q} = 1 + q + ⋯ + +q^{n−1} = \frac{1 − q^{n}}{1 − q} ,
[n]_{q}! = [1]_{q}[2]_{q} ⋯ [n]_{q}, and
\left[{n \atop k}\right]_{q} = \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!}

denote the usual q-analogues of n, n!, and \binom{n}{k}. We shall use the standard conventions that [0]_{q} = 0 and [0]_{q}! = 1. For any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we let coinv(σ) equal the number of co-inversions in σ, that is, the number of 1 ≤ i < j ≤ n such that σ_{i} < σ_{j}.

Let

R_{n}^{(a,b,c,d)}(x, q) = ∑_{σ∈S_{n}} x^{mmp^{(a,b,c,d)}(σ)}q^{coinv(σ)}.

It turns out that we can easily obtain q-analogues of the recursions (1) and (4). That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, it is easy to see that

q^{coinv(σ^{(i)})}x^{mmp^{(k,0,0,0)}(σ^{(i)})} = \begin{cases}q^{n+1−i}q^{coinv(σ)}x^{mmp^{(k,0,0,0)}(σ)}, & if i > n − k; \\ q^{n+1−i}q^{coinv(σ)}x^{1+mmp^{(k,0,0,0)}(σ)}, & if i ≤ n − k. \end{cases}

It then follows that for n ≥ k,

R_{n+1}^{(k,0,0,0)}(x, q) = [k]_{q}R_{n}^{(k,0,0,0)}(x, q) + xq^{k}[n + 1 − k]_{q}R_{n}^{(k,0,0,0)}(x, q).

Thus for n ≤ k,

R_{n+1}^{(k,0,0,0)}(x, q) = [n]_{q}!

and for s ≥ 1,

R_{k+s}^{(k,0,0,0)}(x, q) = [k]_{q}! ∏_{i=1}^{s}([k]_{q} + xq^{k}[i]_{q}).

Similarly, we can find a q-analogue of the recursion (3). That is, for any σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, it is easy to see that

q^{coinv(σ^{(i)})}x^{mmp^{(a,b,0,0)}(σ^{(i)})} = \begin{cases}q^{n+1−i}q^{coinv(σ)}x^{mmp^{(a,b,0,0)}(σ)}, & if i ≤ b or i > n − a + 1; \\ q^{n+1−i}q^{coinv(σ)}x^{1+mmp^{(a,b,0,0)}(σ)}, & if b + 1 ≤ i ≤ n − a + 1. \end{cases}

It then follows that for n ≥ a + b,

R_{n+1}^{(a,b,0,0)}(x, q) = ([a]_{q} + q^{n−b}[b]_{q})R_{n}^{(k,0,0,0)}(x, q) + q^{a}[n + 1 − (a + b)]_{q}xR_{n}^{(k,0,0,0)}(x, q).

Thus for n ≤ a + b,

R_{n+1}^{(a,b,0,0)}(x, q) = [n]_{q}!

and for s ≥ 1,

R_{a+b+s}^{(a,b,0,0)}(x, q) = [k]_{q}! ∏_{i=1}^{s}([a]_{q} + q^{a+i}[b]_{q} + q^{a}x[i]_{q}).

Note that if a + b = k where a, b ≥ 1 and n > k, then R_{n}^{(a,b,0,0)}(x, q) ≠ R_{n}^{(k,0,0,0)}(x, q).

5 R_{n}^{(k≤ max,∅,0,0)}(x) – another type of quadrant marked mesh patterns

We say that σ_{i} matches the quadrant marked mesh pattern MMP (k≤ max, ∅, 0, 0) in σ = σ_{1} ⋯ σ_{n} ∈ S_{n} if in G(σ) relative to the coordinate system with origin (i, σ_{i}), there are no points in quadrant II in G(σ) and there are at least k − 1 points that lie in quadrant I to the left of the largest value occurring in quadrant I. Said another way, σ_{i} matches the pattern MMP (k≤ max, ∅, 0, 0) in σ if none of σ_{1}, …, σ_{i−1} is greater than σ_{i} and if σ_{j} > σ_{i} is the maximum of σ_{i+1}, …, σ_{n}, then there are at least k points among σ_{i+1}, …, σ_{j} which are greater than σ_{i}. It is easy to see that MMP (k≤ max, ∅, 0, 0) is equivalent to the following (ordinary) marked mesh pattern in the terminology of Úlfarsson [10]:

k−1 .

For σ ∈ S_{n}, we let mmp^{(k≤ max,∅,0,0)}(σ) be the number of i such that σ_{i} matches

MMP (k≤ max, ∅, 0, 0)

in σ and we let

R_{n}^{(k≤ max,∅,0,0)}(x) = ∑_{σ∈S_{n}} x^{mmp^{(k≤ max,∅,0,0)}(σ)}.

Clearly, R_{n}^{(1≤max,∅,0,0)}(x) = R_{n}^{(1,∅,0,0)}(x). We can compute R_{n}^{(k≤ max,∅,0,0)}(x) for k ≥ 2 as follows. Given a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let σ^{[i]} denote the permutation of S_{n+1} that results by inserting n + 1 immediately before σ_{i} if 1 ≤ i ≤ n and inserting n + 1 at the end of σ if i = n + 1. It is easy to see that the set of all σ^{[i]} for σ ∈ S_{n} contributes \binom{n}{i−1}R_{i−1}^{(k−1,∅,0,0)}(x)(n + 1 − i)! to R_{n+1}^{(k≤ max,∅,0,0)}(x). That is, the presence of n + 1 in the i-th position of σ^{[i]} means that none of the elements to the right of n + 1 in σ^{[i]} can contribute to mmp^{(k≤ max,∅,0,0)}(σ^{[i]}) while an element to the left of n + 1 in σ^{[i]} will contribute 1 to mmp^{(k≤ max,∅,0,0)}(σ^{[i]}) if and only if it contributes 1 to mmp^{(k−1,∅,0,0)}(σ_{1} ⋯ σ_{i−1}). It follows that for all n ≥ 0,

R_{n+1}^{(k≤ max,∅,0,0)}(x) = ∑_{i=1}^{n+1}(n + 1 − i)!\binom{n}{i − 1}R_{i−1}^{(k−1,∅,0,0)}(x)

or, equivalently,

\frac{R_{n+1}^{(k≤ max,∅,0,0)}(x)}{n!} = ∑_{i=1}^{n+1} \frac{R_{i−1}^{(k−1,∅,0,0)}(x)}{(i − 1)!}.  (9)

Thus multiplying (9) by t^{n} and summing it over all n ≥ 0, we obtain that

\frac{∂}{∂t}R^{(k≤ max,∅,0,0)}(t, x) = ∑_{n≥0} \frac{R_{n+1}^{(k≤ max,∅,0,0)}(x)t^{n}}{n!}

= ∑_{n≥0} t^{n} ∑_{i=1}^{n+1} \frac{R_{i−1}^{(k−1,∅,0,0)}(x)}{(i − 1)!}

= \frac{1}{1 − t}R^{(k−1,∅,0,0)}(t, x).

Hence we obtain the recursion

R^{(k≤ max,∅,0,0)}(t, x) = 1 + ∫_{0}^{t} \frac{1}{1 − z} R^{(k−1,∅,0,0)}(z, x)dz.  (10)

Note that one can find an explicit formula for R^{(k−1,∅,0,0)}(z, x) by using formulas (7) and (8). For example, one can use Mathematica to compute that

R^{(2≤max,∅,0,0)}(t, x) = 1 + t + t^{2} + \frac{1}{6}(5 + x)t^{3} +

\frac{1}{24} (17 + 6x + x^{2}) t^{4} + \frac{1}{120} (74 + 35x + 10x^{2} + x^{3}) t^{5} +

\frac{1}{720} (394 + 225x + 85x^{2} + 15x^{3} + x^{4}) t^{6} +

\frac{1}{5040} (2484 + 1624x + 735x^{2} + 175x^{3} + 21x^{4} + x^{5}) t^{7} +

\frac{1}{40320} (18108 + 13132x + 6769x^{2} + 1960x^{3} + 322x^{4} + 28x^{5} + x^{6}) t^{8} +

\frac{1}{362880} (149904 + 118124x + 67284x^{2} + 22449x^{3} + 4536x^{4} + 546x^{5} + 36x^{6} + x^{7}) t^{9} + ⋯

and

R^{(3≤max,∅,0,0)}(t, x) = 1 + t + t^{2} + t^{3} + \frac{1}{24}2(11 + x)t^{4} + \frac{1}{120}2 (50 + 9x + x^{2}) t^{5} +

\frac{1}{720}2 (274 + 71x + 14x^{2} + x^{3}) t^{6} + \frac{1}{5040}2(1764 + 580x + 155x^{2} + 20x^{3} + x^{4})t^{7} +

\frac{1}{40320}2(13068 + 5104x + 1665x^{2} + 295x^{3} + 27x^{4} + x^{5})t^{8} +

\frac{1}{362880}2(100584 + 48860x + 18424x^{2} + 4025x^{3} + 511x^{4} + 35x^{5} + x^{6})t^{9} + · · · .

and

R^{(4≤max,∅,0,0)}(t, x) = 1 + t + t^{2} + t^{3} + t^{4} + \frac{1}{120}6 (19 + x) t^{5} + \frac{1}{720}6 (107 + 12x + x^{2}) t^{6} +

\frac{1}{5040}6(702 + 119x + 18x^{2} + x^{3})t^{7} + \frac{1}{40320}6(5274 + 1175x + 245x^{2} + 25x^{3} + x^{4})t^{8} +

\frac{1}{362880}6(44712 + 12154x + 3135x^{2} + 445x^{3} + 33x^{4} + x^{5})t^{9} + · · · .

There are several of the coefficients of R_{n}^{(k≤ max,∅,0,0)}(x) that we can explain. First, we claim that

R_{n}^{(k≤ max,∅,0,0)}(x)|_{x^{n−k}} = (k − 1)! for n ≥ k + 1.  (11)

That is, it is easy to see that for n ≥ k + 1, the only permutations σ = σ_{1} ⋯ σ_{n} ∈ S_{n} such that mmp^{(k≤ max,∅,0,0)}(σ) = n − k must have σ_{i} = i for i = 1, …, n − k, σ_{n} = n and σ_{n−k+1} ⋯ σ_{n−1} be some permutation of (n − k + 1), (n − k + 2), …, (n − 1).

Next, we claim that

R_{n}^{(k≤ max,∅,0,0)}(x)|_{x^{n−k−1}} = (k − 1)! (\binom{n}{2} − \binom{k − 1}{2}) for n ≥ k + 2.  (12)

First observe that any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n} such that n ∈ {σ_{1}, …, σ_{n−2}} cannot have mmp^{(k≤ max,∅,0,0)}(σ) = n − k − 1. Now assume that n ≥ k + 2 and σ = σ_{1} ⋯ σ_{n} ∈ S_{n} is such that mmp^{(k≤ max,∅,0,0)}(σ) = n−k−1. Thus it must be that case that n = σ_{n−1} or n = σ_{n}. If σ_{n−1} = n, then it must be the case that mmp^{(k≤ max,∅,0,0)}(red(σ_{1} ⋯ σ_{n−1})) = n − k − 1. In this case, we have n−1 choices for σ_{n} and (k−1)! choices for red(σ_{1} ⋯ σ_{n−1}) by our argument above. Thus there are (n−1)((k−1)!) such elements. Next assume that n = σ_{n}. Then in this case, the only way to produce a σ = σ_{1} ⋯ σ_{n} ∈ S_{n} such that mmp^{(k≤ max,∅,0,0)}(σ) = n − k − 1 is to start with a permutation

τ = τ_{1} ⋯ τ_{n} = 1 2 ⋯ (n − k)τ_{n−k+1} ⋯ τ_{n−1} n

where τ_{n−k+1} ⋯ τ_{n−1} is some permutation of (n − k + 1), (n − k + 2), …, (n − 1) so that mmp^{(k≤ max,∅,0,0)}(τ) = n − k. Now if k ≥ 2, then take some i ∈ {1, …, n − k} in τ and move i immediately after one of τ_{i+1}, …, τ_{n−1}. This will ensure that i does not match the pattern MMP (k≤ max, ∅, 0, 0) in the resulting permutation because i will have a larger element to its left. Each such τ gives rise to (n − 2) + (n − 3) + ⋯ + (k − 1) = \binom{n−1}{2} − \binom{k−1}{2} such permutations. If k = 1, then take some i ∈ {1, …, n − 2} in τ and move i immediately after one of τ_{i+1}, …, τ_{n−1}. In this case, each such τ gives rise to (n − 2) + (n − 3) + ⋯ + 1 = \binom{n−1}{2} = \binom{n−1}{2} − \binom{0}{2} such permutations. Thus in either case, the number of σ ∈ S_{n} with σ_{n} = n and mmp^{(k≤ max,∅,0,0)}(σ) = n − k − 1 is (k − 1)! (\binom{n−1}{2} − \binom{k−1}{2}). It thus follows that the number of σ ∈ S_{n} with mmp^{(k≤ max,∅,0,0)}(σ) = n − k − 1 is (k − 1)! (\binom{n}{2} − \binom{k−1}{2}).

Next we observe that the sequence (R_{n}^{(2≤max,∅,0,0)}(0))_{n≥1} is

1, 2, 5, 17, 74, 394, 2484, 18108, 149904, ….

This is sequence \underline{A000774} from the OEIS where the n-th term in the sequence is

n!(1 + ∑_{i=1}^{n} \frac{1}{i}).

The sequence (R_{n}^{(2≤max,∅,0,0)}(x)|_{x})_{n≥3} is

1, 6, 35, 225, 1624, 13, 132, 118124, …

which is sequence \underline{A000399} in the OEIS. The n-th term of this sequence is c(n, 3) which is the number of permutations σ ∈ S_{n} which have three cycles. We can give a direct proof of this result. That is, we have the following proposition.

Proposition 3. For all n ≥ 3,

R_{n}^{(2≤max,∅,0,0)}(x)|_{x} = c(n, 3).

Proof. Suppose that n ≥ 3 and σ is a permutation of S_{n} with 3 cycles C_{1}, C_{2}, C_{3} where have arranged the cycles so that the largest element in each cycle is on the left and we order the cycles by increasing largest elements. Then we let \overline{σ} be the result of erasing the parentheses and commas in C_{1}C_{2}C_{3}. For example, if σ = (5, 3, 4, 1) (8, 2, 6) (9, 7), then \overline{σ} = 5 3 4 1 8 2 6 9 7. It is easy to see that under this map only the first element of \overline{σ} matches the pattern MMP (2 ≤ max, ∅, 0, 0) in \overline{σ}.

We claim that every τ ∈ S_{n} such that mmp^{(2≤max,∅,0,0)}(τ) = 1 is equal to \overline{σ} for some σ ∈ S_{n} that has two three cycles. That is, suppose that mmp^{(2≤max,∅,0,0)}(τ) = 1 where τ = τ_{1} ⋯ τ_{n} ∈ S_{n} and τ_{i} matches the pattern MMP (2 ≤ max, ∅, 0, 0) in τ. First we claim that i = 1. It cannot be that any of τ_{1}, …, τ_{i−1} are greater than τ_{i} since otherwise τ_{i} would not match the pattern MMP (2 ≤ max, ∅, 0, 0) in τ. But if i ≠ 1, then τ_{1} < τ_{i} and τ_{1} would match the pattern MMP (2 ≤ max, ∅, 0, 0) in τ which would mean that mmp^{(2≤max,∅,0,0)}(τ) ≥ 2. Next suppose that τ_{k} = n and τ_{j} is the maximum element of {τ_{2}, …, τ_{k−1}}. It must be that case that τ_{1} < τ_{j} since otherwise τ_{1} would not match the pattern MMP (2 ≤ max, ∅, 0, 0) in τ. We claim that τ_{2}, …, τ_{j−1} must all be less than τ_{j}. That is, if τ_{r} is the maximum of {τ_{2}, …, τ_{j−1}} and τ_{r} > τ_{1}, then we would have τ_{r} < τ_{j} < τ_{k} = n so that τ_{r} would match the pattern MMP (2 ≤ max, ∅, 0, 0) in τ which would imply that mmp^{(2≤max,∅,0,0)}(τ) ≥ 2. It then follows that if σ = (τ_{1}, …, τ_{j−1}) (τ_{j}, …, τ_{j−1}) (τ_{k}, …, τ_{n}), then \overline{σ} = τ. Thus we have proved that for n ≥ 3, R_{n}^{(2≤max,∅,0,0)}(x)|_{x} = c(n, 3).

The sequence (\frac{1}{2}R_{n}^{(3≤max,∅,0,0)}(0))_{n≥2} is

1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, …

which is sequence \underline{A000254} in the OEIS whose n-th term is c(n + 1, 2) which is the number of permutations of S_{n+1} with 2 cycles. We shall give a direct proof of this fact.

Proposition 4. For all n ≥ 2,

R_{n}^{(3≤max,∅,0,0)}(0) = 2c(n, 2).

Proof. Suppose that σ = σ_{1} ⋯ σ_{n} is a permutation in S_{n} such that mmp^{(3≤max,∅,0,0)}(σ) = 0. Let a(σ) be the i such that σ_{i} = n. If a(σ) ≠ 1, then let b(σ) = j where σ_{j} = max({σ_{1}, …, σ_{a(σ)−1}}). If b(σ) ≠ 1, then let c(σ) = i where σ_{i} = max({σ_{1}, …, σ_{b(σ)−1}}). First we claim that if c(σ) is defined, then c(σ) = 1. That is, if c(σ) ≠ 1, then σ_{1} < σ_{c(σ)} < σ_{b(σ)} < σ_{a(σ)} = n so that σ_{1} would match the pattern MMP (3 ≤ max, ∅, 0, 0). We also claim that if c(σ) is defined, then σ_{1} must be the second largest element among {σ_{1}, …, σ_{a(σ)−1}} otherwise σ_{1} would match the pattern MMP (3 ≤ max, ∅, 0, 0) in σ. Thus we have three possible cases for a σ ∈ S_{n} such that mmp^{(3≤max,∅,0,0)}(σ) = 0.

Case 1. a(σ) = 1. There are clearly (n − 1)! such permutations as σ_{2}, …, σ_{n} can be any arrangement of 1, …, n − 1.

Case 2. b(σ) = 1.

Case 3. c(σ) = 1 and σ_{1} is the second largest element in {σ_{1}, …, σ_{a(σ)−1}}.

Next we define a map θ which takes the permutations in Cases 2 and 3 into the set of permutations τ of S_{n} which have 2 cycles C_{1}C_{2} where we have arranged the cycles so that the largest element in each cycle is on the left and we have max(C_{1}) < max(C_{2}) = n. In Case 2, we let

θ(σ) = (σ_{b(σ)}, …, σ_{a(σ)−1}) (σ_{a(σ)}, …, σ_{n}).

In Case 3, we let

θ(σ) = (σ_{b(σ)}, …, σ_{a(σ)−1}, σ_{c(σ)}, …, σ_{b(σ)−1}) (σ_{a(σ)}, …, σ_{n}).

Now suppose that τ is a permutation with two cycles C_{1}C_{2}, C_{1} = (α_{1}, …, α_{k}) and C_{2} = (β_{1}, …, β_{n−k}), where |C_{1}| = k > 1. Again we assume that we have arranged the cycles so that the largest element in the cycle is on the left and max(C_{1}) < max(C_{2}) = n. Then there exists a σ in Case 2 such that θ(σ) = τ and a γ in Case 3 such that θ(γ) = τ. That is, if α_{j} is the second largest element in {α_{1}, …, α_{k}}, then

σ = α_{1}, …, α_{k}β_{1} ⋯ β_{n−k}

is a permutation in Case 2 such that θ(σ) = τ and

γ = α_{j} ⋯ α_{k}α_{1}, …, α_{j−1}β_{1} ⋯ β_{n−k}

is a permutation in Case 3 such that θ(γ) = τ. The only permutations with 2 cycles C_{1}C_{2} that we have not accounted for are the permutations τ where |C_{1}| = 1. But if |C_{1}| = 1, then σ = α_{1}β_{1} ⋯ β_{n−1} is a permutation in Case 2 such that θ(σ) = τ. θ shows that the number of permutations in Cases 2 and 3 is equal to 2c(n, 2) minus the number of τ such that |C_{1}| = 1. However, it is easy to see that the number of τ with two cycles C_{1}C_{2} such that |C_{1}| = 1 is (n − 1)! which is equal to the number of permutations in Case 1. Thus we have shown that R_{n}^{(3≤max,∅,0,0)}(0) = 2c(n, 2).

The sequence (\frac{1}{6}R_{n}^{(≤4 max,∅,0,0)}(0))_{n≥3} which is

1, 4, 19, 107, 702, 5274, 44712, 422, 568, …

does not appear in the OEIS. However, the sequence (\frac{1}{6}R_{n}^{(4≤max,∅,0,0)}(x)|_{x})_{n≥5} which is

1, 12, 119, 1175, 12154, 133938, …

seems to be \underline{A001712} in the OEIS whose n-th term is ∑_{k=0}^{n}(−1)^{n+k}\binom{k+2}{2}3^{k}s(n + 2, k + 2) where s(n, k) is the Stirling number of the first kind.

Problem 5. Can we prove this formula (directly)?

6 R_{n}^{(a,0,b,0)}(x) = R_{n}^{(b,0,a,0)}(x) = R_{n}^{(0,a,0,b)}(x) = R_{n}^{(0,b,0,a)}(x)

The equalities in the section title are true by Lemma 1. We will consider R_{n}^{(a,0,b,0)}(x).

In this case, we do not know how to compute the generating function R^{(1,0,1,0)}(t, x). However, we can develop a recursion to compute R_{n}^{(1,0,1,0)}(x). That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let

A_{i}(σ) = χ(σ_{i} matches the pattern MMP (1, 0, 1, 0) in σ) and
B_{i}(σ) = χ(σ_{i} matches the pattern MMP (∅, 0, 1, 0) in σ)

where for any statement A, χ(A) = 1 if A is true and χ(A) = 0 if A is false. Note that at most one of A_{i}(σ) and B_{i}(σ) can be equal to 1. Then let

F_{n}^{(1,0,1,0)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) = ∑_{σ∈S_{n}} ∏_{i=2}^{n} x_{i}^{A_{i}(σ)}y_{i}^{B_{i}(σ)}.  (13)

Note that (1, σ_{1}) never contributes to mmp^{(1,0,1,0)}(σ) or mmp^{(∅,0,1,0)}(σ) so that F_{n}^{(1,0,1,0)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) records all the information about the contributions of σ_{2}, …, σ_{n} to mmp^{(1,0,1,0)}(σ) or mmp^{(∅,0,1,0)}(σ) as σ ranges over S_{n}.

Recall that given a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, σ^{[i]} denotes the permutation of S_{n+1} that results by inserting n + 1 immediately before σ_{i} if 1 ≤ i ≤ n and inserting n + 1 at the end of σ if i = n + 1. First consider all the permutations σ^{[1]} as σ ranges over S_{n}. Clearly, since each of these permutations start with n + 1, the first element of σ^{[1]}, which is n + 1, does not contribute to either mmp^{(1,0,1,0)}(σ^{[1]}) or mmp^{(∅,0,1,0)}(σ^{[1]}). Moreover n + 1 does not effect whether any other σ_{i} contributes to mmp^{(1,0,1,0)}(σ^{[1]}) or mmp^{(∅,0,1,0)}(σ^{[1]}) but it does shift the corresponding indices by 1. Thus the second element of σ^{[1]} which is σ_{1} does not contribute to either mmp^{(1,0,1,0)}(σ^{[1]}) or mmp^{(∅,0,1,0)}(σ^{[1]}). However, for the (i + 1)-st element σ^{[1]} which is the old σ_{i}, we have

1. A_{i+1}(σ^{[1]}) = 1 if and only if A_{i}(σ) = 1 and

2. B_{i+1}(σ^{[1]}) = 1 if and only if B_{i}(σ) = 1.

Thus it follows that the contribution of the permutations of the form σ^{[1]} to F_{n+1}^{(1,0,1,0)}(x_{2}, …, x_{n+1}; y_{2}, …, y_{n+1}) is just F_{n}^{(1,0,1,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}). For i ≥ 2, again consider all the permutations σ^{[i]} as σ ranges over S_{n}. For j < i, if A_{j}(σ) = 1, then A_{j}(σ^{[i]}) = 1 and if B_{j}(σ) = 1, then A_{j}(σ^{[i]}) = 1. For j ≥ i, if A_{j}(σ) = 1, then A_{j+1}(σ^{[i]}) = 1 and if B_{j}(σ) = 1, then B_{j+1}(σ^{[i]}) = 1. Moreover the fact that n + 1 is in position i in σ^{[i]} means that B_{i}(σ^{[i]}) = 1. Since at most one of A_{i}(σ) and B_{i}(σ) can equal 1, it follows that the contribution of the permutations of the form σ^{[i]} to F_{n+1}(x_{2}, …, x_{n+1}; y_{2}, …, y_{n+1}) is just

y_{i}F_{n}^{(1,0,1,0)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n+1}).

Thus

F_{n+1}^{(1,0,1,0)}(x_{2}, …, x_{n+1}; y_{2}, …, y_{n+1}) = F_{n}^{(1,0,1,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}) +
∑_{i=2}^{n+1} y_{i}F_{n}^{(1,0,1,0)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n+1}).  (14)

It is then easy to see that

R_{n}^{(1,0,1,0)}(x) = F_{n}^{(1,0,1,0)}(x, …, x; 1, …, 1).  (15)

Using (14) and (15), one can compute that

R_{1}^{(1,0,1,0)}(x) = 1,
R_{2}^{(1,0,1,0)}(x) = 2,
R_{3}^{(1,0,1,0)}(x) = 5 + x,
R_{4}^{(1,0,1,0)}(x) = 14 + 8x + 2x^{2},
R_{5}^{(1,0,1,0)}(x) = 42 + 46x + 26x^{2} + 6x^{3},
R_{6}^{(1,0,1,0)}(x) = 132 + 232x + 220x^{2} + 112x^{3} + 24x^{5},
R_{7}^{(1,0,1,0)}(x) = 429 + 1093x + 1527x^{2} + 1275x^{3} + 596x^{4} + 120x^{5}, and
R_{8}^{(1,0,1,0)}(x) = 1430 + 4944x + 9436x^{2} + 11384x^{3} + 8638x^{4} + 3768x^{5} + 720x^{6}.

It is easy to see that a permutation σ avoids MMP (1, 0, 1, 0) if and only if it avoids the pattern 123, that is, if σ ∈ S_{n}(123). From a well-known fact (see, e.g. [3]), it follows that the sequence (R_{n}^{(1,0,1,0)}(0))_{n≥1} is the Catalan numbers. Thus it is not surprising that it is difficult to find a simple expression for R^{(1,0,1,0)}(t, x) since then R^{(1,0,1,0)}(t, 0) would give us an exponential generating function for the Catalan numbers which is not known. It is also easy to see that for any n > 2, the most occurrences of the pattern MMP (1, 0, 1, 0) occurs when σ_{1} = 1 and σ_{n} = n. Clearly, there are (n − 2)! such permutations which explains the coefficients of the largest power of x appearing in (R_{n}^{(1,0,1,0)}(x))_{n≥1}. We note that neither the sequence (R_{n}^{(1,0,1,0)}(x)|_{x})_{n≥3} nor the sequence (R_{n}^{(1,0,1,0)}(x)|_{x^{n−3}})_{n≥3} appear in the OEIS.

We can use similar reasoning to develop a recursion to compute R_{n}^{(1,0,a,0)}(x). That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let

A_{i}^{a}(σ) = χ(σ_{i} matches the pattern MMP (1, 0, a, 0) in σ) and
B_{i}^{a}(σ) = χ(σ_{i} matches the pattern MMP (∅, 0, a, 0) in σ).

Then let

F_{n}^{(1,0,a,0)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) = ∑_{σ∈S_{n}} ∏_{i=2}^{n} x_{i}^{A_{i}^{a}(σ)}y_{i}^{B_{i}^{a}(σ)}.  (16)

We can now use the same analysis that we did to prove (14) to prove that

F_{n+1}^{(1,0,a,0)}(x_{2}, …, x_{n+1}; y_{2}, …, y_{n+1}) = F_{n}^{(1,0,a,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}) +

∑_{i=2}^{a} F_{n}^{(1,0,a,0)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n+1}) +

∑_{i=a+1}^{n} y_{i}F_{n}^{(1,0,a,0)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n+1}).  (17)

The difference in this case is that if n ≥ a, then inserting n + 1 immediately before σ_{1}, …, σ_{a} does not give rise to an extra factor of y_{i}, while inserting n + 1 immediately before σ_{a+1}, …, σ_{n} or at the end does give rise to a factor of y_{i} since then n + 1 matches the pattern MMP (∅, 0, a, 0). It is then easy to see that

R_{n}^{(1,0,a,0)}(x) = F_{n}^{(1,0,a,0)}(x, …, x; 1, …, 1).  (18)

Using (17) and (18) one can compute that for a = 2,

R_{1}^{(1,0,2,0)}(x) = 1,
R_{2}^{(1,0,2,0)}(x) = 2,
R_{3}^{(1,0,2,0)}(x) = 6,
R_{4}^{(1,0,2,0)}(x) = 22 + 2x,
R_{5}^{(1,0,2,0)}(x) = 90 + 26x + 4x^{2},
R_{6}^{(1,0,2,0)}(x) = 394 + 232x + 82x^{2} + 12x^{3},
R_{7}^{(1,0,2,0)}(x) = 1806 + 1776x + 1062x^{2} + 348x^{3} + 48x^{4}, and
R_{8}^{(1,0,2,0)}(x) = 8558 + 12546x + 11118x^{2} + 6022x^{3} + 1836x^{4} + 240x^{5}.

Again, it is easy to see that one obtains the maximum number of MMP (1, 0, 2, 0)-matches in a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n} if either σ_{1} = 1, σ_{2} = 2, and σ_{n} = n or σ_{1} = 2, σ_{2} = 1, and σ_{n} = n. It follows that for n ≥ 4, the coefficient of the highest power of x in R_{n}^{(1,0,2,0)}(x) is 2(n − 3)!. The sequence (R_{n}^{(1,0,2,0)}(0))_{n≥1} whose initial terms are

1, 2, 6, 22, 90, 394, 1806, 8558, …

is the so-called large Schröder numbers, \underline{A006318} in the OEIS. This follows from the fact that avoiding MMP (1, 0, 2, 0) is the same as avoiding simultaneously the patterns 1234 and 2134, a known case (see [3, Table 2.2]). The same numbers count so-called separable permutations (those avoiding simultaneously the patterns 2413 and 3142) and other eight (non-equivalent modulo trivial bijections) classes of avoidance of two (classical) patterns of length 4 (see [3, Table 2.2]). We note that neither the sequence (R_{n}^{(1,0,2,0)}(x)|_{x})_{n≥4} nor the sequence (R_{n}^{(1,0,2,0)}(x)|_{x^{n−4}})_{n≥4} appear in the OEIS.

One can also develop a recursion to compute R_{n}^{(b,0,a,0)}(x) when b ≥ 2 but it is more complicated. That is, in such a case, we have to keep track of the patterns MMP (∅, 0, a, 0), MMP (1, 0, a, 0), …, MMP (b, 0, a, 0). We will show how this works in the case when a = b = 2. That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let

A_{i}^{2,2}(σ) = χ(σ_{i} matches the pattern MMP (2, 0, 2, 0) in σ),
B_{i}^{2,2}(σ) = χ(σ_{i} matches the pattern MMP (1, 0, 2, 0) in σ, but does not match the pattern
MMP (2, 0, 2, 0) in σ) and
C_{i}^{2,2}(σ) = χ(σ_{i} matches the pattern MMP (∅, 0, 2, 0) in σ).

Then let

G_{n}^{(2,0,2,0)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}; z_{3}, …, z_{n}) = ∑_{σ∈S_{n}} ∏_{i=3}^{n} x_{i}^{A_{i}^{2,2}(σ)}y_{i}^{B_{i}^{2,2}(σ)}z_{i}^{C_{i}^{2,2}(σ)}.  (19)

Note that for any σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, we cannot have either σ_{1} or σ_{2} match any of the patterns MMP (∅, 0, 2, 0), MMP (1, 0, 2, 0), or MMP (2, 0, 2, 0) in σ so that is why we do not need variables with subindices 1 or 2. Clearly, for n < 3,

G_{n}^{(2,0,2,0)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}; z_{3}, …, z_{n}) = n!.

For n = 3, we can never have a pattern match for MMP (2, 0, 2, 0) or MMP (1, 0, 2, 0). We can have a pattern match for MMP (∅, 0, 2, 0) only if σ = 123 or σ = 213. Thus G_{3}^{2,2}(x_{3}, y_{3}, z_{3}) = 4 + 2z_{3}.

Consider all the permutations σ^{[i]} where i ∈ {1, 2} as σ ranges over S_{n}. Clearly, since each of these permutations start with n + 1 or has its second element equal to n + 1, n + 1 does not contribute to either mmp^{(2,0,2,0)}(σ^{[i]}), mmp^{(1,0,2,0)}(σ^{[i]}), or mmp^{(∅,0,2,0)}(σ^{[i]}). Moreover n + 1 does not effect whether any other σ_{i} contributes to mmp^{(2,0,2,0)}(σ^{[i]}), mmp^{(1,0,2,0)}(σ^{[i]}), or mmp^{(∅,0,2,0)}(σ^{[i]}), but it does shift the index over by 1. Thus the contribution of the permutations of the form σ^{[1]} and σ^{[2]} to G_{n+1}^{(2,0,2,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}; z_{3}, …, z_{n+1}) is just 2G_{n}^{(2,0,2,0)}(x_{4}, …, x_{n+1}; y_{4}, …, y_{n+1}, z_{4}, …, z_{n+1}). Fix i ≥ 3 and consider all the permutations σ^{[i]} as σ ranges over S_{n}. For j < i, if A_{j}(σ) = 1, then A_{j}(σ^{[i]}) = 1, if B_{j}(σ) = 1, then A_{j}(σ^{[i]}) = 1 and if C_{j}(σ) = 1, then B_{j}(σ^{[i]}) = 1. For j ≥ i, if A_{j}(σ) = 1, then A_{j+1}(σ^{[i]}) = 1, if B_{j}(σ) = 1, then B_{j+1}(σ^{[i]}) = 1 and if C_{j}(σ) = 1, then C_{j+1}(σ^{[i]}) = 1. Moreover, the fact that n + 1 is in position i in σ^{[i]} means that C_{i}(σ^{[i]}) = 1. Since at most one of A_{i}(σ) = 1, B_{i}(σ) = 1, and C_{i}(σ) = 1 can hold for any i, it follows that the contribution of the permutations of the form σ^{[i]} to G_{n+1}^{(2,0,2,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}; z_{3}, …, z_{n+1}) is just z_{i}F_{n}(x_{3}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{3}, …, x_{i−1}, y_{i+1}, …, y_{n+1}; y_{3}, …, y_{i−1}, z_{i+1}, …, z_{n+1}). Thus

G_{n+1}^{(2,0,2,0)}(x_{3}, …, x_{n+1}; y_{3}, …, y_{n+1}; z_{3}, …, z_{n+1}) =

2G_{n+1}^{(2,0,2,0)}(x_{4}, …, x_{n+1}; y_{4}, …, y_{n+1}; z_{4}, …, z_{n+1}) +

∑_{i=3}^{n+1} z_{i}G_{n}^{(2,2)}(x_{3}, …, x_{i−1}, x_{i+1}, …, x_{n+1}; x_{2}, …, x_{i−1},

y_{i+1}, …, y_{n+1}; y_{3}, …, y_{i−1}, z_{i+1}, …, z_{n+1}). (20)

It is then easy to see that

R_{n}^{(2,0,2,0)}(x) = G_{n}^{(2,0,2,0)}(x, …, x; 1, …, 1; 1, …, 1).  (21)

Using (20) and (21) one can compute that R_{1}^{(2,0,2,0)}(x) = 1, R_{2}^{(2,0,2,0)}(x) = 2, R_{3}^{(2,0,2,0)}(x) = 6, R_{4}^{(2,0,2,0)}(x) = 24, R_{5}^{(2,0,2,0)}(x) = 116 + 4x, R_{6}^{(2,0,2,0)}(x) = 632 + 80x + 8x^{2}, R_{7}^{(2,0,2,0)}(x) = 3720 + 1056x + 240x^{2} + 24x^{3}, and R_{8}^{(2,0,2,0)}(x) = 23072 + 11680x + 4480x^{2} + 992x^{3} + 96x^{4}.

Again, it is easy to see that one obtains the maximum number of MMP (2, 0, 2, 0)-matches in a permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n} if {σ_{1}, σ_{2}} = {1, 2} and {σ_{n−1}, σ_{n}} = {n − 1, n}. It follows that for n ≥ 5, the coefficient of the highest power of x in R_{n}^{(1,0,2,0)}(x) is 4(n − 4)!. In this case, the sequence (R^{(2,0,2,0)}(0))_{n≥1} does not appear in the OEIS, but it clearly counts the number of permutations which avoid the permutations 12345, 21345, 12354, and 21354.

While we cannot find a formula for R^{(1,0,1,0)}(t, x), we can find a restricted version of this generating function. That is, let S_{n}(1 → n) denote the set of permutations σ = σ_{1} ⋯ σ_{n} such that 1 appears to the left of n in σ. Then let

B^{(1,0,1,0)}(t, x) = ∑_{n≥2} B_{n}^{(1,0,1,0)}(x)\frac{t^{n−2}}{(n − 2)!}  (22)

where

B_{n}^{(1,0,1,0)}(x) = ∑_{σ∈S_{n}(1→n)} x^{mpp^{(1,0,1,0)}(σ)}.

Let S_{n}(i, j) denote the set of all permutations σ = σ_{1} ⋯ σ_{n} ∈ S_{n} such that σ_{i} = 1 and σ_{j} = n where 1 ≤ i < j ≤ n. It is easy to see that for s < i, σ_{s} matches the pattern MMP (1, 0, 1, 0) in σ if and only if σ_{s} matches the pattern MMP (0, 0, 1, 0) in σ_{1} ⋯ σ_{i−1}. Clearly if i < s < j, then σ_{s} matches the pattern MMP (1, 0, 1, 0) in σ. Finally, if j < s ≤ n, then σ_{s} matches the pattern MMP (1, 0, 1, 0) in σ if and only if σ_{s} matches the pattern MMP (1, 0, 0, 0) in σ_{j+1} ⋯ σ_{n}. It follows that

B_{n}^{(1,0,1,0)}(x) = ∑_{1≤i<j≤n} \binom{n − 2}{i − 1, j − i − 1, n − j}(j − i − 1)!x^{j−i−1}R_{i−1}^{(0,0,1,0)}(x)R_{n−j}^{(1,0,0,0)}(x)

or, equivalently,

\frac{B_{n}^{(1,0,1,0)}(x)}{(n − 2)!} = ∑_{1≤i<j≤n} x^{j−i−1} \frac{R_{i−1}^{(0,0,1,0)}(x)}{(i − 1)!} \frac{R_{n−j}^{(1,0,0,0)}(x)}{(n − j)!}

= ∑_{a,b,c≥0,a+b+c=n−2} x^{a} \frac{R_{b}^{(0,0,1,0)}(x)}{b!} \frac{R_{c}^{(1,0,0,0)}(x)}{c!}.  (23)

It is easy to see from (2) that R^{(1,0,0,0)}(t, x) = R^{(0,0,1,0)}(t, x) = (1 − tx)^{−1/x}. Multiplying (23) by \frac{t^{n−2}}{(n−2)!} and summing for n ≥ 2, we obtain

B^{(1,0,1,0)}(t, x) = \frac{1}{(1 − tx)}R^{(0,0,1,0)}(t, x)R^{(0,0,1,0)}(t, x) = (1 − tx)^{−1− \frac{2}{x}} .  (24)

One can use (24) to show that for n ≥ 1,

B_{2n}^{(1,0,1,0)}(x) = 2^{n−1} ∏_{i=1}^{n−1}(1 + ix) ∏_{i=1}^{n−1}(2 + (2i − 1)x)  (25)

and

B_{2n−1}^{(1,0,1,0)}(x) = 2^{n−1} ∏_{i=1}^{n−2}(1 + ix) ∏_{i=1}^{n−1}(2 + (2i − 1)x).  (26)

Problem 6. Can one find a direct explanation of formulas (25) and (26)?

For example, it follows that the number of permutations σ ∈ S_{n}(1 → n) which avoid MMP (1, 0, 1, 0) is 2^{n−2}. This is easy to see since to avoid MMP (1, 0, 1, 0) one must have 1 and n adjacent and there must be decreasing sequences on either side of 1 and n. Thus such a permutation is determined by choosing for each i ∈ {2, …, n − 1} whether it is placed on the left or the right of the adjacent pair 1n.

There is a second class of permutations for which it is easy to compute the generating function for the distribution of matches of the pattern MMP (1, 0, 1, 0). That is, suppose that k, ℓ > 0 and n > k + ℓ, Let β = β_{1} ⋯ β_{k} be any permutation of n − k + 1, …, n and α = α_{1} … α_{ℓ} be any permutation of 1, …, ℓ. Then we let S\overline{βα} ; n denote the set of permutations σ ∈ S_{n} such that βα is a consecutive sequence in σ. Now suppose that a ≤ k, b ≤ ℓ, mmp^{(a,0,0,0)}(red(β)) = 0, mmp^{(0,0,b,0)}(red(α)) = 0, and

R_{n}^{(a,0,b,0),\overline{βα}}(x) = ∑_{σ∈S\overline{βα} ; n} x^{mmp^{(a,0,b,0)}(σ)}.

Then we claim that for n > k + ℓ,

R_{n}^{(a,0,b,0),\overline{βα}}(x) = ∑_{i=0}^{n−k−ℓ} \binom{n − k − ℓ}{i}R_{i}^{(0,0,b,0)}(x)R_{n−k−ℓ−i}^{(a,0,0,0)}(x).

That is, suppose that σ ∈ S\overline{βα} ; n is a permutation where there are i elements to the left of the occurrence of βα. Then a σ_{j} with j ≤ i matches the pattern MMP (a, 0, b, 0) in σ if and only if σ_{j} matches the pattern MMP (0, 0, b, 0) in σ_{1} ⋯ σ_{i}. Similarly for j > i + k + ℓ, σ_{j} matches the pattern MMP (a, 0, b, 0) in σ if and only if σ_{j} matches the pattern MMP (a, 0, 0, 0) in σ_{k+ℓ+1} ⋯ σ_{n}. Finally our assumptions ensure that none of the elements in \overline{βα} matches the pattern MMP (a, 0, b, 0) in σ. It then follows that

R^{(a,0,b,0),\overline{βα}}(t, x) = ∑_{n≥k+ℓ} \frac{t^{n−k−ℓ}}{(n − k − ℓ)!}R_{n}^{(a,0,b,0),\overline{βα}}(x) = R^{(a,0,0,0)}(t, x)R^{(0,0,b,0)}(t, x).

For example, since R^{(0,0,1,0)}(t, x) = R^{(1,0,0,0)}(t, x) = (1 − tx)^{−1/x}, it follows that

R^{(1,0,1,0),\overline{n1}}(t, x) = ∑_{n≥2} \frac{t^{n−2}}{(n − 2)!}R_{n}^{(1,0,1,0),\overline{n1}}(x)

= (1 − tx)^{−2/x} = 1 + ∑_{n≥1} \frac{t^{n}}{n!} ∏_{i=0}^{n−1}(2 + ix).

7 R_{n}^{(1,0,1,1)}(x) = R_{n}^{(0,1,1,1)}(x) = R_{n}^{(1,1,0,1)}(x) = R_{n}^{(1,1,1,0)}(x)

The equalities in the section title are true by Lemma 1. Thus we shall only consider R_{n}^{(1,0,1,1)}(x).

In this case, we can develop a recursion to compute R_{n}^{(1,0,1,1)}(x) which is very similar to the recursion that we developed to compute R_{n}^{(1,0,1,0)}(x). That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let

C_{i}(σ) = χ(σ_{i} matches the pattern MMP (1, 0, 1, 1) in σ) and
D_{i}(σ) = χ(σ_{i} matches the pattern MMP (∅, 0, 1, 1) in σ).

Then let

F_{n}^{(1,0,1,1)}(x_{2}, …, x_{n−1}; y_{2}, …, y_{n−1}) = ∑_{σ∈S_{n}} ∏_{i=2}^{n−1} x_{i}^{C_{i}(σ)}y_{i}^{D_{i}(σ)}.

Note that σ_{1} and σ_{n} never contribute to mmp^{(1,0,1,1)}(σ) or mmp^{(∅,0,1,1)}(σ) so that F_{n}^{(1,0,1,1)}(x_{2}, …, x_{n−1}; y_{2}, …, y_{n−1}) records all the information about the contributions of 2, …, n − 1 to mmp^{(1,0,1,1)}(σ) or mmp^{(∅,0,1,1)}(σ) as σ ranges over S_{n}.

First consider all the permutations σ^{[1]} as σ ranges over S_{n}. Clearly, since each of these permutations starts with n + 1, n + 1 does not contribute to either mmp^{(1,0,1,1)}(σ^{[1]}) or mmp^{(∅,0,1,1)}(σ^{[1]}). Moreover, n + 1 does not effect whether any other σ_{i} contributes to mmp^{(1,0,1,1)}(σ^{[1]}) or mmp^{(∅,0,1,1)}(σ^{[1]}), but it does shift the index over by 1. Thus the contribution of the permutations of the form σ^{[1]} to F_{n+1}^{(1,0,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) is just F_{n}^{(1,0,1,1)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}). Next consider all the permutations σ^{[n+1]} as σ ranges over S_{n}. Clearly, since each of these permutations ends with n + 1, n + 1 does not contribute to either mmp^{(1,0,1,1)}(σ) or mmp^{(∅,0,1,1)}(σ). However, while n + 1 does not effect whether any other i contributes to mmp^{(1,0,1,1)}(σ), it does ensure that each (i, σ_{i}) that contributed to mmp^{(∅,0,1,1)}(σ) will now contribute to mmp^{(1,0,1,1)}(σ^{[n+1]}). Thus it is easy to see that the contribution of the permutations of the form σ^{[n+1]} to F_{n+1}^{(1,0,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) is just F_{n}^{(1,0,1,1)}(x_{2}, …, x_{n−1}; x_{2}, …, x_{n−1}). For 2 ≤ i ≤ n, again consider all the permutations σ^{[i]} as σ ranges over S_{n}. For j < i, if C_{j}(σ) = 1, then C_{j}(σ^{[i]}) = 1 and if D_{j}(σ) = 1, then C_{j}(σ^{[i]}) = 1. For j ≥ i, if C_{j}(σ) = 1, then C_{j+1}(σ^{[i]}) = 1 and if D_{j}(σ) = 1, then D_{j+1}(σ^{[i]}) = 1. Moreover, the fact that n + 1 is in position i in σ^{[i]} means that D_{i}(σ^{[i]}) = 1. Since at most one of C_{i}(σ) = 1 and D_{i}(σ) = 1 holds, it follows that the contribution of the permutations of the form σ^{[i]} to F_{n+1}^{(1,0,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) is just

y_{i}F_{n}^{(1,0,1,1)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n}).

Thus

F_{n+1}^{(1,0,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}) = F_{n}^{(1,0,1,1)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}) +
F_{n}^{(1,0,1,1)}(x_{2}, …, x_{n−1}; x_{2}, …, x_{n−1}) +
∑_{i=2}^{n−1} y_{i}F_{n}^{(1,0,1,1)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n}).  (27)

It is then easy to see that

R_{n}^{(1,0,1,1)}(x) = F_{n}^{(1,0,1,1)}(x, …, x; 1, …, 1).  (28)

Using (27) and (28) one can compute that

R_{1}^{(1,0,1,1)}(x) = 1,
R_{2}^{(1,0,1,1)}(x) = 2,
R_{3}^{(1,0,1,1)}(x) = 6,
R_{4}^{(1,0,1,1)}(x) = 20 + 4x,
R_{5}^{(1,0,1,1)}(x) = 70 + 42x + 8x^{2},
R_{6}^{(1,0,1,1)}(x) = 252 + 300x + 144x^{2} + 24x^{3},
R_{7}^{(1,0,1,1)}(x) = 924 + 1812x + 1572x^{2} + 636x^{3} + 96x^{4}, and
R_{8}^{(1,0,1,1)}(x) = 3432 + 9960x + 13440x^{2} + 9576x^{3} + 3432x^{4} + 480x^{5}.

In this case, the sequence (R_{n}^{(1,0,1,1)}(0)) is \underline{A000984} in the OEIS which is the sequence whose n-th term is the central binomial coefficient \binom{2n}{n} which has lots of combinatorial interpretations. That is, we claim that R_{n}^{(1,0,1,1)}(0) = \binom{2n−2}{n−1}. Note that avoiding MMP (1, 0, 1, 1) is equivalent to simultaneously avoiding the patterns 1324, 1342, 2314 and 2341, which, in turn, by applying the complement is equivalent to simultaneous avoidance of the patterns 4231, 4213, 3241 and 3214. It is a known fact (see [3, Subsection 6.1.1]) that the number of permutations in S_{n} avoiding simultaneously the patterns 4132, 4123, 3124 and 3142 is given by \binom{2n−2}{n−1}. Mark Tiefenbruck [8] has constructed a bijection between the set of permutations of S_{n} which simultaneously avoid the patterns 4132, 4123, 3124 and 3142 and the set of permutations of S_{n} which simultaneously avoid the patterns 4231, 4213, 3241 and 3214. Indeed, this is a special case of a more general bijection which will appear in a forthcoming paper by Remmel and Tiefenbruck [9] so we will not give the details here.

In this case, it is also easy to understand the coefficient of the highest power of x in the polynomial R_{n}^{(1,0,1,1)}(x). That is, one obtains the maximum number of occurrences of the pattern MMP (1, 0, 1, 1) when the permutation σ either starts with 1 and ends with either 2 n or n 2 or it starts with 2 and ends with either 1 n or n 1. Thus it is easy to see that the coefficient of the highest power of x occurring in R_{n}^{(1,0,1,1)}(x) is 4((n − 3)!)x^{n−3} for n ≥ 4.

While we cannot find a formula for R^{(1,0,1,1)}(t, x), we can find generating functions for the distribution of MMP (1, 0, 1, 1)-matches in certain restricted classes of permutations. That is, let

B^{(1,0,1,1)}(t, x) = ∑_{n≥2} B_{n}^{(1,0,1,1)}(x)\frac{t^{n−2}}{(n − 2)!}

where

B_{n}^{(1,0,1,1)}(x) = ∑_{σ∈S_{n}(1→n)} x^{mpp^{(1,0,1,1)}(σ)}.

Consider the set S_{n}^{(k+1)} of all permutations σ = σ_{1} ⋯ σ_{n} ∈ S_{n} such that σ_{k+1} = 1 and σ_{j} = n for some k + 1 < j ≤ n. It is easy to see that for s ≤ k, σ_{s} matches the pattern MMP (1, 0, 1, 1) in σ if and only if σ_{s} matches the pattern MMP (0, 0, 1, 0) in σ_{1} ⋯ σ_{k}. Clearly σ_{k+1} = 1 does not match the pattern MMP (1, 0, 1, 1) in σ. If k + 1 < s ≤ n, then σ_{s} matches the pattern MMP (1, 0, 1, 1) in σ if and only if σ_{s} matches the pattern MMP (1, 0, 0, 1) in σ_{k+2} ⋯ σ_{n}. It follows that

B_{n}^{(1,0,1,1)}(x) = ∑_{k=0}^{n−2} \binom{n − 2}{k}R_{k}^{(0,0,1,0)}(x)R_{n−k−1}^{(1,0,0,1)}(x)

or, equivalently,

\frac{B_{n}^{(1,0,1,1)}(x)}{(n − 2)!} = ∑_{k=0}^{n−2} \frac{R_{k}^{(0,0,1,0)}(x)}{k!} \frac{R_{n−k−1}^{(1,0,0,1)}(x)}{(n − 2 − k)!}  (29)

Multiplying (29) by \frac{t^{n−2}}{(n−2)!} and summing for n ≥ 2, we obtain

B^{(1,0,1,1)}(t, x) = R^{(0,0,1,0)}(t, x) ∑_{n≥0} \frac{t^{n}}{n!}R_{n+1}^{(1,0,0,1)}(x).

By (6), we have that

∑_{n≥0} \frac{t^{n}}{n!}R_{n+2}^{(1,0,0,1)}(x) = 2(1 − tx)^{− \frac{2}{x} −1}.

Hence

∑_{n≥0} \frac{t^{n}}{n!}R_{n+1}^{(1,0,0,1)}(x) = 1 + ∫_{0}^{t} 2(1 − zx)^{− \frac{2}{x} −1}dz = (1 − tx)^{−2/x}.

Since R^{(0,0,1,0)}(t, x) = (1 − tx)^{−1/x}, we obtain

B^{(1,0,1,1)}(t, x) = (1 − tx)^{−3/x} = 1 + 3t + ∑_{n≥2} \frac{t^{n}}{n!} ∏_{i=0}^{n−1}(3 + ix).

For example, it follows that the number of permutations σ ∈ S_{n}(1 → n) which avoid MMP (1, 0, 1, 1) is 3^{n}.

Next suppose that k, ℓ > 0 and n > k+ℓ, and let γ_{k,ℓ} = n(n−1) ⋯ (n−k+1)ℓ(ℓ−1) ⋯ 1. Then we let S\overline{γ_{k,ℓ}} ; n denote the set of permutations σ ∈ S_{n} such that γ_{k,ℓ} is a consecutive sequence in σ and

R_{n}^{(1,0,1,1),\overline{γ_{k,ℓ}}}(x) = ∑_{σ∈S\overline{γ_{k,ℓ}} ; n} x^{mmp^{(1,0,1,1)}(σ)}.

Then it is easy to see that for n > k + ℓ,

R_{n}^{(1,0,1,1),\overline{γ_{k,ℓ}}}(x) = ∑_{i=0}^{n−k−ℓ} \binom{n − k − ℓ}{i}R_{i}^{(0,0,1,0)}(x)R_{n−k−ℓ−i}^{(1,0,0,1)}(x).  (30)

That is, if σ ∈ S\overline{γ_{k,ℓ}} ; n is such that there are i elements to the left of the occurrence of γ_{k,ℓ}, then a σ_{j} with j ≤ i matches the pattern MMP (1, 0, 1, 1) in σ if and only if σ_{j} matches the pattern MMP (0, 0, 1, 0) in σ_{1} ⋯ σ_{i}. Similarly for j > i + k + ℓ, σ_{j} matches the pattern MMP (1, 0, 1, 1) in σ if and only if σ_{j} matches the pattern MMP (1, 0, 0, 1) in σ_{k+ℓ+1} ⋯ σ_{n}. Clearly no element that is part of γ_{k,ℓ} can match MMP (1, 0, 1, 1) in σ.

It then follows that

R^{(1,0,1,1),\overline{γ_{k,ℓ}}}(t, x) = ∑_{n≥k+ℓ} \frac{t^{n−k−ℓ}}{(n − k − ℓ)!}R_{n}^{(1,0,1,1),\overline{γ_{k,ℓ}}}(x) = R^{(1,0,0,0)}(t, x)R^{(1,0,0,1)}(t, x).

Since

∑_{n≥1} \frac{t^{n−1}}{(n − 1)!}R_{n}^{(1,0,0,1)}(x) = (1 − tx)^{−2/x},

we have that

∑_{n≥0} \frac{t^{n}}{n!}R_{n}^{(1,0,0,1)}(x) = 1 + ∫_{0}^{t}(1 − zx)^{−2/x}dz = \frac{1 − x + (1 − tx)^{1− \frac{2}{x}}}{2 − x} .

Hence,

R^{(1,0,1,1),\overline{n1}}(t, x) = ∑_{n≥2} \frac{t^{n−2}}{(n − 2)!}R_{n}^{(1,0,1,1),\overline{n1}}(x)

= (1 − tx)^{−1/x} \frac{1 − x + (1 − tx)^{1− \frac{2}{x}}}{2 − x} .

One can use Mathematica to show that

R^{(1,0,1,1),\overline{n1}}(t, x) = 1 + 2t + (5 + x)\frac{t^{3}}{3!} + (14 + 8x + 2x^{2})\frac{t^{4}}{4!} +

(41 + 50x + 23x^{2} + 6x^{3})\frac{t^{5}}{5!} + (122 + 268x + 214x^{2} + 92x_{2}^{3}4x^{4})\frac{t^{6}}{6!} +

(365 + 1283x + 1689x^{2} + 1117x^{3} + 466x^{4} + 120x^{5})\frac{t^{7}}{7!} +

(1094 + 5660x + 11412 + 11656x^{3} + 6934x^{4} + 2844x^{5} + 720x^{6})\frac{t^{8}}{8!} +

(3281 + 23524x + 68042x^{2} + 102880x^{3} + 89849x^{4} +

49996x^{5} + 20268x^{6} + 5040x^{7})\frac{t^{9}}{9!} + ⋯

The sequence (R_{n}^{(1,0,1,1),\overline{n1}}(0))_{n≥0} is

1, 2, 5, 14, 41, 122, 365, 1094, 3281, …

which is sequence \underline{A007051} in the OEIS whose n-th term is \frac{1+3^{n}}{2} . This is easily explained from the recursion (30) which shows that for n ≥ 2,

R_{n}^{(1,0,1,1),\overline{n1}} = ∑_{k=0}^{n−2} \binom{n − 2}{k}R_{k}^{(0,0,1,0)}(0)R_{n−k−1}^{(1,0,0,1)}(0).

Now R_{k}^{(0,0,1,0)}(0) = 1 since only the decreasing permutation σ = n(n − 1) ⋯ 21 has no MMP (0, 0, 1, 0) matches and R_{n−k−1}^{(1,0,0,1)}(0) = 2^{n−k−1} by (5). Thus

R_{n}^{(1,0,1,1),\overline{n1}}(0) = ∑_{k=0}^{n−2} \binom{n − 2}{k}2^{n−k−1}

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

Also the coefficient of the highest power of x occurring in R_{n}^{(1,0,1,1),\overline{n1}}(x) is (n − 3)! for n ≥ 4 which counts all the permutations that start with 2 and end with n1.

8 The function R_{n}^{(1,1,1,1)}(x)

We can develop a recursion to compute R_{n}^{(1,1,1,1)}(x) but our recursion will require 4 sets of variables. That is, for any permutation σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, let

K_{i}(σ) = χ(σ_{i} matches the pattern MMP (1, 1, 1, 1) in σ),
L_{i}(σ) = χ(σ_{i} matches the pattern MMP (∅, 1, 1, 1) in σ),
M_{i}(σ) = χ(σ_{i} matches the pattern MMP (1, ∅, 1, 1) in σ), and
N_{i}(σ) = χ(σ_{i} matches the pattern MMP (∅, ∅, 1, 1) in σ).

Then let

H_{n}^{(1,1,1,1)}(x_{2}, …, x_{n−1}; y_{2}, …, y_{n−1}; z_{2}, …, z_{n−1}; w_{2}, …, w_{n−1})

= ∑_{σ∈S_{n}} ∏_{i=2}^{n} x_{i}^{K_{i}(σ)}y_{i}^{L_{i}(σ)}z_{i}^{M_{i}(σ)}w_{i}^{N_{i}(σ)}.

First consider all the permutations σ^{[1]} as σ ranges over S_{n}. The point (1, n + 1) in σ^{[1]} does not contribute to either mmp^{(1,1,1,1)}(σ^{[1]}), mmp^{(∅,1,1,1)}(σ^{[1]}), mmp^{(1,∅,1,1)}(σ^{[1]}), or mmp^{(∅,∅,1,1)}(σ^{[1]}). However,

1. if K_{i}(σ) = 1, then K_{i+1}(σ^{[1]}) = 1,

2. if L_{i}(σ) = 1, then L_{i+1}(σ^{[1]}) = 1,

3. if M_{i}(σ) = 1, then K_{i+1}(σ^{[1]}) = 1, and

4. if N_{i}(σ) = 1, then L_{i+1}(σ^{[1]}) = 1. It follows that the contribution of the permutations of the form σ^{[1]} to H_{n+1}^{(1,1,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}; z_{2}, …, z_{n}; w_{2}, …, w_{n}) is

H_{n}^{(1,1,1,1)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}; x_{3}, …, x_{n}; y_{3}, …, y_{n}).

Next consider all the permutations σ^{[n+1]} as σ ranges over S_{n}. Clearly, since each of these permutations ends with n+1, n+1 does not contribute to mmp^{(1,1,1,1)}(σ^{[n+1]}), mmp^{(∅,1,1,1)}(σ^{[n+1]}), mmp^{(1,∅,1,1)}(σ^{[n+1]}),or mmp^{(∅,∅,1,1)}(σ^{[n+1]}). However,

1. if K_{i}(σ) = 1, then K_{i}(σ^{[1]}) = 1,

2. if L_{i}(σ) = 1, then K_{i}(σ^{[1]}) = 1,

3. if M_{i}(σ) = 1, then M_{i}(σ^{[1]}) = 1, and

4. if N_{i}(σ) = 1, then M_{i}(σ^{[1]}) = 1. It follows that the contribution of the permutations of the form σ^{[n+1]} to H_{n+1}^{(1,1,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}; z_{2}, …, z_{n}; w_{2}, …, w_{n}) is

H_{n}^{(1,1,1,1)}(x_{2}, …, x_{n−1}; x_{2}, …, x_{n−1}; z_{2}, …, z_{n−1}; z_{2}, …, z_{n−1}).

For 2 ≤ i ≤ n, again consider all the permutations σ^{[i]} as σ ranges over S_{n}. First note that the fact that n + 1 is in position i means that N_{i}(σ^{[i]}) = 1. Then for j < i,

1. if K_{j}(σ) = 1, then K_{j}(σ^{[i]}) = 1,

2. if L_{j}(σ) = 1, then K_{j}(σ^{[i]}) = 1,

3. if M_{j}(σ) = 1, then M_{j}(σ^{[i]}) = 1, and

4. if N_{j}(σ) = 1, then M_{j}(σ^{[i]}) = 1. Similarly, for j ≥ i,

1. if K_{j}(σ) = 1, then K_{j+1}(σ^{[i]}) = 1,

2. if L_{j}(σ) = 1, then L_{j+1}(σ^{[i]}) = 1,

3. if M_{j}(σ) = 1, then K_{j+1}(σ^{[i]}) = 1, and

4. if N_{j}(σ) = 1, then L_{j+1}(σ^{[i]}) = 1. It follows that for 2 ≤ i ≤ n, the contribution of the permutations of the form σ^{[i]} to H_{n+1}^{(1,1,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}; z_{2}, …, z_{n}; w_{2}, …, w_{n}) is

w_{i}H_{n}^{(1,1,1,1)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n};
z_{2}, …, z_{i−1}, x_{i+1}, …, x_{n}; z_{2}, …, z_{i−1}, y_{i+1}, …, y_{n})

Thus

H_{n+1}^{(1,1,1,1)}(x_{2}, …, x_{n}; y_{2}, …, y_{n}; z_{2}, …, z_{n+1}; w_{2}, …, w_{n}) =  (31)

H_{n}^{(1,1,1,1)}(x_{3}, …, x_{n}; y_{3}, …, y_{n}; x_{3}, …, x_{n}; y_{3}, …, y_{n}) +

H_{n}^{(1,1,1,1)}(x_{2}, …, x_{n−1}; x_{2}, …, x_{n−1}; z_{2}, …, z_{n−1}; z_{2}, …, z_{n−1}) +

∑_{i=2}^{n} w_{i}H_{n}^{(1,1,1,1)}(x_{2}, …, x_{i−1}, x_{i+1}, …, x_{n}; x_{2}, …, x_{i−1}, y_{i+1}, …, y_{n};

z_{2}, …, z_{i−1}, x_{i+1}, …, x_{n}; z_{2}, …, z_{i−1}, y_{i+1}, …, y_{n}).

It is then easy to see that

R_{n}^{(1,1,1,1)}(x) = H_{n}^{(1,1,1,1)}(x, …, x; 1, …, 1; 1, …, 1; 1, …, 1).  (32)

Note that for all σ ∈ S_{3}

mmp^{(1,1,1,1)}(σ) = mmp^{(∅,1,1,1)}(σ) = mmp^{(1,∅,1,1)}(σ) = 0.

However, for mmp^{(∅,∅,1,1)}(σ) = 1 if σ equals 132 or 231. Thus

H_{3}^{(1,1,1,1)}(x_{2}, y_{2}, z_{2}, w_{2}) = 4 + 2w_{2}.

Using (31) and (32), one can compute that

R_{1}^{(1,1,1,1)}(x) = 1,
R_{2}^{(1,1,1,1)}(x) = 2,
R_{3}^{(1,1,1,1)}(x) = 6,
R_{4}^{(1,1,1,1)}(x) = 24,
R_{5}^{(1,1,1,1)}(x) = 104 + 16x,
R_{6}^{(1,1,1,1)}(x) = 464 + 224x + 32x^{2},

R_{7}^{(1,1,1,1)}(x) = 2088 + 2088x + 768x^{2} + 96x^{3}, and

R_{8}^{(1,1,1,1)}(x) = 9392 + 16096x + 11056x^{2} + 3392x^{3} + 384x^{4}.

In this case, the sequence (R_{n}^{(1,1,1,1)}(0))_{n≥1} seems to be \underline{A128652} in the OEIS, which is the number of square permutations of length n. There is a formula for the numbers, namely,

a(n) = 2(n + 2)4^{n−3} − 4^{2n−5}\binom{2n − 6}{n − 3}.

Problem 7. Can we prove this formula (directly)?

In this case, it is again easy to understand the coefficient of the highest power of x occurring in the polynomial R_{n}^{(1,1,1,1)}(x). That is, one obtains the maximum number of occurrences of the pattern MMP (1, 1, 1, 1) when the permutation σ either

(i) starts with 1 (n − 1) or (n − 1) 1 and ends with either 2 n or n 2, (ii) starts with 2 (n − 1) or (n − 1) 2 and ends with either 1 n or n 1, (iii) starts with 1 n or n 1 and ends with either 2 (n − 1) or (n − 1) 2, or (iv) starts with 2 n or n 2 and ends with either 1 (n − 1) or (n − 1) 1. Thus it is easy to see that the coefficient of the highest power of x occurring in R_{n}^{(1,1,1,1)}(x) is 16((n − 4)!)x^{n−4} for n ≥ 5.

9 Conclusion

In this paper, we have began the study of the distributions of quadrant marked mesh patterns of the form MMP (a, b, c, d) in S_{n} and certain subsets of S_{n}. As is evidenced by several of our examples, avoiding a quadrant mesh pattern MMP (a, b, c, d) is equivalent to simultaneously avoiding certain classes of classical patterns. For example, avoiding the quadrant mesh pattern MMP (1, 1, 1, 1) is equivalent to simultaneously avoiding all classical patterns of the form σ_{1}σ_{2}σ_{3}σ_{4}σ_{5} where σ_{3} = 3 and {σ_{1}, σ_{2}} is either {1, 4}, {2, 4}, {1, 5}, or {2, 5}. Thus our results also give results on classical pattern avoidance. Note, however, that our distribution results are not necessarily equivalent to studying the occurrences of such patterns. For example, avoiding MMP (1, 0, 0, 0) is equivalent to avoiding the classical pattern 12. The number of occurrences of the pattern 12 in a permutation σ is the number of coinversions in σ. However, mmp^{(1,0,0,0)}(132) = 1 while coinv(σ)(132) = 2 since 1 participates in 2 coinversions in 132 but only contributes 1 to mmp^{(1,0,0,0)}(132).

There are several other special subclasses of permutations where we have studied the distribution of the quadrant mesh patterns MMP (a, b, c, d). For example, with Mark Tiefenbruck, we have studied the distribution of quadrant mesh patterns in 132-avoiding permutations where we can find explicit formulas for generating functions of the form

∑_{n≥0} t^{n} ∑_{σ∈S_{n}(132)} x^{mmp^{(a,b,c,d)}(σ)}.

See [5, 6]. Similarly in [4], we have found generating functions of the form

1 + ∑_{n≥1} \frac{t^{2n}}{(2n)!} ∑_{σ∈UD_{2n}} x^{mmp^{(a,b,c,d)}(σ)}

and

∑_{n≥1} \frac{t^{2n−1}}{(2n − 1)!} ∑_{σ∈UD_{2n−1}} x^{mmp^{(a,b,c,d)}(σ)}

where UD_{n} is the set of up-down permutations of S_{n} and (a, b, c, d) is any four-tuple which has one 1 and three 0s. For example, we have shown that

1 + ∑_{n≥1} \frac{t^{2n}}{(2n)!} ∑_{σ∈UD_{2n}} x^{mmp^{(1,0,0,0)}(σ)} = sec(xt)^{1/x}.

10 Acknowledgements

We are grateful to the anonymous referees for many helpful comments and suggestions.

References

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

[2] Í. Hilmarsson, I. Jónsdóttir, S. Sigurdardottir, and S. Vidarsdóttir, Wilf classification of mesh patterns of short length, preprint.

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

[4] S. Kitaev and J. Remmel, Quadrant marked mesh patterns in alternating permutations, preprint.

[5] S. Kitaev, J. Remmel, and M. Tiefenbruck, Quadrant marked mesh patterns in 132avoiding permutations I, preprint.

[6] S. Kitaev, J. Remmel, and M. Tiefenbruck, Quadrant marked mesh patterns in 132avoiding permutations II, in preparation.

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

   at http://oeis.org.

[8] M. Tiefenbruck, personal communication.

[9] J. Remmel and M. Tiefenbruck, Extending bijections which preserve marked occurrence of patterns to bijection which preserve all occurrences of patterns, preprint.

[10] H. Úlfarsson, A unification of permutation patterns related to Schubert varieties,

   preprint. Available at http://arxiv.org/abs/1002.4361.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05E05. Keywords: permutation statistics, marked mesh patterns, distribution.

(Concerned with sequences \underline{A000254}, \underline{A000399}, \underline{A000774}, \underline{A000984}, \underline{A001712}, \underline{A006318}, \underline{A007051}, and \underline{A128652}.)

Received January 4 2012; revised version received April 1 2012. Published in Journal of Integer Sequences, April 11 2012.

Return to Journal of Integer Sequences home page.