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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.