Lecture Hall Partitions

Mireille Bousquet-Mélou ^{∗}

LaBRI, Université Bordeaux 1 351 cours de la Libération 33405 Talence Cedex, FRANCE bousquet@labri.u-bordeaux.fr

Kimmo Eriksson ^{†}

Dept. of Mathematics Stockholm University S-106 91 Stockholm, SWEDEN kimmo@nada.kth.se

Abstract

We prove a finite version of the well-known theorem that says that the number of partitions of an integer N into distinct parts is equal to the number of partitions of N into odd parts. Our version says that the number of “lecture hall partitions of length n” of N equals the number of partitions of N into small odd parts: 1, 3, 5, …, 2n − 1. We give two proofs: one via Bott’s formula for the Poincaré series of the affine Coxeter group C̃_{n}, and one direct proof.

1 Introduction

Let D be the set of integer partitions with distinct parts, and let O be the set of integer partitions with odd parts. It is well-known, since Euler, that the generating function for the elements of D is equal to the generating function for the elements of O:

∑_{μ∈D} q^{|μ|} = ∏_{i≥1}(1 + q^{i}) = ∏_{i≥1} \frac{1 − q^{2i}}{1 − q^{i}} = ∏_{i≥0} \frac{1}{1 − q^{2i+1}} = ∑_{μ∈O} q^{|μ|},  (1)

where the weight |μ| of a partition μ = (μ_{1}, …, μ_{m}) is μ_{1} + ⋯ + μ_{m}. In other words, partitions with distinct parts are equinumerous with partitions with odd parts. One can wonder whether there exists a “finite version” of this result: is there an interpretation of ∏_{0≤i≤n−1}(1 − q^{2i+1})^{−1} in terms of partitions having distinct parts?

For n ≥ 1, let L_{n} be the following set of partitions (having possibly some empty parts):

L_{n} = \{(λ_{1}, …, λ_{n}) : 0 ≤ \frac{λ_{1}}{1} ≤ \frac{λ_{2}}{2} ≤ … ≤ \frac{λ_{n}}{n} \} .

We call the members of L_{n} lecture hall partitions of length n, since they describe all possible ways of designing a lecture hall with space for up to n rows of seats placed on integer heights, such that at every seat there is a clear view of the speaker without obstruction from the seats in front (Figure 1).

Removing the empty parts puts L_{n} in one-to-one correspondence with the following subset of D:

D_{n} = \{(μ_{1}, μ_{2}, …, μ_{m}) ∈ D : m ≤ n and \frac{μ_{1}}{n − m + 1} ≤ \frac{μ_{2}}{n − m + 2} ≤ … ≤ \frac{μ_{m}}{n} \} .

We will prove the following remarkable theorem.

∗Partially supported by EC grant CHRX-CT93-0400 and PRC “Mathématiques et Informatique”.

†Partially supported by EC grant CHRX-CT93-0400 and by postdoc grants from NFR and Wenner-Gren Stiftelsen.

[figure: 1; 2; 4; 6]

Figure 1: The design of a lecture hall of four rows corresponding to the lecture hall partition (1, 2, 4, 6).

Theorem 1.1 (Lecture Hall Theorem) The generating function for lecture hall partitions of length n is

∑_{λ∈L_{n}} q^{|λ|} = ∏_{i=0}^{n−1} \frac{1}{1 − q^{2i+1}} .

Equivalently, the generating function for the partitions of D_{n} is ∏_{0≤i≤n−1}(1 − q^{2i+1})^{−1}. Observe that D_{n} ⊂ D_{n+1} and D = lim D_{n}, so in the limit this theorem yields the familiar identity (1).

We will in fact prove a refinement of the Lecture Hall Theorem. We define the even and odd weights |λ|_{e} and |λ|_{o} of a partition λ = (λ_{1}, …, λ_{n}) by

|λ|_{e} = ∑_{0≤k≤⌊(n−1)/2⌋} λ_{n−2k}  and |λ|_{o} = ∑_{0≤k≤⌊n/2⌋−1} λ_{n−2k−1}.

