Combinatorics Proof?

Question

How would I prove $$\sum_{b=0}^a \frac{(2a)!}{b!b!(a-b)!(a-b)!} = \binom{2a}{a}\binom{2a}{a}$$

I am familiar with the identity $$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\binom{n}{k}^2$$ Would I be able to use this?

Answer 1

This is not purely bijective proof. The identity that you said you knew of it can be proved bijectively. We will use that fact to prove the new identity.

First rewrite \begin{align} \frac{(2a)!}{b!b!(a-b)!(a-b)!} &= \frac{(2a)!}{a!a!}\frac{a!a!}{b!(b-a)!b!(b-a)!}\\ &={2a \choose a} {a\choose b}{a \choose b-a}\end{align} It follows that \begin{align} \sum_{b=0}^a \frac{(2a)!}{b!b!(a-b)!(a-b)!} &={2a \choose a}\sum_{b=0}^a {a\choose b}{a\choose a-b}\\ &={2a\choose a}{2a\choose a}\quad \text{(by your identity)} \end{align}

Answer 2

The summand $\frac{(2a)!}{(b!)^2((a-b)!)^2}$ counts the number of ways to color the elements of a set $S$ of size $2a$ in four colors, so that there are $b$ elements in the first two colors and $a-b$ elements in the last two colors.

The right hand side counts the number of ways to choose two subsets $A$ and $B$ of $S$ of size $a$. This induces a coloring in the following way:

• $x\in A, x\in B\implies x$ is red.
• $x\in A, x\notin B\implies x$ is blue.
• $x\notin A, x\in B\implies x$ is green.
• $x\notin A, x\notin B\implies x$ is black.

Combining these two pieces, you can make a combinatorial proof.