Séminaire Lotharingien de Combinatoire 68 (2012), Article B68a

QUADRANT MARKED MESH PATTERNS IN ALTERNATING PERMUTATIONS

SERGEY KITAEV AND JEFFREY REMMEL

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

                   E-mail: sergey.kitaev@cis.strath.ac.uk

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

                         E-mail: jremmel@ucsd.edu

Abstract. This paper is a continuation of the systematic study of the distribution of quadrant marked mesh patterns initiated by the authors in [J. Integer Sequences 12 (2012), Article 12.4.7]. We study quadrant marked mesh patterns on up-down and down-up permutations, also known as alternating and reverse alternating permutations, respectively. In particular, we refine classical enumeration results of André [C. R. Acad. Sci. Paris 88 (1879), 965–967; J. Math. Pur. Appl. 7 (1881), 167–184] on alternating permutations by showing that the distribution with respect to the quadrant marked mesh pattern of interest is given by (sec(xt))^{1/x} on up-down permutations of even length and by ∫_{0}^{t}(sec(xz))^{1+ \frac{1}{x}} dz on down-up permutations of odd length.

1. Introduction

The notion of mesh patterns was introduced by Brändén and Claesson [4] to provide explicit expansions for certain permutation statistics as, possibly infinite, linear combinations of (classical) permutation patterns (see [6] for a comprehensive introduction to the theory of permutation patterns). This notion was further studied in [3, 5, 7, 9, 10, 13].

Let σ = σ_{1} … σ_{n} be a permutation in the symmetric group S_{n} written in one-line notation. 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 shown 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 shown in Figure 1. For any a, b, c, d ∈ ℕ, where ℕ = {0, 1, 2, …} is the set of natural numbers 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 of G(σ) in quadrant I, there is 1 point of G(σ) in quadrant II, there are 2 points in quadrant III, and 2 points 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 of 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 of G(σ) in quadrant I, 2 points in quadrant II, no points in quadrant III, and no points 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 σ.

2010 Mathematics Subject Classification. 05A15, 05E05.

Key words and phrases. permutation statistics, marked mesh pattern, distribution.

Figure 1. The graph of σ = 471569283.

Note how the (two-dimensional) notation of Úlfarsson [13] 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}  .

Kitaev and Remmel [7] studied the distribution of quadrant marked mesh patterns in the symmetric group S_{n}, and Kitaev, Remmel, and Tiefenbruck [9, 10] studied the distribution of quadrant marked mesh patterns in 132-avoiding permutations in S_{n}. The main goal of this paper is to study the distribution of the statistics mmp^{(1,0,0,0)}, mmp^{(0,1,0,0)}, mmp^{(0,0,1,0)}, and mmp^{(0,0,0,1)} in the set of up-down and down-up permutations. We say that σ = σ_{1} … σ_{n} ∈ S_{n} is an up-down permutation if it is of the form

σ_{1} < σ_{2} > σ_{3} < σ_{4} > σ_{5} < ⋯,

and σ is a down-up permutation if it is of the form

σ_{1} > σ_{2} < σ_{3} > σ_{4} < σ_{5} > · · · .

Let UD_{n} denote the set of all up-down permutations in S_{n} and DU_{n} denote the set of all down-up permutations in S_{n}. Given a permutation σ = σ_{1} … σ_{n} ∈ S_{n}, we define the reverse of σ, σ^{r}, to be σ_{n}σ_{n−1} … σ_{1} and the complement of σ, σ^{c}, to be (n + 1 − σ_{1})(n + 1 − σ_{2}) … (n + 1 − σ_{n}). For n ≥ 1, we let

A_{2n}(x) = ∑_{σ∈UD_{2n}} x^{mmp^{(1,0,0,0)}(σ)},  B_{2n−1}(x) = ∑_{σ∈UD_{2n−1}} x^{mmp^{(1,0,0,0)}(σ)},
C_{2n}(x) = ∑_{σ∈DU_{2n}} x^{mmp^{(1,0,0,0)}(σ)}, and D_{2n−1}(x) = ∑_{σ∈DU_{2n−1}} x^{mmp^{(1,0,0,0)}(σ)}.

We then have the following simple proposition.

Proposition 1. For all n ≥ 1,

(1) A_{2n}(x) = ∑_{σ∈DU_{2n}} x^{mmp^{(0,1,0,0)}(σ)} = ∑_{σ∈DU_{2n}} x^{mmp^{(0,0,0,1)}(σ)} = ∑_{σ∈UD_{2n}} x^{mmp^{(0,0,1,0)}(σ)},

(2) C_{2n}(x) = ∑_{σ∈UD_{2n}} x^{mmp^{(0,1,0,0)}(σ)} = ∑_{σ∈UD_{2n}} x^{mmp^{(0,0,0,1)}(σ)} = ∑_{σ∈DU_{2n}} x^{mmp^{(0,0,1,0)}(σ)},

(3) B_{2n−1}(x) = ∑_{σ∈UD_{2n−1}} x^{mmp^{(0,1,0,0)}(σ)} = ∑_{σ∈DU_{2n−1}} x^{mmp^{(0,0,0,1)}(σ)} = ∑_{σ∈DU_{2n−1}} x^{mmp^{(0,0,1,0)}(σ)},

and

(4) D_{2n−1}(x) = ∑_{σ∈DU_{2n−1}} x^{mmp^{(0,1,0,0)}(σ)} = ∑_{σ∈UD_{2n−1}} x^{mmp^{(0,0,0,1)}(σ)} = ∑_{σ∈UD_{2n−1}} x^{mmp^{(0,0,1,0)}(σ)}.

Proof. It is easy to see that for any σ ∈ S_{n},

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

Then part 1 easily follows since

σ ∈ UD_{2n} ⟺ σ^{r} ∈ DU_{2n} ⟺ σ^{c} ∈ DU_{2n} ⟺ (σ^{r})^{c} ∈ UD_{2n}.  (1.1)

Parts 2, 3, and 4 are proved in a similar manner. □

It follows from Proposition 1 that the study of the distribution of the statistics mmp^{(1,0,0,0)}, mmp^{(0,1,0,0)}, mmp^{(0,0,1,0)}, and mmp^{(0,0,0,1)} in the set of up-down and down-up permutations can be reduced to the study of the generating functions

A(t, x) = 1 + ∑_{n≥1} A_{2n}(x)\frac{t^{2n}}{(2n)!},

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

C(t, x) = 1 + ∑_{n≥1} C_{2n}(x)\frac{t^{2n}}{(2n)!},

and

D(t, x) = ∑_{n≥1} D_{2n−1}(x)\frac{t^{2n−1}}{(2n − 1)!}.

In the case when x = 1, these generating functions are well known. That is, the operation of complementation shows that A_{2n}(1) = C_{2n}(1) and B_{2n−1}(1) = D_{2n−1}(1) for all n ≥ 1, and André [1, 2] proved that

