What is $\binom{n}{2} \binom{n}{1} + \binom{n}{3} \binom{n}{2} + \ldots + \binom{n}{n-1} \binom{n}{n-2} + \binom{n}{n} \binom{n}{n-1}$?
Solution 1:
A combinatoric proof : Let : $$A = \{1, 2, \ldots, 2 k\}, B = \{1, \ldots, k\} \text{ and } C = \{k + 1, \ldots, 2 k\}$$ We need to choose $k - 1$ elements from $A$. There are two ways :
- First way : Choose $k - 1$ element directly for $A$ : In this case, we have then : $$\binom{2 k}{k - 1}$$ ways.
- Second way : We can choose $r$ elements from $B$ and $k - 1 - r$ from $C$ for $r \in \{0, \ldots, k -1 \}$ : In this case we have : $$\sum_{r = 0}^{k-1} \binom{k}{r} \binom{k}{k - 1 - r}$$ ways.