Lecture Hall Partitions 2

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

For a non-decreasing integer sequence a = (a_{1}, …, a_{n}) we define L_{a} to be the set of n-tuples of integers λ = (λ_{1}, …, λ_{n}) satisfying 0 ≤ \frac{λ_{1}}{a_{1}} ≤ \frac{λ_{2}}{a_{2}} ≤ … ≤ \frac{λ_{n}}{a_{n}} . This generalizes the so-called lecture hall partitions, corresponding to a_{i} = i and previously studied by the authors and by G. Andrews. We find sequences a such that the weight generating function for these a-lecture hall partitions has the remarkable form

∑_{λ∈L_{a}} q^{|λ|} = \frac{1}{(1 − q^{e_{1}})(1 − q^{e_{2}}) ⋯ (1 − q^{e_{n}})}.

In the limit when n tends to infinity, we obtain a family of identities of the kind “the number of partitions of an integer m such that the quotient between consecutive parts is greater than θ is equal to the number of partitions of m into parts belonging to the set P_{θ},” for certain real numbers θ and integer sets P_{θ}. We then underline the connection between lecture hall partitions and Ehrhart theory and discuss some reciprocity results.

1 Introduction

Suppose a lecture hall is to be built with n rows of seats placed at distances a_{1}, a_{2}, …, a_{n} from the speaker, at heights λ_{1}, λ_{2}, …, λ_{n}. If the people in the audience are of negligible height, then the condition on the architecture for every seat to give a clear view of the speaker is that the slopes are weakly increasing, that is, \frac{λ_{i}}{a_{i}} ≤ \frac{λ_{i+1}}{a_{i+1}} for 1 ≤ i < n. This justifies the following definition (Figure 1).

Definition 1.1 Given a non-decreasing sequence of n positive integers a = (a_{1}, a_{2}, …, a_{n}), an a-lecture hall partition is an n-tuple of integers λ = (λ_{1}, …, λ_{n}) satisfying

0 ≤ \frac{λ_{1}}{a_{1}} ≤ \frac{λ_{2}}{a_{2}} ≤ … ≤ \frac{λ_{n}}{a_{n}} .

We let L_{a} denote the set of a-lecture hall partitions.

Let |λ| = λ_{1} +⋯+λ_{n} be the weight of λ. Let S_{a}(q) denote the weight generating function for a-lecture hall partitions, i.e. S_{a}(q) = ∑_{λ∈L_{a}} q^{|λ|}. For example, an obvious result is that the generating function for (1, 1, …, 1)-lecture hall partitions is

S_{(1,1,...,1)}(q) = \frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})}.

∗Partially supported by EC grant CHRX-CT93-0400 and GDR AMI.

†Partially supported by EC grant CHRX-CT93-0400.

[figure: 1; 2; 4; 6]

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

The study of lecture hall partitions was initiated in a previous paper [3] by the same authors, where the generating function for (1, 2, 3, …, n)-lecture hall partitions was shown to have a similar nice form:

S_{(1,2,...,n)}(q) = \frac{1}{(1 − q)(1 − q^{3}) ⋯ (1 − q^{2n−1})}.  (1)

For general a, the generating function S_{a}(q) is always a rational function, but usually with a nontrivial numerator. We call the sequences a for which the series S_{a}(q) is the multiplicative inverse of a polynomial polynomic sequences.

The result above, though simple to state, seems far from trivial. Two different proofs were presented in [3], one using Bott’s formula for the affine Coxeter group C̃_{n}, and one more combinatorial. Recently, Andrews [2] gave a third proof, starting from MacMahon’s method of partition analysis (see [5], Vol. 2, Section VIII). In the present paper, we shall generalize the combinatorial approach of our previous paper to exhibit an infinite family of nontrivial polynomic sequences. This family includes the example (1) above and also for instance the sequence of every other Fibonacci number:

S_{(1,3,8,21,...,F_{2n+1})}(q) = \frac{1}{(1 − q^{1})(1 − q^{1+3})(1 − q^{3+8})(1 − q^{8+21}) ⋯ (1 − q^{F_{2n−1}+F_{2n+1}})}.

Our results will allow us to generalize the following classical theorem, first published in 1748 by Euler [4]: the generating function for partitions into distinct parts is

∑_{μ:μ_{i+1}>μ_{i}} q^{|μ|} = ∏_{i≥0} \frac{1}{1 − q^{2i+1}} .

In other words, the number of partitions of an integer m into distinct parts is equal to the number of partitions of m into odd parts. The standard way to perceive the condition μ_{i+1} > μ_{i} is that the difference between consecutive parts must be at least one. The famous Rogers-Ramanujan identities and related formulas (see Andrews’s book [1]) are results of the same type, counting partitions with conditions on the difference between parts. However, the condition in Euler’s theorem can equivalently be perceived as demanding that the quotient between consecutive parts be greater than one. In this way one can see that we derive Euler’s theorem by letting n tend to infinity in (1). More generally, we will derive from our main result many identities of the same type: we will describe an infinite family of real numbers θ and integer sets P_{θ} for which the number of partitions of m such that the quotient between any two parts is greater than θ is equal to the number of partitions of m into parts belonging to the set P_{θ}.

Furthermore, we will discuss strict lecture hall partitions, obtained by taking strict inequalities in Definition 1.1 (which is in fact quite reasonable from the architectural point of view). We shall find that they are connected to lecture hall partitions through a reciprocity theorem of the kind discussed by Stanley in [6], and give a simple proof of this theorem.

The outline of the paper is as follows. After discussing polynomic sequences in Section 2 we go on with an approach to enumerating a-lecture hall partitions for general sequences a in Section 3. We will find that in order to obtain explicit results further assumptions on a are needed. This leads in Section 4 to the definition of a family of sequences a for which we compute nice generating functions. Taking the limit, we obtain the Euler-like results mentioned earlier. Finally, Section 5 deals with strict lecture hall partitions, establishes the reciprocity theorem and relates self-reciprocal sequences to continued fractions.

2 Polynomic sequences

As we mentioned in the introduction, we will exhibit several sequences a = (a_{1}, a_{2}, …, a_{n}) such that the generating function for a-lecture hall partitions has the remarkable form

S_{a}(q) = \frac{1}{(1 − q^{e_{1}})(1 − q^{e_{2}}) ⋯ (1 − q^{e_{n}})}

for some positive integers e_{1}, …, e_{n}, all different. In combinatorial terms, this can equivalently be stated as the a-lecture hall partitions of weight m being equinumerous with the partitions of m into parts belonging to the set {e_{1}, …, e_{n}}. We say that such a sequence a is a polynomic sequence since the series S_{a} is the inverse of a polynomial. In this section we collect what we know to be true about polynomic sequences and make some conjectures on their nature, based on computer search.

First, there is a trivial kind of polynomic sequence, namely (a_{1}, …, a_{n}) such that a_{i+1} is divisible by a_{i} for all i. This property will be denoted a_{i}|a_{i+1}. Then, integer multiples of polynomic sequences are polynomic sequences, for L_{(ka_{1},...,ka_{n})} = L_{(a_{1},...,a_{n})}. Our first conjecture says that all polynomic sequences are integer multiples of polynomic sequences starting with a one.

