mjhjmtu

I'm having a hard time reasoning through the formula for combinations $fracn!k!left(n-kright)!$. I understand the reason for the permutations formula and I know that for the combinations we divide by $k!$ to adjust for the repeated cases, since order does not matter. But what exactly happens when we divide the set of permutations by $k!$ ?

I know this may seem like a silly question... I just can't take this for granted, lest I miss a chance to apply it correctly. Can you describe what's happening here step by step, sort like debugging a script?

Let $X$ be a finite set of size $n$. Suppose we want to know the number of combinations of size $k$. First a definition:

A combination is a subset of $X$

So let us instead ask: How can we construct a combination? I suggest that we do this by constructing a permutation. Let’s use this definition:

A subpermutation of $X$ is some subset of $X$ with some ordering attached.

There are two ways two proceed. This one is called forwards:

How do we construct a subpermutation? Well it has to be ordered so let’s choose the first element. There are $n$ choices and we can partition the set of permutations by the choice of first element, so we haven’t missed anything yet with this choice and we haven’t double counted anything. So we carry on and eventually we stop after $k$ elements and conclude that there are $fracn!(n-k)!=n(n-1)cdots(n-k+1)$ subpermutations of size $k.$

Given a subpermutation we can forget the order to get a combination. However as there are multiple subpermutations with the same set and different orders, we have counted the same combination multiple times by getting to it in different ways. If we divide by the number of ways of getting to each combination, we will not be counting things multiple times. So how many ways to get to a combination? Well that’s the number of ways to have a different order on a subpermutation without changing the set. How many of those? Well there’s $k$ choices for the first, $k-1$ for the second, and so on, so $k!$ total, hence we divide by $k!.$

This is the backwards way:

Suppose we know there are $C$ combinations of size $k$ and we want to compute $P,$ the number of subpermutations of size $k$. Here is an algorithm:

1. Choose a combination of size $k$
   


2. Choose some ordering on that combination

And there are $C$ ways of doing part 1, and $k!$ ways to do part 2, so there are $Ck!$ ways to make a subpermutation of size $k.$ We haven’t double counted because we don’t double count in step 1 or 2 and two subpermutations need the same set and the same order to be equal. Therefore $P=Ck!$, but we happen to know $P$ and not $C$ so we can deduce $C=frac Pk!$

Maybe, looking at an example clarifies this best :

You have $20$ objects and have to choose $5$ of them. How many possibilities are there ?

You have $20,19,18,17,16$ choices explaining how $frac20!15!$ comes into the play.

Now each combination can appear in $5!$ possible orders which correspond to the same combination. Therefore we have to divide by $5!$ to find the number of combinations.

This can be generalized to arbitary numbers explaining how the binomial coefficient emerges.

Let's bunch together permutations that have the same content. Each resulting equivalence class has $k!$ members. Therefore, the number of such classes is $k!$ times smaller than the number of permutations. A combination is just an equivalence class or, if you prefer, one nominated element thereof.

Assume that you want to know the number of combinations of $k$ elements out of $n$ elements. One way to pick such a combination is the arrange all $n$ elements in any arbitrary order (there are $n!$ ways to do so) and pick the first $k$ of them as "your selection". As the remaining $n-k$ elements can be arranged in any order, each ordered selection of the first $k$ elements appears $(n-k)!$ times in the set of all permutations of the $n$ elements, so you have to divide $n!$ by $(n-k)!$ to count the different (ordered) "selections" of $k$ elements. Now, as you are not interested in the order of the $k$ elements, all $k!$ permutations of a "selection" represent the same combination, so you still have to divide the number by $k!$, which makes a total of $fracn!k!(n-k)!$ combinations. So, in short, this dividing "removes the order" when counting (here: the order of the first $k$ elements and the order of the remaining $n-k$ elements).

Instead of trying to figure out directly why we should divide the permutations by $k!$, let's try thinking of it from the other direction:

Given $n$ distinct objects, there is some number of ways of choosing a combination of $k$ of those objects where the order of objects in the final list of $k$ doesn't matter.
Let's not worry about exactly how to calculate that number yet;
it's enough to know that it exists. (We could, for example, just list all
the combinations by brute force with careful checking for duplicates.)
For any $n$ and any $k,$ let $C(n,k)$ represent the number of combinations.

