Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a simple way to show that $$n!\over r!(n-r)!$$ is always an integer?

share|cite|improve this question
you can use induction in Pascal's triangle – pascalhein Jun 4 '13 at 20:16
up vote 10 down vote accepted

I'm guessing you would like a noncombinatorial proof, as it ${n \choose k}$ is used to count and therefore must be an integer. If that's the case, here's an idea:

Hint: $$\frac{n!}{r!(n-r)!} = \frac{n\cdot(n-1)\cdot(n-2)\cdot(n-r+1)}{r!}$$

The numerator is a product of $r$ consecutive integers. Can you prove now, using induction, that the product of $r$ consecutive integers is always divisible by $r!$?

share|cite|improve this answer
Well I had a go, and no I couldn't, but fortunately someone else could: – Luigi Plinge Jun 4 '13 at 21:55

Under the assumption that $0\le r\le n$, and $r,n\in\mathbb{N}$, this expression counts the number of ways to choose $r$ out of $n$ distinguishable objects.

share|cite|improve this answer

The symmetric group $S_n$ has $n!$ elements. Letting it act on $n$ points, of which $r$ are coloured red the the remaining $n-r$ are coloured yellow, the subgroup of $S_n$ that of permutation that do no affect the colouring is isomorphism to $S_r\times S_{n-r}$ (permuting red and yellow points among each other independently). By Lagrange's theorem, the order $r!(n-r)!$ of the stabiliser subgroup divides the order $n!$ of the whole group.

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.