Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 17 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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 mPk / nPk (mPk = 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.

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

share|improve this answer
    
Does it look all right, now? I did a few dirty tricks with that quotient of fractions to A) make it bigger, B) make the "main" line a bit longer. –  Jyrki Lahtonen Jul 4 '12 at 12:28
    
Kiitos, Jyrki ! –  Deek Jul 4 '12 at 13:17
    
Tá failte romhat! –  Jyrki Lahtonen Jul 4 '12 at 20:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.