Of course, |λ| = |λ|_{o} + |λ|_{e}. In section 3 we will prove the bivariate identity

∑_{λ∈L_{n}} x^{|λ|_{e}}y^{|λ|_{o}} = ∏_{i=0}^{n−1} \frac{1}{1 − x^{i+1}y^{i}} .  (2)

Setting q = x = y in this identity gives the Lecture Hall Theorem. By instead setting x = tq and y = t^{−1}q we obtain the following alternative form of (2):

∑_{λ∈L_{n}} t^{|λ|_{e}−|λ|_{o}}q^{|λ|} = ∏_{i=0}^{n−1} \frac{1}{1 − tq^{2i+1}} .

If we introduce the new statistic s(λ) = |λ|_{e} − |λ|_{o} and take the limit when n tends to infinity, we obtain a refined version of Euler’s identity:

∑_{μ∈D} t^{s(λ)}q^{|μ|} = ∑_{μ∈O} t^{ℓ(μ)}q^{|μ|},

where ℓ(μ) stands for the length (the number of parts) of the partition μ.

Returning to the lecture hall partitions, it is obvious that the conditions on the parts can be restated on the form \frac{λ_{i+1}}{λ_{i}} ≥ \frac{i+1}{i} if λ_{i} ≠ 0. To our knowledge, Theorem 1.1 is the first enumerative result concerning partitions that involves conditions on the quotient of two consecutive parts, although enumerating partitions is a very classical topic (see Andrews’s book [1], where some other refinements of Euler’s theorem are discussed). In a sequel to this paper [3] we will discuss generalizations to other sets of partitions of the form

\{(λ_{1}, λ_{2}, …, λ_{n}) : 0 ≤ \frac{λ_{1}}{a_{1}} ≤ \frac{λ_{2}}{a_{2}} ≤ … ≤ \frac{λ_{n}}{a_{n}} \}

where (a_{1}, …, a_{n}) is a given sequence of integers.

We will now presume some familiarity with Coxeter group theory (see Humphreys’s book [6]), and in particular with the finite group C_{n}: [figure: …; 4]and the affine Coxeter group C̃_{n}: [figure: …; 4; 4]. By the Poincaré series of these groups one means the length generating functions,

C_{n}(q) = ∑_{π∈C_{n}} q^{ℓ(π)}  and  C̃_{n}(q) = ∑_{π∈_{C_{n}}} q^{ℓ(π)}.

Bott [2] gave, as an application of Morse theory to the topology of Lie groups, a general formula for the Poincaré series of the affine groups in terms of the Poincaré series of the finite groups and their “exponents”. For C̃_{n} this takes the following form.

Theorem 1.2 (Bott’s Formula, 1956) The Poincaré series of C̃_{n} is

C̃_{n}(q) = \frac{C_{n}(q)}{(1 − q)(1 − q^{3}) … (1 − q^{2n−1})}.

Observe the similarity between the denominator and the generating function in the Lecture Hall Theorem. In section 2 we will give a combinatorial argument for the equivalence between these two theorems. In section 3 we give a direct, bijective-type proof of the refined version (2) of the Lecture Hall Theorem. Combining these two results we thus obtain a combinatorial proof of Bott’s formula for C̃_{n}.

2 Bott’s Formula for C̃_{n} and the Lecture Hall Theorem

The affine Coxeter group C̃_{n} can be represented by infinite permutations on ZZ as follows (see H. Eriksson’s thesis [4], or H. Eriksson and K. Eriksson [5]). Start with the real line and erect mirrors at positions x = 0 and x = n + 1. Let s_{0} be the infinite set of transpositions generated by mirror images of the transposition (−1, 1). Similarly, let s_{n} be the set of all mirror images of the transposition (n, n + 2), and for i between 1 and n − 1, let s_{i} be the set of all mirror images of (i, i + 1). Now C̃_{n} is the group of infinite permutations generated by S = {s_{0}, s_{1}, …, s_{n}}. Such an infinite permutation π will be thought of as a rearrangement of ZZ written from left to right, … π(−2)π(−1)π(0)π(1)π(2) …, satisfying the two mirror conditions π(−m) = −π(m) and π(n + 1 − m) = −π(n + 1 + m) for all integers m. Note that the mirror conditions together imply the translative property π(i + 2n + 2) = π(i) + 2n + 2 for all i.

