Séminaire Lotharingien de Combinatoire 51 (2004), Article B51e

EQUIDISTRIBUTION AND SIGN-BALANCE ON 132-AVOIDING PERMUTATIONS

Toufik Mansour^{1,2}

Department of Mathematics, Chalmers University of Technology S-412 96 Göteborg, Sweden

                    E-mail: toufik@math.chalmers.se

Abstract. Let R_{n} be the set of all permutations of length n which avoid 132. In this paper we study the statistics last descent (“ldes”), first descent (“fdes”), last rise (“lris”), and first rise (“fris”) on the set R_{n}. In particular, we prove that the bistatistic (“fris”,“lris”) on the set of all permutations R_{n}\{n … 21} and the bistatistic (“n − ldes”,“n − fdes”) on the set of all permutations of R_{n}\{12 … n} are equidistributed. Furthermore, we consider the case of sign balance for these statistics on the set of all permutations R_{n}, and we give a combinatorial interpretation for some of these statistics.

1. Introduction

Let S_{n} denote the set of permutations of {1, …, n}, written in one-line notation, and suppose that π ∈ S_{n} and σ ∈ S_{k}. We say that a subsequence of π has type σ whenever it has the same pairwise comparisons as σ. For example, the subsequence 24869 of the permutation 214538769 has type 12435. We say that π avoids σ (or π is σ-avoiding) whenever π contains no subsequence of type σ. For example, the permutation 214538769 avoids 4321 and 2413, but it has 2589 as a subsequence, so it does not avoid 1234. We denote the set of σ-avoiding permutations in S_{n} by S_{n}(σ). We define R_{n} = S_{n}(132). For π ∈ R_{n}, we define the following statistics:

(1) ldes(π) = last descent of π = max{1 ≤ i ≤ n − 1|π_{i} > π_{i+1}} where ldes(12 … n) = 0,

(2) fdes(π) = first descent of π = min{1 ≤ i ≤ n − 1|π_{i} > π_{i+1}} where fdes(12 … n) = 0,

(3) lris(π) = last rise of π = max{1 ≤ i ≤ n − 1|π_{i} < π_{i+1}} where lris(n … 21) = 0,

(4) fris(π) = first rise of π = min{1 ≤ i ≤ n − 1|π_{i} < π_{i+1}} where fris(n … 21) = 0,

(5) lind(π) = π^{−1}(n) = the index of the letter “n” in π,

(6) find(π) = π^{−1}(1) = the index of the letter “1” in π.

Key words and phrases. 132-avoiding permutations, Dyck paths, equidistribution of statistics, signbalance.

1Research financed by EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

2Current address: Department of Mathematics, University of Haifa, 31905 Haifa, Israel. E-mail:

toufik@math.haifa.ac.il.

Foata and Schützenberger [FS, Theorem 1] proved that the major index and the inversion number are equidistributed on S_{n} whose inverse has a prescribed descent set. Recently, Adin and Roichman [AR, Theorem 1.1] gave an analogue for this result for S_{n}(321). They proved that the statistics “ldes” and “lind − 1” are equidistributed on the set S_{n}(321). Note that these statistics are identical on the set R_{n}. (To prove that, let s = π_{1}^{−1}. We may assume that s > 1, otherwise π equals the identity of S_{n}, which has no descents. Clearly, π_{s−1} > π_{s}. Furthermore, we have 1 = π_{s} < π_{s+1} < ⋯ < π_{n} since π avoids 132. Therefore, s − 1 is exactly the last descent of π.)

The Catalan sequence is the sequence (C_{n})_{n≥0} = (1, 1, 2, 5, 14, 42, 132, 429, 1430, …), where C_{n} = \frac{1}{n+1} \binom{2n}{n} is called the nth Catalan number. The generating function for the Catalan numbers is denoted by C(t) = \frac{1−\sqrt{1−4t}}{2t}. The Catalan numbers provide a complete answer to the problem of counting certain properties of more than 100 different combinatorial structures (see [S, page 219 and Exercise 6.19]). The structures that are useful for us in the present paper are Dyck paths (see [S]) and 132-avoiding permutations (see [Kn]).

