Write an integer partition $\lambda\vdash n$ in two different ways:

(1) $\lambda=\lambda_1\geq\lambda_2\geq\lambda_3\cdots\geq\lambda_k\geq1$

(2) $\lambda=1^{m_1}2^{m_2}3^{m_3}\cdots n^{m_n}$ for some $m_i\geq0$.

Denote the length of a partition, compatible with (1) and (2), by $m_1+m_2+\cdots+m_n=k$.

QUESTION. According to enough experimental evidence, $$\sum_{\lambda\vdash n}(-1)^{n-k}\frac{k!}{m_1!\cdots m_n!}\prod_{i=1}^k\binom{n+1}{\lambda_i}=\binom{2n}n.$$ Is it true? If so, any proof?

  • $\begingroup$ We've received two cool solutions of different flavors. More is welcome! $\endgroup$ – T. Amdeberhan Dec 14 '16 at 16:56

Multiply the whole equality by $(-1)^n$.

First of all, notice that $k\choose m_1,\dots,m_k$ is the number of ways to permute the numbers $\lambda_1,\dots,\lambda_k$, so the left-hand side equals $$ L=\sum_{\lambda_i\geq 1, \; \lambda_1+\dots+\lambda_k=n} (-1)^k\prod_{i=1}^k{n+1\choose \lambda_i}. $$ Denote $$ S(x)=\sum_{j=1}^{n+1} {n+1\choose j}x^l=(1+x)^{n+1}-1. $$ Then, due to the formula above, $L$ is the coefficient of $x^n$ in $$ 1-S(x)+S(x)^2-\dots=\frac1{1+S(x)}=\frac1{(1+x)^{n+1}} =\sum_{i=0}^\infty(-1)^i{n+i\choose i}x^i, $$ thus $L=(-1)^n{2n\choose n}$, as desired.

  • $\begingroup$ Nice, nice it is! Up-voted. $\endgroup$ – T. Amdeberhan Dec 14 '16 at 16:40

Here is a purely combinatorial proof of a more general identity $$ \sum_{\lambda\vdash n}(-1)^{n-k}\frac{k!}{m_1!\cdots m_n!}\prod_{i=1}^k\binom{A}{\lambda_i}=\binom{A+n-1}n. $$ As Ilya suggests, we rewrite this as $$\sum_{\lambda_i\geq 1, \; \lambda_1+\dots+\lambda_k=n} (-1)^{n-k}\prod_{i=1}^k{A\choose \lambda_i}.$$ This is an alternating sum of sequences $(S_1,\dots,S_k)$ of subsets of $\{1,2,\dots,A\}$, $\sum |S_i|=n$. We identify each subset $S_i$ with an increasing sequence $p_{i1}<\dots<p_{i|S_i|}$. Then we have a sequence of length $n$: $(u_1,\dots,u_n)=(p_{11},\dots,p_{1|S_1|},p_{21}\dots,p_{2|S_2|},\dots,p_{k|S_k|})$, which we should partition onto $k$ strictly increasing pieces. If we fix a sequence $(u_1,\dots,u_n)$ and partition it onto the minimal number of strictly increasing pieces, then we may subpartition each of them in arbitrary way. This makes the corresponding alternating sum equal to 0 unless all pieces contain exactly 1 number, in other words, the sequence is non-strictly decreasing. But the number of non-strictly decreasing sequences of length $n$ and elements from 1 to $A$ equals $\binom{A+n-1}n$, this is combinations with repetition formula.

  • $\begingroup$ Really nice, a combinatorial proof! Up-voted. $\endgroup$ – T. Amdeberhan Dec 14 '16 at 16:41

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.