Calculate $\sum_{i=0}^{n}i^2 \cdot \binom{n}{i}^2 $

Question

Calculate $$\sum_{i=0}^{n}i^2 \cdot \binom{n}{i}^2 $$

I tried to do this via combinatorics interpretation. So we want $$ \langle A,a,B,b \rangle $$ such that $$ A \subset \left\{ 1,...,n \right\} \\ B \subset \left\{ 1,...,n \right\} \\ a \in A \\ b \in B $$ So that is $$ n \cdot n \cdot 2^{n-1} \cdot 2^{n-1} = n^2 2^{2n-2} $$ because we choose $a$ and take ($n-1$)-subset of $\left\{ 1,...,n \right\}$ without $a$. And the same for $B,b$. But result supposendly is $$n^2 \binom{2 n-2}{n-1} $$ why? Where I failed?

Answer 1

An algebraic proof can be done starting from the identity $\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$, which is proved here. Then use the fact that for $0<i<n$ you have $i\binom{n}{i}=n\binom{n-1}{i-1}$. This shows that indeed $$\sum_{i=0}^ni^2\binom{n}{i}^2=\sum_{i=1}^{n}n^2\binom{n-1}{i-1}^2=n^2\sum_{j=0}^{n-1}\binom{n-1}{j}=n^2\binom{2(n-1)}{n-1}.$$

As for your combinatorial interpretation; the number $i^2\binom{n}{i}^2$ can indeed be interpreted as the number of ways to choose subsets $A,B\subset\{1,\ldots,n\}$ with $|A|=|B|=i$, and then choosing $a\in A$ and $b\in B$. I do not see how this leads to the number $$n\cdot n\cdot2^{n-1}\cdot 2^{n-1}.$$ Perhaps you did not take into account that $|A|=|B|$?

Of course the number of ways to choose $A,B\subset\{1,\ldots,n\}$ does not depend on the choice of $a$ and $b$, but only on $i$. Indeed the number of ways to choose $A$ and $B$ is $\binom{n-1}{i}$ each, which shows that $$\sum_{i=0}^ni^2\binom{n}{i}^2=n^2\sum_{i=0}^n\binom{n-1}{i}^2,$$ where $n^2$ is the number of ways to choose $a,b\in\{1,\ldots,n\}$. This reduces the problem to finding a combinatorial interpretation for the identity $$\sum_{i=0}^n\binom{n-1}{i}^2=\binom{2(n-1)}{n-1}.$$ Consider choosing $n-1$ balls from a total of $2(n-1)$ balls, of which $n-1$ are blue and $n-1$ are red. There are clearly $\binom{2(n-1)}{n-1}$ ways to choose. We can split up the count by the number $i$ of red balls chosen; then we must choose $n-1-i$ blue balls and hence $$\binom{2(n-1)}{n-1}=\sum_{i=0}^{n-1}\binom{n-1}{i}\binom{n-1}{n-1-i}=\sum_{i=0}^n\binom{n-1}{i}^2.$$

Answer 2

We can do this exclusively with combinatorics. In how many ways can I take $n$ men and $n$ women, choose equally many members of each gender, and choose from among those choose a king and queen? If we do it in that order, the answer is your sum. On the other hand, we could choose the king and queen first, and then choose equally many men and women from the remaining $2n-2$ people, we get an alternative expression for the total. All we need to prove now is $$\sum_{k=0}^{n-1}\binom{n-1}{k}^2=\binom{2n-2}{n-1}.$$But the left-hand side is $\sum_{k=0}^{n-1}\binom{n-1}{k}\binom{n-1}{n-1-k}$, i.e. the number of ways to form a size-$n-1$ subcommittee of arbitrary gender ratio.