A combinatorial proof of the identity $\sum\limits_{k=0}^nk^2 {n \choose k}^2 = n^2 {2n - 2 \choose n- 1}$

Question

I have seen the proof of $\sum_{k=1}^{n} {{k} {n \choose k}^2 ={ n} {{2n-1} \choose {n-1}}}$ done with boys and girls and I somehow understand it, but $$\sum_{k=0}^{n}k^2 {n \choose k}^2 = n^2 {2n - 2 \choose n- 1}$$

is a little different.

I tried it like this:

What is the number of ways a group of $n$ boys and $n$ girls can be divided into a team of $n$ people with a boy leader and a girl supervisor who isn't a part of the team?

On the RHS:

There are two groups of n boys and n girls and we choose the leader from the $n$ boys and then we choose the supervisor from the $n$ girls and then we choose a team of $n - 1$ people for the boy from $2n - 2$ children.

On the LHS:

We can rewrite it into

$$\sum\limits_{k=0}^nk{n \choose k}k{n \choose n - k}$$

We first choose $k$ boys for a team and then a leader from them and then we choose girls who aren't part of the team. And I don't know what's next.

Answer 1

The left hand side counts, for each $k$, the number of ways you can choose $k$ boys and $n-k$ girls to form a team. Among these $k$ boys there are $k$ ways to choose the boy leader. There are $k$ ways to choose a girl supervisor from the $k$ girls that are not on the team.

Answer 2

Okay, let's look at RHS: $n^2 { 2n-2 \choose n-1 }$

Suppose we have $2n$ balls, of which $n$ are black and $n$ are white. We want to choose $n+1$ balls in total, but we do it as follow: We have $2$ boxes. In first box, we put exactly $2$ balls, one black, one white, which can be done in $n^2$ ways. The rest goes in exactly ${ 2n-2 \choose n-1}$ ways ( we don't bother about colours for the second box).

Now LHS: $\sum_{k=1}^n k^2 {n \choose k} {n \choose n-k}$ (note I start the sum from $1$ (since it is $0$ for $k=0$ ) )

Assume that in those $n+1$ balls we want to pick exactly $k$ black balls $k \in \{1,...,n\}$ ( it cannot be $n+1$, since we must have at least one white ball). So there is exactly ${n \choose k}$ ways to pick those $k$ black balls, and ${n \choose n-k}$ to pick white balls. Now we have $n$ balls in the second box, we choose one of black balls from there ($k$ ways) and put it in the first box. Now we have $1$ black ball in the first box, and $n-1$ balls in second box. Note that we choosed $n-k$ white balls, so exactly $k$ hasn't been chosen yet, so we can choose one of them to be in the first box in exactly $k$ ways. So that we get $k^2 {n \choose k} { n \choose n-k}$. Now sum $k \in \{1,...,n\}$

Answer 3

Vandermonde and some basic identities also work: $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{k}^2 &=\sum_{k=0}^nk(k-1)\binom{n}{k}^2+\sum_{k=0}^nk\binom{n}{k}^2\tag1\\ &=n(n-1)\sum_{k=0}^n\binom{n-2}{k-2}\binom{n}{n-k}+n\sum_{k=0}^n\binom{n-1}{k-1}\binom{n}{n-k}\tag2\\ &=n(n-1)\binom{2n-2}{n-2}+n\binom{2n-1}{n-1}\tag3\\[3pt] &=(n-1)^2\binom{2n-2}{n-1}+(2n-1)\binom{2n-2}{n-1}\tag4\\[3pt] &=n^2\binom{2n-2}{n-1}\tag5 \end{align} $$ Explanation:
$(1)$: $k^2=k(k-1)+k$
$(2)$: $k(k-1)\binom{n}{k}=n(n-1)\binom{n-2}{k-2}$ and $k\binom{n}{k}=n\binom{n-1}{k-1}$
$(3)$: Vandermonde Identity
$(4)$: $n\binom{2n-2}{n-2}=(n-1)\binom{2n-2}{n-1}$ and $n\binom{2n-1}{n-1}=(2n-1)\binom{2n-2}{n-1}$
$(5)$: $(n-1)^2+(2n-1)=n^2$

Answer 4

If you rewrite it like you did, you can see it as follows: You pick $k$ boys and hence $n-k$ girls. From the $k$ boys you pick a leader. The girl which will be supervisor, you pick from the $k$ girls which didn't make the team. This gives $$k\binom{n} {k} k\binom{n} {n-k} $$ possibilities. Sum over $k$ to get all possible teams.

remark you didn't have to rewrite it, just change the 'story' to ''you pick $k$ girls which don' t make the team'' and you end up with the original summation.