0
$\begingroup$

An integer partition is a sequence $\lambda=(\lambda_1\geq\lambda_2\geq\dotsb\geq\lambda_k)$ of positive integers, for some $k\geq1$. Consider the following two sets of partitions of $n$. Fix a positive integer $s>1$.

Let $\mathcal{O}_{n,s}=\{\lambda\vdash n: \lambda_i\in\{1,3,5,\dotsc,2s-1\}\}$. Parts are odd integers.

Also, let $\mathcal{A}_{n,s}=\{a_1+2a_2+2a_3+\dotsb+2a_s=n: a_1\geq a_2\geq a_3\geq\dotsb\geq a_s\geq0\}\subset\mathbb{Z}^s_{\geq0}$. In my earlier MO post Seeking a bijective proof enumerating two partition sets: Part I, I proposed a question on $\#\mathcal{O}_{n,s}=\#\mathcal{A}_{n,s}$ which was subsequently answered by Per Alexandersson.

Let's add one more set of partitions $$\mathcal{B}_{n,s}=\{a_1+a_2+\cdots+a_s=n: a_2\geq 2a_1, 2a_3\geq 3a_2, 3a_4\geq 4a_3,\dotsc,(s-1)a_s\geq sa_{s-1}\}.$$ I would like ask:

QUESTION. Is there a combinatorial or bijective proof of the equinumerosity $\#\mathcal{O}_{n,s}=\#\mathcal{B}_{n,s}$?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Just to mark this question as answered, let me convert my comments into an answer.

The set of partitions $\mathcal{B}_{n,s}$ you define are called the "lecture hall partitions" and they were introduced by Mireille Bousquet-Mélou and Kimmo Eriksson in [1]. See also the survey on the mathematics of lecture hall partitions by Carla Savage in [2]. The fact that there are the same number of lecture hall partitions of $n$ into at most $s$ parts as partitions of $n$ into odd parts less than $2s$ was the main result of that first paper of Bousquet-Mélou and Eriksson, and they gave a couple of different proofs: one based on affine Coxeter groups, the other more direct and combinatorial. At the end of their paper they gave a recursive bijection between $\mathcal{B}_{n,s}$ and $\mathcal{O}_{n,s}$ based on their combinatorial argument. A simple bijection was later obtained by Niklas Eriksen; see the FPSAC 2002 conference article [3].

[1] Bousquet-Mélou, Mireille; Eriksson, Kimmo, Lecture hall partitions, Ramanujan J. 1, No. 1, 101-111 (1997). ZBL0909.05008.

[2] Savage, Carla D., The mathematics of lecture hall partitions, J. Comb. Theory, Ser. A 144, 443-475 (2016). ZBL1343.05032.

[3] Eirksen, Niklas, A simple bijection between lecture hall partitions and partitions into odd integers, FPSAC 2002.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .