I want to prove the following identity combinatorially: $$\sum_{k = 1}^nk^2 {n \choose k}^2 = n^2{2n - 2 \choose n - 1}$$
We can introduce the following counting problem: How many ways are there to pick 2 teams from $n$ people with the same number of members that have a captain. For a fixed $k$, it is straightforward to show that this can be done in ${n \choose k}^2k^2$ ways. Now to find all the possibilities, we iterate all the possible values for $k$. ($1 \leq k \leq n$)
I have a problem with the right hand side. Here's my attempt so far (Not only is it a mess but it's also wrong.): We can first pick the captains of the two teams in $n^2$ ways. Make 2 lists of the remaining $n - 1$ people. This leaves us with $2(n - 1) = 2n - 2$ elements.
Now we pick $n - 1$ people from the disjoint union of these lists in ${2n - 2 \choose n - 1}$ ways. We should now find a way to determine 2 teams of the same size based on the chosen people. If all the chosen $n - 1$ people are in the first list, then we can just set both of the teams to contain all of the people. So now suppose that $k$ people are chosen from the first list and $n - 1 - k$ people are chosen from the second list.
Our teams should be constructed uniquely so that we don't over-count. But I can't come up with a unique method of choosing the teams. A naive idea is to let the first team contain the $k$ people chosen from the first list (Assuming that $k \geq n - 1 - k$) and somehow removing elements from the second list until there are $k$ people left. But this has a lot of problems. It is over counting SO MUCH. Eg. we are ignoring the symmetry of the lists.
I'm pretty sure there are more elegant ways of showing the right hand side is counting the same thing. Hints would be appreciated and thanks in advance. (Other combinatorial arguments are also highly welcome.)
This is rather simple really, you're almost there.
The key idea is to "see double". Imagine that using magic, each of the $n$ persons gets doubled, so there are now $2n$ persons. Where there was formerly just one person there is now a pair of twins, one which we color green and another which we color red (to be able to distinguish them). There is then a green team and a red team, and they both have $k$ members for some $k$.
Denote by $Y$ the set of all people except the captains. Then $Y$ has $2n-2$ members. Now, consider a set $Z$ of persons defined as follows. Take all the green people not in the green team (which makes $n-k$ members), and add the red team except the capitain (which makes $k-1$ members). It is clear that the original teams can be reconstructed if we know $Z$ and if we know who the captains are . And $Z$ is an arbitrary $(n-1)$-subset of $Y$, hence the $\binom{2n-2}{n-1}$ coefficient.