|
From its definition a combination $(^n_k)$, is the number of distinct subsets of size k from a set of n elements. This is clearly an integer, however I was curious as to why the equation $\frac{n!}{k!(n-k)!}$ always evaluates to an integer. So far I figured: $n!$, is clearly divisible by $k!$, and $(n-k)!$, individually, but I could not seem to make the jump to proof that that $n!$ is divisible by their product. |
|||||
|
|
See my post here for a simple purely arithmetical proof that every binomial coefficient is an integer. The proof shows how to rewrite any binomial coefficient fraction as a product of fractions whose denominators are all coprime to any given prime $\rm\:p\:$. This implies that no primes divide the denominator (when written in lowest terms), so the fraction is an integer. The key property that lies at the heart of this proof is that, among all products of $\rm\: n\:$ consecutive integers, $\rm\ n!\ $ has the least possible power of $\rm\:p\:$ dividing it - for all primes $\rm\:p\:$. Thus $\rm\ n!\ $ divides every product of $\rm\:n\:$ consecutive integers, since it has a smaller power of every prime divisor. Therefore $$\rm\displaystyle\quad\quad {m \choose n}\ =\ \frac{m!/(m-n)!}{n!}\ =\ \frac{m\:(m-1)\:\cdots\:(m-n+1)}{n\:(n-1)\quad\quad\:\cdots\:\quad\quad 1\quad\quad}\ \in\ \mathbb Z$$ |
||||
|
|
|
Well, one noncombinatorial way is to induct on $n$ using Pascal's triangle; that is, using the fact that ${n \choose k} = {n-1 \choose k - 1} + {n-1 \choose k}$ (easy to verify directly) and that each ${n - 1 \choose 0}$ is just $1$. |
|||
|
|
|
As Jonas mentioned, it counts something so it has to be a natural number. Another way is to notice that product of $m$ consecutive natural numbers is divisible by $m!$.(Prove this!) So if we write $n! = n(n-1)(n-2) \cdots (k+1) \times (k!)$, we find that $k!$ divides $k!$ and $n(n-1)(n-2) \cdots (k+1)$ is a product of $(n-k)$ consecutive natural numbers and hence $(n-k)!$ divides it. |
|||||||||
|
