Take the 2-minute tour ×
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.

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

share|improve this question
3  
you can use induction in Pascal's triangle –  pascalhein Jun 4 '13 at 20:16

3 Answers 3

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|improve this answer
    
Well I had a go, and no I couldn't, but fortunately someone else could: math.stackexchange.com/a/12121/43314 –  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|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|improve this answer

Your Answer

 
discard

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.