INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A07

PARITY THEOREMS FOR STATISTICS ON PERMUTATIONS AND CATALAN WORDS

Mark Shattuck

Department of Mathematics, University of Tennessee, Knoxville, TN 37996-1300, USA

                          shattuck@math.utk.edu

Received: 2/11/05, Accepted: 4/3/05, Published: 4/20/05

Abstract

We establish parity theorems for statistics on the symmetric group S_{n}, the derangements D_{n}, and the Catalan words C_{n}, giving both algebraic and bijective proofs. For the former, we evaluate q-generating functions at q = −1; for the latter, we define appropriate signreversing involutions. Most of the statistics involve counting inversions or finding the major index of various words.

Keywords: Permutation statistic, inversion, major index, derangement, Catalan numbers.

1. Introduction

We’ll use the following notational conventions: ℕ := {0, 1, 2, … }, ℙ := {1, 2, … }, [0] := ∅, and [n] := {1, …, n} for n ∈ ℙ. Empty sums take the value 0 and empty products the value 1, with 0^{0} := 1. The letter q denotes an indeterminate, with 0_{q} := 0, n_{q} :=

1 + q + ⋯ + q^{n−1} for n ∈ ℙ, 0!_{q} := 1, n!_{q} := 1_{q}2_{q} ⋯ n_{q} for n ∈ ℙ, and \binom{n}{k}_{q} := n!_{q}/k!_{q}(n − k)!_{q}

for n ∈ ℕ and 0 ⩽ k ⩽ n. The binomial coefficient \binom{n}{k} is equal to zero if k is a negative integer or if 0 ⩽ n < k.

Let Δ be a finite set of discrete structures and I : Δ → N, with generating function

G(I, Δ; q) := ∑_{δ∈Δ} q^{I(δ)} = ∑_{k} |{δ ∈ Δ : I(δ) = k}| q^{k}.  (1.1)

Of course, G(I, Δ; 1) = |Δ|. If Δ^{+} := {δ ∈ Δ : I(δ) is even} and Δ^{−} := {δ ∈ Δ : I(δ) is odd}, then G(I, Δ; −1) = |Δ^{+}|−|Δ^{−}|. Hence if G(I, Δ; −1) = 0, the set Δ is “balanced” with respect to the parity of I. For example, setting q = −1 in the binomial theorem,

(1 + q)^{n} = ∑_{S⊆[n]} q^{|S|} = ∑_{k=0}^{n} \binom{n}{k}q^{k},  (1.2)

yields the familiar result that a finite nonempty set has as many subsets of odd cardinality as it has subsets of even cardinality.

When G(I, Δ; −1) = 0 and hence |Δ^{+}| = |Δ^{−}|, it is instructive to identify an I−parity changing involution of Δ. For the statistic |S| in (1.2), the map

S ↦ \begin{cases}S ∪ \{1\}, & if 1 ∉ S; \\ S − \{1\}, & if 1 ∈ S, \end{cases}

furnishes such an involution. More generally, if G(I, Δ; −1) = |Δ^{+}|−|Δ^{−}| = c, it suffices to identify a subset Δ^{∗} of Δ of cardinality |c| contained completely within Δ^{+} or Δ^{−} and then to define an I-parity changing involution on Δ − Δ^{∗}. The subset Δ^{∗} thus captures both the sign and magnitude of G(I, Δ; −1). Evaluation of q-generating functions as in (1.1) at q = −1 has yielded parity theorems for statistics on set partitions [9, 13], lattice paths [10], domino arrangements [11], and Laguerre configurations [10].

Since each member of Δ − Δ^{∗} is paired with another of opposite I-parity, we have |Δ| ≡ |Δ^{∗}| (mod 2). Thus, the I-parity changing involutions described above also yield combinatorial proofs of congruences of the form a_{n} ≡ b_{n} (mod 2). Shattuck [9] has, for example, given such a combinatorial proof of the congruence

S(n, k) ≡ \binom{n − ⌊k/2⌋ − 1}{n − k} (mod 2)

for Stirling numbers of the second kind, answering a question posed by Stanley [12, p. 46, Exercise 17b].

In §2 below, we establish parity theorems for several permutation statistics defined on all of S_{n}, algebraically by evaluating q-generating functions at q = −1 and combinatorially by identifying appropriate parity changing involutions. In §3, we analyze the parity of some statistics on D_{n}, the set of derangements of [n] (i.e., permutations of [n] having no fixed points).

