Bijective Proofs of Parity Theorems for Partition Statistics

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

                     shattuck@math.utk.edu

Abstract

We give bijective proofs of parity theorems for four related statistics on partitions of finite sets. A consequence of our results is a combinatorial proof of a congruence between Stirling numbers and binomial coefficients.

1 Introduction

The notational conventions of this paper are as follows: ℕ := {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 binomial coefficient \binom{n}{k} is equal to zero if k is a negative integer or if 0 ⩽ n < k.

Let Π(n, k) denote the set of all partitions of [n] with k blocks and Π(n) the set of all partitions of [n]. Associate to each π ∈ Π(n, k) the ordered partition (E_{1}, …, E_{k}) of [n] comprising the same blocks as π, arranged in increasing order of their smallest elements, and define statistics w̃, ŵ, w^{∗}, and w by

w̃(π) := ∑_{i=1}^{k}(i − 1)(|E_{i}| − 1),  (1.1)

ŵ(π) := ∑_{i=1}^{k} i(|E_{i}| − 1) = w̃(π) + n − k,  (1.2)

w^{∗}(π) := ∑_{i=1}^{k} i|E_{i}| = w̃(π) + n + \binom{k}{2},  (1.3)

and

w(π) := ∑_{i=1}^{k}(i − 1)|E_{i}| = w̃(π) + \binom{k}{2}.  (1.4)

Consider the generating functions (see [1], [3], [5], and [6])

S̃_{q}(n, k) := ∑_{π∈Π(n,k)} q^{w̃(π)},  (1.5)
Ŝ_{q}(n, k) := ∑_{π∈Π(n,k)} q^{ŵ(π)} = q^{n−k}S̃_{q}(n, k),  (1.6)
S_{q}^{∗}(n, k) := ∑_{π∈Π(n,k)} q^{w^{∗}(π)} = q^{\binom{k}{2}+n}S̃_{q}(n, k),  (1.7)

and

S_{q}(n, k) := ∑_{π∈Π(n,k)} q^{w(π)} = q^{\binom{k}{2}}S̃_{q}(n, k).  (1.8)

Summing the q-Stirling numbers S̃_{q}(n, k), Ŝ_{q}(n, k), S_{q}^{∗}(n, k), and S_{q}(n, k) over k yields the respective q-Bell numbers B̃_{q}(n), B̂_{q}(n), B_{q}^{∗}(n), and B_{q}(n). These polynomials reduce to the classical Stirling and Bell numbers when q = 1. Wagner [7] evaluates the foregoing polynomials when q = −1 using algebraic techniques and raises the question of finding bijective proofs.

We now describe a combinatorial method for evaluating these polynomials when q = −1. More generally, let Δ be a finite set of discrete structures and I : Δ → ℕ, with generating function

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

Of course, G(I, Δ; 1) = |Δ|. If Δ_{i} := {δ ∈ Δ : I(δ) ≡ i (mod 2)}, then G(I, Δ; −1) = |Δ_{0}| − |Δ_{1}|. Our strategy for finding G(I, Δ; −1) will be to identify a subset Δ^{∗} of Δ contained completely within Δ_{0} or Δ_{1} and then to define an I-parity changing involution on Δ − Δ^{∗}. The subset Δ^{∗} thus captures both the sign and magnitude of G(I, Δ; −1). In the present setting, Δ will either be Π(n) or Π(n, k) and I, one of the aforementioned partition statistics.

In § 2, we give bijective proofs establishing B̃_{q}(n) and B̂_{q}(n) as well as the four q-Stirling numbers when q = −1. In § 3, a bijection yielding B_{−1}^{∗}(n) and B_{−1}(n) is given. A consequence of our results is a combinatorial proof requested by Stanley of the congruence [4, p. 46]

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

where S(n, k) = |π(n, k)| denotes the Stirling number of the second kind.

2 The First Bijection

Throughout, we’ll represent π ∈ Π(n) by (E_{1}, E_{2}, …), the unique ordered partition of [n] comprising the same blocks as π, arranged in increasing order of their smallest elements. Let F_{0} = F_{1} = 1, with F_{n} = F_{n−1} + F_{n−2} if n ⩾ 2.

Theorem 2.1. For all n ∈ ℕ,

B̃_{−1}(n) := ∑_{k=0}^{n} S̃_{−1}(n, k) = F_{n}.  (2.1)

Proof. Let Π_{i}(n) := {π ∈ Π(n) : w̃(π) ≡ i (mod 2)} so that B̃_{−1}(n) = |Π_{0}(n)| − |Π_{1}(n)|. To prove (2.1), we’ll identify a subset Π̃(n) of Π_{0}(n) such that |Π̃(n)| = F_{n} along with a w̃-parity changing involution of Π(n) − Π̃(n).

The set Π̃(n) consists of those partitions π = (E_{1}, E_{2}, …) whose blocks satisfy the two conditions:

each block of odd index comprises a set of consecutive integers;  (2.2a)
each block of even index is a singleton.  (2.2b)

Now |Π̃(n)| = F_{n}, as |Π̃(n)| is seen to satisfy the Fibonacci recurrence, upon considering whether or not {n} is a block. For if {n} is not a block and n−2 belongs to an odd-numbered (respectively, even-numbered) block of π ∈ Π̃(n), then {n − 1, n} constitutes a proper subset of (respectively, all of) the last block of π.

Suppose now that π = (E_{1}, E_{2}, …) belongs to Π(n) − Π̃(n) and that i_{0} is the smallest of the integers i for which E_{2i−1} fails to satisfy (2.2a) or E_{2i} fails to satisfy (2.2b). Let M be the largest member of E_{2i_{0}−1} ∪ E_{2i_{0}}. If M belongs to E_{2i_{0}−1}, move it to E_{2i_{0}}, while if M belongs to E_{2i_{0}}, move it to E_{2i_{0}−1} (note that if |E_{2i_{0}}| = 1, then necessarily M ∈ E_{2i_{0}−1}). The resulting map is a parity changing involution of Π(n) − Π̃(n).

Below, we illustrate the fixed point set Π̃(n) and the pairings of Π(n)−Π̃(n) when n = 4, wherein the first two members of each row are paired.

Π_{0}(n) − Π̃(n)  Π_{1}(n)  Π̃(n)
{1, 2, 4}, {3}  {1, 2}, {3, 4}  {1, 2, 3, 4}
{1, 3, 4}, {2}  {1, 3}, {2, 4}  {1, 2, 3}, {4}
{1}, {2, 3, 4}  {1, 4}, {2, 3}  {1}, {2}, {3, 4}
{1, 3}, {2}, {4}  {1}, {2, 3}, {4}  {1, 2}, {3}, {4}
{1, 4}, {2}, {3}  {1}, {2, 4}, {3}  {1}, {2}, {3}, {4}

Note that the above bijection preserves the number of blocks of π ∈ Π(n). We’ll use its restriction to Π(n, k) to prove

Theorem 2.2. For all n ∈ ℕ,

S̃_{−1}(n, k) = \binom{n − ⌊k/2⌋ − 1}{n − k},  0 ⩽ k ⩽ n.  (2.3)

Proof. Let Π_{i}(n, k) := Π_{i}(n) ∩ Π(n, k) for i = 0, 1, Π̃(n, k) := Π̃(n) ∩ Π(n, k), and π = (E_{1}, …, E_{k}) ∈ Π̃(n, k). If k is even, identify each pair of blocks (E_{2i−1}, E_{2i}), 1 ⩽ i ⩽ k/2, with summands x_{i} in a composition x_{1} + ⋯ + x_{k/2} = n, where each x_{i} ⩾ 2. If k is odd, identify (E_{1}, E_{2}), …, (E_{k−2}, E_{k−1}), (E_{k}) with summands x_{i} in x_{1} + ⋯ + x_{(k+1)/2} = n where x_{i} ⩾ 2 for 1 ⩽ i ⩽ \frac{k−1}{2} and x_{(k+1)/2} ⩾ 1. The cardinality of Π̃(n, k) is then given by the right hand side of (2.3), and the restriction of the prior bijection to Π(n, k) − Π̃(n, k) is again an involution, and inherits the parity changing property, which proves (2.3).

From (2.3) along with (1.6), (1.7), and (1.8), we have

Ŝ_{−1}(n, k) = (−1)^{n−k}\binom{n − ⌊k/2⌋ − 1}{n − k},  0 ⩽ k ⩽ n,  (2.4)
S_{−1}^{∗}(n, k) = (−1)^{\binom{k}{2}+n}\binom{n − ⌊k/2⌋ − 1}{n − k},  0 ⩽ k ⩽ n,  (2.5)

and

S_{−1}(n, k) = (−1)^{\binom{k}{2}}\binom{n − ⌊k/2⌋ − 1}{n − k},  0 ⩽ k ⩽ n.  (2.6)

The bijection establishing (2.3) clearly applies to (2.4)–(2.6) as well.

Let S(n, k) = |Π(n, k)| denote the Stirling number of the second kind. The bijection of Theorem 2.2 also proves combinatorially that

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

since off of a set of cardinality \binom{n−⌊k/2⌋−1}{n−k}, each partition π ∈ Π(n, k) is paired with another of opposite w̃-parity. This furnishes an answer to a question raised by Stanley [4, p. 46].

Let F_{−3} = −1, F_{−2} = 1, and F_{−1} = 0. We conclude this section by proving

Theorem 2.3. For all n ∈ ℕ,

B̂_{−1}(n) := ∑_{k=0}^{n} Ŝ_{−1}(n, k) = (−1)^{n−1}F_{n−3}.  (2.8)

Proof. Let n ⩾ 3, Π̃(n) be as in the proof of Theorem 2.1, and Π̂(n) ⊆ Π̃(n) consist of those partitions with an odd number of blocks and whose last block is a singleton. First, |Π̂(n)| = |Π̃(n − 3)| = F_{n−3} as the removal of n − 2, n − 1, and n from π ∈ Π̂(n) is seen to be a bijection between Π̂(n) and Π̃(n − 3). Since ŵ(π) = w̃(π) + n − k and since every π ∈ Π̂(n) has an even w̃(π) value and an odd number of blocks, the ŵ-parity of each π ∈ Π̂(n) is opposite the parity of n. Thus, Π̂(n) agrees with the right hand side of (2.8) in both sign and magnitude.

The w̃-parity changing involution of Theorem 2.1 defined on Π(n) − Π̃(n) also changes the ŵ-parity. We now extend this involution to Π(n) − Π̂(n) as follows: if the last block of π ∈ Π̃(n) − Π̂(n) is {n}, merge it with the penultimate block; if the last block is not a singleton, take n from this block and form the singleton {n}. The resulting extension is a ŵ-parity changing involution of Π(n) − Π̂(n).

3 A Second Bijection

The Bell numbers B_{−1}^{∗}(n) are quite different from the numbers B̃_{−1}(n) and B̂_{−1}(n), as demonstrated by the following theorem.

Theorem 3.1. For all n ∈ ℕ,

B_{−1}^{∗}(n) := ∑_{k=0}^{n} S_{−1}^{∗}(n, k) = \begin{cases}1, & if n ≡ 0 (mod 3); \\ −1, & if n ≡ 1 (mod 3); \\ 0, & if n ≡ 2 (mod 3). \end{cases}  (3.1)

Proof. Let Π_{i}(n) := {π ∈ Π(n) : w^{∗}(π) ≡ i (mod 2)} and Π^{∗}(n) consist of those partitions π = (E_{1}, E_{2}, …) whose blocks satisfy

E_{2i−1} = {3i − 2, 3i − 1}, E_{2i} = {3i} for 1 ⩽ i ⩽ ⌊n/3⌋.  (3.2)

Then Π^{∗}(n) is a singleton contained in Π_{0}(n) if n ≡ 0 (mod 3) or contained in Π_{1}(n) if n ≡ 1 (mod 3). If n ≡ 2 (mod 3), Π^{∗}(n) is a doubleton containing two partitions of opposite w^{∗}- parity, which we pair.

Suppose now that π = (E_{1}, E_{2}, …) ∈ Π(n) − Π^{∗}(n) and that i_{0} is the smallest index for which condition (3.2) fails to hold. Let n_{1} = 3i_{0} − 2, n_{2} = 3i_{0} − 1, n_{3} = 3i_{0} and V_{1} = E_{2i_{0}−1}, V_{2} = E_{2i_{0}}, V_{3} = E_{2i_{0}+1} (the latter two if they occur). Consider the following four disjoint cases concerning the relative positions of the n_{i} within the V_{i}:

(I) n_{2} ∈ V_{2}, n_{3} ∈ V_{3}, and |V_{2} ∪ V_{3}| ⩾ 3;

(II) Either (a) or (b) holds where (a) V_{2} = {n_{2}} and V_{3} = {n_{3}},
(b) n_{2}, n_{3} ∈ V_{1};
(III) n_{2} ∈ V_{2} and n_{3} ∈ V_{1} ∪ V_{2};
(IV) n_{2} ∈ V_{1}, n_{3} ∈ V_{2}, and |V_{1} ∪ V_{2}| ⩾ 4.

Within each case, we pair partitions of opposite parity as shown below, leaving the other blocks undisturbed:

(i) V_{2} = {n_{2}, …, M}, V_{3} = {n_{3}, … } ↔ V_{2} = {n_{2}, … }, V_{3} = {n_{3}, …, M}, where M is the largest member of V_{2} ∪ V_{3};

(ii) V_{1} = {n_{1}, … }, V_{2} = {n_{2}}, V_{3} = {n_{3}} ↔ V_{1} = {n_{1}, n_{2}, n_{3}, … };
(iii) V_{1} = {n_{1}, n_{3}, … }, V_{2} = {n_{2}, … } ↔ V_{1} = {n_{1}, … }, V_{2} = {n_{2}, n_{3}, … };
(iv) V_{1} = {n_{1}, n_{2}, …, N}, V_{2} = {n_{3}, … } ↔ V_{1} = {n_{1}, n_{2}, … }, V_{2} = {n_{3}, …, N},

where N is the largest member of V_{1} ∪ V_{2}.

The resulting map is a parity changing involution of Π(n) − Π^{∗}(n), which implies (3.1).

Below, we illustrate the fixed point set Π^{∗}(n) along with the pairings of Π(n) − Π^{∗}(n) when n = 4.

Π_{0}(n)  Π_{1}(n) − Π^{∗}(n)  Π^{∗}(n)

{1, 2, 3, 4}  {1, 4}, {2}, {3}  {1, 2}, {3}, {4}
{1, 2}, {3, 4}  {1, 2, 4}, {3}
{1, 3}, {2, 4}  {1}, {2, 3, 4}
{1, 4}, {2, 3}  {1, 3, 4}, {2}
{1}, {2, 3}, {4}  {1, 3}, {2}, {4}
{1}, {2, 4}, {3}  {1}, {2}, {3, 4}
{1}, {2}, {3}, {4}  {1, 2, 3}, {4}

Note that the bijection above, like the one used for Theorem 2.3, does not always preserve the number of blocks and hence has no meaningful restriction to Π(n, k), unlike the bijection of Theorem 2.1.

Remark. In [2], Ehrlich evaluates σ(n) := − ∑_{π∈Π(n)}(−1)^{α(π)}, where α(π) := ∑_{i odd} |E_{i}| for π = (E_{1}, E_{2}, …) ∈ Π(n). The bijection of Theorem 3.1 establishing B_{−1}^{∗}(n) also provides an alternative to Ehrlich’s iterative argument establishing his σ(n) since

σ(n) = − ∑_{π=(E_{1},E_{2},...)∈Π(n)}(−1)^{|E_{1}|+|E_{3}|+|E_{5}|+···}

= − ∑_{π=(E_{1},E_{2},...)∈Π(n)}(−1)^{|E_{1}|+2|E_{2}|+3|E_{3}|+···}

= −B_{−1}^{∗}(n).

Since S_{q}(n, k) = q^{−n}S_{q}^{∗}(n, k),

B_{−1}(n) := ∑_{k=0}^{n} S_{−1}(n, k) = (−1)^{n}B_{−1}^{∗}(n),

and so by (3.1),

B_{−1}(n) = \begin{cases}(−1)^{n}, & if n ≡ 0 (mod 3); \\ (−1)^{n+1}, & if n ≡ 1 (mod 3); \\ 0, & if n ≡ 2 (mod 3), \end{cases}  (3.3)

with the above bijection clearly showing this. The preceding also supplies a combinatorial proof that B(n), the n^{th} Bell number, is even if and only if n ≡ 2 (mod 3) since every partition of [n] is paired with another of opposite w^{∗}-parity when n ≡ 2 (mod 3) and since all partitions are so paired except for one otherwise (cf. Ehrlich [2, p. 512]).

4 Acknowledgments

The author would like to thank Professor Donald Knuth for calling Ehrlich’s paper to his attention.

References

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

[2] G. Ehrlich, Loopless algorithms for generating permutations, combinations, and other combinatorial configurations, J. ACM 20 (1973), 500–513.

[3] S. Milne, A q-analogue of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc. 245 (1978), 89–118.

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

[5] M. Wachs and D. White, p, q-Stirling numbers and partition statistics, J. Combin. Theory A 56 (1991), 27–46.

[6] C. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199–218.

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

2000 Mathematics Subject Classification: Primary 11B73; Secondary 11B39. Keywords: partition statistics, q-Stirling numbers, q-Bell numbers, Fibonacci numbers.

(Concerned with sequence \underline{A000045}.)

Received May 6 2004; revised version received January 17 2005. Published in Journal of Integer Sequences, January 17 2005.

Return to Journal of Integer Sequences home page.