For a binomial such as $\binom {15} {6}=\frac{15\times14\times13\times12\times11\times10}{6\times5\times4\times3\times2\times1}$, it seems that it always divides evenly into an integer, and I understand that there is a proof that this fraction must be an integer. Is there a way other than trial and error to determine which numbers in the denominator divide into which numbers in the numerator?

  • $\begingroup$ In any $n$ consecutive numbers, one of them is divisible by $n$. However, that isn't enough to show that the result of a binomial is an integer. $\endgroup$ – Thomas Andrews Apr 4 '13 at 20:27
  • 1
    $\begingroup$ Consider: $$\frac{15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10}{6\cdot 5\cdot4\cdot 3\cdot 2\cdot1}$$ The only number in the numerator divisible by $6$ is $12$. The only number divisible by $4$ is also $12$. Yet the result is still an integer, becausewen can take one $2$ from $\frac{12}{6}$ and the other $2$ from $14$. $\endgroup$ – Thomas Andrews Apr 4 '13 at 20:30
  • 3
    $\begingroup$ Fun proof: for $n \ge m$ use the injection $S_m \times S_{n-m} \rightarrow S_n$ to see that $m!(n-m)!$ divides $n!$. I think I saw this from Qiaochu Yuan but can't find it at the moment.. $\endgroup$ – Cocopuffs Apr 4 '13 at 20:33
  • 1
    $\begingroup$ @Cocopuffs : OK, so the number of cosets of $S_m\times S_{n-m}$ in the group $S_n$ is the same as the number of size-$m$ subsets of a size-$n$ set. Is there some natural bijection between the set of cosets and the set of subsets of size $m$? $\endgroup$ – Michael Hardy Apr 4 '13 at 23:46
  • $\begingroup$ @MichaelHardy This is a good question - none is obvious to me $\endgroup$ – Cocopuffs Apr 5 '13 at 14:50

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$, and we want to show that $k!(n-k)!$ divides $n!$, try to think of $$n!=k!(n-k)!\binom{n}{k}$$ For the left hand side, $n!$ is the number of arrangement for $n$ objects.

For the right hand side, to arrange those $n$ objects, you can first arrange $k$ of them, that gives you $\binom{n}{k}k!$, then arrange rest of the $n-k$, that is $(n-k)!$, thus the total way of arranging $n$ objects is $k!(n-k)!\binom{n}{k}$.

Since the right hand side and the left hand side count the same thing, therefore $k!(n-k)!$ must divide $n!$

  • $\begingroup$ Yes, I understand the principles behind the proof. What I am looking for is a method to actually do the division systematically without trial and error. The larger question here is whether this problem is analogous to the general problem of factoring (and thus no known polynomial time solution exists) or whether the special circumstances of this division make available a rule for doing the factor cancellation in linear time. $\endgroup$ – Tyler Durden Apr 8 '13 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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