Shattuck and Wagner [10] derive a parity theorem for the number of inversions in binary words of length n with k 1’s. In §4, we obtain comparable results for C_{n}, the set of binary words of length 2n with n 1’s and with no initial segment containing more 1’s than 0’s (termed Catalan words).

Recall that the inversion and major index statistics for a word w = w_{1}w_{2} ⋯ w_{m} in some alphabet are given by

maj (w) := ∑_{i∈D(w)} i, where D(w) := {1 ≤ i ≤ m − 1 : w_{i} > w_{i+1}},

and

inv(w) := |{(i, j) : i < j and w_{i} > w_{j}}| .

2. Permutation Statistics

2.1 Some Balanced Permutation Statistics

Let S_{n} be the set of permutations of [n]. A function f : S_{n} → ℕ is called a permutation statistic. Two important permutation statistics are inv and maj , which record the number of inversions and the major index, respectively, of a permutation σ = σ_{1}σ_{2} ⋯ σ_{n}, expressed as a word. The statistics inv and maj have the same q-generating function over S_{n}:

∑_{σ∈S_{n}} q^{inv(σ)} = n!_{q} = ∑_{σ∈S_{n}} q^{maj (σ)},  (2.1)

[12, Corollary 1.3.10] and [1, Corollary 3.8].

Substituting q = −1 into (2.1) reveals that n!_{−1} = 0 if n ≥ 2, and hence inv and maj are both balanced if n ≥ 2. Interchanging σ_{1} and σ_{2} in σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ S_{n} changes the parity of both inv and maj and thus furnishes an appropriate involution. Note that switching the elements 1 and 2 in σ changes the inv-parity, but not necessarily the maj-parity.

Now express σ ∈ S_{n} in the standard cycle form

σ = (α_{1})(α_{2}) ⋯,

where α_{1}, α_{2}, … are the cycles of σ, ordered by increasing smallest elements with each cycle (α_{i}) written with its smallest element in the first position. Let S_{n,k} denote the set of permutations of [n] with k cycles and c(n, k) := |S_{n,k}|, the signless Stirling number of the first kind. The c(n, k) are connection constants in the polynomial identities

q(q + 1) ⋯ (q + n − 1) = ∑_{k=0}^{n} c(n, k)q^{k}.  (2.2)

Setting q = −1 in (2.2) reveals that there are as many permutations of [n] with an even number of cycles as there are with an odd number of cycles if n ≥ 2. Alternatively, breaking apart or merging α_{1} and α_{2} as shown below, leaving the other cycles undisturbed, changes the parity of the number of cycles:

α_{1} = (1 ⋯ 2 ⋯), … ↔ α_{1} = (1 ⋯), α_{2} = (2 ⋯), ….

This involution also shows that the statistic recording the number of cycles of σ with even cardinality is balanced if n ≥ 2.

Given σ = (α_{1})(α_{2}) ⋯, expressed in standard cycle form, let

w(σ) := ∑_{i}(i − 1)|α_{i}|.

Edelman, Simion, and White [4] show that

∑_{σ∈S_{n}} x^{|σ|}q^{w(σ)} = ∏_{i=0}^{n−1}(xq^{i} + i),  (2.3)

where |σ| denotes the number of cycles. Setting x = 1 in (2.3) yields

∑_{σ∈S_{n}} q^{w(σ)} = ∏_{i=0}^{n−1}(q^{i} + i),  (2.4)

another q-generalization of n!.

Setting q = −1 in (2.4) shows that the w statistic is balanced if n ≥ 2. Alternatively, if the last cycle has cardinality greater than one, break off the last member and form a 1-cycle with it; if the last cycle contains a single member, place it at the end of the penultimate cycle.

2.2. An Unbalanced Permutation Statistic

Carlitz [2] defines the statistic inv_{c} on S_{n} as follows: express σ ∈ S_{n} in standard cycle form; then remove parentheses and count inversions in the resulting word to obtain inv_{c}(σ). As an illustration, for the permutation σ ∈ S_{7} given by 3241756, we have inv_{c}(σ) = 3, the number of inversions in the word 1342576.

Let

c_{q}(n, k) := ∑_{σ∈S_{n,k}} q^{inv_{c}(σ)},  (2.5)

where S_{n,k} is the set of permutations of [n] with k cycles. Then c_{q}(n, 0) = δ_{n,0}, c_{q}(0, k) = δ_{0,k}, and

