Séminaire Lotharingien de Combinatoire 54A (2005), Article B54Aa

ENUMERATION OF SEQUENCES CONSTRAINED BY THE RATIO OF CONSECUTIVE PARTS

SYLVIE CORTEEL*, SUNYOUNG LEE^{†}, AND CARLA D. SAVAGE^{‡}

Abstract. Recurrences are developed to enumerate any family of nonnegative integer sequences λ = (λ_{1}, …, λ_{n}) satisfying the constraints:

\frac{λ_{1}}{a_{1}} ≥ \frac{λ_{2}}{a_{2}} ≥ ⋯ ≥ \frac{λ_{n−1}}{a_{n−1}} ≥ \frac{λ_{n}}{a_{n}} ≥ 0,

for a given constraint sequence a = [a_{1}, …, a_{n}] of positive integers. They are applied to derive new counting formulas, to reveal new relationships between families, and to give simple proofs of the truncated lecture hall and anti-lecture hall theorems.

Résumé. Nous développons des récurrences pour énumérer des familles de suites d’entiers λ = (λ_{1}, …, λ_{n}) satisfaisant les contraintes

\frac{λ_{1}}{a_{1}} ≥ \frac{λ_{2}}{a_{2}} ≥ ⋯ ≥ \frac{λ_{n−1}}{a_{n−1}} ≥ \frac{λ_{n}}{a_{n}} ≥ 0,

pour une suite d’entiers positifs donnée a = [a_{1}, …, a_{n}]. Ces récurrences permettent de dériver de nouvelles formules dénumération, de révéler de nouvelles relations entre certaines familles, et de donner des preuves simples des théorèmes des partitions Lecture Hall tronquées et des compositions Lecture Hall tronquées.

1. Introduction

We consider the problem of enumerating nonnegative integer sequences λ = (λ_{1}, …, λ_{n}) satisfying the constraints:

\frac{λ_{1}}{a_{1}} ≥ \frac{λ_{2}}{a_{2}} ≥ ⋯ ≥ \frac{λ_{n−1}}{a_{n−1}} ≥ \frac{λ_{n}}{a_{n}} ≥ 0,  (1)

for a given constraint sequence a = [a_{1}, …, a_{n}] of positive integers.

We refer to a sequence λ = (λ_{1}, …, λ_{n}) of nonnegative integers as a composition into n nonnegative parts. If the parts of λ are nonincreasing, then λ is a partition. Partitions and compositions are commonly defined by the set of parts allowed, the number of occurrences of a part, or the difference between consecutive parts. In

* CNRS PRiSM, UVSQ, 45 Avenue des Etats-Unis, 78035 Versailles, France.

(syl@prism.uvsq.fr).

† Computer Science, North Carolina State University, Box 8206, Raleigh, NC 27695, USA. (slee7@unity.ncsu.edu) Research supported in part by NSF grant DMS-0300034.

‡ Computer Science, North Carolina State University, Box 8206, Raleigh, NC 27695, USA. (savage@csc.ncsu.edu) Research supported in part by NSF grants DMS-0300034 and INT-0230800.

contrast, the compositions satisfying (1) are constrained by the ratio of consecutive parts and we refer to them as ratio compositions. Generating functions are known for ratio compositions only for some special constraint sequences, a, including:

a = [1, 1, …, 1]: ordinary partitions [1];

a = [1, 2, 4, …, 2^{n−1}]: Cayley compositions [8, 2, 14, 4]; a = [r^{n−1}, r^{n−2}, …, r, 1]: Hickerson partitions [13]; a = [n, n − 1, …, 1]: lecture hall partitions [5, 6, 7, 15, 16, 3]; a = [1, 2, …, n]: anti-lecture hall compositions [9]; a = [1, 2, 1, 2, ..., 2 − (−1)^{n}]: one-two compositions [11]; a = [n, n − 1 …, n − t + 1]: truncated lecture hall partitions [10]; a = [n−t+1, n−t, …, n]: truncated anti-lecture hall compositions [10].

In this paper, we introduce a common approach for the enumeration of ratio compositions by using as a statistic a bound on the size of the first part. This generalizes the enumeration of ordinary partitions via the Gaussian polynomials.

In Section 2, we derive a recurrence for the generating function of any family of ratio compositions with first part bounded. We use this to derive new counting formulas and their q-analogs. Among these, we discover a family of polynomials with several interesting properties which arise in the enumeration of lecture hall partitions. In addition, we find a functional relationship between the generating functions for the ratio compositions constrained by a sequence [a_{1}, a_{2}, …, a_{n}] and those constrained by its reverse sequence [a_{n}, a_{n−1} …, a_{1}]. This reveals for the first time the relationship between, e.g., lecture hall partitions and anti-lecture hall compositions and between Hickerson partitions and Cayley compositions.