A Dyck path is a path in the plane integer lattice ℤ^{2} consisting of up-steps U = (1, 1) and down-steps D = (1, −1) which never passes below the x-axis. We denote the set of Dyck paths of length 2n by P_{n}. A point on the Dyck path is called a peak if it is immediately preceded by an up-step and immediately followed by a down-step. For p ∈ P_{n}, we define

lpeak(p) = the height (the y-coordinate) of the last peak of p.

Recently, Adin and Roichman [AR, Theorem 1.2] proved that the statistics “ldes” on the set S_{n}(321), “ldes” on the set P_{n}, and “lind − 1” are equidistributed on the set P_{n}. In this paper we prove the following analogue of this result.

Theorem 1.1. For all n ≥ 1, we have

∑_{p∈P_{n}} q^{n−lpeak(p)} = ∑_{π∈R_{n}} q^{ldes(π)}.

In addition, we study the sign-and-“find” and sign-and-“lind” enumerators for R_{n} (see [AR, Theorem 1.3] for S_{n}(321)), and we prove the following result.

Theorem 1.2. For all n ≥ 1,

∑_{π∈R_{2n}} sign(π)q^{ldes(π)} = (1 − q) ∑_{π∈R_{2n+1}} sign(π)q^{find(π)−1},

and

∑_{π∈R_{2n−1}} sign(π)q^{ldes(π)} = ∑_{π∈R_{n−1}} q^{2(find(π)−1)}.

The paper is organized as follows. In Section 2, we study the statistics “ldes”, “fdes”, “lris”, and “fris” on the set R_{n}. In particular, we prove that the bistatistic (“fris”,“lris”) on the set R_{n}\{n … 21} and the bistatistic (“n − ldes”,“n − fdes”) on the set R_{n}\{12 … n} are equidistributed. In Section 3, we consider the case of sign balance of some statistics on the set R_{n}. Finally, in Section 4, we give a combinatorial interpretation (using Dyck paths) for some of these statistics.

2. Equidistribution of statistics

In this section, we study the statistics “ldes”, “fdes”, “lris”, and “fris” on the set R_{n} by using the block decomposition approach of 132-avoiding permutations in S_{n} (see [MV]).

First of all, let us describe the block decomposition of a permutation π ∈ R_{n}. Let n ≥ 1 and π = (π′, n, π′′) ∈ R_{n} such that π_{j} = n. π avoids 132 if and only if π′ is a permutation of the numbers n − j + 1, n − j + 2, …, n − 1, π′′ is a permutation of the numbers 1, 2, …, n − j, and both π′ and π′′ avoid 132. This representation is called the block decomposition of π.

Theorem 2.1. The statistic “fris” on the set R_{n}\{n … 21} and the statistic “n−ldes” on the set R_{n}\{12 … n} are equidistributed, that is, for n ≥ 1, we have

∑_{π∈R_{n}\{n...21}} q^{fris(π)} = ∑_{π∈R_{n}\{12...n}} q^{n−ldes(π)}.

Moreover,

∑_{n≥0} ∑_{π∈R_{n}} q^{fris(π)}x^{n} = \frac{1}{1 − x} − \frac{1}{1 − qx} + \frac{1}{1 − qxC(x)}

and

∑_{n≥0} ∑_{π∈R_{n}} q^{ldes(π)} = \frac{1}{1 − xC(qx)}.

Proof. Let F_{n}(q) = ∑_{π∈R_{n}} q^{ldes(π)} for n ≥ 0. Using the block decomposition of π ∈ R_{n}, we may derive a recurrence for F_{n}(q). Namely, by making use of the fact that |S_{m}(132)| = C_{m} = \frac{1}{m+1} \binom{2m}{m} (see [Kn]), we get for n ≥ 1,

