# how prove $\sum_{m=0}^{n}\left(\frac{n!}{m!(n-m)!}\right)^2=\frac{(2n)!}{(n!)^2}$?

How to prove $\forall n \in \mathbb N$

$$\sum_{m = 0}^{n} \left(\frac{n!}{m!(n-m)!}\right)^2=\frac{(2n)!}{(n!)^2}$$

-
think about this, divide $2n$ balls into two equal piles of balls with $n$ for each. And you are going to take $n$ balls from them. –  Yimin Feb 24 '13 at 17:36
It's just $\sum_{m = 0}^{n} (C_m^n)^2$ –  hjpotter92 Feb 24 '13 at 17:37
@BackinaFlash it is $C_n^m$ –  Yimin Feb 24 '13 at 17:37
@Yimin Last time I checked, there was a square too; and $n!$ is numerator. –  hjpotter92 Feb 24 '13 at 17:38

In terms of binomial coefficients the proposed identity is

$$\sum_{m=0}^n\binom{n}m^2=\binom{2n}n\;.$$

Once you realize that $\dbinom{n}m^2=\dbinom{n}m\dbinom{n}{n-m}$, this becomes a special case of Vandermonde’s identity, and you’ll find a combinatorial proof in the linked article. (I’m pretty sure that you’ll also find combinatorial proofs on this site.)

-
You mean $$\sum_{m=0}^n\binom{n}m^2$$ –  hjpotter92 Feb 24 '13 at 17:42
@BackinaFlash: And $n$ on top everwhere else, too. Thanks. –  Brian M. Scott Feb 24 '13 at 17:44
@Maisam: You’re welcome. –  Brian M. Scott Feb 24 '13 at 17:46

Note that $$\left(\frac{n!}{m!(n-m)!}\right)^2=\binom{n}{m}\binom{n}{n-m}.$$ Now imagine that we have a group of $n$ boys and $n$ girls, and want to choose a committee of $n$ people.

It is clear that the number of ways to choose a committee of $n$ from our $2n$ people is $\binom{2n}{n}=\frac{(2n)!}{n!n!}$.

Now let us count this another way. For any $m$ with $0\le m\le n$, there are $\binom{n}{m}\binom{n}{n-m}$ ways to choose a committee with $m$ boys and $n-m$ grls. Sum over all $m$.

Remark: Counting something in two different ways can be a powerful method for proving combinatorial identities.

-

First of all $$\frac{n!}{m!(n-m)!} = \binom{n}{m}$$ is a binomial coefficient, and so is $$\frac{(2n)!}{(n!)^2} = \binom{2n}{n}$$

Then consider the coefficient of $x^{n}$ in $$(1 + x)^{2n},$$ which is $\dbinom{2n}{n}$, but can also be computed via $$(1 + x)^{2n} = ((1 + x)^{n})^{2} = (\sum_{m=0}^{n} \binom{n}{m} x^{m})^{2}$$ as $$\sum_{m = 0}^{n} \binom{n}{m} \binom{n}{n-m} = \sum_{m = 0}^{n} \binom{n}{m}^{2}$$

-