∑_{n≥0} A_{2n}(1)\frac{t^{2n}}{(2n)!} = sec(t)

and

∑_{n≥1} B_{2n−1}(1)\frac{t^{2n−1}}{(2n − 1)!} = tan(t).

Thus, the number of up-down permutations is given by the exponential generating function

sec(t) + tan(t) = tan (\frac{t}{2} + \frac{π}{4} ) .  (1.2)

We shall prove the following theorem.

Theorem 1. We have

A(t, x) = (sec(xt))^{1/x},
B(t, x) = (sec(xt))^{1/x} ∫_{0}^{t}(sec(xz))^{−1/x}dz,
C(t, x) = 1 + ∫_{0}^{t}(sec(xy))^{1+ \frac{1}{x}} ∫_{0}^{y}(sec(xz))^{1/x}dz dy,

and

D(t, x) = ∫_{0}^{t}(sec(xz))^{1+ \frac{1}{x}} dz.

As an immediate corollary of Theorem 1, we get, for example, that the bivariate exponential generating function for up-down permutations, where the variable x keeps track of occurrences of MMP (1, 0, 0, 0), is given by

A(t, x) + B(t, x) = (sec(xt))^{1/x} (1 + ∫_{0}^{t}(sec(xz))^{−1/x}dz) ,

which refines (1.2).

One can use these generating functions to find some initial values of the polynomials A_{2n}(x), B_{2n−1}(x), C_{2n}(x), and D_{2n−1}(x). For example, we have used Mathematica to compute the following tables.

QUADRANT MARKED MESH PATTERNS IN ALTERNATING PERMUTATIONS 5

\begin{matrix}n & A_{2n}(x) \\ 0 & 1 \\ 1 & x \\ 2 & x^{2}(3 + 2x) \\ 3 & x^{3} (15 + 30x + 16x^{2}) \\ 4 & x^{4} (105 + 420x + 588x^{2} + 272x^{3}) \\ 5 & x^{5} (945 + 6300x + 16380x^{2} + 18960x^{3} + 7936x^{4}) \\ 6 & x^{6} (10395 + 103950x + 429660x^{2} + 893640x^{3} + 911328x^{4} + 353792x^{5}) \end{matrix}

\begin{matrix}n & B_{2n−1}(x) \\ 1 & 1 \\ 2 & 2x \\ 3 & 8x^{2}(1 + x) \\ 4 & 16x^{3} (3 + 8x + 6x^{2}) \\ 5 & 128x^{4} (3 + 15x + 27x^{2} + 17x^{3}) \\ 6 & 256x^{5} (15 + 120x + 381x^{2} + 556x^{3} + 310x^{4}) \\ 7 & 1024x^{6} (45 + 525x + 2562x^{2} + 6420x^{3} + 8146x^{4} + 4146x^{5}) \end{matrix}

\begin{matrix}n & C_{2n}(x) \\ 0 & 1 \\ 1 & 1 \\ 2 & x(2 + 3x) \\ 3 & x^{2} (8 + 28x + 25x^{2}) \\ 4 & x^{3} (48 + 296x + 614x^{2} + 427x^{3}) \\ 5 & x^{4} (384 + 3648x + 13104x^{2} + 20920x^{3} + 12465x^{4}) \\ 6 & x^{5} (3840 + 51840x + 282336x^{2} + 769072x^{3} + 1039946x^{4} + 555731x^{5}) \end{matrix}

n D_{2n−1}(x)
1 1
2 x(1 + x)
3 x^{2} (3 + 8x + 5x^{2})
4 x^{3} (15 + 75x + 121x^{2} + 61x^{3})
5 x^{4} (105 + 840x + 2478x^{2} + 3128x^{3} + 1385x^{4})
6 x^{5} (945 + 11025x + 51030x^{2} + 115350x^{3} + 124921x^{4} + 50521x^{5})
7 x^{6}(10395 + 166320x + 1105335x^{2} + 3859680x^{3}
+7365633x^{4} + 7158128x^{5} + 2702765x^{6})

The outline of this paper is as follows. In Section 2, we shall prove Theorem 1. Then, in Section 3, we shall study the entries of the tables above explaining them either explicitly or through recursions.

2. Proof of Theorem 1

The proof of all parts of Theorem 1 proceeds in the same manner. Namely, there are simple recursions satisfied by the polynomials A_{2n}(x), B_{2n+1}(x), C_{2n}(x), and D_{2n+1}(x) based on the position of the largest value in the permutation.

2.1. The generating function A(t, x). If σ = σ_{1} … σ_{2n} ∈ UD_{2n}, then 2n must occur in one of the positions 2, 4, …, 2n. Let UD_{2n}^{(2k)} denote the set of permutations σ ∈ UD_{2n} such that σ_{2k} = 2n. A schematic diagram of an element in UD_{2n}^{(2k)} is shown in Figure 2.

Figure 2. The graph of a permutation σ ∈ UD_{2n}^{(2k)}.

