4

The formula for combinations without the repetitions is as follows: $$ \frac{n!}{r!(n-r)!}$$

This is achieved by doing $$\frac{n!}{(n-r)!}*\frac{1}{r!}$$

What I don't understand where $\frac{1}{r!}$ comes from. I know that the first part is what you do when you have n things and want all the combinations of r of those things, in a way that order doesn't matter.

How does this $\frac{1}{r!}$ remove repetitions taking in consideration the order? My guess is that $\frac{1}{r!}$ is the percentage of $\frac{n!}{(n-r)!}$ things that are repetitions, but how was this value discovered? Is it just a coincidence or property or is there some logic behind this?

Thanks.

Segmentation fault
  • 1,765

2 Answers2

3

You have $n$ elements to put in the first place, $n-1$ in the second place, ... , $n-1+r$ in the $r^{th}$ place. Now you have $\frac{n!}{(n-r)!}$

If you have a set of $r$ elements, then you have $r!$ permutations of said set. Permutation is essentially a way you can order such $r$ elements.

Since with combinations you don't order elements, which at first you did, you must divide the first expression by $r!$, and then you get $\frac{n!}{(n-r)!r!}$ .

mivan
  • 95
2

Try choosing two items out of five, so with $n=5$ and $r=2$:

The first can be any of five and, given the first choice, the second can be any of the remaining four. That makes the number of possibilities $5\times 4= \dfrac{5!}{3!}$

But these possibilities have an order. In full they are $$(1,2), (2,1), (1,3), (3,1), (1,4), (4,1), (1,5), (5,1), \\ (2,3), (3,2), (2,4), (4,2), (2,5), (5,2), \\ (3,4), (4,3), (3,5), (5,3), \\(4,5), (5,4)$$

and to get the ordered possibilities you need to divide this by $2!$ as the number of orders of $r$ items

Henry
  • 157,058