In Section 3, we derive a different recurrence for the enumeration of ratio compositions with first part bounded. By allowing the bound to approach infinity, we get a recurrence for the generating function of any family of ratio compositions with first part unbounded. As one consequence, we discover new “easy” proofs of the (truncated) lecture hall and (truncated) anti-lecture hall theorems. In contrast to earlier proofs, where deriving a recurrence was a challenge, here the recurrence is generic and the work is moved entirely to “standard” q-series manipulation in an induction proof.

2. Enumeration of ratio compositions with first part bounded

To build a recurrence, let [a_{1}, …, a_{n}] = [s_{n}, s_{n−1}, …, s_{1}] for an infinite sequence of positive integers {s_{i}}. For n ≥ 0, let S_{n} be the set of compositions λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying

\frac{λ_{1}}{s_{n}} ≥ \frac{λ_{2}}{s_{n−1}} ≥ ⋯ ≥ \frac{λ_{n−1}}{s_{2}} ≥ \frac{λ_{n}}{s_{1}} ≥ 0.  (2)

Let S_{n}^{(j,i)} be the set of λ ∈ S_{n} with λ_{1} ≤ js_{n} + i and let

S_{n}^{(j,i)}(q) = ∑_{λ∈S_{n}^{(j,i)}} q^{|λ|}.

Theorem 1. For n ≥ 0, j ≥ 0, and 0 ≤ i ≤ s_{n},