[figure: s_{1}; s_{1}; s_{1}; s_{1}; s_{1}; s_{1}; s_{0}; s_{0}; s_{0}; s_{4}; s_{4}]
Figure 2: The actions of s_{0}, s_{1}, s_{4} ∈ C̃_{4} as transpositions on ZZ.

We will henceforth regard as mirrors also all mirror images of mirrors, that is, the positions k(n + 1) for integers k. A window is the set of positions between two adjacent mirrors. We will frequently refer to the class

⟨i⟩ = {i + k(2n + 2), −i + k(2n + 2) : k ∈ ZZ}

of all mirror images of a non-mirror number i. An inversion in a permutation π is an unordered pair {i, j} of non-mirror numbers such that i < j but i is to the right of j in π (that is, π^{−1}(i) > π^{−1}(j)). A class inversion is the set of all mirror images of an inversion {i, j},

{{i + k(2n + 2), j + k(2n + 2)}, {−i + k(2n + 2), −j + k(2n + 2)} : k ∈ ZZ} ,

and all these mirror images are also inversions. It is proved in [5] that the length of an element of C̃_{n} is the number of its class inversions. Every class inversion can in a unique way be seen as the set of mirror images of an inversion {i, j′} where 1 ≤ j ≤ i ≤ n and j′ is a member of ⟨j⟩, and we refer to it as an (i, ⟨j⟩)-class inversion. Thus, the length of an infinite permutation π ∈ C̃_{n} is

ℓ(π) = ∑_{i=1}^{n} ∑_{j=1}^{i} I_{i,j}(π),

where I_{i,j}(π) is the number of (i, ⟨j⟩)-class inversions.

The finite group C_{n} is embedded in C̃_{n} as the subgroup of permutations such that there is no inversion between any member of {−n, …, 0, …, n} and any member of the complement of this set. The parabolic quotient C̃_{n}/C_{n} can be viewed as the subset of permutations in C̃_{n} such that the numbers −n, …, 0, …, n appear in that order in π from left to right. Then every permutation π in C̃_{n} has a unique factorization as π_{1} ∘ π_{2} where π_{1} ∈ C̃_{n}/C_{n} and π_{2} ∈ C_{n}, and its length is simply ℓ(π) = ℓ(π_{1}) + ℓ(π_{2}); cf. Humphreys [6, p. 123]. Thus, Bott’s Formula is equivalent to

∑_{π∈_{C_{n}}/C_{n}} q^{ℓ(π)} = \frac{1}{(1 − q)(1 − q^{3}) … (1 − q^{2n−1})}.  (3)

In order to show that Bott’s Formula is equivalent to the Lecture Hall Theorem, it is therefore sufficient to find a bijection λ from C̃_{n}/C_{n} to the set L_{n} of lecture hall partitions of length n, such that ℓ(π) = |λ(π)|. Our candidate will be the n-tuple λ(π) = (λ_{1}, …, λ_{n}) defined by

λ_{i} = ∑_{j=1}^{i} I_{i,j}(π).

Clearly we have ℓ(π) = λ_{1} + … + λ_{n} = |λ(π)|.

Proposition 2.1 The correspondence λ is a bijection from C̃_{n}/C_{n} to the set L_{n} of lecture hall partitions of length n.

The proposition will follow easily once we have the lemma below. In the proof we will tacitly use the fact that in an infinite permutation in C̃_{n}/C_{n}, every j = 1, 2, …, n lies to the right of the mirror at zero, hence −j lies to the left of zero, and therefore, thanks to the translative property, all members of the class ⟨j⟩ that lie to the right of j in this permutation must be greater than j (and hence in fact be greater than n).

