# Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity:

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

Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ and $B$, each of size $n-1$. Now, we further partition $S$ into $n$ parts: $C_0, C_1, \ldots C_{n-1}$

By the addition principle we have ${2n-2\choose n-1} = \sum\limits_{k=0}^{n-1}C_k$

Additionally, each $C_k$ is given by ${n-1\choose k}{n-1\choose n-1-k}={n-1\choose k}^2$ since $k$ of the elements will be in $A$ and $n-1-k$ elements will be in $B$. Thus we have: \begin{align} \sum\limits_{k=0}^{n-1}{n-1\choose k}^2 =&{2n-2\choose n-1} \end{align} Reindexing: $$\sum\limits_{k=1}^{n}{n-1\choose k-1}^2 = {2n-2\choose n-1}$$ Here is where I am lost. I cannot think of a combinatorial argument for the $n^2$ and what remains on the left. If you have better ideas skip this! My first thought is the following:

$$\sum\limits_{k=1}^{n}n{n-1\choose k-1}^2 = n{2n-2\choose n-1}$$ This is counting the same thing, but what is $n$? The reason I do this is because now all I need is a $k$ in the sum on the LHS:

$$\sum\limits_{k=1}^{n}kn{n-1\choose k-1}^2 = \sum\limits_{k=1}^{n}k^2\dfrac{n}{k}{n-1\choose k-1}^2 = \sum\limits_{k=1}^{n}k^2{n\choose k}^2$$

And somehow this is equivalent to the RHS $n^2{2n-2\choose n-1}$ Again though, what is the combinatorial argument?

Thanks for all the help!

-
It’s false as stated: for $n=2$ the lefthand side is $$1^2\binom21+2^2\binom22=2+4=6\;,$$ and the righthand side is $$2^2\binom21=8\;.$$ –  Brian M. Scott Feb 11 '13 at 4:11
I made a typo in the original identity. If you look throughout the first steps of my proof, I build a ${n-1\choose k-1}^2$ –  CodeKingPlusPlus Feb 11 '13 at 4:16

$$\sum_{k=1}^nk^2\binom{n}k^2=n^2\binom{2n-2}{n-1}\;.\tag{1}$$

You have $n$ men and $n$ women. You want to choose a team of $n+1$ people, and on this team you will designate a man and a woman as co-captains. You can choose the co-captains in $n^2$ ways, and you can then choose the remainder of the team in $\binom{2n-2}{n-1}$ ways, so the righthand side of $(1)$ counts the possible teams.

Now let’s count the teams with exactly $k$ women, for $k=1,\dots,n$. There are $\binom{n}k$ ways to choose the women, and $k$ ways to designate one the female co-captain. There are then $n$ ways to pick the male co-captain and $\binom{n-1}{n-k}$ ways to pick the remaining men. And

$$kn\binom{n}k\binom{n-1}{n-k}=kn\binom{n}k\binom{n-1}{k-1}=k^2\binom{n}k^2\;,$$

so the lefthand side counts the same thing according to the number of women on the team.

-
I don't understand why $$kn\binom{n}k\binom{n-1}{n-k}=kn\binom{n}k\binom{n-1}{k-1}$$ can someone kindly explain? –  larrysummersstatistics Nov 25 '14 at 22:43
@larrysummersstatistics: $$\binom{n-1}{n-k}=\binom{n-1}{(n-1)-(n-k)}=\binom{n-1}{k-1}\;.$$ This is just an instance of the fact that $\binom{m}\ell=\binom{m}{m-\ell}$ for any $m$ and $\ell$. –  Brian M. Scott Nov 25 '14 at 22:55

Consider a group of 2n people .Now consider there are two groups($A,B$) of n people.

From the groups(of 2n people) you have to select a smaller group of $n+1$ people selecting one representative of each group $A,B$

Explanation of the RHS.

At first select the representative of each group.This can be done in $n^2$ ways anthe remainder of the team can be selected in $\binom{2n-2}{n-1}$ ways.

Now the LHS,

From the n persons of the first group we select $k$ persons in $\binom{n}{k}$ ways , from among those k persons we select a representative in $k$ ways .So the total no. of ways of selecting the group and representative of the $k$ persons is $k\binom{n}{k}$ .Similarly in case of the 2nd group there are $k\binom{n}{k}$.So the toal no. of ways will be $$\sum _{k=1}^{n}k^2\binom{n}{k}^2$$

As in both the cases we are doing the same thing but in a different way,so we must have,

$$\sum _{k=1}^{n}k^2\binom{n}{k}^2=n^2\binom{2n-2}{n-1}$$

-
The "similarly in the case of the second group" suggest you select the same number $k$ as from the first group. But that leaves you with $2k$ people, so that's notright. Instead you need to choose $n+1-k$ people from the second group, which is not quite similar. –  Marc van Leeuwen Feb 11 '13 at 5:15

This is just a way to reformulate the answer by Brian Scott so that it avoids any algebraic manipulation of binomial coefficients.

Consider colouring the squares of a $2\times n$ rectangle with colours red, white, blue, subject to the following restrictions

• Exactly one square of each of the two rows must be white,
• There must be $n-1$ each of red and blue squares.

Every solution has equally many blue squares in the first row as red squares in the second row; let this number be $n-k$ (with $1\leq k\leq n$). Now for any solution with this value of $k$ we must choose in the first row $k-1$ red squares, $1$ white square and $n-k$ blue squares, and in the second row similarly with red and blue interchanged. For each row this number is given by the trinomial coefficient $\binom n{k-1,1,n-k}$, giving $$\sum_{k=1}^n\binom n{k-1,1,n-k}^2$$ solutions in all. On the other hand, one may just choose the white squares in both rows (giving the factor $n^2$), and then the $n-1$ red squares among the remaining $2(n-1)$, for $$n^2\binom{2(n-1)}{n-1}$$ possibilities. Finally the trinomial coefficient above can be seen to be $k\binom nk$: for $\binom nk$ ways to choose the subset for the first two colours together, and $k$ choices for the single white square among them.

-