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?
> 
> 
> 



an identity for a sum over partitions
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.


