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

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.

• If all you're after is to prove the statement, and you don't have to come up with an intuitive scenario that illustrates why the statement is true, then it would probably be easier to just use induction. Commented Aug 8, 2023 at 3:47
• @JustinSkycak I need to find a proof in the form of combinatorial illustration. Commented Aug 8, 2023 at 5:05
• math.stackexchange.com/questions/391239/… Commented Aug 8, 2023 at 22:33

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.

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

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