# ${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) is chosen or not. Now we use the obvious identity ${n \choose 1}=n$ and also that ${n \choose 2}=\sum_{i=1}^{n-1} i=\frac {n(n-1)}{2}$, both of which can be proved combinatorically and argue by induction, first on $r$ and then on $n$.

But this is a very lengthy process and I think not a good solution. Is there any shorter and better method to do this.

• – lab bhattacharjee Jun 21 '14 at 16:36
• Let $F(n,r)=\frac{n!}{r!(n-r)!}$. It is a not hard computation to show that $F(n,r)$ satisfies the Pascal Identity and the initial conditions for $\binom{n}{r}$. So $F(n,r)=\binom{n}{r}$ for all $n,r$. That is probably in essence what you did, and it is perfectly fine if one wants to write a non-counting proof. – André Nicolas Jun 21 '14 at 18:18
• Resort to the natural language definition of $n \choose r$. The number of ways of choosing $r$ from $n$ is the sum of the number of ways two mutually exclusive events can occur: (a) choose a given item $S_n$ and then choose $r-1$ items from the remaining $n-1$; or (b) reject a given item $S_n$ and then choose $r$ items from the remaining $n-1$ – Marconius Jul 6 '15 at 21:42