c_{q}(n, k) = c_{q}(n − 1, k − 1) + (n − 1)_{q}c_{q}(n − 1, k), ∀n, k ∈ ℙ,  (2.6)

since n may go in a cycle by itself or come directly after any member of [n − 1] within a cycle.

Using (2.6), it is easy to show that

x(x + 1_{q}) ⋯ (x + (n − 1)_{q}) = ∑_{k=0}^{n} c_{q}(n, k)x^{k}.  (2.7)

Setting x = 1 in (2.7) gives

c_{q}(n) := ∑_{k=0}^{n} c_{q}(n, k) = ∑_{σ∈S_{n}} q^{inv_{c}(σ)} = ∏_{j=0}^{n−1}(1 + j_{q}).  (2.8)

Theorem 2.1. For all n ∈ N,

c_{−1}(n) := ∑_{σ∈S_{n}}(−1)^{inv_{c}(σ)} = 2^{⌊n/2⌋}.  (2.9)

Proof. Put q = −1 in (2.8) and note that

j_{q}|_{q=−1} = \begin{cases}0, & if j is even; \\ 1, & if j is odd. \end{cases}

Alternatively, with S_{n}^{+}, S_{n}^{−} denoting the members of S_{n} with even or odd inv_{c} values, respectively, we have c_{−1}(n) = |S_{n}^{+}| − |S_{n}^{−}|. To prove (2.9), it thus suffices to identify a subset S_{n}^{∗} of S_{n}^{+} such that |S_{n}^{∗}| = 2^{⌊n/2⌋} along with an inv_{c}-parity changing involution of S_{n} − S_{n}^{∗}.

First assume n is even. In this case, the set S_{n}^{∗} consists of those permutations expressible in standard cycle form as a product of 1-cycles and the transpositions (2i − 1, 2i), 1 ≤ i ≤ n/2. Note that S_{n}^{∗} ⊆ S_{n}^{+} with zero inv_{c} value for each of its 2^{n/2} members.

Before giving the involution on S_{n}−S_{n}^{∗}, we make a definition: given σ = (α_{1})(α_{2}) ⋯ ∈ S_{m} in standard cycle form and j, 1 ≤ j ≤ m, let σ_{[j]} be the permutation of [j] (in standard cycle form) obtained by writing the members of [j] in the order as they appear within the cycles of σ (e.g., if σ = (163)(25)(4)(7) ∈ S_{7} and j = 4, then σ_{[4]} = (13)(2)(4) and σ_{[7]} = σ).

Suppose now σ ∈ S_{n} − S_{n}^{∗} is expressed in standard cycle form and that i_{0} is the smallest integer i, 1 ≤ i ≤ n/2, for which σ_{[2i]} ∈ S_{2i} − S_{2i}^{∗}. Then it must be the case for σ that

(i) neither 2i_{0} − 1 nor 2i_{0} starts a cycle, or

(ii) exactly one of 2i_{0} − 1, 2i_{0} starts a cycle with 2i_{0} − 1 and 2i_{0} not belonging to the same cycle.

Switching 2i_{0} −1 and 2i_{0} within σ, written in standard cycle form, changes the inv_{c} value by one, and the resulting map is thus a parity changing involution of S_{n} − S_{n}^{∗}.

If n is odd, let S_{n}^{∗} ⊆ S_{n}^{+} consist of those permutations expressible as a product of 1-cycles and the transpositions (2i, 2i + 1), 1 ≤ i ≤ \frac{n−1}{2}. Switch 2i_{0} and 2i_{0} + 1 within σ ∈ S_{n} − S_{n}^{∗}, where i_{0} is the smallest i, 1 ≤ i ≤ \frac{n−1}{2}, for which σ_{[2i+1]} ∈ S_{2i+1} − S_{2i+1}^{∗}.

The preceding parity theorem has the refinement

Theorem 2.2. For all n ∈ N,

c_{−1}(n, k) := ∑_{σ∈S_{n,k}}(−1)^{inv_{c}(σ)} = \binom{⌊n/2⌋}{n − k},  0 ≤ k ≤ n.  (2.10)

Proof. Set q = −1 in (2.7) to get

∑_{k=0}^{n} c_{−1}(n, k)x^{k} = x^{⌈n/2⌉}(x + 1)^{⌊n/2⌋} = ∑_{k=⌈n/2⌉}^{n} \binom{⌊n/2⌋}{n − k}x^{k}.

