Why do we divide with r! when calculating combinations without repetitions

Question

The formula for combinations without repetitions is $_nC_r=\frac{n!}{r!(n-r)!}$.

I understand the part $n!/(n-r)!$. That part should calculate all possible combinations (numerator $n!$), then remove the unnecessery ones (denominator $(n-r)!$) which overflow $r$ allowed places.

But after calculating $n!$, then cleaning it up with $(n-r)!$, how does $r!$ remove those combinations that only differ by order of elements? I understand the logic behind $n!/(n-r)!$, but after we get the number of all possible combinations of $n$ elements in $r$ places, why does $r!$ divide $n!$ such that it outputs the number of possible combinations with different elements, i.e. it ignores the combinations that differ by order of elements?

Answer 1

Right, so you understand that $n!/(n-r)!$ is the number of ways of selecting $r$ numbers from $n$ numbers $\{1,2,\ldots,n\}$ so that the order of the selections count (I figure we might as well use numbers for the things we are selecting since it provides us with a solid example).

Let's say that $\binom{n}{r}$ is the number of ways of selecting $r$ numbers from $n$ numbers so that the order doesn't count, we'll call these "ordered selections". We haven't got a formula for $\binom{n}{r}$ yet but we know what we want it to mean.

Now imagine listing the $\binom{n}{r}$ ordered selections, each one a unique combination of $r$ numbers. We can further imagine that each selection of $r$ numbers in our list of $\binom{n}{r}$ selections is displayed in ascending order therefore justifying us calling them "ordered selections".

Now we can use our list of ordered selections to make a list of selections where order does count, "unordered selections" for short. We simply permute the $r$ numbers in each ordered selection and list them too.

Each of the $\binom{n}{r}$ ordered selections of $r$ numbers has $r!$ distinct permutations, so our new list has $r!\binom{n}{r}$ unordered selections. But we already know this is also $n!/(n-r)!$, so

$$r!\binom{n}{r}=\frac{n!}{(n-r)!}$$ $$\implies \binom{n}{r}=\frac{n!}{r!(n-r)!}$$

---

Example:

List all ordered selections of 3 numbers from $\{1,2,3,4\}$ so $n=4$ and $r=3$:

$$\begin{array}{c}(1,2,3)\\(1,2,4)\\(1,3,4)\\(2,3,4)\end{array}$$

We see that $\binom{4}{3}=4$ by listing these. But the crux here is that we can now use each ordered choice to list the rest of the unordered selections by permuting the numbers of each ordered selection. Notice there are $3!=6$ permutations of each ordered selection (including the original ascending order permutation):

$$\begin{array}{cccccc}(1,2,3)&(1,3,2)&(2,1,3)&(2,3,1)&(3,1,2)&(3,2,1)\\(1,2,4)&(1,4,2)&(2,1,4)&(2,4,1)&(4,1,2)&(4,2,1)\\(1,3,4)&(1,4,3)&(3,1,4)&(3,4,1)&(4,1,3)&(4,3,1)\\(2,3,4)&(2,4,3)&(3,2,4)&(3,4,2)&(4,2,3)&(4,3,2)\end{array}$$

So $3!\binom{4}{3}$ is the number of un ordered selections. We know this is $4!/(4-3)!$ so to parallel the general argument above, we have

$$3!\binom{4}{3}=\frac{4!}{(4-3)!}$$

$$\implies \binom{4}{3}=\frac{4!}{3!(4-3)!}$$

Going forwards from the first list to the second is equivalent to multiplying the list size by $3!$. Going backwards from the second list to the first is equivalent to dividing the list size by $3!$. This multiplication principle in reverse is sometimes called the division principle although they are really one and the same.

Answer 2

Each permutation of a given variation give us the same combination.

So since there is ${n!\over (n-r)!}$ variation of order $r$ we must divide it by $r!$

Answer 3

Consider a simple case with n=3 and r=2. Then with n!/(n-r)! We are counting

AB AC BA BC CA CB

but we are only interested in pairs independent by the order then we divide by $r!$.

Answer 4

How many ways are there to pick $r$ objects out of $n$?

Well, here is one way to do that: line up all $n$ objects randomly, and simply pick the first $r$ of that line-up.

Now, there are $n!$ line-ups possible, but that overcounts the number of ways to get $r$ out of $n$ in two ways:

First, the first $r$ objects in the line-up could be switched around, but any such switcheroo will still lead to the same $r$ objects being picked. Since there are $r!$ ways to mix up the first $r$ objects, we are therefore overcounting by a factor of $r!$

Second, the $n-r$ remaining objects can also swap places, while still leading to the same group of $r$ objects being picked. So, we are also overcounting by a factor of $(n-r)!$

So, we need to divide $n!$ by $r!$ and by $(n-r)!$

Answer 5

You make your selection of $r$ elements from the $n$, but because this is a combination, you don't care which order they were selected in.

So choosing $(23,45,67)$ is the same as choosing $(45,67,23),$ $(67,23,45),$ $(67,45,23),$ $(45,23,67),$ or $(23,67,45)$. Removing that order-of-choosing variation is the $r!$ in the denominator, since the chosen elements can occur in $r!$ orders (and for combinations, we're not interested in order).

Note that $n!$ calculates all the possible permutations of the full set, and $n!/(n-r)!$ calculates the permutations of every possible portion of the set that is $r$ in size - which can be seen as a selection process, choosing $r$ items successively.

For example, the $n!/(n-r)!$ value calculates the drawing of bingo balls in order - like the (ordered) tuple $(34, 67, 12)$. If we tip the selected balls into a bucket, the order they were drawn is no longer relevant - like the set $\{12,34,67\}$, which doesn't have an order, but can be created from $r!$ ordered tuples.