(2.1)  F_{n}(q) = F_{n−1}(q) + q ∑_{j=0}^{n−2} q^{j}C_{j}F_{n−1−j}(q).

Multiplying both sides by x^{n}, summing over all n ≥ 1, and finally using F_{0}(q) = 1, we obtain that

F (x; q) = 1 + ∑_{n≥1} ∑_{π∈R_{n}} q^{ldes(π)}x^{n} = \frac{1}{1 − xC(xq)}.

Let now H_{n}(q) = ∑_{π∈R_{n}} q^{fris(π)} for n ≥ 0. Again, using the block decomposition of π, we may derive a recurrence for H_{n}(q). First of all, the contribution of the permutations π with π_{1} = n gives 1 + q(H_{n−1}(q) − 1). Secondly, the contribution of the permutations π with π_{2} = n gives C_{n−2}q. Finally, for π_{j} = n with j ≥ 3, we get as contribution (H_{j−1}(q) − 1)C_{n−j} whenever π′ ≠ (n − 1) … (n + 1 − j) in the decomposition π = (π′, n, π′′), and q^{j−1}C_{n−j} for π′ = (n − 1) … (n + 1 − j). Hence, for n ≥ 1, we have

H_{n}(q) = 1 + q(H_{n−1}(q) − 1) + C_{n−2}q + ∑_{j=2}^{n−1} C_{n−1−j}(H_{j}(q) − 1) + ∑_{j=2}^{n−1} q^{j}C_{n−1−j},

or, equivalently,

(2.2)  H_{n}(q) = 1 + q(H_{n−1}(q) − 1) + ∑_{j=2}^{n−1} C_{n−1−j}(H_{j}(q) − 1) + ∑_{j=1}^{n−1} q^{j}C_{n−1−j}.

If we write K_{n}(q) for q^{n}(H_{n}(q^{−1}) − 1) + 1, then it is easy to see that

K_{n}(q) = K_{n−1}(q) + q ∑_{j=0}^{n−2} q^{j}C_{j}K_{n−1−j}(q).

Since K_{0}(q) = K_{1}(q) = 1, an induction on n together with Equation (2.1) gives for n ≥ 0,

q^{n}(H_{n}(1/q) − 1) + 1 = F_{n}(q).

The rest follows now easily. □

Theorem 2.2. The statistic “lris” on the set R_{n}\{n … 21} and the statistic “n−fdes” on the set R_{n}\{12 … n} are equidistributed, that is, for n ≥ 1, we have

∑_{π∈R_{n}\{n...21}} q^{lris(π)} = ∑_{π∈R_{n}\{12...n}} q^{n−fdes(π)}.

Moreover,

∑_{n≥0} ∑_{π∈R_{n}} q^{fdes(π)}x^{n} = \frac{1 − q + q(1 − x)^{2}C(x)}{(1 − x)(1 − xq)}

and

∑_{n≥0} ∑_{π∈R_{n}} q^{lris(π)}x^{n} = \frac{1 + x(C(xq) − 1)C(xq)}{1 − x}.

Proof. Let L_{n}(q) = ∑_{π∈R_{n}} q^{fdes(π)} for n ≥ 0. Let π = (π′, n, π′′) ∈ R_{n} such that π_{j} = n. Using this block decomposition of π, we may derive a recurrence for L_{n}(q). Namely, the contribution of the permutations with j = 1 gives C_{n−1}q, the contribution for j = 2 gives C_{n−2}q^{2}, the contribution for n ≥ j ≥ 3 and π′ ≠ (n + 1 − j) … (n − 1) gives C_{n−j}(L_{j−1}(q) − 1), the contribution for n − 1 ≥ j ≥ 3 and π′ = (n + 1 − j) … (n − 1) gives q^{j}C_{n−j}, and the contribution for j = n and π′ = (n + 1 − j) … (n − 1)n gives 1. Hence, for n ≥ 1, we have

L_{n}(q) = C_{n−1}q + C_{n−2}q^{2} + ∑_{j=3}^{n} C_{n−j}(L_{j−1}(q) − 1) + ∑_{j=3}^{n−1} q^{j}C_{n−j} + 1,

