Gfrktyl

I'm having a hard time reasoning through the formula for combinations $frac{n!}{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?

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 $frac{20!}{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 $frac{n!}{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).

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: $$frac{100!}{(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,560×40,560= 105,287,270,400 times as many positions if you distinguish between indistinguisable pieces swapping places. brings it less than $1.22times 10^{78}$ instead of more than 1.26 times 10 to the 89 .

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 $$ frac{5!}{3!2!}$$.

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) = frac{n!}{(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) = frac{P(n,k)}{k!}$$

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

$$C(n,k) = frac{P(n,k)}{k!} = frac{1}{k!} P(n,k) = frac{1}{k!} cdot frac{n!}{(n-k)!} = frac{n!}{k!(n-k)!}$$