Dividing factorials is always integer

Question

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

Answer 1

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!$?

Answer 2

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.

Answer 3

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.