Is there a simple combinatoric interpretation of this identity?

Question

I came across an exercise in which we are asked to prove the identity:

$${2n\choose n}=\sum_{k=0}^n{n\choose k}^2$$

The exercise gives the hint:

$$\left(1+x\right)^{2n}=\left[(1+x)^n\right]^2$$

It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...

It's clear that ${2n \choose n}$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $\sum_{k=0}^n{n\choose k}^2$ equivalently?

Answer 1

Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $A\cup B$ is $\binom{2n}n$. On the other hand, we can get any $n$-element subset of $A\cup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $A\cup B$ has the form $(A\setminus X)\cup Y$ where $X\subseteq A$, $Y\subseteq B$, $|X|=|Y|=k$ for some $k\in\{0,\dots,n\}$. The number of different sets we can get in this way is $\sum_{k=0}^n\binom nk\binom nk$.

Answer 2

This is also a well know interpretation.

Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.

The number of total way is ${2n \choose n}$.

And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), \ldots, (n,0)$.

The sum of all way is $\sum_{k=0}^n{n\choose k}^2$.

Hence, both value are same.

Answer 3

Another interpretation: As Erick Wong stated in the comments, $$\binom{n}{k}^2 = \binom{n}{k}\binom{n}{n - k}$$ We can interpret $$\binom{2n}{n}$$ as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression $$\binom{n}{k}\binom{n}{n - k}$$ counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence, $$\binom{2n}{n} = \sum_{k = 0}^{n} \binom{n}{k}\binom{n}{n - k} = \sum_{k = 0}^{n} \binom{n}{k}^2$$