Conjecture 2.1 If (a_{1}, …, a_{n}) is a polynomic sequence, then all a_{i} are divisible by a_{1}.

Polynomic sequences can be appended to trivial sequences to produce more polynomic sequences, according to the following result.

Proposition 2.2 Let (a_{1}, …, a_{n}) be a positive non-decreasing integer sequence, and suppose that there exists m ≤ n such that

(i) a_{1}|a_{2}| … |a_{m},

(ii) a_{m−1}|(a_{m+1}, …, a_{n}), and

(iii) (a_{m}, …, a_{n}) is polynomic. Then (a_{1}, …, a_{n}) is also polynomic.

Note that condition (ii) would follow from the two other conditions if Conjecture 2.1 was proved to be true. Proposition 2.2 is a straightforward consequence of the following lemma.

Lemma 2.3 Let (a_{1}, …, a_{n}) be a positive non-decreasing sequence satisfying the first two conditions of Proposition 2.2. Then there exist m − 1 positive integers e_{1}, …, e_{m−1} such that

S_{(a_{1},...,a_{n})}(q) = S_{(a_{m},...,a_{n})}(q) ∏_{i=1}^{m−1} \frac{1}{1 − q^{e_{i}}} .

Proof. For any partition λ = (λ_{1}, …, λ_{n}), augmented by λ_{0} = 0, we define the integers μ_{1}, …, μ_{n} by

λ_{i} = \frac{a_{i}}{a_{i−1}} λ_{i−1} + μ_{i} for 1 ≤ i ≤ m,

and

λ_{i} = \frac{a_{i}}{a_{m−1}} λ_{m−1} + μ_{i} for m < i ≤ n.  (2)

Note that (2) holds for i = m as well. Then λ is an (a_{1}, …, a_{n})-lecture hall partition if and only if μ_{i} ≥ 0 for 1 ≤ i < m and μ = (μ_{m}, …, μ_{n}) is an (a_{m}, …, a_{n})-lecture hall partition. Moreover, there exist m − 1 positive integers e_{1}, …, e_{m−1} such that

|λ| = |μ| + ∑_{i=1}^{m−1} e_{i}μ_{i}.

This leads to the announced result.

Our second conjecture is basically the reciprocal of Proposition 2.2.

Conjecture 2.4 Let (a_{1}, …, a_{n}) be a polynomic sequence, and let m be the least integer such that a_{m+2} is not divisible by a_{m+1}. Then (a_{m}, …, a_{n}) is a polynomic sequence.

If this conjecture is true, a complete characterization of polynomic sequences would follow from the characterization of polynomic sequences (a_{1}, …, a_{n}) such that a_{3} is not divisible by a_{2}. A consequence of our main theorem in Section 4 is that we obtain such sequences by taking a_{1} to be any positive integer, a_{2} = ℓa_{1}, and letting a_{3}, …, a_{n} be determined by

