Sign up ×
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.

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.

share|cite|improve this question
You answered it in your first sentence. One way to show that something is an integer is to show that it counts something. So I guess you want a non-counting proof. – Jonas Meyer Nov 23 '10 at 23:03
@Jonas the fact that $nCr$ relates to Pascal's Triangle is another answer. I wouldn't call it a proof though. – Cole Johnson Jan 7 '14 at 19:37

6 Answers 6

up vote 15 down vote accepted

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), therefore 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 every prime $\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)\ \cdots\:\phantom{m-n}1\phantom{+1}}\ \in\ \mathbb Z$$

share|cite|improve this answer
Thanks, and sorry for the late reply/upvote :) – Akusete Sep 3 '12 at 7:45

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

share|cite|improve this answer

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.

share|cite|improve this answer
I haven't thought too hard about this, but does there exist a direct proof (that does not rely on induction) of the fact that the product of $m$ consecutive numbers is divisible by $m!$? – Vladimir Sotirov Nov 23 '10 at 23:38
@Vladimir: You could prove that the prime factors of the numerator is of higher power than that of the denominator. You can look at Bill's proof which he has posted in the next post. – user17762 Nov 24 '10 at 0:07
@Vladimir: Generally, any proof (in Peano arithmetic) that some property is true for all integers must use induction. It may not explicitly invoke induction, e.g. the induction might be hidden way down some chain of lemmas. So it's not clear what it means for such a proof to "not rely on induction". – Bill Dubuque Nov 24 '10 at 0:16

Here is how I envision justifying a binomial coefficient (bc) to always be an integer. A bc is of the form n!/((k!(n-k)!) . First consider just n!/(n-k)! which reduces to the terms n,(n-1), : : : (n-k+2),(n-k+1) in the numerator. If n = 14 and k =5 for example, it would be 14!/9! = 14,13,12,11,10 left in the numerator. We now bring in the remaining denominator term, k!, so we have 14,13,12,11,10 /5,4,3,2,1 for our bc. Remembering how a sequence of consecutive integers are created (or invoking the well ordered principle), we can say that any integer k will occur at least once in every sequence of k consecutive integers, and as there are k integers in the numerator, at least one will be divisible in turn by each integer in the denominator. Note in my example that 4 and 3 both divide 12. I hope this helps, but you probably already have a good handle on it by now. Bill

share|cite|improve this answer

According to this, the highest power of a prime number, $p, $ that divides $N!$ is $$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

Since $\dbinom{N}{M} = \dfrac{N!}{M! (N-M)!}\,, $ the question then becomes, is $s_p(M!) + s_p((N-M)!) \le s_p(N!)$?

Clearly $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le x + y. $ Since $\left \lfloor x+y \right \rfloor$ is the greatest integer less than or equal to $x + y, $ it follows that $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le \left \lfloor x+y \right \rfloor,$

Hence $$\left \lfloor \dfrac{M}{p^{\,i}} \right \rfloor + \left \lfloor \dfrac{N-M}{p^{\,i}} \right \rfloor \le \left \lfloor \dfrac{N}{p^{\,i}} \right \rfloor$$

for all $i$. Summing, we get $s_p(M!) + s_p((N-M)!) \le s_p(N!)$

It follows that $\dbinom{N}{M}$ is an integer.

share|cite|improve this answer

Another way to think of it is combinatorially, which is of course the motivation.

Let $1\le k\le n$. Consider the set $S$ of all sequences of $k$ distinct numbers among $\{1,\dots,n\}$. The size of $S$ is $n\cdot (n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$. Say two sequences in $S$ are equivalent if the underlying set of elements is the same. Then each equivalence class has exactly $k!$ elements since any choice of $k$ elements admits $k!$ permutations. So the set $S$ can be partitioned into sets each of which has size $k!$. So $|S|$ is divisible by $k!$.

share|cite|improve this answer

Your Answer


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.