3 Combinations#
Combinations are a way to count the numbers of ways to choose \(k\) objects from a set of \(n\) objects without regard to order.
We can think about this in the following way: We have \(n\) objects and order them in some way. Then we choose the first \(k\) objects in the order. This intuition leads to the following rule:
There are \(n!\) ways to order \(n\) objects. However, when we choose the first \(k\) objects, the order of that subset doesn’t matter. So, we have to divide out the number of ways to order the \(k\) objects. This is \(k!\). Similarly, the order of the remaining \(n-k\) objects also doesn’t matter, so we have to divide out \((n-k)!\).
Example: Who gets cake?
There are 20 people at a party, but only 5 of those get cake. How many ways can we choose the 5 people to get cake?
Step 1: We first form a line of 20 people. The first 5 people in the line get cake. How many ways can we order the 20 people? Since all 20 people are distinct, there are \(20!\) ways to order them.
Step 2: We choose the first 5 people. But they all get the same cake. For them it doesn’t matter if they are at the first or the fifth position. So, we have to divide out the number of ways to order the 5 people. This is \(5!\).
Step 3: For the last 15 people, it also doesn’t matter in which order they are: It doesn’t matter if you are at spot 6 or 20 in the line, you don’t get cake. So, we have to divide out the number of ways to order the 15 people. This is \(15!\).
So, the total number of ways to choose 5 people out of 20 that get cake is:
Choosing \(k\) objects from \(n\) objects{rule}
The number of ways to choose \(k\) objects from \(n\) objects is: