3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I would say yes. Very much so. $\endgroup$ – Somos Dec 11 '18 at 17:04
  • $\begingroup$ and in the last identity, you lost the Sum $\endgroup$ – G Cab Dec 11 '18 at 17:45
6
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.