Possibilities

Tree Diagrams



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.

Permutations

A permutation is an arrangement of things in which order matters. Putting the same items in a different order gives a different permutation.

Arranging everything: factorials

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 01234 5610
n! 112624 1207203,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.

Arranging some of the things

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.

When things can repeat

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.

Combinations

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.

From permutations to combinations

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.

Examples

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.

Permutation or combination?

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
In Excel

More on combinations and permutations.
Khan Academy on counting, permutations, and combinations.