[Math] Why do we divide Permutations to get to Combinations

combinatoricspermutations

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

Best Answer

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.