or, equivalently,

(2.3)  L_{n}(q) = 1 + q ∑_{j=0}^{n−2} q^{j}C_{n−1−j} + ∑_{j=0}^{n−1} C_{n−1−j}(L_{j}(q) − 1).

Multiplying by x^{n}, summing over n ≥ 1, and finally using L_{0}(q) = L_{1}(q) = 1, we obtain that

∑_{n≥0} L_{n}(q)x^{n} = \frac{1 − q + q(1 − x)^{2}C(x)}{(1 − x)(1 − xq)}.

Now, let P_{n}(q) = ∑_{π∈R_{n}} q^{lris(π)} for n ≥ 0. Again, we may derive a recurrence for P_{n}(q) by using the above block decomposition of π. Namely, the contribution for j = n gives C_{n−1}q^{n−1}, the contribution for j = n − 1 gives C_{n−2}q^{n−2}, the contribution for 1 ≤ j ≤ n − 2 and π′′ ≠ (n − j) … 21 gives C_{j−1}q^{j}(P_{n−j}(q) − 1), and the contribution for n − 2 ≥ j ≥ 1 and π′′ = (n − j) … 21 gives q^{j−1}C_{j−1}. Hence, for n ≥ 1, we have

P_{n}(q) = C_{n−1}q^{n−1} + C_{n−2}q^{n−2} + ∑_{j=1}^{n−2} C_{j−1}q^{j}(P_{n−j}(q) − 1) + ∑_{j=1}^{n−2} q^{j−1}C_{j−1},

or, equivalently,

(2.4)  P_{n}(q) = ∑_{j=0}^{n−1} q^{j}C_{j} + q ∑_{j=0}^{n−1} C_{j}q^{j}(P_{n−1−j}(q) − 1).

Multiplying by x^{n}, summing over n ≥ 1, and using finally P_{0}(q) = P_{1}(q) = 1, we obtain that

∑_{n≥0} P_{n}(q)x^{n} = \frac{1 + x(C(xq) − 1)C(xq)}{1 − x}.

Using Equations (2.3) and (2.4) together with an induction on n, we conclude that q^{n}(P_{n}(q^{−1}) − 1) + 1 = L_{n}(q), and this completes the proof. □

More generally, we prove that the bistatistics (“fris”,“lris”) on the set R_{n}\{n … 21} and (“n − ldes”,“n − fdes”) on the set R_{n}\{12 … n} are equidistributed.

Theorem 2.3. The bistatistic (“fris”,“lris”) on the set R_{n}\{n … 21} and the bistatistic (“n − ldes”,“n − fdes”) on the set R_{n}\{12 … n} are equidistributed, that is, for n ≥ 1, we have

∑_{π∈R_{n}\{12...n}} p^{n−ldes(π)}q^{n−fdes(π)} = ∑_{π∈R_{n}\{n...21}} p^{fris(π)}q^{lris(π)}.

Moreover,

∑_{n≥0} ∑_{π∈R_{n}} p^{fris(π)}q^{lris(π)}x^{n} = 1 + \frac{x(1 − p + p(1 − 2qx + pq^{2}x^{2})C(qx))}{(1 − x)(1 − pqx)(1 − pqxC(qx))}.

Proof. Let A_{n}(p, q) = ∑_{π∈R_{n}} p^{fris(π)}q^{lris(π)} for n ≥ 1 and A_{0}(p, q) = 1. Using the block decomposition π = (π′, n, π′′) ∈ R_{n} where π_{j} = n once more, we derive a recurrence for A_{n}(p, q) if n ≥ 1. Namely, the contribution of the permutations with π′ = (n − 1) … (n + 1 − j) and π′′ = (n − j) … 1 gives ∑_{j=0}^{n−1}(pq)^{j}. The contribution of the permutations where π′ = (n − 1) … (n + 1 − j) and π′′ ≠ (n − j) … 1 gives

