Adopt the standard notation for integer partitions, writing $\lambda_1^{a_1} \cdots \lambda_k^{a_k}$ as shorthand for the partition $a_1 \lambda_1 + \cdots + a_k \lambda_k$ with parts $\lambda_1 > \cdots > \lambda_k \geq 1$ and multiplicities $a_i \geq 1$.

If $\lambda = \lambda_1^{a_1} \cdots \lambda_k^{a_k} \vdash n$, its collapsed image is the partition with multiple occurrences of parts removed, and is denoted by $\underline{\lambda} := \lambda_1 \cdots \lambda_k$. Introduce the set $\underline{\mathcal{P}_n}=\{\,\underline{\lambda}: \,\lambda\vdash n\}$ as well as the all-familiar $\mathcal{P}_n=\{\,\lambda: \,\lambda\vdash n\}$

QUESTION. Is this true? If so, is there a combinatorial proof? $$\#\underline{\mathcal{P}_n}=\sum_{j=0}^{n-1}\#\mathcal{P}_j.$$ CORRECTED. $$\sum_{\underline{\lambda}\in\underline{\mathcal{P}_n}}\text{length}(\underline{\lambda})=\sum_{j=0}^{n-1}\#\mathcal{P}_j.$$

Remark. For a related problem, see here:


The result does not seem to be stated correctly. For instance, $\underline{\mathcal{P}_3}=\{ 3,21,1\}$, yet $p(0)+p(1)+p(2)=4$, where $p(n)=\#\mathcal{P}_n$. It is true that $$\sum_{\lambda\in\underline{\mathcal{P_n}}}\ell(\lambda)=p(0)+p(1)+\cdots+ p(n-1),$$ where $\ell(\lambda)$ is the number of parts of $\lambda$. This is equivalent to the case $k=1$ of Enumerative Combinatorics, vol. 1, second ed., Exercise 1.80, which has a simple combinatorial proof.

  • $\begingroup$ Ouch. Yes, your correction is true! Thanks. $\endgroup$ – T. Amdeberhan May 14 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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