Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

up vote 7 down vote accepted

$$\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.

share|improve this answer

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.

share|improve this answer

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}$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.