pq(A_{n−1}(p, q) − 1) + ∑_{j=2}^{n} q^{j}p^{j−1}(P_{n−j}(q) − 1).

(P_{n}(q) is the polynomial appearing in the proof of Theorem 2.2.) The contribution of the permutations where π′ ≠ (n − 1) … (n + 1 − j) and π′′ = (n − j) … 1 gives ∑_{j=1}^{n} q^{j−1}(H_{j−1}(p) − 1). (H_{n}(p) is the polynomial appearing in the proof of Theorem 2.1). Finally, the contribution of the permutations where π′ ≠ (n−1) … (n+1−j) and π′′ ≠ (n − j) … 1 equals ∑_{j=1}^{n} q^{j}(H_{j−1}(p) − 1)(P_{n−j}(q) − 1). Hence, for n ≥ 1, we have

A_{n}(p, q) = pq(A_{n−1}(p, q) − 1) + ∑_{j=0}^{n−1}(pq)^{j} + q ∑_{j=1}^{n−1}(pq)^{j}(P_{n−1−j}(q) − 1)

+ ∑_{j=0}^{n−1} q^{j}(H_{j}(p) − 1) + q ∑_{j=0}^{n−1} q^{j}(H_{j}(p) − 1)(P_{n−1−j}(q) − 1).

Let A(x; p, q), P (x; q), and H(x; p) be the generating functions for the sequences A_{n}(p, q), P_{n}(q), and H_{n}(p), respectively, that is,

A(x; p, q) = ∑_{n≥0} A_{n}(p, q)x^{n}, P (x; q) = ∑_{n≥0} P_{n}(q)x^{n}, and H(x; p) = ∑_{n≥0} H_{n}(p)x^{n}.

Multiplying the above recurrence by x^{n}, summing over n ≥ 1, and finally using A_{0}(p, q) = H_{0}(p) = P_{0}(q) = 1, we obtain that

(1 − pqx)A(x; p, q) = 1 + \frac{x}{(1 − x)(1 − pqx)} + \frac{x}{1 − x} (H(qx; p) − \frac{1}{1 − qx})

+ \frac{qx}{1 − pqx} (P (x; q) − \frac{1}{1 − x}) − qx (P (x; q) − \frac{1}{1 − x})

− \frac{pqx}{1 − x} + xq (H(qx; p) − \frac{1}{1 − qx}) (P (x; q) − \frac{1}{1 − x}) .

From Theorem 2.1 we have

H(x; q) = \frac{1}{1 − qxC(x)} + \frac{1}{1 − x} − \frac{1}{1 − qx},

while Theorem 2.2 yields

P (x; q) = \frac{1}{1 − x}(1 + x(C(qx) − 1)C(qx)).

Hence,

A(x; p, q) = 1 + \frac{x(1 − p + p(1 − 2qx + pq^{2}x^{2})C(qx))}{(1 − x)(1 − pqx)(1 − pqxC(qx))}.

We now turn to the computation of the generating function

B(x; p, q) = ∑_{n≥0} ∑_{π∈R_{n}} p^{n−ldes(π)}q^{n−fdes(π)}x^{n}.

Using the arguments in the proof of the formula for A(x; p, q), we get that

B(x; p, q) = A(x; p, q) − \frac{1}{1 − x} + \frac{1}{1 − pqx}.

Hence,

∑_{n≥0} ∑_{π∈R_{n}\\{12...n\}} p^{n−ldes(π)}q^{n−fdes(π)}x^{n} = B(x; p, q) − \frac{1}{1 − pqx}

= A(x; p, q) − \frac{1}{1 − x}

= ∑_{n≥0} ∑_{π∈R_{n}\{n...21}} p^{fris(π)}q^{lris(π)}x^{n},

as requested. □

3. Sign Balance on R_{n}