S_{n}^{(j,i)}(q) = \{ \begin{matrix}1 & if n = 0 or j = i = 0, else \\ S_{n}^{(j−1,s_{n})}(q) & if i = 0, else \\ S_{n}^{(j,i−1)}(q) + q^{js_{n}+i}S_{n−1}^{(j,⌊is_{n−1}/s_{n}⌋)}(q) & otherwise. \end{matrix}

Proof. The theorem is clearly true for n = 0 and for j = i = 0. Let (n, j, i) satisfy n > 0, (j, i) > (0, 0). If i = 0, then j > 0 and js_{n} + i = js_{n} = (j − 1)s_{n} + s_{n}, so the theorem is true. Assume, then, that 1 ≤ i ≤ s_{n}. By definition, λ ∈ S_{n}^{(j,i)} if and only if either λ ∈ S_{n}^{(j,i−1)} or λ ∈ S_{n} and λ_{1} = js_{n} + i. But (js_{n} + i, λ_{2}, …, λ_{n}) ∈ S_{n} if and only if (λ_{2}, …, λ_{n}) ∈ S_{n−1} and (js_{n} + i)/λ_{2} ≥ s_{n}/s_{n−1}. That is,

λ_{2} ≤ \frac{s_{n−1}}{s_{n}} (js_{n} + i) = js_{n−1} + i\frac{s_{n−1}}{s_{n}} .

So, since λ_{2} is an integer,

λ_{2} ≤ js_{n−1} + ⌊i\frac{s_{n−1}}{s_{n}} ⌋.

Note, since 1 ≤ i ≤ s_{n}, ⌊is_{n−1}/s_{n}⌋ ≤ s_{n−1}, so (λ_{2}, …, λ_{n}) ∈ S_{n−1}^{(j,⌊is_{n−1}/s_{n}⌋)}. □

Remark 1. For ordinary partitions, P_{n}, into n nonnegative parts, {s_{i}} = {1} and ⌊is_{n−1}/s_{n}⌋ = i, so the recurrence of Theorem 1 reduces to the recurrence

P_{n}^{(j,i)}(q) = P_{n}^{(j,i−1)}(q) + q^{j+i}P_{n−1}^{(j,i)}(q),

the familiar recurrence for Gaussian polynomials.

The lecture hall partitions [5], L_{n}, are those compositions, necessarily partitions, satisfying

\frac{λ_{1}}{n} ≥ \frac{λ_{2}}{n − 1} ≥ ⋯ ≥ \frac{λ_{n−1}}{2} ≥ \frac{λ_{n}}{1} ≥ 0.  (3)

Then L_{n} = S_{n} with {s_{i}} = {i} in (2). Since ⌊i(n − 1)/n⌋ = i − 1 we get the following from Theorem 1.

Corollary 1. For n ≥ 0, j ≥ 0, and 0 ≤ i ≤ n, let L_{n}^{(j,i)}(q) be the generating function for the lecture hall partitions λ ∈ L_{n} with λ_{1} ≤ jn + i.

L_{n}^{(j,i)} = \{ \begin{matrix}1 & if n = 0 or j = i = 0, else \\ L_{n}^{(j−1,n)}(q) & if i = 0, else \\ L_{n}^{(j,i−1)}(q) + q^{jn+i}L_{n−1}^{(j,i−1)}(q) & otherwise. \end{matrix}

For fixed n > 0, any t ≥ 0 can be written uniquely in the form t = jn + i, where 0 ≤ i < n. So, we get a nice counting formula for lecture hall partitions with largest part at most t.

Theorem 2. For n ≥ 0, j ≥ 0, and 0 ≤ i ≤ n, the number of lecture hall partitions in L_{n} with first part bounded by jn + i is

L_{n}^{(j,i)} = (j + 1)^{n−i}(j + 2)^{i}.

Proof. If n = 0 then i = 0, so (j + 1)^{0−0}(j + 2)^{0} = 1. If i = j = 0, then (1)^{n−0}(2)^{0} = 1. Let (n, j, i) satisfy n > 0, (j, i) > (0, 0) and assume the theorem is true for (n′, i′, j′) < (n, i, j). If i = 0, then j > 0 and by Corollary 1, L_{n}^{(j,0)}(1) = L_{n}^{(j−1,n)}(1), which, by induction, is (j)^{n−n}(j + 1)^{n} = (j + 1)^{n}(j + 2)^{0}. Otherwise, by Corollary 1,

L_{n}^{(j,i)}(1) = L_{n}^{(j,i−1)}(1) + L_{n−1}^{(j,i−1)}(1)
= (j + 1)^{n−i+1}(j + 2)^{i−1} + (j + 1)^{n−i}(j + 2)^{i−1}
= (j + 1)^{n−i}(j + 2)^{i}.

□

In [5], it was shown that the generating function for the lecture hall partitions, L_{n} is:

L_{n}(q) = \frac{1}{(q; q^{2})_{n}} ,  (4)

where (a; q)_{n} = (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}). Let D be the set of partitions into distinct parts and let O be the set of partitions into odd parts. The sets D and O have generating functions D(q) = (−q; q)_{∞} and O(q) = (q; q^{2})_{∞}^{−1}, respectively. Since lim_{n→∞} L_{n} = D, the Lecture Hall Theorem (4) is a finite version of Euler’s Theorem which says that D(q) = O(q). The polynomial L_{n}^{(j)}(q) = L_{n}^{(j,0)}(q) can be viewed as a q-analog of (j + 1)^{n} that encapsulates a further finitization of Euler’s Theorem in the following sense.

Corollary 2. The lecture hall polynomials L_{n}^{(j)}(q) satisfy

(i) L_{n}^{(j)}(1) = (j + 1)^{n},

(ii) lim_{n→∞} L_{n}^{(j)}(q) = (−q; q)_{∞}, and

(iii) lim_{j→∞} L_{n}^{(j)}(q) = (q; q^{2})_{n}^{−1}.

Proof. The first equation follows from Theorem 2. The second and third follow from the observations that lim_{n→∞} L_{n}^{(j)} = D and lim_{j→∞} L_{n}^{(j)} = L_{n}. □

The anti-lecture hall compositions [9], A_{n}, are those sequences satisfying

\frac{λ_{1}}{1} ≥ \frac{λ_{2}}{2} ≥ ⋯ ≥ \frac{λ_{n−1}}{n − 1} ≥ \frac{λ_{n}}{n} ≥ 0.  (5)

It was shown in [9] that A_{n} has generating function A_{n}(q) = (−q, q)_{n}/(q^{2}; q)_{n}. The constraint sequence for A_{n}, in the sense of (1), is [1, 2, …, n], the reverse of the constraint sequence [n, n − 1, …, 1] for L_{n}. We introduce some notation to describe the relationship between their generating functions. Let S[a_{1}, a_{2}, …, a_{k}] be the set of compositions λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying

\frac{λ_{1}}{a_{1}} ≥ \frac{λ_{2}}{a_{2}} ≥ ⋯ ≥ \frac{λ_{n−1}}{a_{n−1}} ≥ \frac{λ_{n}}{a_{n}} ≥ 0,  (6)

with S^{(j,i)}[a_{1}, a_{2}, …, a_{n}] denoting those with λ_{1} ≤ ja_{1} +i and let S^{(j)}[a_{1}, a_{2}, …, a_{n}] = S^{(j,0)}[a_{1}, a_{2}, …, a_{n}].

Theorem 3. The generating functions for S^{(j)}[a_{1}, a_{2}, …, a_{n}] and S^{(j)}[a_{n}, a_{n−1}, …, a_{1}] satisfy:

S^{(j)}[a_{1}, a_{2}, …, a_{n}](q) = q^{j(a_{1}+a_{2}+···+a_{n})}S^{(j)}[a_{n}, a_{n−1}, …, a_{1}](1/q).

Proof. The result follows if we show that λ ∈ S^{(j)}[a_{n}, a_{n−1}, …, a_{1}] if and only if μ ∈ S^{(j)}[a_{1}, a_{2}, …, a_{n}], where μ is defined by μ_{i} = js_{i} − λ_{n+1−i}.

So, assume λ ∈ S^{(j)}[a_{n}, a_{n−1}, …, a_{1}], that is, λ_{1} ≤ ja_{n} and a_{i}λ_{n−i} ≥ a_{i+1}λ_{n+1−i} for 1 ≤ i ≤ n. Then for 1 ≤ i ≤ n,

λ_{n+1−i} ≤ \frac{a_{i}}{a_{i+1}} \frac{a_{i+1}}{a_{i+2}} ⋯ \frac{a_{n−1}}{a_{n}} a_{n}j = a_{i}j,

so μ_{i} = ja_{i} − λ_{n+1−i} ≥ 0. Also, μ_{1} = ja_{1} − λ_{n} satisfies μ_{1} ≤ ja_{1}. To show μ ∈ S^{(j)}[a_{1}, a_{2}, …, a_{n}], it remains to show a_{i+1}μ_{i} ≥ a_{i}μ_{i+1}:

a_{i+1}μ_{i} = a_{i+1}(ja_{i} − λ_{n+1−i}) = ja_{i}a_{i+1} − a_{i+1}λ_{n+1−i} ≥ ja_{i}a_{i+1} − a_{i}λ_{n−i} = a_{i}μ_{i+1}.

The converse is similar. □

Remark 2. The proof of Theorem 3 also shows that for 1 ≤ i ≤ n, λ ∈ S^{(j)}[a_{n}, a_{n−1}, …, a_{1}] if and only if μ ∈ S^{(j+1)}[a_{1}, a_{2}, …, a_{n}] and μ_{n} ≥ a_{n} − i.

Corollary 3. Lecture hall partitions, L_{n}^{(j)}, with first part bounded by jn and antilecture hall compositions, A_{n}^{(j)} with first part bounded by j have the following relationship:

A_{n}^{(j)}(q) = q^{jn(n+1)/2}L_{n}^{(j)}(1/q).

Proof. Observe that A_{n}^{(j)} = S^{(j)}[1, 2, …, n] and L_{n}^{(j)} = S^{(j)}[n, n − 1, …, 1] and apply Theorem 3. □

This gives a counting formula for anti-lecture hall compositions.

Corollary 4. The number of anti-lecture hall compositions in A_{n} with first part bounded by j is

A_{n}^{(j)}(1) = (j + 1)^{n}.

Proof. By Theorem 3, A_{n}^{(j)}(1) = L_{n}^{(j)}(1). By definition, L_{n}^{(j)}(q) = L_{n}^{(j,0)}(q), and by Corollary 2, L_{n}^{(j,0)}(1) = (j + 1)^{n}(j + 2)^{0}. □

As another example of the application of Theorems 1 and 3, we consider Hickerson partitions H_{n} (for r = 2) and Cayley compositions, C_{n}. H_{n} is the set of compositions into n nonnegative parts satisfying λ_{i} ≥ 2λ_{i+1} and C_{n} is the set of compositions into n nonnegative parts satisfying λ_{i} ≥ λ_{i+1}/2. So, H_{n} = S[2^{n−1}, 2^{n−2}, …, 1] and C_{n} = S[1, 2, 4, …, 2^{n−1}]. Let B(n) be the number of binary partitions of n, i.e., the number of partitions of n into powers of 2. It is easy to check that B(0) = B(1) = 1, B(2n) = B(2n − 2) + B(n), and B(2n) = B(2n + 1).

Theorem 4. For 0 ≤ i < 2^{n−1}, the number of Hickerson partitions with first part at most i is H_{n}^{(0,i)} = B(2i); with first part at most 2^{n−1} + i is H_{n}^{(1,i)} = B(2^{n} + 2i); with first part at most 2^{n} is H_{n}^{(2,0)} = B(2^{n+1}) − 1.

Proof. Use the recurrence of Theorem 1 with the observation that since {s_{i}} = {2^{i−1}} for Hickerson partitions, ⌊is_{i−1}/s_{i}⌋ = ⌊i/2⌋. The theorem follows by induction using the properties of B(n). □

Cayley’s Theorem [8] says that the number of compositions in C_{n} with n positive parts and with first part 1 is equal to the number of partitions of 2^{n−1} − 1 into parts from the set {1, 1′, 2, 4, …, 2^{n−2}}. If we apply Theorem 3 and Remark 2, we get a generalization and reformulation of Cayley’s Theorem.

Theorem 5. For 0 ≤ i < 2^{n−1}, the number of Cayley compositions into n positive parts with first part 1 and last part at least 2^{n−1} − i is B(2i). The number with first part at most 2 and last part at least 2^{n} − i is B(2^{n} + 2i).

Setting i = 2^{n−1} − 1 in Theorem 5 gives:

Corollary 5. The number of Cayley compositions into n positive parts with first part 1 is B(2^{n} − 2); with first part at most 2 is B(2^{n+1} − 2).

These results can be generalized to r-ary Hickerson partitions and Cayley compositions. For other families of ratio compositions, we can expect Theorem 1 to be most useful for sequences {s_{i}} where ⌊is_{n−1}/s_{n}⌋ has a nice form.

As t gets larger, solving for H_{n}^{(t)} gets harder. This is in spite of the fact that H_{n} has the nice generating function H_{n}(q) = ∏_{t=1}^{n}(1 − q^{2^{t}−1})^{−1} [13]. However, we will see in the next section that if S_{n}^{(j)}(q) has a nice generating function when j = 1, there is hope that lim_{j→∞} S_{n}^{(j)}(q) will also.

In the next section we show how to get a recurrence for the generating function of ratio compositions when the first part unrestricted.

3. Enumeration of ratio sequences with first part unbounded.

We define two slight variations of the set S^{(j)}[a_{1}, a_{2}, …, a_{n}] below:

P^{(j)}[a_{1}, a_{2}, …, a_{n}] = {λ ∈ S^{(j)}[a_{1}, a_{2}, …, a_{n}] | λ_{n} ≥ 1};
R^{(j)}[a_{1}, a_{2}, …, a_{n}] = {λ ∈ S^{(j)}[a_{1}, a_{2}, …, a_{n}] | λ_{1} < ja_{1}}.

In P^{(j)}, all parts must be positive, whereas in R^{(j)} parts can be nonnegative, but the bound on the first part becomes strict.

Theorem 6. For j ≥ 1,

P^{(j)}[a_{1}, a_{2}, …, a_{k}](q) = ∑_{t=0}^{k} q^{(a_{1}+a_{2}+···+a_{t})}P^{(1)}[a_{t+1}, …, a_{k}](q)P^{(j−1)}[a_{1}, …, a_{t}](q).

Proof. Let λ ∈ P^{(j)}[a_{1}, a_{2}, …, a_{k}] and let t be the maximum index such that λ_{t} > a_{t}. Then (λ_{1} − a_{1}, λ_{2} − a_{2}, …, λ_{t} − a_{t}) ∈ P^{(j−1)}[a_{1}, …, a_{t}] and (λ_{t+1}, …, λ_{k}) ∈ P^{(1)}[a_{t+1}, …, a_{k}]. □

Note that P^{(1)}(q) can be computed using Theorem 1 as

P^{(1)}[s_{n}, …, s_{1}](q) = S_{n}^{(1,0)}[s_{1}, …, s_{n}](q) − S_{n−1}^{(1,0)}[s_{2}, …, s_{n}](q).

Thus, taking the limit as j → ∞ in Theorem 6 gives a recurrence for counting the sequences λ in P [a_{1}, a_{2}, …, a_{k}] without a restriction on the size of the first part.

Theorem 7. For n ≥ k,

P [a_{1}, a_{2}, …, a_{k}](q) = ∑_{t=0}^{k} q^{(a_{1}+a_{2}+···+a_{t})}P^{(1)}[a_{t+1}, …, a_{k}](q)P [a_{1}, a_{2}, …, a_{t}](q).

Remark 3. Theorem 6 and its proof are valid with all occurrences of P replaced by R. We need only change the statement “let t be the maximum index such that λ_{t} > a_{t}” to “let t be the maximum index such that λ_{t} ≥ a_{n−t+1}”. Similarly, Theorem 7 holds with P replaced by R.

Theorem 7 can be used to find an explicit form for the generating function in families where P^{(1)}[a_{1}, …, a_{k}] (or R^{(1)}[a_{1}, …, a_{k}]) is known.

Remark 4. For ordinary partitions into k positive parts, a_{i} = 1, so

P [a_{1}, a_{2}, …, a_{k}](q) = (q; q)_{k}^{−1}

and

P^{(1)}[a_{t+1}, …, a_{k}](q) = q^{k−t},

and the recurrence of Theorem 7 becomes

\frac{1}{(q; q)_{k}} = ∑_{t=0}^{k} \frac{q^{k}}{(q; q)_{t}} ,

which counts partitions into k positive parts by summing over the number, t, of parts greater than 1. □

The partitions L_{n,k} = P [n, n − 1, …, n − k + 1] are called truncated lecture hall partitions with all parts positive. The compositions A_{n,k} = R[n−k+1, n−k+2, …, n] are called truncated anti-lecture hall compositions with nonnegative parts. These were introduced in [10] where their generating functions were shown to be

L_{n,k}(q) = q^{\binom{k+1}{2}} [ \begin{matrix}n \\ k \end{matrix} ]_{q} \frac{(−q^{n−k+1}; q)_{k}}{(q^{2n−k+1}; q)_{k}} ,  (7)

A_{n,k}(q) = [ \begin{matrix}n \\ k \end{matrix} ]_{q} \frac{(−q^{n−k+1}; q)_{k}}{(q^{2(n−k+1)}; q)_{k}} .  (8)

We now show how Theorem 7 can be used to give simple proofs of the (Truncated) Lecture Hall and (Truncated) Anti-lecture Hall Theorems. We begin by computing P^{(1)}[n, n − 1, …, n − k + 1](q) for L_{n,k} and R^{(1)}[n − k + 1, n − k + 2, …, n](q) for A_{n,k}.

Lemma 1. For n ≥ k ≥ 1, the generating function for truncated lecture hall partitions into k positive parts with first part less than or equal to n is

P^{(1)}[n, n − 1, …, n − k + 1](q) = q^{\binom{k+1}{2}} [ \begin{matrix}n \\ k \end{matrix} ]_{q} .

Proof. We show that P^{(1)}[n, n−1, …, n−k +1] is the set of partitions into k distinct parts from {1, 2, …, n}, which has the generating function claimed. If λ ∈ P^{(1)}[n, n− 1, …, n − k + 1], 1 ≥ λ_{1}/n ≥ λ_{2}/(n − 1) ≥ ⋯ ≥ λ_{k}/(n − k + 1) > 0, so the parts of λ are distinct and bounded by n. Conversely, if λ_{i} ≥ λ_{i+1} + 1 for 1 ≤ i ≤ n − 1 and λ_{1} ≤ n, then λ_{i+1} ≤ n − i, so

λ_{i}(n−i) ≥ (λ_{i+1} +1)(n−i) ≥ λ_{i+1}(n−i)+n−i ≥ λ_{i+1}(n−i)+λ_{i+1} ≥ λ_{i+1}(n−i+1),

that is, λ_{i}/(n − i + 1) ≥ λ_{i+1}/(n − i), so λ ∈ P^{(1)}[n, n − 1, …, n − k + 1]. □

Lemma 2. For n ≥ k ≥ 1, the generating function for truncated anti-lecture hall compositions into k nonnegative parts with first part less than n − k + 1 is

R^{(1)}[n − k + 1, n − k + 2, …, n](q) = [ \begin{matrix}n \\ k \end{matrix} ]_{q} .

Proof. If λ ∈ R^{(1)}[n − k + 1, n − k + 2, …, n], then for 1 ≤ i ≤ n, λ_{i} < n − k + i and λ_{i−1} ≥ λ_{i}(n − k + i − 1)/(n − k + i), so

λ_{i−1} − λ_{i} ≥ λ_{i}((n − k + i − 1)/(n − k + i) − 1) = −λ_{i}/(n − k + i) > −1.

Thus, λ_{i−1} − λ_{i} ≥ 0 and λ is a partition into at most k parts of size at most n − k. Conversely, any such partition is in R^{(1)}[n − k + 1, n − k + 2, …, n]. □

Corollary 6.

|L_{n,k}^{(j)}| = (j)^{k}\binom{n}{k} = |A_{n,k}^{(j)}|.

Proof. By induction. It is obviously true for j = 0. Then for j > 0, by Theorem 6 and Lemma 2,

L_{n,k}^{(j)}(1) = ∑_{t=0}^{k} \binom{n − t}{k − t}\binom{n}{t}(j − 1)^{t}.

We use the classical identity \binom{n−t}{k−t}\binom{n}{t} = \binom{n}{k}\binom{k}{t} and the binomial theorem and get the result. By Theorem 3, L_{n,k}^{(j)}(1) = A_{n,k}^{(j)}(1). □

Lemma 3. The generating function for truncated lecture hall partitions satisfies

L_{n,k}(q) = q^{\binom{k+1}{2}} ∑_{t=0}^{k} q^{(n−k)t} [ \begin{matrix}n − t \\ k − t \end{matrix} ]_{q} L_{n,t}(q),

for k ≥ 1 and L_{n,0}(q) = 1.

Proof. Since L_{n,k} = P [n, n − 1, …, n − k + 1], apply Theorem 7 with Lemma 1 to get

L_{n,k}(q) = ∑_{t=0}^{k} q^{n+(n−1)+···+(n−t+1)}q^{\binom{k−t+1}{2}} [ \begin{matrix}n − t \\ k − t \end{matrix} ]_{q} L_{n,t}(q)

and simplify. □

This gives the Truncated Lecture Hall Theorem:

Theorem 8. [10]

L_{n,k}(q) = q^{\binom{k+1}{2}} [ \begin{matrix}n \\ k \end{matrix} ]_{q} \frac{(−q^{n−k+1}; q)_{k}}{(q^{2n−k+1}; q)_{k}} .

Proof. Let

L_{n,k}(q) = \frac{L_{n,k}(q)}{q^{\binom{k+1}{2}} [ \begin{matrix}n \\ k \end{matrix} ]_{q}} .

We show

L_{n,k}(q) = \frac{(−q^{n−k+1}; q)_{k}}{(q^{2n−k+1}; q)_{k}} .  (9)

Substituting for L_{n,k}(q) and L_{n,t}(q) in the recurrence of Lemma 3 and simplifying gives L_{n,1} = 1 and for k > 1,

L_{n,k}(q) = ∑_{t=0}^{k} q^{(n−k)t+\binom{t+1}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} L_{n,t}(q),  (10)

as

[ \begin{matrix}n − t \\ k − t \end{matrix} ]_{q} [ \begin{matrix}n \\ t \end{matrix} ]_{q} = [ \begin{matrix}n \\ k \end{matrix} ]_{q} [ \begin{matrix}k \\ t \end{matrix} ]_{q} .

We make use of (a transformation of) one of the q-Chu Vandermonde identities (1.5.2) from [12]:

\frac{(−aq; q)_{k}}{(cq; q)_{k}} = ∑_{t=0}^{k} a^{t}q^{\binom{t+1}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} \frac{(−(c/a)q^{−t+1}; q)_{t}}{(cq^{k−t+1}; q)_{t}} .

We do the substitution a = q^{n−k} and c = q^{2n−k} and get

\frac{(−q^{n−k+1}; q)_{k}}{(q^{2n−k+1}; q)_{k}} = ∑_{t=0}^{k} q^{t(n−k)+\binom{t+1}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} \frac{(−q^{n−t+1}; q)_{t}}{(q^{2n−t+1}; q)_{t}} ,

which shows that L_{n,k}(q) as given by (9) is the solution to the recurrence (10).

From this we also get the Lecture Hall Theorem: Theorem 9. [5]

L_{n}(q) = \frac{(−q; q)_{n}}{(q^{n+1}; q)_{n}} = \frac{1}{(q; q^{2})_{n}} .

Proof. Setting k = n in Theorem 8 gives L_{n,n}, which is the set of partitions in L_{n} with all parts positive. So, L_{n,n}(q) = q^{\binom{n+1}{2}}L_{n}(q). □

The approach for truncated anti-lecture hall compositions is similar. Lemma 4. For n ≥ k,

A_{n,k}(q) = ∑_{t=0}^{k} q^{(n−k)t+\binom{t+1}{2}} [ \begin{matrix}n \\ k − t \end{matrix} ]_{q} A_{n−k+t,t}(q)

with A_{n,k}^{(0)}(q) = 1.

Proof. Since A_{n,k} = R[n − k + 1, n − k + 2, …, n], apply Theorem 7, using Remark 3, then Lemma 2 and simplify. □

Now we get an easy proof of the Truncated Anti-lecture Hall Theorem. Theorem 10. [10]

A_{n,k}(q) = [ \begin{matrix}n \\ k \end{matrix} ]_{q} \frac{(−q^{n−k+1}; q)_{k}}{(q^{2(n−k+1)}; q)_{k}} .

Proof. Let

A_{n,k}(q) = \frac{A_{n,k}(q)}{[ \begin{matrix}n \\ k \end{matrix} ]_{q}}.

Then using Lemma 4, we get that

A_{n,k}(q) = ∑_{t=0}^{k} q^{(n−k)t+\binom{t+1}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} A_{n−k+t,t}(q),  (11)

as

[ \begin{matrix}n \\ k \end{matrix} ]_{q} [ \begin{matrix}k \\ k − t \end{matrix} ]_{q} = [ \begin{matrix}n − k + t \\ t \end{matrix} ]_{q} [ \begin{matrix}n \\ k − t \end{matrix} ]_{q} .

We make use of another transformation of the q-Chu Vandermonde identity (1.5.2) from [12]:

\frac{(−c/a; q)_{k}}{(c; q)_{k}} = ∑_{t=0}^{k}(c/a)^{t}q^{\binom{t}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} \frac{(−a; q)_{t}}{(c; q)_{t}} .

Set c = q^{2(n−k+1)} and a = q^{n−k+1} and get

\frac{(−q^{n−k+1}; q)_{k}}{(q^{2(n−k+1)}; q)_{k}} = ∑_{t=0}^{k} q^{(n−k)t+\binom{t+1}{2}} [ \begin{matrix}k \\ t \end{matrix} ]_{q} \frac{(−q^{n−k+1}; q)_{k}}{(q^{2(n−k+1)}; q)_{k}} ,

showing A_{n,k}(q) = \frac{(−q^{n−k+1};q)_{k}}{(q^{2(n−k+1)};q)_{k}} satisfies the recurrence. □

Setting k = n in Theorem 10 gives the Anti-Lecture Hall Theorem.

Theorem 11. [9]

A_{n}(q) = \frac{(−q; q)_{n}}{(q^{2}; q)_{n}} .

4. Concluding Remarks

The recurrences of Theorems 1 and 7 provide simple computational tools to investigate any family of ratio compositions. More importantly, they supply the foundation for an inductive proof of any conjectured enumeration result. Our experiments suggest that counting formulas and generating functions will be possible for many other families of ratio compositions.

One particular question of interest is to characterize the subfamily of partitions into odd parts in {1, 3, …, 2n − 1} that is counted by the polynomial L_{n}^{(j)}(q).

References

[1] George E. Andrews. The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.- London-Amsterdam, 1976. Encyclopedia of Mathematics and its Applications, Vol. 2.

[2] George E. Andrews. The Rogers-Ramanujan reciprocal and Minc’s partition function. Pacific J. Math., 95(2):251–256, 1981.

[3] George E. Andrews. MacMahon’s partition analysis. I. The lecture hall partition theorem. In Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), volume 161 of Progr. Math., pages 1–22. Birkhäuser Boston, Boston, MA, 1998.

