User:Minimal Counterexample/sandbox

Lecture hall partition

In number theory and combinatorics, a lecture hall partition is a partition that satisfies additional constraints on its parts. Informally, a lecture hall partition is an arrangement of rows in a tiered lecture hall, with the condition that students on any row can see over the heads of the students in front of them. Bousquet-M\'elou and Eriksson introduced them in 1997.

Definitions

The lecture hall partitions $\mathbf {L} _{n}$ are defined by

$\mathbf {L} _{n}=\left\{\lambda \in \mathbb {Z} ^{n}:0\leq {\frac {\lambda _{1}}{1}}\leq {\frac {\lambda _{2}}{2}}\leq \cdots \leq {\frac {\lambda _{n}}{n}}\right\},$

where λ_i refers to the i-th component of λ. A lecture hall partition of N is any $\lambda \in \mathbf {L} _{n}$ such that N = |λ|, where $|\lambda |=\lambda _{1}+\cdots +\lambda _{n}.$

The s-lecture hall partitions, denoted $\mathbf {L} _{n}^{(s)},$ are a generalization of $\mathbf {L} _{n}.$ Given a sequence s = (s₁,..., s_n), the s-lecture hall partitions are defined by

$\mathbf {L} _{n}^{(s)}=\left\{\lambda \in \mathbb {Z} ^{n}:0\leq {\frac {\lambda _{1}}{s_{1}}}\leq {\frac {\lambda _{2}}{s_{2}}}\leq \cdots \leq {\frac {\lambda _{n}}{s_{n}}}\right\}.$

In fact, $\mathbf {L} _{n}=\mathbf {L} _{n}^{(1,2,\ldots ,n)}.$ The term s-lecture hall partition is a misnomer. A partition, strictly speaking, disregards the order of the parts λ_i. However, given an s-lecture hall partition λ of N, there may be a permutation of λ that is also an s-lecture hall partition of N; in this case, λ is properly called a composition of N. If s is non-decreasing, then λ is always a partition; for example, the lecture hall partitions $\mathbf {L} _{n}$ are named properly, because in this case s = (1, 2, ..., n).

The lecture hall theorem

The lecture hall theorem states that the number of lecture hall partitions of N in $\mathbf {L} _{n}$ is equal to the number of partitions of N into odd parts less than 2n. Euler's partition theorem, for comparison, equates the number of partitions with odd parts to the number of partitions with distinct parts. Therefore, in the limit $n\to \infty$, the number of lecture hall partitions of N in $\mathbf {L} _{n}$ equals the number of partitions of N with distinct parts.

The lecture hall theorem takes the form of a generating function as

$\sum _{\lambda \in \mathbf {L} _{n}}q^{|\lambda |}=\prod _{i=1}^{n}{\frac {1}{1-q^{2i-1}}}.$

Polynomic sequences

A sequence s is called polynomic if

$\sum _{\lambda \in \mathbf {L} _{n}^{(s)}}q^{|\lambda |}=\prod _{i=1}^{n}{\frac {1}{1-q^{d_{i}}}},$

where d₁,..., d_n are some positive integers. By the lecture hall theorem, s = (1,..., n) is a polynomic sequence with d_i = 2i-1.

(k, l) sequences

For positive integers k, l, define the (k, l) sequence a by

${\begin{aligned}a_{2i}&=la_{2i-1}-a_{2i-2}\\a_{2i+1}&=ka_{2i}-a_{2i-1},\end{aligned}}$

where a₁ = 1 and a₂ = l. Similarly, define the (l, k) sequence b by interchanging k and l:

${\begin{aligned}b_{2i}&=kb_{2i-1}-b_{2i-2}\\b_{2i+1}&=lb_{2i}-b_{2i-1},\end{aligned}}$

where b₁ = 1 and b₂ = k. Denote $\mathbf {G} _{n}^{(k,l)}=\mathbf {L} _{n}^{(a)}$ and define

$G_{n}^{(k,l)}(x,y)=\sum _{\lambda \in \mathbf {G} _{n}^{(k,l)}}x^{|\lambda |_{o}}y^{|\lambda |_{e}},$

where $|\lambda |_{o}=\lambda _{1}+\lambda _{3}+\cdots$ and $|\lambda |_{e}=\lambda _{2}+\lambda _{4}+\cdots .$

References

Mireille Bousquet-M\'elou and Kimmo Eriksson. Lecture hall partitions. Ramanujan J., 1(1):101–111, 1997.