Fraction of two binomial coefficients

Question

In an exercise I was asked to simplify a term containing the following fraction: $${\binom{m}{k}\over\binom{n}{k}}$$

The solution does assume the following is true in the first step, without explaining why. I unfortunately cannot reconstruct the step:

$${\binom{m}{k}\over\binom{n}{k}} = {\binom{n-k}{m-k}\over\binom{n}{m}}$$

Has anyone a good explanation why this transformation is possible?

Answer 1

I don't know if it should be a memorized formula necessarily, but I can justify it combinatorially:

$$\binom{n}{m}\binom{m}{k} $$

Counts the number of ways of selecting $m$ items out a pool of $n$ and placing them in bin A, and then selecting $k$ items out of bin A and putting them in bin B. You end up with $m-k$ items in the first bin and $k$ items in the second. We might have well as done it in reverse order though: select $k$ items out of $n$ to put into bin B, and then select $m-k$ items out of $n-k$ to put into bin A. Hence:

$$=\binom{n}{k}\binom{n-k}{m-k}.$$

Equating these two yields the given equality of ratios after rearrangement.

Answer 2

$$\frac{\binom{m}{k}}{\binom{n}{k}}=\frac{m!}{\rlap{\,/}k!(m-k)!}{\frac{\rlap{\,/}k!(n-k)!}{n!}}$$

$$\frac{\binom{n-k}{m-k}}{\binom{n}{m}}=\frac{(n-k)!}{(m-k)!\rlap{\;\;\;\;//}(n-m)!}\frac{m!\rlap{\;\;\;\;//}(n-m)!}{n!}$$

Compare carefully both expression and be convinced they're identical

Answer 3

The equivalence of the 2 expressions above has been explained by previous posters.

By simplification, I wonder if you mean produce an equivalent expression that will be more likely to compute without causing register overflow for factorials of large numbers ? Or do you just want to simplify it in a purely mathematical sense, i.e. write it in its most simple form ? If the former, it's best to write it as a product of a series of quotients. In the case of the expression $${\binom{m}{k}},$$ this works out as the product of $k$ individual quotients.

For the full deal, i.e. $${\binom{m}{k}\over\binom{n}{k}},$$ you also have a similar number of quotients under the line. So the overall ratio also works out as the product of $k$ quotients, each of which will not be too big a number. Computing this, the $m$, $n$ and $k$ are transformed to floating point before evaluating each quotient and then forming the product of all $k$ of them. The result is then rounded to give the true integer result.

If the latter, I do not know of a simpler form, except perhaps

$$\frac{^mP_k}{^nP_k}$$

where $^mP_k$ is the number of $k$ sized permutations possible for $m$ objects.

But this does not look much better.

You could also develop the right hand side of the equivalence above and get : $$\frac{\displaystyle{\frac{m!}{n!}}}{\displaystyle{\hspace 5pt\frac{(m-k)!}{(n-k)!}}\hspace 5pt}$$

This then reduces to $$\frac{m(m-1)(m-2)\cdots(m-n+1)}{(m-k)(m-k-1)(m-k-2)\cdots(m-n+1)}$$

which is a product of $(m-n)$ individual quotients, i.e.

$$\prod_{i=0, j=0}^{i=n-1, j=n-k-1}\frac{m-i}{m-k-j}$$

So you just loop through this process for $(m-n)$ times, each time calculating each quotient and multiplying it to the existing product. If $m$ and $n$ are both much bigger than $k$, then there should be less computations doing it this way as well as less risk of register overflow.

Anyone knowing LaTex better than me please edit this mess.

While it's a bit simplified computationally, it's been complicated expressionally . . .