Combinatorial proof $\sum^n_{k=0} {{2n}\choose{k}}{{n}\choose{k}}{{2n-k}\choose{n}} = {{2n}\choose{n}}^2$

Question

I need to prove that:

$$\sum^n_{k=0} {{2n}\choose{k}}{{n}\choose{k}}{{2n-k}\choose{n}} = {{2n}\choose{n}}^2$$

So I figured that we can think of a situation in which we have $2$ groups of pairs of people. In both of them there are $n$ men and $n$ women. In each group, each man creates a pair with some woman (same can be said from the perspective of each woman). I presented my caoncept with a simple paint drwaing below: In the equation, on the RHS we choose $n$ people from group $1$ and then $n$ from group $2$. On the LHS we choose $k \leq n$ people from group $1$ and then $k$ men from group of men of group $2$. Then we take men of group $2$ that were not chosen and at that point we have $n - k + k = n$ people chosen. At the end we choose $n$ people from $2n-k$ that are left in group $1$.

I know that it's wrong but I have no idea how to make it right.

Answer 1

We make the following change to the expression: $$\sum_{k=0}^{n} \binom{2n}{k} \binom{n}{k} \binom{2n-k}{n}=\sum_{k=0}^{n} \binom{2n}{k} \binom{n}{n-k} \binom{2n-k}{n}$$ $$\text{since} ~~ \binom{n}{k}= \binom{n}{n-k}$$

Consider the following scenario:

Suppose you have two groups, Group A is of $2n$ people and Group B is of $n$ people. Now consider you have to form two Teams, Team A and Team B of $n$ people each with the following restrictions:

$1$. The $n$ members of Team A can only come from Group A.

$2$. The $n$ members of Team B can come from both the groups: Group A and Group B.

Method $1$ of doing this:

Step $1$, choosing Team B:

Since choosing from team B has no restrictions, you can choose $k$ people from group A, and you need more $n-k$ people so you take them from group B.

Now this $k$ will vary from $0$ to $n$.Since you can't choose more than $n$ people from Group B. ( as group B has the maximum limit of $n$ people)

Step $2$, choosing Team A :
Remember Team A can only come from Group A ( our restriction), so from the $2n-k$ people left ( as we already chose $k$ people for step 1), we choose $n$ people.

Thus we get the following expression for completing the entire process: $$\sum_{k=0}^{n} \binom{2n}{k} \binom{n}{n-k} \binom{2n-k}{n}$$

Method 2:
Consider we do Step $2$ first then Step $1$, since our order of doing the steps should not matter in the selection of both the teams.

This means we first select members for Team A which has restrictions. Then we choose members for team B.

So we first choose $n$ members from group A for team A. We can do this with the following number of ways: $\binom{2n}{n}$.

Now from the rest of the people left, ($n$ people left in group A and $n$ people left in group B) we choose $n$ people for team B.
This also can be done in $\binom{2n}{n}$ ways.

Hence our answer is $\binom{2n}{n} \cdot \binom{2n}{n}$=$(\binom{2n}{n})^2 $

Answer 2

Let's assume we have $2$ distinct groups of $2n$ people, either of which consists of $n$ men and $n$ women. Our goal is to form a team that has $n$ members from either group. Obviously, the number of such teams is $\binom{2n}{n}^2.$

Now, let's count the desired number in a different way. If we are supposed to form a team that has only $k$ men from the first group, the number of such teams is clearly:

$$\binom{n}{k} \times \binom{n}{n-k} \times \binom{2n}{n}.$$

However, $k$ may vary from $0$ to $n$. So, the total number is:

$$\sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \binom{2n}{n}.$$

On the other hand, it's very easy to verify that:

$$\binom{n}{n-k} \binom{2n}{n}=\binom{2n}{k} \binom{2n-k}{n}=\frac{(2n!)}{k!(n-k)!n!}.$$

We are done.

Answer 3

First examine the term of the series.

$$\dbinom{2n}{k}\dbinom{2n-k}{n}\dbinom{n}{k}$$

This counts the ways to part a set of $2n$ elements into subsets of $k$, $n-k$, $k$, and $n-k$ elements respectively.

Note the symmetry. How else might we perform this task?

Well, we may first part the set into two of $n$ elements and then part each of these into the required subset. $$\dbinom{2n}{n}\dbinom{n}{k}^2$$

So...