[4] George E. Andrews, Peter Paule, Axel Riese, and Volker Strehl. MacMahon’s partition analysis. V. Bijections, recursions, and magic squares. In Algebraic combinatorics and applications (Gößweinstein, 1999), pages 1–39. Springer, Berlin, 2001.

[5] Mireille Bousquet-Mélou and Kimmo Eriksson. Lecture hall partitions. Ramanujan J., 1(1):101– 111, 1997.

[6] Mireille Bousquet-Mélou and Kimmo Eriksson. Lecture hall partitions II. Ramanujan J., 1(2):165–185, 1997.

[7] Mireille Bousquet-Mélou and Kimmo Eriksson. A refinement of the lecture hall theorem. J. Combin. Theory. Ser. A, 86(1):63–84, 1999.

[8] Arthur Cayley. On a problem in the partition of numbers. Philosophical Magazine, 13:245– 248, 1857. reprinted in: The Collected Mathematical Papers of A. Cayley, Vol. III, Cambridge University Press, Cambridge, 1890, 247-249).

[9] Sylvie Corteel and Carla D. Savage. Anti-lecture hall compositions. Discrete Math., 263(1-3):275–280, 2003.

[10] Sylvie Corteel and Carla D. Savage. Lecture hall theorems, q-series and truncated objects. J. Combin. Theory Ser. A, 108(2):217–245, 2004.

[11] Sylvie Corteel and Carla D. Savage. Partitions and compositions defined by inequalities. Ramanujan J., 8(3):357–381, 2004.

[12] George Gasper and Mizan Rahman. Basic hypergeometric series, volume 35 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1990. With a foreword by Richard Askey.

[13] Dean R. Hickerson. A partition identity of the Euler type. Amer. Math. Monthly, 81:627–629, 1974.

[14] Henryk Minc. A problem in partitions: Enumeration of elements of a given degree in the free commutative entropic cyclic groupoid. Proc. Edinburgh Math. Soc. (2), 11:223–224, 1958/1959.

[15] Ae Ja Yee. On the combinatorics of lecture hall partitions. Ramanujan J., 5(3):247–262, 2001.

[16] Ae Ja Yee. On the refined lecture hall theorem. Discrete Math., 248(1-3):293–298, 2002.