13
$\begingroup$

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?

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

2 Answers 2

22
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice, nice it is! Up-voted. $\endgroup$ Dec 14, 2016 at 16:40
14
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Really nice, a combinatorial proof! Up-voted. $\endgroup$ Dec 14, 2016 at 16:41

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.