# Is there any known algorithm for factoring the fractional components of a binomial?

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?

• 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. – Thomas Andrews Apr 4 '13 at 20:27
• 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$. – Thomas Andrews Apr 4 '13 at 20:30
• 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.. – Cocopuffs Apr 4 '13 at 20:33
• @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$? – Michael Hardy Apr 4 '13 at 23:46
• @MichaelHardy This is a good question - none is obvious to me – 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!$