Or let S_{n,k}^{±} := S_{n,k} ∩S_{n}^{±} and S_{n,k}^{∗} := S_{n,k} ∩S_{n}^{∗}. Then S_{n,k}^{∗} ⊆ S_{n,k}^{+} and its cardinality agrees with the right-hand side of (2.10). The restriction of the map used for Theorem 2.1 to S_{n,k} − S_{n,k}^{∗} is again an involution and inherits the parity changing property.

Remark. The bijection of Theorem 2.2 also proves combinatorially that

c(n, k) ≡ \binom{⌊n/2⌋}{n − k} (mod 2),  0 ⩽ k ⩽ n,  (2.11)

since off of a set of cardinality \binom{⌊n/2⌋}{n−k}, each permutation σ ∈ S_{n,k} is paired with another of opposite inv_{c}-parity. The congruences in (2.11) can also be obtained by taking mod 2 the polynomial identities in (2.2) (cf. [12, p. 46, Exercise 17c]).

3. Some Statistics for Derangements

A permutation σ of [n] having no fixed points (i.e., i ∈ [n] such that σ(i) = i) is called a derangement. Let D_{n} denote the set of derangements of [n] and d_{n} := |D_{n}|. A typical inclusion-exclusion argument gives the well known formula

d_{n} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} ,  ∀n ∈ ℕ.  (3.1)

Given σ ∈ D_{n}, express it in the form

σ = (α_{1})(α_{2}) ⋯,

where α_{1}, α_{2}, … are the cycles of σ arranged as follows:

(i) the cycles α_{1}, α_{2}, … are ordered by increasing second smallest elements;

(ii) each cycle (α_{i}) is written with the second smallest element in the last position.

Garsia and Remmel [6] term this the ordered cycle factorization (OCF for brief) of σ.

Define the statistic inv_{o} on D_{n} as follows: write out the cycles of σ ∈ D_{n} in OCF form; then remove parentheses and count inversions in the resulting word to obtain inv_{o}(σ). As an illustration, for the derangement σ ∈ D_{7} given by 4321756, we have inv_{o}(σ) = 3, the number of inversions in the word 2314576.

The statistic inv_{o} is due to Garsia and Remmel [6], who show that the generating function

D_{q}(n) := ∑_{σ∈D_{n}} q^{inv_{o}(σ)} = n!_{q} ∑_{k=0}^{n} \frac{(−1)^{k}}{k!_{q}} ,  ∀n ∈ ℕ,  (3.2)

which generalizes (3.1).

Theorem 3.1. For all n ∈ ℕ,

D_{−1}(n) = \begin{cases}1, & if n is even; \\ 0, & if n is odd. \end{cases}  (3.3)

Proof. Formula (3.3) is an immediate consequence of (3.2), for

∑_{k=0}^{n} \frac{(−1)^{k}n!_{q}}{k!_{q}} |_{q=−1} = ∑_{k=0}^{n}(−1)^{k} ∏_{i=k+1}^{n} i_{q}|_{q=−1} = (−1)^{n−1}n_{−1} + (−1)^{n},

as

j_{−1} = \begin{cases}0, & if j is even; \\ 1, & if j is odd. \end{cases}

Alternatively, let σ = (α_{1})(α_{2}) ⋯ ∈ D_{n} be expressed in OCF form, first assuming n is odd. Locate the leftmost cycle of σ containing at least three members and interchange the first two members of this cycle. Now assume n is even. If σ has a cycle of length greater than two, proceed as in the odd case. If all cycles of σ are transpositions and σ ≠ (1, 2)(3, 4) ⋯ (n − 1, n), let i_{0} be the smallest integer i for which the transposition (2i − 1, 2i) fails to occur in σ. Switch 2i_{0} − 1 and 2i_{0} in σ, noting that 2i_{0} − 1 and 2i_{0} must both start cycles. Thus whenever n is even, every σ ∈ D_{n} is paired with another of opposite inv_{o}-parity except for (1, 2)(3, 4) ⋯ (n − 1, n), which has inv_{o} value zero.

Now consider the generating function d_{q}(n) resulting when one restricts inv to D_{n}, i.e.,

d_{q}(n) := ∑_{σ∈D_{n}} q^{inv(σ)}.  (3.4)

We have been unable to find a simple formula for d_{q}(n) which generalizes (3.1) or a recurrence satisfied by d_{q}(n) that generalizes one for d_{n}. However, we do have the following parity result.