Lemma 2.2 Given π ∈ C̃_{n}/C_{n} and 1 ≤ j < i ≤ n, the inversion count I_{i,j}(π) satisfies:

(a) I_{i,j} ≥ I_{i−1,j}, with equality if i lies directly to the right of i − 1 in π; and

(b) If the member of ⟨j⟩ in the window of π containing i is to the left of i then I_{i,j} = I_{i,i} must hold, and otherwise I_{i,j} = I_{i,i} − 1.

Proof. (a) If i lies directly to the right of i − 1 in π, then i and i − 1 must have equally many inversions with members of ⟨j⟩ for any j < i. If i lies further to the right of i − 1, it can only have more such inversions (one with every member of ⟨j⟩ that lies between i − 1 and i).

(b) If in fact i and j lie in the same window it follows that also in all other windows the members of ⟨i⟩ and ⟨j⟩ differ by i − j < n and hence either both are greater than i or both are less than j. Thus the equality I_{i,j} = I_{i,i} holds in this case. Now consider what happens when i slides rightwards. Every time i passes a mirror a new (i, ⟨i⟩)-class inversion is created, so I_{i,i} is increased by one. But similarly, every time i passes a member of ⟨j⟩ a new (i, ⟨j⟩)-class inversion is created, so I_{i,j} is increased by one. Since these events alternate, this completes the proof.

Proof of Proposition 2.1. First we shall prove that λ(π) is a lecture hall partition, that is, that \frac{λ_{i}}{i} ≥ \frac{λ_{i−1}}{i−1} for all 1 < i ≤ n. By using first part (a) and then part (b) of the lemma above, we get

\frac{λ_{i}}{i} = \frac{∑_{j=1}^{i} I_{i,j}}{i} ≥ \frac{I_{i,i} + ∑_{j=1}^{i−1} I_{i−1,j}}{i} ≥ \frac{∑_{j=1}^{i−1} I_{i−1,j}}{i − 1} = \frac{λ_{i−1}}{i − 1},

as desired. For the converse, given a lecture hall partition λ, there is clearly a unique way to construct a π ∈ C̃_{n}/C_{n} with inversion counts satisfying ∑_{j=1}^{i} I_{i,j}(π) = λ_{i} for all i = 1, 2, …, n: Start with just the mirrors, then place 1 in the unique window such that I_{1,1} = λ_{1}. Proceed with placing 2 in the unique slot between a member of ⟨1⟩ and a mirror such that I_{2,1} + I_{2,2} = λ_{2}, and continue in this manner in turn with 3, 4, …, n. To prove that there does exist a slot for element i, it suffices to show that if i is placed directly to the right of i − 1, then the inversion count ∑_{j=1}^{i} I_{i,j}(π) will be strictly less than 1 + \frac{i}{i−1}λ_{i−1}. By part (b) of the lemma above, we have the equality I_{i,i−1} = I_{i,i} if i is directly to the right of i − 1. Thanks to the lemma again we can compute

∑_{j=1}^{i} I_{i,j} = I_{i,i−1} + ∑_{j=1}^{i−1} I_{i,j} = I_{i−1,i−1} + ∑_{j=1}^{i−1} I_{i−1,j} < 1 + \frac{i}{i − 1} ∑_{j=1}^{i−1} I_{i−1,j} = 1 + \frac{i}{i − 1}λ_{i−1}.

As observed above, this bijection between C̃_{n}/C_{n} and L_{n} establishes equivalence between Bott’s Formula and the Lecture Hall Theorem.

3 A direct proof of the refined Lecture Hall Theorem

The refined Lecture Hall Theorem says that

∑_{λ∈L_{n}} x^{|λ|_{e}}y^{|λ|_{o}} = ∏_{i=0}^{n−1} \frac{1}{1 − x^{i+1}y^{i}} .