\{ \begin{matrix}a_{2i} & = ℓa_{2i−1} − a_{2i−2}, \\ a_{2i+1} & = ka_{2i} − a_{2i−1} \end{matrix}

for any two integers ℓ ≥ 2 and k ≥ 2. We call such a sequence a (k, ℓ)-sequence. For instance, a = (1, 2, 3, …, n) is the (k, ℓ)-sequence obtained with a_{1} = 1 and k = ℓ = 2, while a = (1, 3, 8, …, F_{2n+1}) is the (k, ℓ)-sequence obtained with a_{1} = 1 and k = ℓ = 3. Note that the (k, ℓ)-sequences satisfy Conjecture 2.1. Our third conjecture is that we have obtained all polynomic sequences such that a_{2} |̸a_{3}.

Conjecture 2.5 Let a = (a_{1}, …, a_{n}) be a polynomic sequence such that a_{3} is not divisible by a_{2}. Then a is a (k, ℓ)-sequence.

Finally, we have a fourth conjecture that seems very natural and would follow from the combination of Conjectures 2.4 and 2.5: that the class of polynomic sequences is hereditary.

Conjecture 2.6 If (a_{1}, …, a_{n}) is a polynomic sequence, then (a_{1}, …, a_{n−1}) is a polynomic sequence.

This last conjecture is related to material in the last section. There we characterize self-reciprocal sequences, show that they generalize the (k, ℓ)-sequences and form a hereditary class.

3 An approach to enumerating lecture hall partitions

In this section, we fix a non-decreasing sequence a = (a_{1}, …, a_{n}) of positive length n. We let L_{a} be the set of a-lecture hall partitions. We will often omit the reference to a.

3.1 Reduced and standard partitions

We will refine the weight generating function to consider the even and odd weights of λ = (λ_{1}, …, λ_{n}), defined respectively as

|λ|_{e} = λ_{n} + λ_{n−2} + λ_{n−4} + … and |λ|_{o} = λ_{n−1} + λ_{n−3} + λ_{n−5} + …

Of course, |λ| = |λ|_{e} + |λ|_{o}. Let S_{a}(x, y) be the two-variable generating function for lecture hall partitions:

S_{a}(x, y) = ∑_{λ∈L_{a}} x^{|λ|_{e}}y^{|λ|_{o}}.

All further work will be done in the two-variable setting. Taking q = x = y gives the generating functions discussed in previous sections.

We will describe a way of splitting any lecture hall partition λ as λ = μ + ∑_{i=1}^{n} k_{i}λ^{(i)} (with partitions considered as members of an n-dimensional vector space), where μ belongs to a finite set R of reduced lecture hall partitions, the standard lecture hall partitions λ^{(i)} constitute a natural basis of L_{a}, and the k_{i} are nonnegative integers. This implies that the generating function for lecture hall partitions factors as

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

Our goal is to compute the two factors of the expression above. The second one is easy, for we will give the λ^{(i)} explicitly. The first one with the reduced lecture hall partitions is harder and we will succeed only for some particular sequences a, which generalize slightly the (k, ℓ)-sequences mentioned in the previous section.

We shall now define the reduced and standard lecture hall partitions. To begin with, note that an alternative way of expressing the lecture hall condition is that λ_{i} ≥ ⌈a_{i}λ_{i−1}/a_{i−1}⌉. Given an n-tuple λ = (λ_{1}, …, λ_{n}) ∈ IR^{n}, we define its D-sequence to be the n-tuple D(λ) = (d_{1}, …, d_{n}) where

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

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

For 1 ≤ i ≤ n, define the standard lecture hall partitions λ^{(i)} by

λ^{(i)} = (0, …, 0, a_{i}, a_{i+1}, …, a_{n}).

They are obviously lecture hall partitions, and D(λ^{(i)}) = (0, …, 0, a_{i}, 0, …, 0). More generally, if λ belongs to L_{a}, then the sum λ + λ^{(i)} also belongs to L_{a}, and its D-sequence is (d_{1}, …, d_{i−1}, a_{i} + d_{i}, d_{i+1}, …, d_{n}) where (d_{1}, …, d_{n}) = D(λ). The following lemma describes for which λ the difference λ − λ^{(i)} also lies in L_{a}.

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

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

Now we define a lecture hall partition to be reduced if every subtraction of a standard lecture hall partition destroys the lecture hall property. By the lemma above this can be stated as follows.

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

Since the D-sequence completely defines the partition, there are exactly a_{1}a_{2} ⋯ a_{n} reduced lecture hall partitions. The set of reduced partitions of L_{a} will be denoted R. Iterating Lemma 3.1 leads to the following reduction result.

Proposition 3.3 The map λ ↦ (μ, k_{1}, …, k_{n}) given by k_{i} = ⌊d_{i}/a_{i}⌋, with (d_{1}, …, d_{n}) = D(λ), and

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

defines a bijection from L_{a} to R × IN^{n}.

Consequently, the generating function for lecture hall partitions is

S_{a}(x, y) = \frac{P (x, y)}{∏_{i=1}^{n}(1 − x^{|λ^{(i)}|_{e}}y^{|λ^{(i)}|_{o}})}  (3)

where the polynomial P (x, y) enumerates reduced lecture hall partitions:

P (x, y) = ∑_{μ∈R} x^{|μ|_{e}}y^{|μ|_{o}}.

Computing this polynomial is thus the central problem one has to solve in order to enumerate lecture hall partitions using our approach. In Section 4, we compute it by induction on the length of a for some particular sequences a, using the involution on reduced lecture hall partitions described next.

3.2 An involution on reduced lecture hall partitions

For μ ∈ IN^{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{a_{n−2k−1}}{a_{n−2k}} μ_{n−2k}⌋ − μ_{n−2k−1} & for n − 2k − 1 ≥ 1, \end{matrix}  (4)

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}^{∗}. Equivalently,

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

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

Example. Let n = 6 and take (a_{1}, …, a_{6}) = (1, 2, 3, 5, 6, 9). Then μ = (0, 1, 3, 9, 13, 21) is a reduced lecture hall partition, since D(μ) = (0, 1, 1, 4, 2, 1). We obtain μ^{∗} = (0, 1, 4, 9, 12, 21) and D(μ^{∗}) = (0, 1, 2, 2, 1, 3). Thus μ^{∗} is also a reduced lecture hall partition. Moreover, computing (μ^{∗})^{∗} shows that (μ^{∗})^{∗} = μ. We shall see that this holds in general.

Proposition 3.4 The correspondence μ ↦ μ^{∗} defines an involution on the set R.

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

Lemma 3.5 For integers ℓ, m ≥ 0 and i, j ≥ 1,

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

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

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

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

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

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

Finally, equation (6) says precisely that the involutive property (μ^{∗})^{∗} = μ holds.

Let us now indicate how we are going to use this involution to enumerate reduced lecture hall partitions. Let a_{n+1} ≥ a_{n}, and let R′ denote the set of reduced (a_{1}, …, a_{n}, a_{n+1})-lecture hall partitions. We extend the involution μ ↦ μ^{∗} into a bijection Υ from R × [0, a_{n+1} − 1] onto R′, by defining

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

For convenience, let us denote the extended partition Υ(μ, i) by η. We want to compute |η|_{e} and |η|_{o}. As μ_{n−2k}^{∗} = μ_{n−2k}, it is clear that |η|_{o} = |μ|_{e}. Moreover,

\begin{aligned}|η|_{e} & = i + ⌈\frac{a_{n+1}}{a_{n}} μ_{n}^{∗}⌉ + ∑_{n−2k−1∈[1,n−1]} μ_{n−2k−1}^{∗} \\ & = i + ⌈\frac{a_{n+1}}{a_{n}} μ_{n}⌉ + ∑_{n−2k−1∈[1,n−1]} (⌈\frac{a_{n−2k−1}}{a_{n−2k−2}} μ_{n−2k−2}⌉ + ⌊\frac{a_{n−2k−1}}{a_{n−2k}} μ_{n−2k}⌋ − μ_{n−2k−1}) \\ & = i + ∑_{n−2k∈[1,n]} ⌈\frac{a_{n−2k+1}}{a_{n−2k}} μ_{n−2k}⌉ + ∑_{n−2k∈[2,n]} ⌊\frac{a_{n−2k−1}}{a_{n−2k}} μ_{n−2k}⌋ − |μ|_{o}. \end{aligned} (7)

We cannot go further in this calculation without any additional assumptions on the sequence a. In the next section we study some particular sequences for which the weight |η|_{e} can be expressed in a very simple way in terms of |μ|_{e} and |μ|_{o}. This will allow us to enumerate reduced lecture hall partitions by induction on the length of a.

4 Generating functions for (k, ℓ)-sequences

In this section, we fix two integers k, ℓ ≥ 2 and two initial values a_{1}, a_{2} satisfying one of the following conditions:

a_{2} = a_{1}ℓ or a_{2} = a_{1}ℓ − 1 or a_{1} = 1.  (8)

We define an infinite sequence (a_{i})_{i≥1} by

\{ \begin{matrix}a_{2i} & = ℓa_{2i−1} − a_{2i−2} & for i ≥ 2 \\ a_{2i+1} & = ka_{2i} − a_{2i−1} & for i ≥ 1. \end{matrix}  (9)

This generalizes the (k, ℓ)-sequences defined in Section 2.

For n ≥ 1, we will be able to enumerate reduced (a_{1}, …, a_{n})-lecture hall partitions. We will then compute the weights of the standard lecture hall partitions λ^{(i)}, which will finally provide the generating function for lecture hall partitions thanks to (3).

4.1 Reduced lecture hall partitions for (k, ℓ)-sequences

For n ≥ 1, we denote the set of reduced (a_{1}, …, a_{n})-lecture hall partitions by R_{n}, and their generating function by P_{n}(x, y). Let us return to the last lines of the previous section: the correspondence Υ is a bijection from R_{n} × [0, a_{n+1} − 1] to R_{n+1}. We combine the last equation of (7) with the following simple lemma.

Lemma 4.1 Let i ≥ 2 and m ≥ 0. Then

⌈\frac{a_{i+1}}{a_{i}} m⌉ + ⌊\frac{a_{i−1}}{a_{i}} m⌋ = \{ \begin{matrix}km & if i is even, \\ ℓm & if i is odd. \end{matrix}

We obtain

|η|_{e} = \{ \begin{matrix}i + k|μ|_{e} − |μ|_{o} & if n is even, \\ i + ⌈\frac{a_{2}}{a_{1}} μ_{1}⌉ + ℓ ∑_{n−2k∈[3,n]} μ_{n−2k} − |μ|_{o} & if i is odd, \end{matrix}

which gives, using (8),

|η|_{e} = \{ \begin{matrix}i + k|μ|_{e} − |μ|_{o} & if n is even, \\ i + ℓ|μ|_{e} − |μ|_{o} & if n is odd, \end{matrix}  (10)

(remember that μ_{1} ∈ [0, a_{1} − 1]).

Thus the bijection Υ : R_{n} × [0, a_{n+1} − 1] → R_{n+1} is such that, if η = Υ(μ, i), then |η|_{o} = |μ|_{e}, and |η|_{e} is given by (10). This implies that the polynomials P_{n}(x, y) can be computed inductively via the following recurrence relations:

P_{2n+1}(x, y) = \frac{1 − x^{a_{2n+1}}}{1 − x} P_{2n}(x^{k}y, x^{−1}) and P_{2n}(x, y) = \frac{1 − x^{a_{2n}}}{1 − x} P_{2n−1}(x^{ℓ}y, x^{−1}),

with the initial condition P_{0}(x, y) = 1.

Proposition 4.2 Given an infinite sequence (a_{1}, a_{2}, …) satisfying (8) and (9), the generating functions for reduced (a_{1}, …, a_{2n})-lecture hall partitions and reduced (a_{1}, …, a_{2n−1})-lecture hall partitions are respectively given by:

P_{2n}(x, y) = ∏_{i=1}^{2n} \frac{1 − (x^{b_{i}}y^{b_{i}^{∗}})^{a_{2n−i+1}}}{1 − x^{b_{i}}y^{b_{i}^{∗}}}

and

P_{2n−1}(x, y) = ∏_{i=1}^{2n−1} \frac{1 − (x^{b_{i+1}^{∗}}y^{b_{i−1}})^{a_{2n−i}}}{1 − x^{b_{i+1}^{∗}}y^{b_{i−1}}}

where the sequences of exponents b and b^{∗} are defined by b_{0} = 0, b_{1} = 1, b_{1}^{∗} = 0, b_{2}^{∗} = 1, and the same recurrence relations as for a.

Proof. One readily verifies that the sequences b and b^{∗} satisfy the relations

b_{2i}^{∗} = b_{2i−1} and ℓb_{2i+1}^{∗} = kb_{2i}.  (11)

This implies further that

b_{i+1}^{∗} = kb_{i−1} − b_{i−1}^{∗} and b_{i} = ℓb_{i}^{∗} − b_{i−2},

which are exactly the relations forced upon us by the recurrence for P_{n}.

Example. Let k = 2, ℓ = 3, a_{1} = 1 and a_{2} = ℓa_{1} = 3. We have (a_{1}, a_{2}, a_{3}) = (1, 3, 5), (b_{0}, b_{1}, b_{2}) = (0, 1, 3) and (b_{2}^{∗}, b_{3}^{∗}, b_{4}^{∗}) = (1, 2, 5). The reduced (1, 3, 5)-lecture hall partitions are listed below:

\begin{matrix}(0, 0, 0), & (0, 0, 1), & (0, 0, 2), & (0, 0, 3), & (0, 0, 4), \\ (0, 1, 2), & (0, 1, 3), & (0, 1, 4), & (0, 1, 5), & (0, 1, 6), \\ (0, 2, 4), & (0, 2, 5), & (0, 2, 6), & (0, 2, 7), & (0, 2, 8). \end{matrix}

Thus:

P_{3}(x, y) = 1 + x + x^{2} + x^{3} + x^{4} + x^{2}y + x^{3}y + x^{4}y + x^{5}y + x^{6}y + x^{4}y^{2} + x^{5}y^{2} + x^{6}y^{2} + x^{7}y^{2} + x^{8}y^{2}

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

= \frac{1 − (x)^{5}}{1 − x} \frac{1 − (x^{2}y)^{3}}{1 − x^{2}y} \frac{1 − (x^{5}y^{3})^{1}}{1 − x^{5}y^{3}}

= \frac{1 − (x^{b_{2}^{∗}}y^{b_{0}})^{a_{3}}}{1 − x^{b_{2}^{∗}}y^{b_{0}}} \frac{1 − (x^{b_{3}^{∗}}y^{b_{1}})^{a_{2}}}{1 − x^{b_{3}^{∗}}y^{b_{1}}} \frac{1 − (x^{b_{4}^{∗}}y^{b_{2}})^{a_{1}}}{1 − x^{b_{4}^{∗}}y^{b_{2}}} .

4.2 Standard lecture hall partitions for (k, ℓ)-sequences

Recall that the standard (a_{1}, …, a_{n})-lecture hall partitions are the λ^{(i)} = (0, …, 0, a_{i}, a_{i+1}, …, a_{n}), for 1 ≤ i ≤ n. Our computation of their even and odd weights will depend on the following lemma.

Lemma 4.3 For 1 ≤ i ≤ n, let us define the sums E(n, i) and O(n, i) by

E(n, i) = a_{2n} + a_{2n−2} + … + a_{2n−2i+2} and O(n, i) = a_{2n−1} + a_{2n−3} + … + a_{2n−2i+1}.

Then we have, for the sequences a, b and b^{∗} of Proposition 4.2,

E(n, i) = b_{i}a_{2n−i+1} and O(n, i) = b_{i+1}^{∗}a_{2n−i}.

Proof. We shall prove each of these equalities by induction over i. We have E(n, 1) = a_{2n} = b_{1}a_{2n} and E(n, 2) = a_{2n} + a_{2n−2} = ℓa_{2n−1} = b_{2}a_{2n−1} as desired. Define α_{i} to be ℓ if i is even and k if i is odd. Then induction gives, for i ≥ 3,

E(n, i) = E(n, i − 1) + E(n − 1, i − 1) − E(n − 1, i − 2)
= b_{i−1}a_{2n−i+2} + b_{i−1}a_{2n−i} − b_{i−2}a_{2n−i+1}
= α_{i}b_{i−1}a_{2n−i+1} − b_{i−2}a_{2n−i+1}
= b_{i}a_{2n−i+1},

just as we wanted. The argument for O(n, i) is similar.

Thus the weights of standard (a_{1}, …, a_{2n})-lecture hall partitions are given by

\{ \begin{matrix}|λ^{(2n−2i)}|_{e} = & a_{2n} + ⋯ + a_{2n−2i} & = & E(n, i + 1) & = b_{i+1}a_{2n−i} \\ |λ^{(2n−2i)}|_{o} = & a_{2n−1} + ⋯ + a_{2n−2i+1} & = & O(n, i) & = b_{i+1}^{∗}a_{2n−i} \end{matrix} for 0 ≤ i ≤ n − 1,

and

\{ \begin{matrix}|λ^{(2n−2i+1)}|_{e} = & a_{2n} + ⋯ + a_{2n−2i+2} & = & E(n, i) & = b_{i}a_{2n−i+1} \\ |λ^{(2n−2i+1)}|_{o} = & a_{2n−1} + ⋯ + a_{2n−2i+1} & = & O(n, i) & = b_{i+1}^{∗}a_{2n−i} \end{matrix} for 1 ≤ i ≤ n.

The weights of standard (a_{1}, …, a_{2n−1})-lecture hall partitions are given by

\{ \begin{matrix}|λ^{(2n−2i+1)}|_{e} = & a_{2n−1} + ⋯ + a_{2n−2i+1} & = & O(n, i) & = b_{i+1}^{∗}a_{2n−i} \\ |λ^{(2n−2i+1)}|_{o} = & a_{2n−2} + ⋯ + a_{2n−2i+2} & = & E(n − 1, i − 1) & = b_{i−1}a_{2n−i} \end{matrix} for 1 ≤ i ≤ n,

and

\{ \begin{matrix}|λ^{(2n−2i)}|_{e} = & a_{2n−1} + ⋯ + a_{2n−2i+1} & = & O(n, i) & = b_{i+1}^{∗}a_{2n−i} \\ |λ^{(2n−2i)}|_{o} = & a_{2n−2} + ⋯ + a_{2n−2i} & = & E(n − 1, i) & = b_{i}a_{2n−i−1} \end{matrix} for 1 ≤ i ≤ n − 1.

Combining these results with Proposition 4.2 and equation (3), we finally obtain the generating function for lecture hall partitions.

Proposition 4.4 Given an infinite sequence (a_{1}, a_{2}, …) satisfying (8) and (9), the generating functions for (a_{1}, …, a_{2n})-lecture hall partitions and (a_{1}, …, a_{2n−1})-lecture hall partitions are respectively given by:

S_{(a_{1},...,a_{2n})}(x, y) = ∏_{i=1}^{2n} \frac{1}{1 − x^{b_{i}}y^{b^{i}^{∗}}} ∏_{i=n+1}^{2n} \frac{1 − (x^{b_{i}}y^{b_{i}^{∗}})^{a_{2n−i+1}}}{1 − x^{b_{2n−i+1}a_{i}}y^{b_{2n−i+2}^{∗}a_{i−1}}}  (12)

and

S_{(a_{1},...,a_{2n−1})}(x, y) = ∏_{i=1}^{2n−1} \frac{1}{1 − x^{b_{i+1}^{∗}}y^{b_{i−1}}} ∏_{i=n+1}^{2n−1} \frac{1 − (x^{b_{i+1}^{∗}}y^{b_{i−1}})^{a_{2n−i}}}{1 − x^{b_{2n−i+1}^{∗}a_{i}}y^{b_{2n−i}a_{i−1}}}  (13)

where the sequences b and b^{∗} are defined by b_{0} = 0, b_{1} = 1, b_{1}^{∗} = 0, b_{2}^{∗} = 1, and the same recurrence relations as for a.

Examples

1. If k = ℓ, then b_{i+1}^{∗} = b_{i} for i ≥ 0. The proposition above implies that the generating function for (a_{1}, …, a_{n})-lecture hall partitions is

S_{(a_{1},...,a_{n})}(x, y) = ∏_{i=0}^{n−1} \frac{1}{1 − x^{b_{i+1}}y^{b_{i}}} ∏_{i=⌊ \frac{n+1}{2} ⌋}^{n−1} \frac{1 − (x^{b_{i+1}}y^{b_{i}})^{a_{n−i}}}{1 − (x^{a_{i+1}}y^{a_{i}})^{b_{n−i}}} .

For example, if we take k = ℓ = 2, a_{1} = 1 and a_{2} = 3, then property (8) is satisfied and we have a_{i} = 2i − 1 and b_{i} = i for all i. We obtain that the generating function for (1, 3, …, 2n − 1)-lecture hall partitions is

S_{(1,3,...,2n−1)}(x, y) = ∏_{i=0}^{n−1} \frac{1}{1 − x^{i+1}y^{i}} ∏_{i=⌊ \frac{n+1}{2} ⌋}^{n−1} \frac{1 − (x^{i+1}y^{i})^{2n−2i−1}}{1 − (x^{2i+1}y^{2i−1})^{n−i}} .

In particular,

S_{(1,3,5,7)}(q) = \frac{1 − q + q^{3} − q^{4} + q^{5} − q^{7} + q^{8}}{(1 − q)^{2}(1 − q^{12})(1 − q^{16})} .

Observe the nontrivial numerator of this series.

2. The (k, ℓ)-sequences defined in Section 2 satisfy a_{2} = a_{1}ℓ. As noted in that section, it is sufficient to study the case a_{1} = 1, a_{2} = ℓ, or, equivalently, a_{0} = 0, a_{1} = 1. Then we have a_{i} = b_{i} for i ≥ 0. Moreover, properties (11) imply that if the integers i and j are equal modulo two, then b_{i+1}^{∗}b_{j} = b_{i}b_{j+1}^{∗}. This implies that all the terms occurring in the last product of equations (12) and (13) are equal to 1, and leads to the following result, which states that the (k, ℓ)-sequences are indeed polynomic sequences.

Theorem 4.5 Define an infinite sequence by a_{0} = 0, a_{1} = 1 and for n ≥ 1,

\{ \begin{matrix}a_{2n} & = ℓa_{2n−1} − a_{2n−2}, \\ a_{2n+1} & = ka_{2n} − a_{2n−1} \end{matrix}

where ℓ and k are two integers ≥ 2. The generating functions for (a_{1}, …, a_{2n})-lecture hall partitions and (a_{1}, …, a_{2n−1})-lecture hall partitions are respectively given by

S_{(a_{1},...,a_{2n})}(x, y) = ∏_{i=1}^{2n} \frac{1}{1 − x^{a_{i}}y^{a^{i}^{∗}}}

and

S_{(a_{1},...,a_{2n−1})}(x, y) = ∏_{i=1}^{2n−1} \frac{1}{1 − x^{a_{i+1}^{∗}}y^{a_{i−1}}}

where the numbers a_{n}^{∗} are defined by the initial conditions a_{1}^{∗} = 0, a_{2}^{∗} = 1 and the same recurrence relations as for a.

Note (17/06/96). The method we used to enumerate reduced a-lecture hall partitions for sequences a satisfying the recurrence relations (9) and the initial condition (8) can be applied to general a-lecture hall partitions for sequences a satisfying (9) and the more restrictive initial condition a_{2} = ℓa_{1}. This gives a much shorter, direct proof of Theorem 4.5, which goes as follows: the transformation μ ⟼ μ^{∗} given by (4) also induces an involution on general lecture hall partitions (this is actually true for any sequence a). We define a bijection Υ from L_{(a_{1},...,a_{n})} × IN onto L_{(a_{1},...,a_{n},a_{n+1})}, by

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

Then, denoting η = Υ(μ, i), we have |η|_{o} = |μ|_{e}, and |η|_{e} is given by (10). This implies that the series S_{(a_{1},...,a_{n})}(x, y) can be computed inductively via the following recurrence relations:

S_{(a_{1},...,a_{2n+1})}(x, y) = \frac{1}{1 − x}S_{(a_{1},...,a_{2n})}(x^{k}y, x^{−1}) and S_{(a_{1},...,a_{2n})}(x, y) = \frac{1}{1 − x}S_{(a_{1},...,a_{2n−1})}(x^{ℓ}y, x^{−1}),

with the initial condition S_{(a_{1})}(x, y) = 1/(1 − x), and we thus obtain the theorem above.

4.3 Limit theorems

We give two limit theorems in the style of Euler’s theorem, as discussed in the introduction. The sequence (a_{0}, a_{1}, a_{2}, …) is defined as in Theorem 4.5.

First, note that removing the empty parts of lecture hall partitions puts the set L_{(a_{1},...,a_{n})} in one-to-one correspondence with the following set:

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

The conditions on the partitions of D_{n} can be restated as

\frac{μ_{i+1}}{μ_{i}} ≥ \frac{a_{n−m+i+1}}{a_{n−m+i}} .

The following lemma implies that D_{n} ⊂ D_{n+2} for all n.

Lemma 4.6 For i ≥ 1, let us denote q_{i} = a_{i+1}/a_{i}. Then the two sequences (q_{2i})_{i≥1} and (q_{2i−1})_{i≥1} are both decreasing, and converge respectively towards θ_{e} and θ_{o} where

θ_{e} = \frac{kℓ + \sqrt{kℓ(kℓ − 4)}}{2ℓ} and θ_{o} = \frac{kℓ + \sqrt{kℓ(kℓ − 4)}}{2k}.

Consequently, the sequence D_{2n} converges, when n tends to infinity, to the set D_{e} of partitions (μ_{1}, …, μ_{m}) such that μ_{1} > 0 and, for i ≥ 1,

\frac{μ_{i+1}}{μ_{i}} > \{ \begin{matrix}θ_{e} & if m + i is even, \\ θ_{o} & if m + i is odd. \end{matrix}

Similarly, the sequence D_{2n+1} converges, when n tends to infinity, to the set D_{o} of partitions (μ_{1}, …, μ_{m}) such that μ_{1} > 0 and, for i ≥ 1,

\frac{μ_{i+1}}{μ_{i}} > \{ \begin{matrix}θ_{o} & if m + i is even, \\ θ_{e} & if m + i is odd. \end{matrix}

Taking the limit n → ∞ in Theorem 4.5 leads to the following result.

Proposition 4.7 The generating function for the elements of D_{e} is

∑_{μ∈D_{e}} x^{|μ|_{e}}y^{|μ|_{o}} = ∏_{i≥1} \frac{1}{1 − x^{a_{i}}y^{a^{i}^{∗}}} .

The generating function for the elements of D_{o} is

∑_{μ∈D_{o}} x^{|μ|_{e}}y^{|μ|_{o}} = ∏_{i≥1} \frac{1}{1 − x^{a_{i+1}}y^{a_{i−1}^{∗}}} .

When k = ℓ, both θ_{e} and θ_{o} are equal to θ = \frac{k+\sqrt{k^{2}−4}}{2}. The proposition above implies the following generalization of Euler’s result:

the partitions of m such that the quotient of consecutive parts is greater than \frac{k+\sqrt{k^{2}−4}}{2} are equinumerous with the partitions of m into parts belonging to the set {e_{1}, e_{2}, …}, with e_{1} = 1, e_{2} = k + 1 and e_{i+1} = ke_{i} − e_{i−1} for i ≥ 2.

For instance, the partitions of m such that the quotient of consecutive parts is greater than (3 + \sqrt{5})/2 are equinumerous with the partitions of m into parts belonging to the set {1, 4, 11, …, F_{2i−1} + F_{2i+1}, …} where F_{i} is the ith Fibonacci number.

5 Strict lecture hall partitions and reciprocity

The enumeration of lecture hall partitions fits in the framework of Ehrhart theory and, more generally, of the theory of linear homogeneous diophantine systems of inequalities [6]. It is thus not surprising that a reciprocity theorem, relating lecture hall partitions and strict lecture hall partitions, holds. We first show that this theorem can be simply derived from the reduction procedure described in Section 3, without using the general theory. Then we study the sequences a such that the generating function for a-lecture hall partitions is self-reciprocal. We give a partial characterization of these sequences in terms of continued fractions.

Let us first state more precisely the connection between lecture hall partitions and Ehrhart’s theory on the enumeration of integer points lying in the integer multiples of a rational convex polytope of IR^{n}. Let a = (a_{1}, …, a_{n}) be a non-decreasing sequence of positive integers, and let P be the following convex polytope of IR^{n}:

P = \{(x_{1}, …, x_{n}) ∈ IR^{n} : x_{1} + ⋯ + x_{n} = 1 and 0 ≤ \frac{x_{1}}{a_{1}} ≤ … ≤ \frac{x_{n}}{a_{n}} \} .

Then an a-lecture hall partition of weight m is exactly an integer point of mP.

5.1 A reciprocity theorem

Let L_{a} denote, as usual, the set of a-lecture hall partitions, and let L̄_{a} denote the set of strict lecture hall partitions:

L̄_{a} = \{(λ_{1}, …, λ_{n}) ∈ IN^{n} : 0 < \frac{λ_{1}}{a_{1}} < … < \frac{λ_{n}}{a_{n}} \} .

We define the complete generating functions for L_{a} and L̄_{a} by

G(X) = ∑_{λ∈L_{a}} X_{1}^{λ_{1}} … X_{n}^{λ_{n}} and Ḡ(X) = ∑_{λ∈L̄_{a}} X_{1}^{λ_{1}} … X_{n}^{λ_{n}}

where G(X) means G(X_{1}, …, X_{n}). Note that G(X) and Ḡ(X) completely describe the sets L_{a} and L̄_{a}.

Proposition 5.1 For any non-decreasing sequence a = (a_{1}, …, a_{n}), the complete generating functions G(X) and Ḡ(X) for a-lecture hall partitions and strict a-lecture hall partitions are rational functions in X_{1}, …, X_{n}. Moreover, they are related by the following identity:

Ḡ(X) = (−1)^{n}G(1/X),

where G(1/X) = G(1/X_{1}, …, 1/X_{n}).

Example. The generating function for partitions (λ_{1}, λ_{2}) satisfying 0 ≤ λ_{1}/3 ≤ λ_{2}/4 is

G(X_{1}, X_{2}) = \frac{1 + X_{1}X_{2}^{2} + X_{1}^{2}X_{2}^{3}}{(1 − X_{2})(1 − X_{1}^{3}X_{2}^{4})}

whereas the generating function for partitions (λ_{1}, λ_{2}) satisfying 0 < λ_{1}/3 < λ_{2}/4 is

Ḡ(X_{1}, X_{2}) = X_{1}X_{2}^{2} \frac{1 + X_{1}X_{2} + X_{1}^{2}X_{2}^{3}}{(1 − X_{2})(1 − X_{1}^{3}X_{2}^{4})} = G(1/X_{1}, 1/X_{2}).

Proof. This result can be derived from Proposition 7.1 in [6], but we are going to give a direct proof. The decomposition of lecture hall partitions into standard and reduced lecture hall partitions described in Section 3 gives

G(X) = \frac{R(X)}{∏_{i=1}^{n}(1 − X_{i}^{a_{i}} ⋯ X_{n}^{a_{n}})},  (14)

where R(X) = ∑_{μ∈R} X_{1}^{μ_{1}} … X_{n}^{μ_{n}} is the complete generating function for reduced lecture hall partitions. Recall that the reduced lecture hall partitions are the partitions μ such that 0 ≤ μ_{1} < a_{1} and for i ≥ 2

0 ≤ \frac{μ_{i}}{a_{i}} − \frac{μ_{i−1}}{a_{i−1}} < 1.  (15)

As there is a finite number of reduced lecture hall partitions, the series G(X) is a rational function. A similar reduction, performed on strict lecture hall partitions, leads to

Ḡ(X) = \frac{R̄(X)}{∏_{i=1}^{n}(1 − X_{i}^{a_{i}} ⋯ X_{n}^{a_{n}})},  (16)

where R̄(X) is the complete generating function for reduced strict lecture hall partitions, that is, partitions (μ_{1}, …, μ_{n}) satisfying 0 < μ_{1} ≤ a_{1} and for i ≥ 2

0 < \frac{μ_{i}}{a_{i}} − \frac{μ_{i−1}}{a_{i−1}} ≤ 1.  (17)

As the set R̄ of reduced strict lecture hall partitions is finite, Ḡ(X) is also a rational function. Combining (14) and (16) proves that the identity of Proposition 5.1 is equivalent to

R̄(X) = R(1/X) ∏_{i=1}^{n} X_{i}^{ia_{i}}.

But this is clear, as the correspondence

(μ_{1}, …, μ_{n}) ⟼ (a_{1} − μ_{1}, …, ia_{i} − μ_{i}, …, na_{n} − μ_{n})

defines a bijection from R to R̄ (this can be easily checked thanks to (15) and (17)).

Remark. The proof above shows that G(X) and Ḡ(X) are rational functions with denominator ∏_{i=1}^{n}(1− X_{i}^{a_{i}} … X_{n}^{a_{n}}). We can actually be a bit more precise. The definition of reduced partitions implies that the polynomials R(X) and R̄(X) will have a factor (1 + X_{n} + ⋯ + X_{n}^{a_{n}−1}). Thus G(X) and Ḡ(X) are rational functions with denominator (1 − X_{n}) ∏_{i=1}^{n−1}(1 − X_{i}^{a_{i}} … X_{n}^{a_{n}}).

Proposition 5.1 provides the following result for strict lecture hall partitions associated with the sequences of Theorem 4.5.

Corollary 5.2 Let (a_{n})_{n≥0} be the sequence defined by a_{0} = 0, a_{1} = 1 and for n ≥ 1,

\{ \begin{matrix}a_{2n} & = ℓa_{2n−1} − a_{2n−2}, \\ a_{2n+1} & = ka_{2n} − a_{2n−1} \end{matrix}

where ℓ and k are two integers ≥ 2. The generating functions for strict (a_{1}, …, a_{2n})-lecture hall partitions and strict (a_{1}, …, a_{2n−1})-lecture hall partitions are respectively given by

∑_{λ∈L̄_{(a_{1},...,a_{2n})}} x^{|λ|_{e}}y^{|λ|_{o}} = ∏_{i=1}^{2n} \frac{x^{a_{i}}y^{a_{i}^{∗}}}{1 − x^{a_{i}}y^{a^{i}^{∗}}}

and

∑_{λ∈L̄_{(a_{1},...,a_{2n−1})}} x^{|λ|_{e}}y^{|λ|_{o}} = ∏_{i=1}^{2n−1} \frac{x^{a_{i+1}^{∗}}y^{a_{i−1}}}{1 − x^{a_{i+1}^{∗}}y^{a_{i−1}}}

where the sequence (a_{n}^{∗})_{n≥1} is defined by the initial conditions a_{1}^{∗} = 0, a_{2}^{∗} = 1 and the same recurrence relations as for a.

Of course this result follows from Proposition 5.1. However, it can be proved directly, that is, without involving reduced lecture hall partitions: the correspondence λ = (λ_{1}, …, λ_{n}) ⟼ λ̄ = (λ_{1} + β_{1}, …, λ_{n} + β_{n}), where

β_{2i} = a_{2i−1} + a_{2i} and β_{2i−1} = a_{2i−1}^{∗} + a_{2i}^{∗},

(equivalently, β_{i} = a_{i} + a_{i}^{∗}) defines a bijection from L_{(a_{1},...,a_{n})} to L̄_{(a_{1},...,a_{n})}. To check this point, one uses the fact that β_{1} = 1 and for i ≥ 2,

a_{i−1}β_{i} − a_{i}β_{i−1} = 1.

But this argument actually proves something more precise than Corollary 5.2; it implies that the complete generating function for strict lecture hall partitions is

Ḡ(X) = G(X) ∏_{i=1}^{n} X_{i}^{β_{i}}.

According to Proposition 5.1, we also have Ḡ(X) = (−1)^{n}G(1/X), and thus G(X) is self-reciprocal:

G(1/X) = (−1)^{n}G(X) ∏_{i=1}^{n} X_{i}^{β_{i}}.

The following paragraph is devoted to the study of sequences a such that the series G(X) is self-reciprocal.

5.2 Self-reciprocal sequences

Definition 5.3 A non-decreasing sequence a = (a_{1}, a_{2}, …, a_{n}) of positive integers is said to be selfreciprocal if the complete generating function G(X) for a-lecture hall partitions is self-reciprocal:

G(1/X) = ±X^{β}G(X)

for some monomial X^{β} = X_{1}^{β_{1}} … X_{n}^{β_{n}}.

According to the reciprocity result 5.1, the sequence a is self-reciprocal if and only if there exists a (strict) lecture hall partition β = (β_{1}, …, β_{n}) such that the correspondence λ ⟼ λ + β defines a bijection from L_{a} to L̄_{a}. In this case, G(1/X) = (−1)^{n}X^{β}G(X).

If such a bijection exists, any strict lecture hall partition (λ_{1}, …, λ_{n}) is such that λ_{i} ≥ β_{i} for all i, and thus β has to be the (unique) minimal strict lecture hall partition, defined by β_{1} = 1 and β_{i+1} = 1 + ⌊a_{i+1}β_{i}/a_{i}⌋ for i ≥ 1.

Proposition 5.4 The sequence a is self-reciprocal if and only if the minimal strict lecture hall partition (β_{1}, …, β_{n}), defined by β_{1} = 1 and β_{i+1} = 1 + ⌊a_{i+1}β_{i}/a_{i}⌋, satisfies

a_{i}β_{i+1} − a_{i+1}β_{i} = gcd(a_{i}, a_{i+1})

for i ≥ 1. In particular, if (a_{1}, …, a_{n}) is self-reciprocal, then (a_{1}, …, a_{n−1}) is also self-reciprocal.

Proof. As stated above, the sequence a is self-reciprocal if the correspondence λ ⟼ λ + β is a bijection from L_{a} to L̄_{a}. Clearly, λ+β belongs to L̄_{a} when λ belongs to L_{a}. Conversely, given λ = (λ_{1}, …, λ_{n}) ∈ L̄_{a}, does λ − β belong to L_{a}? We have λ_{1} − β_{1} = λ_{1} − 1 ≥ 0. Moreover,

\frac{λ_{i+1} − β_{i+1}}{a_{i+1}} ≥ \frac{λ_{i} − β_{i}}{a_{i}} ⟺ a_{i}λ_{i+1} − a_{i+1}λ_{i} ≥ a_{i}β_{i+1} − a_{i+1}β_{i}.

This inequality must hold for all strict lecture hall partitions λ, and thus the condition for a to be selfreciprocal is that for i ≥ 1,

a_{i}β_{i+1} − a_{i+1}β_{i} = min_{λ∈L̄_{a}} {a_{i}λ_{i+1} − a_{i+1}λ_{i}} .

Let g_{i} denote the right-hand term of this identity. Clearly, g_{i} is a positive multiple of gcd(a_{i}, a_{i+1}). A standard consequence of Euclid’s algorithm (sometimes called Bezout’s theorem) is that there exist two integers n_{0} and m_{0} such that a_{i}n_{0} − a_{i+1}m_{0} = gcd(a_{i}, a_{i+1}). Moreover, for any integer k, the pair (n_{k}, m_{k}) = (n_{0} + ka_{i+1}, m_{0} + ka_{i}) also satisfies a_{i}n_{k} − a_{i+1}m_{k} = gcd(a_{i}, a_{i+1}). For a large k, it is clearly possible to construct a strict lecture hall partition λ such that λ_{i} = m_{k} and λ_{i+1} = n_{k}. This proves that g_{i} = gcd(a_{i}, a_{i+1}) and concludes the proof.

This proposition implies that the trivial polynomic sequences, i.e., the sequences (a_{1}, …, a_{n}) such that a_{i}|a_{i+1}, are self-reciprocal. More interestingly, we give below a complete characterization of selfreciprocal sequences such that a_{i} and a_{i+1} are relatively prime. We show that these sequences are natural generalizations of the sequences studied in Section 4. Without proving any of the conjectures given in Section 2, our result partially explains why the (k, ℓ)-sequences are particular.

Proposition 5.5 Let a = (a_{1}, …, a_{n}) be a non-decreasing sequence of positive integers. The following conditions are equivalent:

(i) a is self-reciprocal and gcd(a_{i}, a_{i+1}) = 1 for 1 ≤ i < n,

(ii) there exist n integers u_{1}, …, u_{n} such that u_{1} ≥ 1, u_{i} ≥ 2 for 2 ≤ i ≤ n, and for i ≥ 0

a_{i+1} = u_{i+1}a_{i} − a_{i−1}

with the initial values a_{−1} = 0 and a_{0} = 1. If these conditions are satisfied, the minimal strict lecture hall partition (β_{1}, …, β_{n}) is defined by β_{1} = 1 and β_{i+1} = u_{i+1}β_{i} − β_{i−1} for i ≥ 1, with the initial condition β_{0} = 0.

Proof. Assume that a is self-reciprocal and gcd(a_{i}, a_{i+1}) = 1. According to the criterion of Proposition 5.4, the minimal strict lecture hall partition β satisfies

a_{i}β_{i+1} − a_{i+1}β_{i} = 1  (18)

for i ≥ 0 (with β_{0} = 0 and a_{0} = 1). Taking the difference of two consecutive such identities gives, for i ≥ 1,

a_{i}(β_{i+1} + β_{i−1}) = β_{i}(a_{i+1} + a_{i−1}).  (19)

But according to (18), a_{i} and β_{i} are relatively prime. Thus (19) implies that there exists an integer u_{i+1} such that a_{i+1} + a_{i−1} = u_{i+1}a_{i} and β_{i+1} + β_{i−1} = u_{i+1}β_{i}. Taking u_{1} = a_{1} completes the construction of the sequence (u_{1}, …, u_{n}).

Conversely, in order to prove that the existence of this sequence implies the first point of Proposition 5.5, we first check that the minimal strict lecture hall partition β has the announced form, and then prove, by induction on i, that a_{i}β_{i+1} − a_{i+1}β_{i} = 1. This proves that gcd(a_{i}, a_{i+1}) = 1 and, via the criterion of Proposition 5.4, that a is self-reciprocal.

Example. Let us take n = 3 and (u_{1}, u_{2}, u_{3}) = (2, 3, 5). We obtain (a_{1}, a_{2}, a_{3}) = (2, 5, 23). The generating function G(X) for a-lecture hall partitions is

\frac{1 + X_{2}X_{3}^{5} + X_{2}^{2}X_{3}^{10} + X_{2}^{3}X_{3}^{14} + X_{2}^{4}X_{3}^{19} + X_{1}X_{2}^{3}X_{3}^{14} + X_{1}X_{2}^{4}X_{3}^{19} + X_{1}X_{2}^{5}X_{3}^{23} + X_{1}X_{2}^{6}X_{3}^{28} + X_{1}X_{2}^{7}X_{3}^{33}}{(1 − X_{1}^{2}X_{2}^{5}X_{3}^{23})(1 − X_{2}^{5}X_{3}^{23})(1 − X_{3})} .

It satisfies G(1/X) = −X_{1}X_{2}^{3}X_{3}^{14}G(X).

The minimal strict lecture hall partition β = (1, 3, 14) satisfies the conditions of Proposition 5.4: 2 × 3 − 5 × 1 = 5 × 14 − 23 × 3 = 1.

Remark. Another way of describing the sequences a of the proposition above is the following: for 1 ≤ i ≤ n, the quotient β_{i}/a_{i} is the ith convergent of the continued fraction

\frac{1}{u_{1} − \frac{1}{u_{2} − \frac{1}{...}}} .

That is,

\frac{β_{i}}{a_{i}} = \frac{1}{u_{1} − \frac{1}{u_{2} − \frac{1}{... − \frac{1}{u_{i}}}}} .

For example, the continued fractions associated with the sequences of Theorem 4.5 are

\frac{1}{1 − \frac{1}{ℓ + 1 − \frac{1}{k − \frac{1}{ℓ − \frac{1}{k − \frac{1}{ℓ − \frac{1}{...}}}}}}} .

Since every positive rational number has a unique continued fraction expansion of the form above, this establishes a bijection between self-reciprocal sequences such that gcd(a_{i}, a_{i+1}) = 1 and positive rational numbers.

Acknowledgements. We are grateful to George Andrews for his great encouragement during this work. We would like also to thank Philippe Flajolet, Sergei Kerov and Svante Linusson for helpful comments and discussions.

References

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

[2] G. E. Andrews, MacMahon’s partition analysis: I. The lecture hall partition theorem, preprint, 1996.

[3] M. Bousquet-Mélou and K. Eriksson, Lecture hall partitions, Report LaBRI 1107-96, Université Bordeaux 1, 1996. To appear in The Ramanujan Journal.

[4] L. Euler, Introductio in analysin infinitorum, Chapter 16. Marcum-Michaelem Bousquet, Lausannae, 1748. French translation: Introduction à l’analyse infinitésimale, ACL éditions, Paris, 1987.

[5] P. A. MacMahon, Combinatory analysis, 2 vols., Cambridge University Press, Cambridge, 1915–1916 (Reprinted: Chelsea, New-York, 1960).

[6] R. P. Stanley, Combinatorial reciprocity theorems, Adv. Math. 14 (1974) 194–253.