Theorem 3.2. For all n ∈ ℕ,

d_{−1}(n) = (−1)^{n−1}(n − 1).  (3.5)

Proof. Equivalently, we show that the numbers d_{−1}(n) satisfy

d_{−1}(n) = −d_{−1}(n − 1) + (−1)^{n−1},  ∀n ∈ ℙ,  (3.6)

with d_{−1}(0) = 1. Let n ⩾ 2, σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ D_{n}, and D_{n}^{∗} ⊆ D_{n} consist of those derangements σ for which σ_{1} = 2 and σ_{2} ⩾ 3. Define an inv-parity changing involution f on D_{n} − D_{n}^{∗} − {n12 ⋯ n − 1} as follows:

(i) if σ_{2} ⩾ 3, whence σ_{1} ⩾ 3, switch 1 and 2 in σ to obtain f(σ);

(ii) if σ_{2} = 1, let k_{0} be the smallest integer k, 1 ⩽ k ⩽ ⌊\frac{n−1}{2}⌋, such that σ_{2k}σ_{2k+1} ≠ (2k − 1)(2k); switch 2k_{0} and 2k_{0} + 1 if σ_{2k_{0}} = 2k_{0} − 1 or switch 2k_{0} − 1 and 2k_{0} if σ_{2k_{0}} ⩾ 2k_{0} + 1 to obtain f(σ).

Thus,

d_{−1}(n) := ∑_{σ∈D_{n}}(−1)^{inv(σ)} = ∑_{σ∈D_{n}^{∗}∪{n12···n−1}}(−1)^{inv(σ)}.  (3.7)

One can regard members σ of D_{n}^{∗} as 2 followed by a derangement of [n − 1] since within the terminal segment σ′ := σ_{2}σ_{3} ⋯ σ_{n}, we must have σ_{2} ≠ 1 and σ_{k} ≠ k for all k ⩾ 3. Thus,

∑_{σ′:σ∈D_{n}^{∗}}(−1)^{inv(σ′)} = d_{−1}(n − 1),

from which

∑_{σ∈D_{n}^{∗}}(−1)^{inv(σ)} = −d_{−1}(n − 1),  (3.8)

since the initial 2 adds an inversion. The recurrence (3.6) follows immediately from (3.7) and (3.8) upon adding the contribution of (−1)^{n−1} from the singleton {n12 ⋯ n−1}.

Now consider the generating function r_{q}(n) resulting when one restricts maj to D_{n}, i.e.,

r_{q}(n) := ∑_{σ∈D_{n}} q^{maj (σ)}.  (3.9)

We were unable to find a simple formula for r_{q}(n) which generalizes (3.1). Yet when q = −1 we have Theorem 3.3. For all n ∈ ℕ,

r_{−1}(n) = \begin{cases}(−1)^{n/2}, & if n is even; \\ 0, & if n is odd. \end{cases}  (3.10)

Proof. First verify (3.10) for 0 ⩽ n ⩽ 3. Let n ⩾ 4 and D_{n}^{∗} ⊆ D_{n} consist of those derangements starting with 2143 when expressed as a word. We define a maj -parity changing involution of D_{n} − D_{n}^{∗} below. Note that for derangements of the form σ = 2143σ_{5} ⋯ σ_{n}, the subword σ_{5} ⋯ σ_{n} is itself a derangement on n − 4 elements. Thus for n ⩾ 4,

r_{−1}(n) := ∑_{σ∈D_{n}}(−1)^{maj (σ)} = ∑_{σ∈D_{n}^{∗}}(−1)^{maj (σ)} = r_{−1}(n − 4),

which proves (3.10).

We now define a maj -parity changing involution f of D_{n} − D_{n}^{∗} when n ⩾ 4. Let σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ D_{n} − D_{n}^{∗} be expressed as a word. If possible, pair σ with σ′ = f(σ) according to (I) and (II) below:

(I) first, if both σ_{1} ≠ 2 and σ_{2} ≠ 1, then switch σ_{1} and σ_{2} within σ to obtain σ′;

(II) if (I) cannot be implemented (i.e., σ_{1} = 2 or σ_{2} = 1) but σ_{3} ≠ 4 and σ_{4} ≠ 3, then switch σ_{3} and σ_{4} within σ to obtain σ′.