We denote the set of all even (respectively odd) permutations π ∈ R_{n} by R_{n}^{+} (respectively R_{n}^{−}). We define e_{n} = |R_{n}^{+}|, o_{n} = |R_{n}^{−}|, and m_{n} = e_{n} − o_{n} for all n ≥ 0. (Simion and Schmidt [SimSch] proved that m_{n} = C_{(n−1)/2} if n is odd and m_{n} = 0 otherwise.) In this section we study the sign-balance of R_{n} with respect to certain statistics.

Theorem 3.1. We have

∑_{n≥0} M_{n}(q)x^{n} = ∑_{n≥0} ∑_{π∈R_{n}} sign(π)q^{ldes (π)} = \frac{1 + x − x^{2}qC(x^{2}q^{2})}{1 − x^{2}C(x^{2}q^{2})}.

Proof. Let F_{n}^{±}(q) = ∑_{π∈R_{n}^{±}} q^{ldes(π)}, and let π = (π′, n, π′′) ∈ R_{n} such that π_{j+1} = n, 0 ≤ j ≤ n − 1. Then, for this block decomposition of π, we have

sign(π) = (−1)^{(j+1)(n−j−1)} sign(π′) sign(π′′) = (−1)^{(j+1)(n−1)} sign(π′) sign(π′′),

or, equivalently,

