# an identity for a sum over partitions

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?

• We've received two cool solutions of different flavors. More is welcome! Dec 14, 2016 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.
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.