Our direct proof of this identity is based on a way of splitting any lecture hall partition λ ∈ L_{n} as λ = μ + ∑_{i=1}^{n} k_{i}λ^{(i)} (with partitions considered as members of an n-dimensional vector space), where μ belongs to a set R_{n} of reduced lecture hall partitions, the λ^{(i)} constitute a natural basis of lecture hall partitions, and the k_{i} are nonnegative integers. Then we can write the left-hand side of the identity as

∑_{μ∈R_{n}} x^{|μ|_{e}}y^{|μ|_{o}} ∏_{i=1}^{n} \frac{1}{1 − x^{|λ^{(i)}|_{e}}y^{|λ^{(i)}|_{o}}} ,

and we will compute these factors separately.

3.1 Reduction of lecture hall partitions

Let n ≥ 1 be fixed. Given an n-tuple λ = (λ_{1}, …, λ_{n}) ∈ IR^{n}, we define its D-sequence to be the n-tuple D(λ) = (d_{1}, …, d_{n}) given by

d_{1} = λ_{1} and d_{i} = λ_{i} − ⌈\frac{iλ_{i−1}}{i − 1} ⌉ for 2 ≤ i ≤ n.

The sequence D(λ) completely defines λ. Moreover, λ ∈ IN^{n} is a lecture hall partition if and only if d_{i} ≥ 0 for all i.

For 1 ≤ i ≤ n, let λ^{(i)} = (0, …, 0, i, i + 1, …, n) ∈ IN^{n}. Then D(λ^{(i)}) = (0, …, 0, i, 0, …, 0) and thus λ^{(i)} is a lecture hall partition of length n. More generally, if λ belongs to L_{n}, then λ + λ^{(i)} also belongs to L_{n}, and its D-sequence is (d_{1}, …, d_{i−1}, i + d_{i}, d_{i+1}, …, d_{n}) where (d_{1}, …, d_{n}) = D(λ). The following lemma describes in which case λ − λ^{(i)} also lies in L_{n}.

Lemma 3.1 Let λ ∈ L_{n}, and let (d_{1}, …, d_{n}) be its D-sequence. Let 1 ≤ i ≤ n. Then λ − λ^{(i)} belongs to L_{n} if and only if d_{i} ≥ i.

Proof. Let (d′_{1}, …, d′_{n}) = D(λ − λ^{(i)}). Then d′_{i} = d_{i} − i and d′_{j} = d_{j} if j ≠ i. Thus d′_{j} ≥ 0 for all j if and only if d_{i} ≥ i.

Definition 3.2 A lecture hall partition of length n is said to be reduced if its D-sequence (d_{1}, …, d_{n}) satisfies 0 ≤ d_{i} < i for 1 ≤ i ≤ n.

Since the D-sequence completely defines the partition, there are exactly n! reduced lecture hall partitions of length n. The set of reduced partitions of L_{n} will be denoted by R_{n}. Iterating Lemma 3.1 leads to the following reduction result.

Proposition 3.3 Let λ be a lecture hall partition of length n with D-sequence (d_{1}, …, d_{n}). Then the map λ ↦ (μ, k_{1}, …, k_{n}) given by k_{i} = ⌊d_{i}/i⌋ and

λ = μ + ∑_{i=1}^{n} k_{i}λ^{(i)}

is a bijection from L_{n} to R_{n} × IN^{n}.

As we remarked in the beginning of this section, this implies that the generating function for lecture hall partitions of length n is

∑_{λ∈L_{n}} x^{|λ|_{e}}y^{|λ|_{o}} = \frac{P_{n}(x, y)}{∏_{i=1}^{n}(1 − x^{|λ^{(i)}|_{e}}y^{|λ^{(i)}|_{o}})}  (4)

where

P_{n}(x, y) = ∑_{μ∈R_{n}} x^{|μ|_{e}}y^{|μ|_{o}}.  (5)

We will compute separately the numerator and denominator of expression (4).

