Gfyuki

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!}$$.