Example: We posit that two teams are evenly matched, but
one happens to be up, 3-2, in a seven game series. What are the
odds the team that is up will win?
Tree diagram:
So, if each branch is equally likely:
Half the time, the Warriors win game 6, and the series is over.
The other half the time, the Cavs win game 6. Then, half the time,
the Warriors win game 7, and half the time the Cavs win game 7.
One half of one half is one quarter... so 25% of the time the Cavs
win the series.
Example:You have gone out for dinner, and have various
after-dinner options (my graphic should say "dessert," not
"desert"):
So how many possible ways can we eat dessert? Three choices for the
sweet, and two for the beverage. 2 * 3 = 6.
If we were the sort of person who chose our meal randomly, there
would be a 1/6 probability of getting any one of those
combinations.
More on probability tree diagrams.
Khan Academy video on tree diagrams.
A permutation is an arrangement of things in which order matters. Putting the same items in a different order gives a different permutation.
Example: In how many orders can we line up three books,
A, B, and C, on a shelf?
We can simply list them all:
ABC, ACB, BAC, BCA, CAB, CBA
That is 6 orders. Or we can count the way we did with tree
diagrams: there are 3 choices for the first slot, then 2
books left for the second slot, then only 1 for the last.
So 3 * 2 * 1 = 6.
In general, n different things can be arranged in n * (n - 1) * (n - 2) * ... * 2 * 1 ways. This product comes up so often that it has its own name and symbol: n factorial, written n!
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 10 |
|---|---|---|---|---|---|---|---|---|
| n! | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 3,628,800 |
Factorials grow very fast: ten people can stand in a line in
over three and a half million different orders!
Note that 0! = 1. As with the light switches on the
Pascal's Triangle page,
there is exactly one way to arrange nothing at all: leave it
alone.
Often we only fill a few places from a larger group.
Example: Eight runners are in a race. In how many ways
can the gold, silver, and bronze medals be awarded?
There are 8 possible gold medalists. Once gold is decided,
7 runners are left for silver, and then 6 for bronze:
8 * 7 * 6 = 336
The number of permutations of k things chosen from
n is written nPk,
and the formula is:
nPk =
n! / (n - k)!
For the race: 8! / 5! = 40,320 / 120 = 336. Dividing by
5! just cancels the runners who did not get a medal.
If an item can be used more than once, every place has the
full set of choices.
Example: How many four-digit PINs are there? Each
digit can be any of 0 through 9, so:
10 * 10 * 10 * 10 = 104 = 10,000
So someone guessing a PIN at random has a 1 in 10,000
chance of getting it right on the first try.
In general, filling k places when each has n
choices gives nk possibilities.
A combination is a selection of things in which order does not matter: we only care which items are chosen, not the order they were chosen in.
Example: From the same eight runners, the top three
advance to the final. How many different groups of three
can advance?
We know there are 336 ordered ways to pick three runners.
But the group {Ana, Ben, Cal} shows up in that count once for
each of its 3! = 6 orders (ABC, ACB, BAC, BCA, CAB, CBA). So
each group is counted 6 times:
336 / 6 = 56 groups
The number of combinations of k things chosen from
n is read "n choose k" and written
nCk or
C(n, k). The formula is:
nCk =
n! / (k! (n - k)!)
That is, the permutations, divided by the k! orders
that we no longer care about.
Notice that choosing 2 toppings to put on is the same as choosing 4 to leave off: in general, n choose k equals n choose (n - k). The numbers in Pascal's Triangle are exactly these "choose" numbers: row n, position k is n choose k.
Ask: if I rearranged my choices, would I have a different outcome? If yes, order matters, and it is a permutation. If no, it is a combination.
| Situation | Does order matter? | Count |
|---|---|---|
| President, VP, and treasurer from 10 members | Yes | 10P3 = 720 |
| A 3-person committee from 10 members | No | 10C3 = 120 |
| Order of 5 songs on a playlist | Yes | 5! = 120 |
| 2 pizza toppings out of 6 | No | 6C2 = 15 |
=FACT(5) gives 5! = 120
=PERMUT(8, 3) gives
8P3 = 336
=COMBIN(8, 3) gives
8C3 = 56
More on combinations and permutations.
Khan Academy on counting, permutations, and combinations.