Product of r Choose m with m Choose k

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r \in \R, m \in \Z, k \in \Z$.

Then:

$\dbinom r m \dbinom m k = \dbinom r k \dbinom {r - k} {m - k}$

where $\dbinom r m$ is a binomial coefficient.


Complex Numbers

For all $z, w \in \C$ such that it is not the case that $z$ is a negative integer and $t, w$ integers:

$\dbinom z t \dbinom t w = \dbinom z w \dbinom {z - w} {t - w}$

where $\dbinom z w$ is a binomial coefficient.


Proof 1

Integral Index

Let $r \in \Z$.


Then:

\(\displaystyle \binom r m \binom m k\) \(=\) \(\displaystyle \frac {r^{\underline m} } {m!} \frac {m^{\underline k} } {k!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {r! m!} {m! \left({r - m}\right)! k! \left({m - k}\right)!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {r! \left({r - k}\right)!} {k! \left({r - k}\right)! \left({m - k}\right)! \left({r - m}\right)!}\)
\(\displaystyle \) \(=\) \(\displaystyle \binom r k \binom {r - k} {m - k}\)

$\Box$


Real Index

Both sides of the above equation are polynomials in $r$.

Since these polynomials agree for all $r \in \Z$, they must agree for all $r \in \R$.

$\blacksquare$


Proof 2

Consider the trinomial coefficient:

$\dbinom r {k, m - k, r - m}$


We use Multinomial Coefficient expressed as Product of Binomial Coefficients:

$\dbinom {k_1 + k_2 + k_3} {k_1, k_2, k_3} = \dbinom {k_1 + k_2} {k_1} \dbinom {k_1 + k_2 + k_3} {k_1 + k_2}$

and substitute as appropriate for $k_1, k_2, k_3$.


We have:

\(\displaystyle \) \(\) \(\displaystyle \dbinom r {k, m - k, r - m}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {\left({m - k}\right) + \left({r - m}\right) + k} {m - k, r - m, k}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {\left({m - k}\right) + \left({r - m}\right)} {m - k} \dbinom {\left({m - k}\right) + \left({r - m}\right) + k} {\left({m - k}\right) + \left({r - m}\right)}\) Multinomial Coefficient expressed as Product of Binomial Coefficients
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {r - k} {m - k} \dbinom r m\)


Similarly:

\(\displaystyle \) \(\) \(\displaystyle \dbinom r {k, m - k, r - m}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {k + \left({m - k}\right) + \left({r - m}\right)} {k, m - k, r - m}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom {k + \left({m - k}\right)} k \dbinom {k + \left({m - k}\right) + \left({r - m}\right)} {\left({m - k}\right) + k}\) Multinomial Coefficient expressed as Product of Binomial Coefficients
\(\displaystyle \) \(=\) \(\displaystyle \dbinom m k \dbinom r m\)

$\blacksquare$


The result follows on equating the two expressions.