Now consider one of those combinations of $k$ items.
If we want to count permutations (where order matters),
this single combination can be arranged in $k!$ distinct permutations.
None of those permutations is the same as any permutation derived from any other combination of $k$ items.
So if we go through the combinations one by one, each adds $k!$ new permutations
to the total. But there are $C(n,k)$ combinations.
So $P(n,k),$ defined as the total number of permutations of $k$ items selected from $n$ distinct items, obeys the equation
$$ P(n, k) = C(n, k) times k!.$$

Now it is a simple arithmetic operation to divide by $k!$ on both sides, with the result
$$ C(n, k) = fracP(n, k)k!.$$

And that's why we divide the number of permutations by $k!.$

My favorite way of explaining this to myself actually would be something in this vein.

Suppose we have a set of $n$ objects, and we want to find the number of unique $k$-arrangements of them - that is, take $k$ objects from the $n$, and each unique arrangement counts as a single one. The term "arrangement" is important - that means order matters. We know this to be given by

$$P(n,k) = fracn!(n-k)!$$

You can rationalize this by thinking of your $k$-arrangement having "slots", and filling them in order. The first slot can be filled by $n$ potential items, the second by $n-1$, and in general the $i^th$ by $n-(i+1)$. This gives

$$P(n,k) = n(n-1)(n-2)...(n-i+1)$$

It is a trivial exercise in algebra to show both expressions are equal.

This becomes relevant when we consider the selection argument. In this case we want the number of $k$-selections - the number of ways to take $k$ objects from the $n$, but this time order doesn't matter.

This is my favorite way to think of it because I didn't realize this until a few weeks ago - I had just been blindly using the known formulas until an "aha!" moment.

Consider a particular $k$-arrangement from our permutation argument. Let it be the permutation

$$(x_1,x_2,x_3,...,x_k)$$

where each $x_i$ is one of the $n$ objects. We know that, no matter which way we arrange this, however, it will be considered the same selection, because in selections/combinations, order does not matter. I could swap $x_1$ and $x_2$, or I could reverse the order, or I could order them "even-odd-even-odd" -- it doesn't matter, they're all the same one.

Which then brings up the question - how many ways are there to rearrange $k$ objects? We know this to be $P(k,k) = k!$. This means that, for every particular arrangement, it is in a sort of "class" of arrangements that are indistinct as selections. For every arrangement of $k$ objects, only one of those $k!$ arrangements is distinct - and that is for every arrangement.

That allows us to conclude that the number of selections/combinations is given by

$$C(n,k) = fracP(n,k)k!$$

Explicitly using the formula for $P(n,k)$, then,

$$C(n,k) = fracP(n,k)k! = frac1k! P(n,k) = frac1k! cdot fracn!(n-k)! = fracn!k!(n-k)!$$

Imagine you have $5$ sports cars that are to be displayed in an event, but there are only 3 spots avaiable. Lamborghini, Mercedez, Ferrari, Porsche, and Bugatti.

Let's say you choose a Mercedez, a Ferrari, and a Lamborghini. There are $5 times 4 times 3 = 5!/2!$ ways to arrange these cars

Notice, however, that the display (Lamborghini, Mercedez, Ferrari) is the same display as (Mercedez, Ferrari, Lamborghini) because you have the same selection of cars. You can arrange $3$ objects in $3!$ ways and still have the same collection of objects.

Therefore you must divide the $5 times 4 times 3 = 5!/2!$ by $3!$, leading to $$ frac5!3!2!$$.

This is the formula for selecting from a distinct list of items. Lets say we pick from 100 songs on a top song list. We only care to pick the top 5 songs. Okay, there are 100! ways to arrange the songs on the original list. Once we take off the top 5, two things happen. The order of the remaining 95 don't matter they aren't the top 5, dividing by 95! cuts that away. We don't care what order the Top 5 are played in, so we divide out the possible orders those top 5 could have, 5! in total number. This arrives us at: $$frac100!(95!)(5!)$$

EDIT: To show why distinctness matters, Here's a case, where it won't give you the number of distinguishable states chessboard positions (legal or not, with all 32 pieces). Why because you have 2 each of indistinguishable rooks,knights,and bishops on each side, as well as 8 indistinguishable pawns on each. This means there are 2×2×2×2×2×2×40,320×40,320=104,044,953,600 times as many positions if you distinguish between indistinguisable pieces swapping places.

Edited chess example due to calculation error.