Combinatorics

Combinations

“Order doesn’t matter”

Combinations = # of subsets of size $k$

Combinations are the same as Permutations, except order doesn’t matter.

• When the order DOESN’T matter, there are less number of permutations, which is why we have the extra $k!$ at the bottom.

We use the Binomial Coefficient to calculate the number of combinations.

Suppose we select $k$ slots from $n$ objects (where order doesn’t matter), the number of ways this can be done is (”$n$ choose $k$”): $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{(n-k)!k!}{=}_n{C}_k$

Sidenote: ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$

• This comes from the Binomial Theorem

Proof

We derive combinations from the idea that ${}_n{C}_{k}k!{=}_n{P}_k$

I am still having trouble understanding how to think about permutations.

Related

• Permutations
• Binomial Coefficient