Lemma 3.4 The even and odd weights of the partitions λ^{(j)}, 1 ≤ j ≤ n, are given by:

\{ \begin{matrix}|λ^{(n−2i)}|_{e} & = n + (n − 2) + … + (n − 2i) & = (i + 1)(n − i) \\ |λ^{(n−2i)}|_{o} & = (n − 1) + (n − 3) + … + (n − 2i + 1) & = i(n − i) \end{matrix} for 0 ≤ i ≤ ⌊\frac{n − 1}{2}⌋ ,

and

\{ \begin{matrix}|λ^{(n−2i−1)}|_{e} & = n + (n − 2) + … + (n − 2i) & = (n − i)(i + 1) \\ |λ^{(n−2i−1)}|_{o} & = (n − 1) + (n − 3) + … + (n − 2i − 1) & = (n − i − 1)(i + 1) \end{matrix} for 0 ≤ i ≤ ⌊\frac{n}{2}⌋ − 1.

Thus the denominator in (4) can be rewritten as

∏_{i=0}^{n−1} (1 − (x^{i+1}y^{i})^{n−i}) .

Comparing (4) with equation (2) shows that what we finally need to prove is the following enumeration result for reduced lecture hall partitions:

P_{n}(x, y) = ∑_{μ∈R_{n}} x^{|μ|_{e}}y^{|μ|_{o}} = ∏_{i=0}^{n−1} \frac{1 − (x^{i+1}y^{i})^{n−i}}{1 − x^{i+1}y^{i}} .  (6)

Example. Let n = 3. The reduced lecture hall partitions are (0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 2), (0, 1, 3) and (0, 1, 4). Thus

P_{3}(x, y) = 1 + x + x^{2} + x^{2}y + x^{3}y + x^{4}y

= (1 + x + x^{2})(1 + x^{2}y)

= \frac{1 − x^{3}}{1 − x} \frac{1 − x^{4}y^{2}}{1 − x^{2}y} .

3.2 Enumeration of reduced lecture hall partitions

Let us denote the set {0, 1, …, n} by [0, n]. We will prove (6) inductively by describing a bijection Υ from R_{n} × [0, n] to R_{n+1} such that if η = Υ(μ, i), then

|η|_{o} = |μ|_{e} and |η|_{e} = i + 2|μ|_{e} − |μ|_{o}.  (7)

These properties imply that the polynomials P_{n}(x, y), defined by (5), satisfy

P_{n+1}(x, y) = \frac{1 − x^{n+1}}{1 − x} P_{n}(x^{2}y, x^{−1}).

Moreover, as (0) is the only reduced partition of length 1, we have P_{1}(x, y) = 1, and we finally obtain (6) by induction over n.

We will now describe the bijection Υ and study its properties. This bijection is closely related to an intriguing involution on the set R_{n} of reduced lecture hall partitions.

3.2.1 An involution on reduced lecture hall partitions

Recall that an n-tuple μ ∈ IR^{n} is characterized by its D-sequence D(μ) = (d_{1}, …, d_{n}), defined by d_{1} = μ_{1} and d_{i} = μ_{i} − ⌈\frac{iμ_{i−1}}{i−1} ⌉ for i ≥ 2.

For μ ∈ R_{n}, let μ^{∗} = (μ_{1}^{∗}, …, μ_{n}^{∗}) be the unique n-tuple such that

\{ \begin{matrix}μ_{n−2k}^{∗} & = μ_{n−2k} & for n − 2k ≥ 1 \\ d_{n−2k−1}^{∗} & = ⌊\frac{n−2k−1}{n−2k}μ_{n−2k}⌋ − μ_{n−2k−1} & for n − 2k − 1 ≥ 1, \end{matrix}  (8)

where (d_{1}^{∗}, …, d_{n}^{∗}) is the D-sequence associated with μ^{∗}. The second equation is of course a short way to define μ_{n−2k−1}^{∗}. Indeed,

μ_{n−2k−1}^{∗} − ⌈\frac{n − 2k − 1}{n − 2k − 2}μ_{n−2k−2}^{∗}⌉ = ⌊\frac{n − 2k − 1}{n − 2k}μ_{n−2k}⌋ − μ_{n−2k−1}.  (9)

In this expression, and always in this section, we have set μ_{i}^{∗} = μ_{i} = 0 if i ≤ 0.

Example. Let μ = (0, 1, 2, 6, 11, 15). Then D(μ) = (0, 1, 0, 3, 3, 1) and thus μ ∈ R_{6}. We obtain μ^{∗} = (0, 1, 4, 6, 9, 15) and D(μ^{∗}) = (0, 1, 2, 0, 1, 4). Hence μ^{∗} is also a reduced lecture hall partition. Moreover, computing (μ^{∗})^{∗} shows that (μ^{∗})^{∗} = μ. We shall see that this holds in general.

Proposition 3.5 The correspondence μ ↦ μ^{∗} defines an involution on the set R_{n} of reduced lecture hall partitions of length n.

In the proof of this proposition, we will use the following simple lemma.

Lemma 3.6 Let ℓ, m and i be nonnegative integers such that i ≥ 1. Then

⌊\frac{i − 1}{i}ℓ⌋ − m ∈ [0, i − 2] ⟺ ℓ − ⌈\frac{i}{i − 1}m⌉ ∈ [0, i − 1].

Proof of Proposition 3.5. Let μ ∈ R_{n}. We first want to prove that μ^{∗} ∈ R_{n}, that is, that d_{i}^{∗} ∈ [0, i − 1] for 1 ≤ i ≤ n. According to (8) and Lemma 3.6, this is true when n − i is odd. Now, since μ_{n−2k}^{∗} = μ_{n−2k} for all k, we can rewrite (9) as

⌊\frac{n − 2k − 1}{n − 2k}μ_{n−2k}^{∗}⌋ − μ_{n−2k−1}^{∗} = μ_{n−2k−1} − ⌈\frac{n − 2k − 1}{n − 2k − 2}μ_{n−2k−2}⌉ = d_{n−2k−1}.  (10)

But d_{n−2k−1} ∈ [0, n − 2k − 2] since μ is a reduced lecture hall partition; hence, according to Lemma 3.6,

d_{n−2k}^{∗} = μ_{n−2k}^{∗} − ⌈\frac{n − 2k − 2}{n − 2k − 1}μ_{n−2k−1}^{∗}⌉ ∈ [0, n − 2k − 1].

Thus μ^{∗} is indeed a reduced lecture hall partition.

Finally, equation (10) says nothing else than that the involutive property (μ^{∗})^{∗} = μ holds.

3.2.2 The bijection Υ

The most natural way of extending the involution μ ↦ μ^{∗} defined above into a bijection Υ from R_{n} ×[0, n] to R_{n+1} is to define

Υ(μ, i) = (μ_{1}^{∗}, …, μ_{n}^{∗}, ⌈\frac{n + 1}{n}μ_{n}^{∗}⌉ + i) .

It is clear that Υ(μ, i) is a reduced lecture hall partition. Moreover, as μ ↦ μ^{∗} defines a bijection on R_{n}, Υ is a bijection from R_{n} × [0, n] to R_{n+1}.

Let us denote the partition Υ(μ, i) by η. We want to prove the properties (7). As μ_{n−2k}^{∗} = μ_{n−2k}, it is clear that |η|_{o} = |μ|_{e}. Moreover,

|η|_{e} = i + ⌈\frac{n + 1}{n}μ_{n}^{∗}⌉ + ∑_{n−2k−1∈[1,n−1]} μ_{n−2k−1}^{∗}

= i + ⌈\frac{n + 1}{n}μ_{n}⌉ + ∑_{n−2k−1∈[1,n−1]} (⌈\frac{n − 2k − 1}{n − 2k − 2}μ_{n−2k−2}⌉ + ⌊\frac{n − 2k − 1}{n − 2k}μ_{n−2k}⌋ − μ_{n−2k−1})

= i + ∑_{n−2k∈[1,n]} ⌈\frac{n − 2k + 1}{n − 2k}μ_{n−2k}⌉ + ∑_{n−2k∈[2,n]} ⌊\frac{n − 2k − 1}{n − 2k}μ_{n−2k}⌋ − |μ|_{o}

= i + ∑_{n−2k∈[1,n]} (⌈\frac{n − 2k + 1}{n − 2k}μ_{n−2k}⌉ + ⌊\frac{n − 2k − 1}{n − 2k}μ_{n−2k}⌋) − |μ|_{o}

since μ_{1} = 0 for any reduced lecture hall partition. The desired result |η|_{e} = i + 2|μ|_{e} − |μ|_{o} now follows from the trivial fact that

⌈\frac{i + 1}{i}m⌉ + ⌊\frac{i − 1}{i}m⌋ = 2m

for any integers m and i such that i ≠ 0.

As shown above, the properties (7) imply the following result, thereby completing the proof of the refined Lecture Hall Theorem.

Proposition 3.7 The generating function for reduced lecture hall partitions of length n according to their even and odd weights is:

∑_{μ∈R_{n}} x^{|μ|_{e}}y^{|μ|_{o}} = ∏_{i=0}^{n−1} \frac{1 − (x^{i+1}y^{i})^{n−i}}{1 − x^{i+1}y^{i}} .

Remark. A direct proof of (6) would consist in describing a bijection ϕ from the set O_{n} of partitions with odd parts having at most n − i parts of size 2i − 1 for i ≤ n to the set R_{n} of reduced lecture hall partitions, such that if ϕ(λ) = μ, then

s(μ) = |μ|_{e} − |μ|_{o} = ℓ(λ) and |μ| = |λ|.

We can define a bijection having these properties by iterating our bijection Υ. Let λ be a partition in O_{n}, so λ = 1^{i_{n}}3^{i_{n−1}} … (2n − 1)^{i_{1}}, with 0 ≤ i_{j} < j for all j. We associate with λ the reduced partition

μ = Υ(Υ(⋯ (Υ(Υ((0), i_{2}), i_{3}), ⋯), i_{n−1}), i_{n}).

In this expression, Υ is seen as a bijection from ⋃_{i}(R_{i} × [0, i]) to ⋃_{i} R_{i+1}. Iterating (7) shows that

s(μ) = i_{1} + ⋯ + i_{n} = ℓ(λ)

and

|μ| = i_{n} + 3i_{n−1} + ⋯ + (2n − 1)i_{1} = |λ|.

For example, let us take n = 6 and λ = 1^{3}3^{0}5^{3}7^{1}9^{1}11^{0}. We obtain

(0) ⟶^{Υ(.,1)} (0, 1) ⟶^{Υ(.,1)} (0, 1, 3) ⟶^{Υ(.,3)} (0, 1, 3, 7) ⟶^{Υ(.,0)} (0, 1, 4, 7, 9) ⟶^{Υ(.,3)} (0, 1, 4, 6, 9, 14).

Thus μ = (0, 1, 4, 6, 9, 14) and we can check that s(μ) = 8 = 1 + 1 + 3 + 3 = ℓ(λ) and |μ| = |λ| = 34. It would naturally be interesting to find a less recursive, more direct decription of this bijection.

References

[1] G. E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1976.

[2] R. Bott, An application of the Morse theory to the topology of Lie-groups, Bull. Soc. Math. France 84 (1956), 251–281.

[3] M. Bousquet-Mélou and K. Eriksson, Lecture hall partitions 2, in preparation.

[4] H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH, Stockholm, 1994.

[5] H. Eriksson and K. Eriksson, Affine Coxeter groups as infinite permutations, Proceedings of 7th FPSAC (Paris, 1995), pp. 185–194.

[6] J. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, 1990.