sign(π) = \{ \begin{matrix}sign(π′) · sign(π′′), & if n is odd, \\ (−1)^{j+1} · sign(π′) · sign(π′′), & if n is even. \end{matrix}

Therefore, for n ≥ 1, we obtain

F_{2n+1}^{±}(q) = F_{2n}^{±}(q) + ∑_{j=0}^{2n−1} q^{j+1}(e_{j}F_{2n−j}^{±}(q) + o_{j}F_{2n−j}^{∓}(q))
F_{2n}^{±}(q) = F_{2n−1}^{±}(q) + ∑_{j=0,2,4,...,2n−2} q^{j+1}(e_{j}F_{2n−1−j}^{∓}(q) + o_{j}F_{2n−1−j}^{±}(q))

+ ∑_{j=1,3,...,2n−3} q^{j+1}(e_{j}F_{2n−1−j}^{±}(q) + o_{j}F_{2n−1−j}^{∓}(q).

Hence, for all n ≥ 1, we have

M_{2n+1}(q) = M_{2n}(q) + ∑_{j=0}^{2n−1} q^{j+1}m_{j}M_{2n−j}(q),
M_{2n}(q) = M_{2n−1}(q) − ∑_{j=0,2,4,...,2n−2} q^{j+1}m_{j}M_{2n−1−j}(q)

+ ∑_{j=1,3,...,2n−3} q^{j+1}m_{j}M_{2n−1−j}(q).

Let M(x; q) = ∑_{n≥0} M_{n}(q)x^{n} and m(x) = ∑_{n≥0} m_{n}x^{n}. Using [M2, Lemma 2.3], we get that

(1 − x − xqm(xq))M(x; q) − (1 + x + xqm(−xq))M(−x; q)

= −xq(m(xq) + m(−xq)),

and

(1 − x + xqm(−xq))M(x; q) + (1 + x − xqm(xq))M(−x; q)

= 2 − xq(m(xq) − m(−xq)).

Hence, solving the above two equations for the variables M(x; q) and M(−x; q), and using the fact that m(x) = 1 + xC(x^{2}) (see [SimSch]), we obtain the desired result. □

As a corollary of the above theorem, we have the following result concerning the sign-and-“ldes” statistic on R_{n}.

Corollary 3.2. For all n ≥ 1, we have

∑_{π∈R_{2n}} sign(π)(−1)^{ldes(π)} = 2C_{n} and ∑_{π∈R_{2n−1}} sign(π)(−1)^{ldes(π)} = C_{n−1}.

Moreover,

1 + ∑_{n≥1} ∑_{π∈R_{n}} sign(π)(−1)^{ldes(π)}x^{n} = (1 + x + x^{2}C(x^{2}))C(x^{2}).

More generally, Theorem 3.1 yields the following result.

Corollary 3.3. For all n ≥ 1, we have

∑_{π∈R_{2n}} sign(π)q^{ldes(π)} = (1 − q) ∑_{π∈R_{2n+1}} sign(π)q^{ldes(π)},

and

∑_{π∈R_{2n−1}} sign(π)q^{ldes(π)} = ∑_{π∈R_{n−1}} q^{2(ldes(π))}.

Theorem 3.4. We have

∑_{n≥0} N_{n}(q)x^{n} = ∑_{n≥0} ∑_{π∈R_{n}} sign(π)q^{fdes(π)}

= 1 + x\frac{(1 − q)(1 − xq + 2q) − q(1 − x^{2})(1 + xq − 2q)C(x^{2})}{(1 − x)(1 − x^{2}q^{2})}.

Proof. Let L_{n}^{±}(q) = ∑_{π∈R_{n}^{±}} q^{fdes(π)}, and let π = (π′, n, π′′) ∈ R_{n} such that π_{j+1} = n, 0 ≤ j ≤ n − 1. Then, for this block decomposition of π, we have

sign(π) = (−1)^{(j+1)(n−j−1)} sign(π′) sign(π′′) = (−1)^{(j+1)(n−1)} sign(π′) sign(π′′),

or, equivalently,

sign(π) = \{ \begin{matrix}sign(π′) · sign(π′′), & if n is odd, \\ (−1)^{j+1} · sign(π′) · sign(π′′), & if n is even. \end{matrix}

Therefore, for n ≥ 1, we obtain

L_{2n+1}^{±}(q) = ∑_{j=0}^{2n−1} q^{j+1}L_{2n−j}^{±} + (L_{j}^{±}(q) − ϵ^{±})e_{2n−j} + (L_{j}^{∓}(q) − ϵ^{∓})o_{2n−j}
L_{2n}^{±}(q) = ∑_{j=0,2,4,...,2n−2} q^{j+1}L_{2n−1−j}^{∓}(q) + (L_{j}^{∓}(q) − ϵ^{∓})e_{2n−1−j} + (L_{j}^{pm}(q) − ϵ^{±})o_{2n−1−j}

+ ∑_{j=1,3,...,2n−3} q^{j+1}L_{2n−1−j}^{±}

+ ∑_{j=1,3,...,2n−3}(L_{j}^{±} − ϵ^{±})e_{2n−1−j} + (L_{j}^{∓} − ϵ^{∓})o_{2n−1−j},

where ϵ^{+} = 1 and ϵ^{−} = 0. Hence, for all n ≥ 1, we have

N_{2n+1}(q) = 1 + ∑_{j=0}^{2n−1} q^{j+1}m_{2n−j} + ∑_{j=0}^{2n}(N_{j}(q) − 1)m_{2n−j},
M_{2n}(q) = 1 − ∑_{j=0,2,...,2n−2} q^{j+1}m_{2n−1−j} + ∑_{j=1,3,...,2n−3} q^{j+1}m_{2n−1−j}

− ∑_{j=0,2,...,2n−2}(N_{j}(q) − 1)m_{2n−1−j} + ∑_{j=1,3,...,2n−1}(N_{j}(q) − 1)m_{2n−1−j}.

Let N(x; q) = ∑_{n≥0} N_{n}(q)x^{n} and m(x) = ∑_{n≥0} m_{n}x^{n}. Using [M2, Lemma 2.3], we get that

\frac{1}{2}(N(x; q) − N(−x; q)) = \frac{x}{1 − x^{2}} + \frac{xq}{2} (\frac{m(x)}{1 − xq} + \frac{m(−x)}{1 + xq} − \frac{2}{1 − x^{2}q^{2}} )

+ \frac{x}{2} [(N(x; q) − \frac{1}{1 − x}) m(x) + (N(−x, q) − \frac{1}{1 + x}) m(−x)] ,

and

\frac{1}{2}(N(x; q) + N(−x, q)) = \frac{1}{1 − x^{2}} − \frac{xq}{2(1 − x^{2}q^{2})}(m(x) − m(−x))

+ \frac{x^{2}q^{2}}{2(1 − x^{2}q^{2})}(m(x) + m(−x) − 2)

− \frac{x}{4} (N(x; q) + N(−x; q) − \frac{2}{1 − x^{2}} ) (m(x) − m(−x))

+ \frac{x}{4} (N(x; q) − N(−x; q) − \frac{2x}{1 − x^{2}} ) (m(x) + m(−x)).

Hence, solving the above two equations for the variables N(x; q) and N(−x; q), and using the fact that m(x) = 1 + xC(x^{2}) (see [SimSch]), we get the desired result. □

4. Dyck paths

Following [Kr], we define a bijection Φ between permutations in S_{n}(132) and Dyck paths from the origin to the point (2n, 0). Let π = π_{1} … π_{n} be a 132-avoiding permutation. We read the permutation π from left to right and successively generate a Dyck path. When π_{j} is read, then in the path we adjoin as many up-steps as necessary, followed by a down-step from height h_{j} + 1 to height h_{j} (measured from the x-axis), where h_{j} is the number of elements in π_{j+1}, π_{j+2}, …, π_{n} which are larger than π_{j}. For example, if π = 534261 ∈ S_{6}, then the corresponding Dyck path is the one shown in Figure 1.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 1; 2; 3; 4; x; y]

Figure 1. The Dyck path Φ(534261).

Namely, the first element to be read is 5. There is one element in 34261 which is larger than 5, therefore the path starts with two up-steps followed by a down-step, thus reaching height 1. Next 3 is read. There are 2 elements in 4261 which are larger than 3, therefore the path continues with two up-steps followed by a down-step, thus reaching height 2. Etc. Conversely, given a Dyck path starting at the origin and returning to the x-axis, the obvious inverse of the bijection Φ produces a 132-avoiding permutation.

Theorem 4.1. For all n ≥ 0, we have

∑_{p∈P_{n}} q^{n−lpeak(p)} = ∑_{π∈R_{n}} q^{ldes(π)}.

Proof. We prove that n + 1 − lpeak(Φ(π)) = fdes(π) for any π ∈ R_{n}. Let π = (π′, 1, π′′) ∈ R_{n} such that π_{1} = j. Since π avoids 132, the letters of π′′ are increasing (i.e., π′′_{a} < π′′_{b} for all a < b). Therefore, by definition of Φ, the Dyck path p = Φ(π) satisfies the equation lpeak(p) = |π′′| + 1 = n + 1 − j, where |π′′| is the number of letters in π′′. □

Remark 4.2. The relation n + 1 − peak(Φ(π)) = fdes(π) for π ∈ R_{n} can be read off immediately from the permutation diagram, see [R].

Acknowledgment. The author thanks the anonymous referee, whose suggestions improved both the content and exposition of this paper. The final version of this paper was written during the author’s stay at the University of Haifa, Israel, and he would like to express his gratitude to the University of Haifa for the support.

References

[AR] Ron M. Adin and Yuval Roichman, Equidistribution and sign-balance on 321-avoiding

    permutations, preprint, 2003, <http://arXiv.org/abs/math.CO/0304429>.

[FS] D. Foata and M.-P. Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159.

[Kn] D. Knuth, The Art of Computer Programming, vol. 1, Addison Wesley, Reading, MA, 1968.

[Kr] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), 510–530.

[M1] T. Mansour, Counting peaks at height k in a Dyck path, Journal Integer of Sequences 5 (2002), Article 02.1.1.

[M2] T. Mansour, Restricted 132-alternating permutations and Chebyshev polynomials, Annals of Combinatorics 7:2 (2003), 201–227.

[MV] T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Séminaire Lotharingien de Combinatoire 47 (2002), Article B47c.

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

[R] A. Reifegerste, On the diagram of 132-avoiding permutations, European J. Combin. 24 (2003), 759–776.

[S] R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986, xi + 306 pages; second printing, Cambridge University Press, Cambridge, 1996.