We now define f for the cases that remain. To do so, consider S_{σ} := σ_{1}σ_{2}σ_{3}σ_{4} ∩ [4], where σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ D_{n} − D_{n}^{∗} is of a form not covered by rules (I) and (II) above. We consider cases depending upon |S_{σ}|. If |S_{σ}| = 2 or if |S_{σ}| = 4, first multiply σ by the transposition (34) and then exchange the letters in the third and fourth positions to obtain σ′. This corresponds to the pairings

i) σ = a1b3 … 4 … ↔ σ′ = a14b … 3 …;

ii) σ = 2ab3 … 4 … ↔ σ′ = 2a4b … 3 …;

iii) σ = 2341 … ↔ σ′ = 2413 …;

iv) σ = 4123 … ↔ σ′ = 3142 …,

where a, b ⩾ 5.

If |S_{σ}| = 3, then pair according to one of six cases shown below where a ⩾ 5, leaving the other letters undisturbed:

i) σ = 314a … ↔ σ′ = 41a3 …; ii) σ = 234a … ↔ σ′ = 24a3 …;

iii) σ = a123 … ↔ σ′ = 2a13 …;

iv) σ = a142 … ↔ σ′ = 2a41 …;

v) σ = 21a3 … 4 … ↔ σ′ = 214a … 3 …;

vi) σ = a143 … 2 … ↔ σ′ = 2a43 … 1 . . ..

It is easy to verify that σ and σ′ have opposite maj -parity in all cases.

4. Statistics for Catalan Words

The Catalan numbers c_{n} are defined by the closed form

c_{n} = \frac{1}{n + 1}\binom{2n}{n},  n ∈ ℕ,  (4.1)

as well as by the recurrence

c_{n+1} = ∑_{j=0}^{n} c_{j}c_{n−j},  c_{0} = 1.  (4.2)

If one defines the generating function

f(x) = ∑_{n⩾0}c_{n}x^{n},  (4.3)

then (4.2) is equivalent to

f(x) = 1 + xf(x)^{2}.  (4.4)

Due to (4.2), the Catalan numbers enumerate many combinatorial structures, among them the set C_{n} consisting of words w = w_{1}w_{2} ⋯ w_{2n} of n 1’s and n 0’s for which no initial segment contains more 1’s than 0’s (termed Catalan words). In this section, we’ll look at two q-analogues of the Catalan numbers, one of Carlitz which generalizes (4.4) and another of MacMahon which generalizes (4.1), when q = −1. These q-analogues arise as generating functions for statistics on C_{n}.

If

C̃_{q}(n) := ∑_{w∈C_{n}} q^{inv(w)},  (4.5)

then

C̃_{q}(n + 1) = ∑_{k=0}^{n} q^{(k+1)(n−k)}C̃_{q}(k)C̃_{q}(n − k),  C̃_{q}(0) = 1,  (4.6)

upon decomposing a Catalan word w ∈ C_{n+1} into w = 0w_{1}1w_{2} with w_{1} ∈ C_{k}, w_{2} ∈ C_{n−k} for some k, 0 ⩽ k ⩽ n, and noting that the number of inversions of w is given by

inv(w) = inv(w_{1}) + inv(w_{2}) + (k + 1)(n − k).

Taking reciprocal polynomials of both sides of (4.6) and writing

C_{q}(n) = q^{\binom{n}{2}}C̃_{q^{−1}}(n)  (4.7)

yields the recurrence [5]

C_{q}(n + 1) = ∑_{k=0}^{n} q^{k}C_{q}(k)C_{q}(n − k),  C_{q}(0) = 1.  (4.8)

If one defines the generating function

f(x) = ∑_{n⩾0}C_{q}(n)x^{n},  (4.9)

then (4.8) is equivalent to the functional equation [3, 5]

f(x) = 1 + xf(x)f(qx),  (4.10)

which generalizes (4.4).

Theorem 4.1. For all n ∈ ℕ,

C_{−1}(n) = \begin{cases}δ_{n,0}, & if n is even; \\ (−1)^{\frac{n−1}{2}} c_{\frac{n−1}{2}} , & if n is odd. \end{cases}  (4.11)

Proof. Setting q = −1 in (4.10) gives

f(x) = 1 + xf(x)f(−x).  (4.12)

Putting −x for x in (4.12), solving the resulting system in f(x) and f(−x), and noting f(0) = 1 yields