Note that there are \binom{2n−1}{2k−1} ways to pick the elements which occur to the left of position 2k in such a permutation σ and there are B_{2k−1}(1) ways to order them since the elements to the left of position 2k form an up-down permutation of length 2k − 1. Each of the elements to the left of position 2k contributes to mmp^{(1,0,0,0)}(σ). Thus the contribution of the elements to the left of position 2k to ∑_{σ∈UD_{2n}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is B_{2k−1}(1)x^{2k−1}. There are A_{2n−2k}(1) ways to order the elements to the right of position 2k since they must form an up-down permutation of length 2n − 2k. Since the elements to the left of position 2k have no effect on whether an element to the right of position 2k contributes to mmp^{(1,0,0,0)}(σ), it follows that the contribution of the elements to the right of position 2k to ∑_{σ∈UD_{2n}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is A_{2n−2k}(x). As a consequence, we obtain

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

or, equivalently,

\frac{A_{2n}(x)}{(2n − 1)!} = ∑_{k=1}^{n} \frac{B_{2k−1}(1)x^{2k−1}}{(2k − 1)!} \frac{A_{2n−2k}(x)}{(2n − 2k)!}.  (2.1)

Multiplying both sides of (2.1) by t^{2n−1} and summing the result over n ≥ 1, we see that

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

By André’s result, we have

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

so that

\frac{∂}{∂t}A(t, x) = tan(xt)A(t, x).

Our initial condition is that A(0, x) = 1. It is easy to check that the solution to this differential equation is

A(t, x) = (sec(xt))^{1/x}.

2.2. The generating function B(t, x). If σ = σ_{1} … σ_{2n+1} ∈ UD_{2n+1}, then 2n + 1 must occur in one of the positions 2, 4, …, 2n. Let UD_{2n+1}^{(2k)} denote the set of permutations σ ∈ UD_{2n+1} such that σ_{2k} = 2n+1. A schematic diagram of an element in UD_{2n}^{(2k)} is shown in Figure 3.

Figure 3. The graph of a permutation σ ∈ UD_{2n+1}^{(2k)}.

Again there are \binom{2n}{2k−1} ways to pick the elements which occur to the left of position 2k in such a permutation σ, and the contribution of the elements to the left of position 2k to ∑_{σ∈UD_{2n+1}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is B_{2k−1}(1)x^{2k−1}. There are B_{2n−2k+1}(1) ways to order the elements to the right of position 2k since they must form an up-down permutation of length 2n − 2k + 1. Since the elements to the left of position 2k have no effect on whether an element to the right of position 2k contributes to mmp^{(1,0,0,0)}(σ), it follows that the contribution of the elements to the right of position 2k to ∑_{σ∈UD_{2n+1}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is B_{2n−2k+1}(x). Consequently, if n ≥ 1, then

B_{2n+1}(x) = ∑_{k=1}^{n} \binom{2n}{2k − 1}B_{2k−1}(1)x^{2k−1}B_{2n−2k+1}(x).

Hence, for n ≥ 1, we have

\frac{B_{2n+1}(x)}{(2n)!} = ∑_{k=1}^{n} \frac{B_{2k−1}(1)x^{2k−1}}{(2k − 1)!} \frac{B_{2n−2k+1}(x)}{(2n − 2k + 1)!}.  (2.2)

Multiplying both sides of (2.2) by t^{2n}, summing the result over n ≥ 1, and taking into account that B_{1}(x) = 1, we see that

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

Since

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

we see that

\frac{∂}{∂t}B(t, x) = 1 + tan(xt)B(t, x).

Our initial condition is that B(0, x) = 0. It is easy to check that the solution to this differential equation is

B(t, x) = (sec(xt))^{1/x} ∫_{0}^{t}(sec(xz))^{−1/x}dz.

2.3. The generating function C(t, x). If σ = σ_{1} … σ_{2n} ∈ DU_{2n}, then 2n must occur in one of the positions 1, 3, …, 2n−1. Let DU_{2n}^{(2k+1)} denote the set of permutations σ ∈ DU_{2n} such that σ_{2k+1} = 2n. A schematic diagram of an element in DU_{2n}^{(2k+1)} is shown in Figure 4.

Figure 4. The graph of a permutation σ ∈ DU_{2n}^{(2k+1)}.

Note that there are \binom{2n−1}{2k} ways to pick the elements which occur to the left of position 2k +1 in such a permutation σ, and there are C_{2k}(1) = A_{2k}(1) ways to order them since the elements to the left of position 2k+1 form a down-up permutation of length 2k. Each of the elements to the left of position 2k + 1 contributes to mmp^{(1,0,0,0)}(σ). Thus the contribution of the elements to the left of position 2k + 1 to ∑_{σ∈UD_{2n}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is A_{2k}(1)x^{2k}. There are B_{2n−2k−1}(1) ways to order the elements to the right of position 2k + 1 since they must form an up-down permutation of length 2n−2k+1. Since the elements to the left of position 2k + 1 have no effect on whether an element to the right of position 2k + 1 contributes to mmp^{(1,0,0,0)}(σ), it follows that the contribution of the elements to the right of position 2k to ∑_{σ∈UD_{2n}^{(2k)}} x^{mmp^{(1,0,0,0)}(σ)} is B_{2n−2k−1}(x). As a consequence, we obtain

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

or, equivalently,

\frac{C_{2n}(x)}{(2n − 1)!} = ∑_{k=0}^{n−1} \frac{A_{2k}(1)x^{2k}}{(2k)!} \frac{B_{2n−2k−1}(x)}{(2n − 2k − 1)!}.  (2.3)

Multiplying both sides of (2.3) by t^{2n−1} and summing the result over n ≥ 1, we see that

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

By André’s result, we have

∑_{n≥0} \frac{A_{2n}(1)x^{2n}t^{2n}}{(2n)!} = sec(xt),

so that

\frac{∂}{∂t}C(t, x) = sec(xt)B(t, x) = (sec(xt))^{1+ \frac{1}{x}} ∫_{0}^{t}(sec(xz))^{\frac{−1}{x}} dz.  (2.4)

Our initial condition is that C(0, x) = 1. Both Maple and Mathematica will solve this differential equation, but the final expressions are complicated and not particularly useful for enumerative purposes. Thus we actually used the right-hand side of (2.4) to find the entries of the table for the initial values of C_{2n}(x) given in the introduction. Nevertheless, we can record the solution of (2.4) as

C(t, x) = 1 + ∫_{0}^{t}(sec(xy))^{1+ \frac{1}{x}} ∫_{0}^{y}(sec(xz))^{\frac{−1}{x}} dz dy.

2.4. The generating function D(t, x). If σ = σ_{1} … σ_{2n+1} ∈ DU_{2n+1}, then 2n + 1 must occur in one of the positions 1, 3, …, 2n + 1. Let DU_{2n+1}^{(2k+1)} denote the set of permutations σ ∈ DU_{2n+1} such that σ_{2k+1} = 2n + 1. A schematic diagram of an element in DU_{2n+1}^{(2k+1)} is shown in Figure 5.

Note that there are \binom{2n}{2k} ways to pick the elements which occur to the left of position 2k + 1 in such a permutation σ, and there are C_{2k}(1) = A_{2k}(1) ways to order them since the elements to the right of position 2k + 1 form a down-up permutation of length 2k. Each of the elements to the left of position 2k + 1 contributes to mmp^{(1,0,0,0)}(σ). Thus the contribution of the elements to the left of position 2k + 1 to ∑_{σ∈DU_{2n+1}^{(2k+1)}} x^{mmp^{(1,0,0,0)}(σ)} is

A_{2k}(1)x^{2k}. There are A_{2n−2k}(1) ways to order the elements to the right of position 2k + 1 since they must form an up-down permutation of length 2n − 2k. Since the elements to the left of position 2k + 1 have no effect on whether an element to the right of position 2k + 1

Figure 5. The graph of a permutation σ ∈ DU_{2n+1}^{(2k+1)}.

contributes to mmp^{(1,0,0,0)}(σ), it follows that the contribution of the elements to the right of position 2k + 1 to ∑_{σ∈DU_{2n+1}^{(2k+1)}} x^{mmp^{(1,0,0,0)}(σ)} is A_{2n−2k}(x). Consequently, if n ≥ 1, then

D_{2n+1}(x) = ∑_{k=0}^{n} \binom{2n}{2k}A_{2k}(1)x^{2k}A_{2n−2k}(x).

Hence, for n ≥ 1, we have

\frac{D_{2n+1}(x)}{(2n)!} = ∑_{k=0}^{n} \frac{A_{2k}(1)x^{2k}}{(2k)!} \frac{A_{2n−2k}(x)}{(2n − 2k)!}.  (2.5)

Multiplying both sides of (2.5) by t^{2n} and summing the result over n ≥ 0, we see that

∑_{n≥0} \frac{D_{2n+1}(x)t^{2n}}{(2n)!} = (∑_{n≥0} \frac{A_{2n}(1)x^{2n}t^{2n}}{(2n)!} ) (∑_{n≥0} \frac{A_{2n}(x)t^{2n}}{(2n)!} ) ,

so that

\frac{∂}{∂t}D(t, x) = sec(x, t)A(t, x) = (sec(xt))^{1+ \frac{1}{x}} .

Our initial condition is that D(0, x) = 0 so that the solution to this differential equation is

D(t, x) = ∫_{0}^{t}(sec(xz))^{1+ \frac{1}{x}} dz.

2.5. A remark on MMP (k, 0, 0, 0) for k ≥ 2. We note that we cannot apply the same techniques to find the distribution of marked mesh patterns MMP (k, 0, 0, 0) in up-down and down-up permutations when k ≥ 2. For example, suppose that we try to set up a recursion for A_{2n}^{(2,0,0,0)}(x) = ∑_{σ∈UD_{2n}} x^{mmp^{(2,0,0,0)}(σ)}. Then, if we consider the permutations σ = σ_{1} … σ_{2n} ∈ UD_{2n} such that σ_{2k} = 2n, we still have \binom{2n−1}{2k−1} ways to pick the elements for σ_{1} … σ_{2k−1}. However, in this case the question of whether some σ_{i} with i < 2k matches the marked mesh pattern MMP (2, 0, 0, 0) in σ is dependent on which values occur in σ_{2k+1} … σ_{2n}. For example, if 2n−1 ∈ {σ_{2k+1}, …, σ_{2n}}, then every σ_{i} with i ≤ k will match the marked mesh pattern MMP (2, 0, 0, 0) in σ. However, if 2n − 1 ∈ {σ_{1}, …, σ_{2k−1}}, this will not be the case. Thus we were not able to find a simple recursion for A_{2n}^{(2,0,0,0)}(x).

3. The coefficients of the polynomials A_{2n}(x), B_{2n+1}(x), C_{2n}(x), and D_{2n+1}(x)

The main goal of this section is to explain several of the coefficients of the polynomials A_{2n}(x), B_{2n+1}(x), C_{2n}(x), and D_{2n+1}(x). For any polynomial P (x), we write ⟨x^{k}⟩ P (x) for the coefficient of x^{k} in P (x). First, it is easy to understand the coefficients of the lowest power of x in each of these polynomials. More precisely, we have the following theorem, where 0!! = 1 and, for n ≥ 1, (2n)!! = ∏_{i=1}^{n}(2i) and (2n − 1)!! = ∏_{i=1}^{n}(2i − 1).

Theorem 2.

(1) For all n ≥ 1, we have

⟨x^{k}⟩ A_{2n}(x) = \begin{cases}0 & if 0 ≤ k < n, \\ (2n − 1)!! & if k = n. \end{cases}

(2) For all n ≥ 1, we have

⟨x^{k}⟩ B_{2n+1}(x) = \begin{cases}0 & if 0 ≤ k < n, \\ (2n)!! & if k = n. \end{cases}

(3) For all n ≥ 1, we have

⟨x^{k}⟩ C_{2n}(x) = \begin{cases}0 & if 0 ≤ k < n − 1, \\ (2(n − 1))!! & if k = n − 1. \end{cases}

(4) For all n ≥ 1, we have

⟨x^{k}⟩ D_{2n+1}(x) = \begin{cases}0 & if 0 ≤ k < n, \\ (2n − 1)!! & if k = n. \end{cases}

Proof. For (1), note that, if σ = σ_{1} … σ_{2n} ∈ UD_{2n}, then σ_{2i+1} always matches the pattern MMP (1, 0, 0, 0) for i = 0, …, n − 1. Thus mmp^{(1,0,0,0)}(σ) ≥ n. We now proceed by induction on n to prove that ⟨x^{n}⟩ A_{2n}(x) = (2n − 1)!! for all n ≥ 1. This is obvious for n = 1 since A_{2}(x) = x. Now suppose that σ = σ_{1} … σ_{2n} ∈ UD_{2n} and mmp^{(1,0,0,0)}(σ) = n. It is then easy to see that σ_{2} = 2n since otherwise σ_{2} is an unwanted occurrence of the pattern MMP (1, 0, 0, 0). Moreover, if τ = red(σ_{3} … σ_{2n}), then τ ∈ UD_{2n−2} and mmp^{(1,0,0,0)}(τ) = n − 1. Thus, since we are assuming by induction that ⟨x^{n−1}⟩ A_{2n−2}(x) = (2n − 3)!!, we have 2n − 1 choices of σ_{1} and (2n − 3)!! choices for τ. Hence ⟨x^{n}⟩ A_{2n}(x) = (2n − 1)!!.

For (2), note that, if σ = σ_{1} … σ_{2n+1} ∈ UD_{2n+1}, then σ_{2i+1} always matches the pattern MMP (1, 0, 0, 0) for i = 0, …, n − 1. Thus mmp^{(1,0,0,0)}(σ) ≥ n. We now proceed by induction on n to prove that ⟨x^{n}⟩ B_{2n+1}(x) = (2n)!! for all n ≥ 1. This is obvious for n = 1 since B_{3}(x) = 2x. Now suppose that σ = σ_{1} … σ_{2n+1} ∈ UD_{2n+1} and mmp^{(1,0,0,0)}(σ) = n. It is then easy to see that σ_{2} = 2n + 1. Moreover, if τ = red(σ_{3} … σ_{2n+1}), then τ ∈ UD_{2n−1} and mmp^{(1,0,0,0)}(τ) = n − 1. Thus, since we are assuming by induction that ⟨x^{n−1}⟩ B_{2n−1}(x) = (2n − 2)!!, we have 2n choices of σ_{1} and (2n − 2)!! choices for τ. Hence ⟨x^{n}⟩ B_{2n+1}(x) = (2n)!! for n ≥ 1.

For (3), note that, if σ = σ_{1} … σ_{2n} ∈ DU_{2n}, then σ_{2i} always matches the pattern MMP (1, 0, 0, 0) for i = 1, …, n − 1. Thus mmp^{(1,0,0,0)}(σ) ≥ n − 1. Now suppose that σ = σ_{1} … σ_{2n} ∈ DU_{2n} and mmp^{(1,0,0,0)}(σ) = n − 1. It is then easy to see that σ_{1} = 2n. Moreover, if τ = σ_{2} … σ_{2n}, then τ ∈ UD_{2n−1} and mmp^{(1,0,0,0)}(τ) = n − 1. Thus we have (2(n − 1))!! choices for τ by part (2). Hence ⟨x^{n−1}⟩ C_{2n}(x) = (2(n − 1))!!.

For (4), note that, if σ = σ_{1} … σ_{2n+1} ∈ DU_{2n+1}, then σ_{2i} always matches MMP (1, 0, 0, 0) for i = 1, …, n. Thus mmp^{(1,0,0,0)}(σ) ≥ n. Now suppose that σ = σ_{1} … σ_{2n+1} ∈ DU_{2n+1} and mmp^{(1,0,0,0)}(σ) = n. It is then easy to see that σ_{1} = 2n+1. Moreover, if τ = σ_{2} … σ_{2n+1}, then τ ∈ UD_{2n} and mmp^{(1,0,0,0)}(τ) = n. Thus we have (2n − 1)!! choices for τ by part (1). Hence ⟨x^{n}⟩ D_{2n+1}(x) = (2n − 1)!! for n ≥ 1. □

We can easily explain the coefficients of the highest power of x in each of the polynomials A_{2n}(x), B_{2n+1}(x), C_{2n}(x), and D_{2n+1}(x). More precisely, we have the following proposition.

Proposition 2.

(1) For all n ≥ 1, the highest power of x that appears in A_{2n}(x) is x^{2n−1}, which appears with coefficient B_{2n−1}(1).

(2) For all n ≥ 1, the highest power of x that appears in B_{2n+1}(x) is x^{2n−1}, which appears with coefficient (2n)B_{2n−1}(1).

(3) For all n ≥ 1, the highest power of x that appears in C_{2n}(x) is x^{2n−2}, which appears with coefficient (2n − 1)A_{2n−2}(1).

(4) For all n ≥ 1, the highest power of x that appears in D_{2n+1}(x) is x^{2n}, which appears with coefficient A_{2n}(1).

Proof. For (1), it is easy to see that mmp^{(1,0,0,0)}(σ) is maximized for a permutation σ = σ_{1} … σ_{2n} ∈ UD_{2n} with σ_{2n} = 2n. In such a case mmp^{(1,0,0,0)}(σ) = 2n − 1 and σ_{1} … σ_{2n−1} can be any element of UD_{2n−1}.

For (2), it is easy to see that mmp^{(1,0,0,0)}(σ) is maximized for a permutation σ = σ_{1} … σ_{2n+1} ∈ UD_{2n+1} with σ_{2n} = 2n + 1. In such a case mmp^{(1,0,0,0)}(σ) = 2n − 1. We then have 2n choices for σ_{2n+1} and red(σ_{1} … σ_{2n−1}) can be any element of UD_{2n−1}. Thus ⟨x^{2n−1}⟩ B_{2n+1}(x) = (2n)B_{2n−1}(1).

For (3), it is easy to see that mmp^{(1,0,0,0)}(σ) is maximized for a permutation σ = σ_{1} … σ_{2n} ∈ DU_{2n} with σ_{2n−1} = 2n. In such a case mmp^{(1,0,0,0)}(σ) = 2n − 2. We then have 2n − 1 choices for σ_{2n} and red(σ_{1} … σ_{2n−2}) can be any element of DU_{2n−2}. Thus ⟨x^{2n−2}⟩ C_{2n}(x) = (2n − 1)C_{2n−2}(1) = (2n − 1)A_{2n−2}(1).

For (4), it is easy to see that mmp^{(1,0,0,0)}(σ) is maximized for a permutation σ = σ_{1} … σ_{2n+1} ∈ DU_{2n+1} with σ_{2n+1} = 2n + 1. In such a case mmp^{(1,0,0,0)}(σ) = 2n. Then σ_{1} … σ_{2n} can be any element of DU_{2n}. Thus ⟨x^{2n}⟩ D_{2n+1}(x) = C_{2n}(1) = A_{2n}(1). □

3.1. Recursions on up-down permutations of even length. By Theorem 2, the lowest power of x that appears with a non-zero coefficient in A_{2n}(x) is x^{n}. Next we consider ⟨x^{n+k}⟩ A_{2n}(x) for fixed k. That is, we let

A_{2n}^{=n+k} = |{σ ∈ UD_{2n} : mmp^{(1,0,0,0)}(σ) = n + k}|

for fixed k ≥ 1. Our goal is to show that A_{2n}^{=n+k} = p_{k}(n)(2n−1)!! for some fixed polynomial p_{k}(n) in n. More precisely, we shall prove the following theorem, where we let

(x) ↓_{n}= x(x − 1) ⋯ (x − n + 1) if n ≥ 1 and (x) ↓_{0}= 1.

Theorem 3. There is a sequence of polynomials p_{0}(x), p_{1}(x), … such that, for all k ≥ 0,

A_{2n}^{=n+k} = p_{k}(n)(2n − 1)!! for all n ≥ k + 1.

Moreover, for k ≥ 1, the values p_{k}(n) are defined by the recursion

p_{k}(n) = \frac{B_{2k+1}(1)}{(2k + 1)!!} + ∑_{j=1}^{k} ∑_{t=k+2}^{n} \frac{B_{2j+1}(1)2^{j}(t − 1) ↓_{j}}{(2j + 1)!} p_{k−j}(t − j − 1),  (3.1)

where p_{0}(x) = 1.

Proof. We proceed by induction on k. For k = 0, we know by Theorem 2 that A_{2n}^{=n} = (2n − 1)!! for all n ≥ 1 so that we may let p_{0}(x) = 1.

Now assume that k ≥ 1 and the theorem is true for s < k. That is, assume that for 0 ≤ s < k, there is a polynomial p_{s}(x) such that for n ≥ s + 1, A_{2n}^{=n+s} = p_{s}(n)(2n − 1)!!.

It is easy to see that, for σ = σ_{1} … σ_{2n} ∈ UD_{2n}, we have mmp^{(1,0,0,0)}(σ) > n + k if σ_{2j} = 2n with j > k + 2, because then σ_{2}, σ_{4}, …, σ_{2k+2} as well as σ_{2i+1}, i = 0, …, n − 1, will match the pattern MMP (1, 0, 0, 0) in σ. Thus, if mmp^{(1,0,0,0)}(σ) = n + k, then 2n ∈ \{σ_{2}, σ_{4}, …, σ_{2k+2}\}. Now suppose that j ≤ k + 1 and σ_{2j} = 2n. Then we have \binom{2n−1}{2j−1} ways to choose the elements σ_{1}, …, σ_{2j−1}, and we have B_{2j−1}(1) ways to order them. Then we know that σ_{i} matches the marked mesh pattern MMP (1, 0, 0, 0) in σ for i odd and for i ∈ {2, 4, …, 2j − 2}. Hence, we have mmp^{(1,0,0,0)}(red(σ_{2j+1} … σ_{2n})) = n − j + k − j + 1. Thus it follows that, for n ≥ k + 1,

A_{2n}^{=n+k} = ∑_{j=1}^{k+1} \binom{2n − 1}{2j − 1}B_{2j−1}(1)A_{2(n−j)}^{=(n−j)+k−j+1}.  (3.2)

Now define p_{k}(n) = \frac{A_{2n}^{=n+k}}{(2n−1)!!} for n ≥ k + 1. Note that A_{2k+2}^{(k+1)+k} = B_{2k+1}(1), since for a permutation τ = τ_{1} … τ_{2k+2} ∈ UD_{2k+2} to have mmp^{(1,0,0,0)}(τ) = 2k + 1, it must satisfy τ_{2k+2} = 2k + 2, and, hence, we have B_{2k+1}(1) choices for τ_{1} … τ_{2k+1}. Hence, p_{k}(k + 1) = \frac{B_{2k+1}(1)}{(2k+1)!!}.

We may rewrite (3.2) as

p_{k}(n)(2n − 1)!! = (2n − 1)p_{k}(n − 1)(2n − 3)!!

+ ∑_{j=2}^{k+1} \frac{∏_{i=0}^{2j−2}(2n − 1 − j)}{(2j − 1)!}B_{2j−1}(1)p_{k−j+1}(n − j)(2n − 2j − 1)!!. (3.3)

Dividing both sides of (3.3) by (2n − 1)!!, we obtain

p_{k}(n) − p_{k}(n − 1) = ∑_{j=2}^{k+1} \frac{B_{2j−1}(1) ∏_{s=1}^{j−1}(2n − 2s)}{(2j − 1)!}p_{k−j+1}(n − j)

= ∑_{j=1}^{k} \frac{B_{2j+1}(1)2^{j}(n − 1) ↓_{j}}{(2j + 1)!} p_{k−j}(n − j − 1).

Hence, for n ≥ k + 1, we have

p_{k}(n) − p_{k}(k + 1) = ∑_{t=k+2}^{n} p_{k}(t) − p_{k}(t − 1)

= ∑_{t=k+2}^{n} ∑_{j=1}^{k} \frac{B_{2j+1}(1)2^{j}(t − 1) ↓_{j}}{(2j + 1)!} p_{k−j}(t − j − 1).

It follows that, for n ≥ k + 1,

p_{k}(n) = \frac{B_{2k+1}(1)}{(2k + 1)!!} + ∑_{j=1}^{k} ∑_{t=k+2}^{n} \frac{B_{2j+1}(1)2^{j}(t − 1) ↓_{j}}{(2j + 1)!} p_{k−j}(t − j − 1).

This proves (3.1).

Since p_{s}(x) is a polynomial for s < k, it is easy to see that

∑_{t=k+2}^{n} \frac{B_{2j+1}(1)2^{j}(t − 1) ↓_{j}}{(2j + 1)!} p_{k−j}(t − j − 1)

is a polynomial in n for j = 1, …, k. Thus p_{k}(n) is a polynomial in n. □

One may use Mathematica and (3.1) to compute the first few expressions for p_{k}(n). For example, we have computed that

p_{0}(n) = 1,
p_{1}(n) = \frac{2}{3}\binom{n}{2},
p_{2}(n) = \frac{n(2 + 7n − 14n^{2} + 5n^{3})}{90},

and

p_{3}(n) = \frac{n(192 − 478n + 213n^{2} + 227n^{3} − 198n^{4} + 35n^{5})}{5670}.

3.2. Recursions on up-down permutations of odd length.

Theorem 4. There is a sequence of polynomials q_{0}(x), q_{1}(x), … such that, for all k ≥ 0, we have

B_{2n+1}^{=n+k} = q_{k}(n)(2n)!! for all n ≥ k + 1.

Moreover, for k ≥ 1, the values q_{k}(n) are defined by the recursion

q_{k}(n) = \frac{B_{2k+1}(1)}{(2k)!!} + ∑_{j=1}^{k} ∑_{t=k+2}^{n} \frac{B_{2j+1}(1) ∏_{s=0}^{j−1}(2t − 1 − 2s)}{(2j + 1)!}q_{k−j}(t − j − 1),  (3.4)

where q_{0}(x) = 1.

Proof. We proceed by induction on k. For k = 0, we know by Theorem 2 that B_{2n+1}^{=n} = (2n)!! for all n ≥ 1 so that we may let q_{0}(x) = 1.

Now assume that k ≥ 1 and the theorem is true for s < k. That is, assume that, for 0 ≤ s < k, there is a polynomial q_{s}(x) such that, for n ≥ s + 1, B_{2n+1}^{=n+s} = q_{s}(n)(2n)!!.

We can argue as in Theorem 3 that, if σ = σ_{1} … σ_{2n+1} ∈ UD_{2n+1} and mmp^{(1,0,0,0)}(σ) = n + k, then 2n ∈ {σ_{2}, σ_{4}, …, σ_{2k+2}}. Now suppose that j ≤ k + 1 and σ_{2j} = 2n. Then we have \binom{2n}{2j−1} ways to choose the elements σ_{1}, …, σ_{2j−1}, and we have B_{2j−1}(1) ways to order them. Then we know that σ_{i} matches the marked mesh pattern MMP (1, 0, 0, 0) in σ for i ∈ {2, 4, …, 2j −2}∪{1, 3, …, 2n−1}. Hence, we have mmp^{(1,0,0,0)}(red(σ_{2j+1} … σ_{2n+1})) = n − j + k − j + 1. Thus it follows that, for n ≥ k + 2,

B_{2n+1}^{=n+k} = ∑_{j=1}^{k+1} \binom{2n}{2j − 1}B_{2j−1}(1)B_{2(n−j)+1}^{=(n−j)+k−j+1}.  (3.5)

Now define q_{k}(n) = \frac{B_{2n+1}^{=n+k}}{(2n)!!} for n ≥ k + 1. Note that B_{2k+3}^{(k+1)+k} = (2k + 2)B_{2k+1}(1) since for a permutation τ = τ_{1} … τ_{2k+3} ∈ UD_{2k+3} to have mmp^{(1,0,0,0)}(τ) = 2k + 1, it must satisfy τ_{2k+2} = 2k + 3, and, hence, we have 2k + 2 choices for τ_{2k+3} and B_{2k+1}(1) choices for τ_{1} … τ_{2k+1}. Thus, q_{k}(k + 1) = \frac{(2k+2)B_{2k+1}(1)}{(2k+2)!!} = \frac{B_{2k+1}(1)}{(2k)!!}.

We may rewrite (3.5) as

q_{k}(n)(2n)!! = (2n)q_{k}(n − 1)(2n − 2)!!

+ ∑_{j=2}^{k+1} \frac{∏_{i=0}^{2j−2}(2n − j)}{(2j − 1)!}B_{2j−1}(1)q_{k−j+1}(n − j)(2n − 2j)!!. (3.6)

Dividing both sides of (3.6) by (2n)!!, we obtain

q_{k}(n) − q_{k}(n − 1) = ∑_{j=2}^{k+1} \frac{B_{2j−1}(1) ∏_{s=1}^{j−1}(2n − 2s − 1)}{(2j − 1)!}q_{k−j+1}(n − j).  (3.7)

Hence, for n ≥ k + 2, we have

q_{k}(n) − q_{k}(k + 1) = ∑_{t=k+2}^{n} q_{k}(t) − q_{k}(t − 1)

= ∑_{t=k+2}^{n} ∑_{j=1}^{k} \frac{B_{2j+1}(1)2^{j} ∏_{s=1}^{j−1}(2n − 2s − 1)}{(2j + 1)!}q_{k−j}(t − j − 1).

It follows that, for n ≥ k + 1,

q_{k}(n) = \frac{B_{2k+1}(1)}{(2k)!!} + ∑_{j=1}^{k} ∑_{t=k+2}^{n} \frac{B_{2j+1}(1)2^{j} ∏_{s=1}^{j−1}(2n − 2s − 1)}{(2j + 1)!}q_{k−j}(t − j − 1).  (3.8)

This proves (3.4).

Since q_{s}(x) is a polynomial for s < k, it is easy to see that

∑_{t=k+2}^{n} \frac{B_{2j+1}(1) ∏_{s=1}^{j−1}(2n − 2s − 1)}{(2j + 1)!}q_{k−j}(t − j − 1)

is a polynomial in n for j = 1, …, k. Thus q_{k}(n) is a polynomial in n. □

One may use Mathematica and (3.4) to compute the first few expressions for q_{k}(n). For example, we have computed that

q_{0}(n) = 1,
q_{1}(n) = \frac{n^{2} − 1}{3},
q_{2}(n) = \frac{(n − 2)(n − 1)(5n^{2} + n − 3)}{90}, and
q_{3}(n) = \frac{35n^{6} − 84n^{5} − 193n^{4} + 345n^{3} + 140n^{2} − 81n + 198}{5670}.

3.3. Recursions on down-up permutations. Similar results hold for down-up permutations.

Theorem 5. There are sequences of polynomials r_{0}(x), r_{1}(x), … and s_{0}(x), s_{1}(x), … such that, for all k ≥ 0, we have

C_{2n}^{=n−1+k} = r_{k}(n)(2n − 2)!! for all n ≥ k + 1,  (3.9)

and

D_{2n+1}^{=n−1+k} = s_{k}(n)(2n − 1)!! for all n ≥ k + 1.  (3.10)

Proof. By Theorem 2, we have C_{2n}^{=n−1} = (2n − 2)!! and D_{2n+1}^{=n} = (2n − 1)!! for all n ≥ 1. Thus we may let r_{0}(x) = s_{0}(x) = 1.

For a permutation σ = σ_{1} … σ_{2n} ∈ DU_{2n} to have mmp^{(1,0,0,0)}(σ) = n−1+k, we must have 2n ∈ \{σ_{1}, σ_{3}, …, σ_{2k+1}\}. If σ_{2j+1} = 2n where j ∈ \{0, 1, …, k\}, then there are \binom{2n−1}{2j} ways to pick the elements of σ_{1} … σ_{2j} and C_{2j}(1) ways to order them. Then red(σ_{2j+2} … σ_{2n}) ∈ UD_{2(n−j−1)+1} and it must have n − 1 + k − (2j) matches of MMP (1, 0, 0, 0). Thus we have B_{2(n−j−1)+1}^{=(n−j−1)+k−j} ways to order σ_{2j+2} … σ_{2n}. It follows that, for n ≥ k + 1,

C_{2n}^{=n−1+k} = ∑_{j=0}^{k} \binom{2n − 1}{2j}C_{2j}(1)B_{2(n−j−1)+1}^{=n−j−1+k−j}.  (3.11)

QUADRANT MARKED MESH PATTERNS IN ALTERNATING PERMUTATIONS 17

But C_{2j}(1) = A_{2j}(1) and B_{2(n−j−1)+1}^{=n−j−1+k−j} = (2(n−j −1))!!q_{k−j}(n−j −1). Thus, for n ≥ k +1, we have

C_{2n}^{=n−1+k} = ∑_{j=0}^{k} \binom{2n − 1}{2j}A_{2j}(1)(2(n − j − 1))!!q_{k−j}(n − j − 1)

= (2n − 2)!! ∑_{j=0}^{k} \frac{A_{2j}(1) ∏_{s=1}^{j}(2n + 1 − 2s)}{(2j)!}(2(n − j − 1))!!q_{k−j}(n − j − 1).

Thus C_{2n}^{=n−1+k} = (2n − 2)!!r_{k}(n), where

r_{k}(n) = ∑_{j=0}^{k} \frac{A_{2j}(1) ∏_{s=1}^{j}(2n + 1 − 2s)}{(2j)!}q_{k−j}(n − j − 1).  (3.12)

A similar argument shows that, for n ≥ k + 1,

D_{2n+1}^{=n+k} = ∑_{j=0}^{k} \binom{2n}{2j}C_{2j}(1)A_{2(n−j)}^{=n−j+k−j}.

Since A_{2(n−j)}^{=n−j+k−j} = (2(n − j) − 1)!!p_{k−j}(n − j), we obtain

D_{2n+1}^{=n+k} = ∑_{j=0}^{k} \binom{2n}{2j}A_{2j}(1)(2(n − j) − 1)!!p_{k−j}(n − j)

= (2n − 1)!! ∑_{j=0}^{k} \frac{A_{2j}(1) ∏_{s=1}^{j}(2n + 2 − 2s)}{(2j)!}p_{k−j}(n − j).

Thus D_{2n+1}^{=n+k} = (2n − 2)!!s_{k}(n), where

s_{k}(n) = ∑_{j=0}^{k} \frac{A_{2j}(1) ∏_{s=1}^{j}(2n + 2 − 2s)}{(2j)!}p_{k−j}(n − j).  (3.13)
□

One may use (3.12) and (3.13) to compute r_{k}(n) and s_{k}(n) for the first few values of k. For example, we have

r_{0}(n) = 1,
r_{1}(n) = \frac{2n^{2} + 2n − 3}{6},
r_{2}(n) = \frac{20n^{4} + 24n^{3} − 128n^{2} − 12n + 45}{360},

and

r_{3}(n) = \frac{280n^{6} + 168n^{5} − 4820n^{4} + 3168n^{3} + 8734n^{2} − 6702n + 2835}{45360}.

Similarly, we have

s_{0}(n) = 1,
s_{1}(n) = \frac{n(n + 2)}{3},
s_{2}(n) = \frac{n(5n^{3} + 16n^{2} − 68n + 47)}{90},

and

s_{3}(n) = \frac{n(35n^{5} + 126n^{4} − 340n^{3} − 417n^{2} + 656n − 60)}{5760}.

4. Conclusion

In this paper, we have shown that one can find the generating functions for the distribution of the quadrant marked mesh patterns MMP (1, 0, 0, 0), MMP (0, 1, 0, 0), MMP (0, 0, 1, 0), and MMP (0, 0, 0, 1) in both up-down and down-up permutations by proving simple recursions based on the position of the largest element in a permutation. As noted in Subsection 2.5, these recursions of simple type no longer hold for the distribution of the quadrant marked mesh patterns MMP (k, 0, 0, 0), MMP (0, k, 0, 0), MMP (0, 0, k, 0), and MMP (0, 0, 0, k) in both up-down and down-up permutations when k ≥ 2. However, our results allow us to derive generating functions for the distribution of other quadrant marked mesh patterns in up-down and down-up permutations. More specifically, for any a, b, c, d ∈ {∅} ∪ ℕ, let

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

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

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

and

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

Then our results allow us to find the distribution of MMP (∅, 0, 0, 0), MMP (0, ∅, 0, 0), MMP (0, 0, ∅, 0), and MMP (0, 0, 0, ∅) over up-down and down-up permutations. More precisely, it is clear that for any σ = σ_{1} … σ_{n} ∈ S_{n}, we have

mmp^{(1,0,0,0)}(σ) + mmp^{(∅,0,0,0)}(σ) = n,  (4.1)

since any σ_{i} either matches MMP (1, 0, 0, 0) or MMP (∅, 0, 0, 0) in σ but cannot match both MMP (1, 0, 0, 0) and MMP (∅, 0, 0, 0) in σ. For any set A ⊆ S_{n}, let A^{r} = {σ^{r} : σ ∈ A}, A^{c} = {σ^{c} : σ ∈ A}, and A^{rc} = {(σ^{r})^{c} : σ ∈ A}. Then, clearly,

∑_{σ∈A} x^{mmp^{(∅,0,0,0)}(σ)} = ∑_{σ∈A^{r}} x^{mmp^{(0,∅,0,0)}(σ)} = ∑_{σ∈A^{c}} x^{mmp^{(0,0,0,∅)}(σ)} = ∑_{(σ∈A^{rc}} x^{mmp^{(0,0,∅,0)}(σ)}.

It then follows from (1.1) and (4.1) that

A(tx, \frac{1}{x}) = A^{(∅,0,0,0)}(t, x) = C^{(0,∅,0,0)}(t, x) = C^{(0,0,0,∅)}(t, x) = A^{(0,0,∅,0)}(t, x).

Using the fact that

σ ∈ UD_{2n+1} ⟺ σ^{r} ∈ UD_{2n+1} ⟺ σ^{c} ∈ DU_{2n+1} ⟺ (σ^{r})^{c} ∈ DU_{2n+1},  (4.2)

it follows that

B(tx, \frac{1}{x}) = B^{(∅,0,0,0)}(t, x) = B^{(0,∅,0,0)}(t, x) = D^{(0,0,0,∅)}(t, x) = D^{(0,0,∅,0)}(t, x).

Similar reasoning will show that

C(tx, \frac{1}{x}) = C^{(∅,0,0,0)}(t, x) = A^{(0,∅,0,0)}(t, x) = A^{(0,0,0,∅)}(t, x) = C^{(0,0,∅,0)}(t, x)

and

D(tx, \frac{1}{x}) = D^{(∅,0,0,0)}(t, x) = D^{(0,∅,0,0)}(t, x) = B^{(0,0,0,∅)}(t, x) = B^{(0,0,∅,0)}(t, x).

Moreover, our techniques can be used to study the distribution of other quadrant marked mesh patterns in up-down and down-up permutations. For example, in [8], we have proved similar recursions based on the position of the smallest element in a permutation to study the distribution of the quadrant marked mesh patterns MMP (1, 0, ∅, 0), MMP (0, 1, 0, ∅), MMP (∅, 0, 1, 0), and MMP (0, ∅, 0, 1) in both up-down and down-up permutations. In this case, the recursions are a bit more subtle, and the corresponding generating functions are not always as simple as in the results of this paper. For example, we have shown that

A^{(1,0,∅,0)}(t, x) = (sec(t))^{x},
B^{(1,0,∅,0)}(t, x) = \frac{sin(t) cos(t)(1 − x + sec(t))}{x + (1 − x) cos(t)}

× ((1 − x) _{2}F_{1} (\frac{1}{2}, \frac{1 + x}{2}; \frac{3}{2}; sin (t^{2})) + x _{2}F_{1} (\frac{1}{2}, \frac{2 + x}{2}; \frac{3}{2}; sin (t^{2}))) ,

where _{2}F_{1}(a, b; c; z) = ∑_{n=0}^{∞} \frac{(a)_{n}(b)_{n}}{(c)_{n}} \frac{z^{n}}{n!} and (x)_{n} = x(x − 1) ⋯ (x − n + 1) if n ≥ 1 and (x)_{0} = 1.

There are several directions for further research that are suggested by the results of this paper. First, one may study the distribution in up-down and down-up permutations of other quadrant marked meshed patterns MMP (a, b, c, d) in the case where a, b, c, d ∈ {∅, 0, 1}. More generally, one may study the distribution of quadrant marked mesh patterns on other classes of pattern-restricted permutations such as 2-stack-sortable permutations or vexillary permutations (see [6] for definitions of these) and many other permutation classes having nice properties. Finally, we conjecture that the polynomials A_{2n}(x), B_{2n+1}(x), C_{2n}(x), and D_{2n+1}(x) are unimodal for all n ≥ 1. This is certainly true for small values of n.

References

[1] D. André, Développements de sec x et de tang x, C. R. Acad. Sci. Paris 88 (1879), 965–967.

[2] D. André, Mémoire sur les permutations alternées, J. Math. Pur. Appl. 7 (1881), 167–184.

[3] S. Avgustinovich, S. Kitaev and A. Valyuzhenich, Avoidance of boxed mesh patterns on permutations, preprint.

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

[5] Í. Hilmarsson, I. Jónsdóttir, S. Sigurðardóttir, H. Úlfarsson and S. Viðarsdóttir, Wilf-classification of mesh patterns of short length, in preparation.

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

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

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

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

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

[11] N. J. A. Sloane, The on-line encyclopedia of integer sequences, available at http://oeis.org/.

[12] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999.

[13] H. Úlfarsson, A unification of permutation patterns related to Schubert varieties, arχiv:1002.4361.