Consider the following identity:
\begin{equation}
\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}
\end{equation}
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:
\begin{equation}
\sum\limits_{k=1}^{n}{n-1\choose k-1}^2 = {2n-2\choose n-1}
\end{equation}
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:
\begin{equation}
\sum\limits_{k=1}^{n}n{n-1\choose k-1}^2 = n{2n-2\choose n-1}
\end{equation}
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:
\begin{equation}
\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
\end{equation}
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!
Best Answer
$$\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.