\begin{aligned}f(x) & = ∑_{n⩾0}C_{−1}(n)x^{n} \\ & = \frac{(2x − 1) + \sqrt{4x^{2} + 1}}{2x} = 1 + ∑_{n⩾1}(−1)^{n−1} \frac{1}{n}\binom{2n − 2}{n − 1}x^{2n−1}, \end{aligned}

which implies (4.11).

Alternatively, note that

C_{−1}(n) = (−1)^{\binom{n}{2}} ∑_{w∈C_{n}}(−1)^{inv(w)},

by (4.5) and (4.7). So (4.11) is equivalent to

∑_{w∈C_{n}}(−1)^{inv(w)} = \begin{cases}δ_{n,0}, & if n is even; \\ c_{\frac{n−1}{2}} , & if n is odd. \end{cases}  (4.13)

To prove (4.13), let C_{n}^{+}, C_{n}^{−} ⊆ C_{n} consist of the Catalan words with even or odd inv values, respectively, and C_{n}^{∗} ⊆ C_{n} consist of those words w = w_{1}w_{2} ⋯ w_{2n} for which

w_{2i}w_{2i+1} = 00 or 11,  1 ⩽ i ⩽ n − 1.  (4.14)

Clearly, C_{n}^{∗} ⊆ C_{n}^{+} with cardinality matching the right-hand side of (4.13). Suppose w ∈ C_{n} − C_{n}^{∗} and that i_{0} is the smallest index for which (4.14) fails to hold. Switch w_{2i_{0}} and w_{2i_{0}+1} in w. The resulting map is a parity changing involution of C_{n} − C_{n}^{∗}, which proves (4.13) and hence (4.11).

Another q-Catalan number arises as the generating function for the major index statistic on C_{n} [8]. If

c̃_{q}(n) := ∑_{w∈C_{n}} q^{maj (w)},  (4.15)

then there is the closed form (see [5], [8, p. 215])

c̃_{q}(n) = \frac{1}{(n + 1)_{q}} \binom{2n}{n}_{q},  ∀n ∈ ℕ,  (4.16)

which generalizes (4.1).

Theorem 4.2. For all n ∈ ℕ,

c̃_{−1}(n) = \binom{n}{⌊n/2⌋}.  (4.17)

Proof. If n is even, then by (4.16),

c̃_{−1}(n) = lim_{q→−1} c̃_{q}(n) = lim_{q→−1} \frac{1}{(n + 1)_{q}} ∏_{i=0}^{n−1} \frac{(2n − i)_{q}}{(n − i)_{q}}

= ∏_{\begin{matrix}i=0 \\ i even \end{matrix}}^{n−2} lim_{q→−1} (\frac{q^{2n−i} − 1}{q^{n−i} − 1}) = ∏_{\begin{matrix}i=0 \\ i even \end{matrix}}^{n−2} \frac{2n − i}{n − i} = ∏_{\begin{matrix}i=0 \\ i even \end{matrix}}^{n−2} \frac{n − i/2}{n/2 − i/2} = \binom{n}{n/2},

with the odd case handled similarly.

Alternatively, let C_{n}^{+}, C_{n}^{−} ⊆ C_{n} consist of the Catalan words with even or odd major index value, respectively, and C_{n}^{∗} ⊆ C_{n} consist of those words w = w_{1}w_{2} ⋯ w_{2n} which satisfy the following two requirements:

(i) one can express w as w = x_{1}x_{2} ⋯ x_{n}, where x_{i} = 00, 11, or 01, 1 ⩽ i ⩽ n;

(ii) for each i, x_{i} = 01 only if the number of 00’s in the initial segment x_{1}x_{2} ⋯ x_{i−1} equals the number of 11’s. (A word in C_{n}^{∗} may start with either 01 or 00.)

Clearly, C_{n}^{∗} ⊆ C_{n}^{+} and below it is shown that |C_{n}^{∗}| = \binom{n}{⌊n/2⌋}. Suppose w = w_{1}w_{2} ⋯ w_{2n} ∈ C_{n} − C_{n}^{∗} and that i_{0} is the smallest integer i, 1 ⩽ i ⩽ n, such that one of the following two conditions holds:

(i) w_{2i−1}w_{2i} = 10, or

(ii) w_{2i−1}w_{2i} = 01 and the number of 0’s in the initial segment w_{1}w_{2} ⋯ w_{2i−2} is strictly greater than the number of 1’s.

Switching w_{2i_{0}−1} and w_{2i_{0}} in w changes the major index by an odd amount and the resulting map is a parity changing involution of C_{n} − C_{n}^{∗}.

We now show |C_{n}^{∗}| = \binom{n}{⌊n/2⌋} by defining a bijection between C_{n}^{∗} and the set Λ(n) of (minimal) lattice paths from (0, 0) to (⌊n/2⌋, n − ⌊n/2⌋). Given w = x_{1}x_{2} ⋯ x_{n} ∈ C_{n}^{∗} as described in (i) and (ii) above, we construct a lattice path λ_{w} ∈ Λ(n) as follows. Let j_{1} < j_{2} < … be the set of indices j, possibly empty and denoted S(w), for which x_{j} = 01, with j_{0} := 0. For s ⩾ 1, let step j_{s} in λ_{w} be a V (vertical step) if s is odd and an H (horizontal step) if s is even.

Suppose now i ∈ [n] − S(w) and that t, t ⩾ 0, is the greatest integer such that j_{t} < i. If t is even, put a V (resp., H) for the i^{th} step of λ_{w} if x_{i} = 11 (resp., 00). If t is odd, put a V (resp., H) for the i^{th} step of λ_{w} if x_{i} = 00 (resp., 11), which now specifies λ_{w} completely. The map w ↦ λ_{w} is seen to be a bijection between C_{n}^{∗} and Λ(n); note that S(w) corresponds to the steps of λ_{w} in which it either rises above the line y = x or returns to y = x from above.

Note that the preceding supplies a combinatorial proof of the congruence \frac{1}{n+1} \binom{2n}{n} ≡ \binom{n}{⌊n/2⌋} (mod 2) for n ∈ ℕ since off of a set of cardinality \binom{n}{⌊n/2⌋}, each Catalan word w ∈ C_{n} is paired with another of opposite maj -parity.

Let P_{n} ⊆ S_{n} consist of those permutations σ = σ_{1}σ_{2} ⋯ σ_{n} avoiding the pattern 312, i.e., there are no indices i < j < k such that σ_{j} < σ_{k} < σ_{i} (termed Catalan permutations).

Knuth [7, p. 238] describes a bijection g between P_{n} and C_{n} in which

inv(σ) = \binom{n}{2} − inv(g(σ)), ∀σ ∈ P_{n},

and hence

C_{q}(n) := ∑_{w∈C_{n}} q^{\binom{n}{2}−inv(w)} = ∑_{σ∈P_{n}} q^{inv(σ)}.  (4.18)

By (4.11) and (4.18), we then have the parity result

∑_{σ∈P_{n}}(−1)^{inv(σ)} = \begin{cases}δ_{n,0}, & if n is even; \\ (−1)^{\frac{n−1}{2}} c_{\frac{n−1}{2}} , & if n is odd. \end{cases}  (4.19)

The composite map g^{−1} ∘ h ∘ g, where h is the involution establishing (4.13), furnishes an appropriate involution for (4.19).

References

[1] G. Andrews, The theory of partitions, Encyclopedia of Mathematics and Applications, Vol. II, Addison-Wesley (1976).

[2] L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University (1968), 1–7.

[3] L. Carlitz and R. Scoville, A note on weighted sequences, Fib. Quart. 13 (1975), 303–306.

[4] P. Edelman, R. Simion, and D. White, Partition statistics on permutations, Discrete Math. 99 (1992), 63–68.

[5] J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory, Ser. A, 40 (1985), 248–264.

[6] A. Garsia and J. Remmel, A combinatorial interpretation of q-derangement and q-Laguerre numbers, Europ. J. Combinatorics 1 (1980), 47–59.

[7] D. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. I, Addison-Wesley (1968).

[8] P. MacMahon, Combinatorial Analysis, Vol. II, Cambridge Univ. Press, 1915–1916. Reprinted, Chelsea, New York, 1960.

[9] M. Shattuck, Bijective proofs of parity theorems for partition statistics, J. Integer Seq. 8 (2005), Art. 5.1.5.

[10] M. Shattuck and C. Wagner, Parity theorems for statistics on lattice paths and Laguerre configurations, Research Report, Department of Mathematics, University of Tennessee (2004).

[11] M. Shattuck and C. Wagner, Parity theorems for statistics on domino arrangements, Elect. J. Combin., to appear.

[12] R. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, 1986.

[13] C. Wagner, Partition statistics and q-Bell numbers (q = −1), J. Integer Seq. 7 (2004), Art. 4.1.1.