Counting outcomes: tree diagrams and the product rule

This topic is about finding out how many different ways we can put things together. That could be how many different ways we can shuffle a deck of cards, or how many different codes there can be on a padlock. The maths behind it is called combinatorics; in the exam it turns up as systematic listing and the product rule for counting.

The thing to take with you is that there are two tools. The tree diagram draws every possibility so you can count them, and it's the right place to start. The product rule and the factorial are the shortcuts you switch to when the tree would be far too big to draw.

The tree diagram for counting

You may have seen the tree diagram in probability, but we can actually also use it to find out how many ways we can put things together. So the tree is a good tool that can show us many different things.

Let's look at an example. Say we're out buying ice cream. We want 3 scoops, but we need to work out how to combine them. We have 3 different flavours to choose from: chocolate, strawberry and raspberry. How many different ways can we put an ice cream together? Here we can use the tree diagram.

We can see on the tree that when we choose the first scoop we have 3 different choices. For each of those choices we again have 3 different choices for the 2nd scoop. For each of those we again have 3 choices for the 3rd scoop. We now count all the last branches and see that we have 27 different combinations of scoops.

Notice how the tree is drawn: one column per scoop, and every branch splits into 3 new branches at the next column. That's what makes it systematic: every branch is split the same way at every step.

Where the tree stops working

The tree diagram is really good for getting an overview of the situation, but where it gets hard is when there are many different combinations. If we had a deck of cards and wanted to find out how many different ways the deck can be shuffled, it becomes impossible to do with a tree diagram. So the tree only works well when we're not dealing with a huge number of possibilities.

The tree isn't the fastest way to work it out either. For the ice cream we drew 27 branches to find the answer, and you can already see the pattern in the drawing: 3 choices, then 3 for each of those, then 3 for each of those. That pattern is the product rule.

The product rule: both-and

We use the multiplication rule, which the exam calls the product rule for counting, when we have a both-and situation. If we want to buy a sandwich where we can choose between 3 kinds of bread, 2 kinds of meat and 4 kinds of cheese, how many ways can we put it together? We want both bread and meat and cheese, so this is a both-and situation, and we just multiply all our options together:

$$3 \times 2 \times 4 = 24$$

We could easily have used the tree here as well, but it's a bit faster to multiply. The same words, both-and and either-or, are the ones we used to pick a rule in probability, and they do the same job here. The full walkthrough, including the either-or case where we add instead, is in the guide about the product rule for counting.

The factorial: when the chain gets long

Say we have 5 children we need to line up in a row. 5 children can stand in 1st place, then 4 in 2nd place, 3 in 3rd place, and so on, so the number of different line-ups is

$$5 \times 4 \times 3 \times 2 \times 1 = 120$$

For a deck of cards the same chain would start at 52 and get very long, so we have a shorter way of writing it: $52!$, read as 52 factorial. The exclamation mark just means multiply all the numbers together, all the way down to 1. That notation gets its own guide about factorials.

Common misunderstandings

• "A tree diagram works for any size of problem." It doesn't. It's great for an overview, but with a deck of cards it becomes impossible to draw. The tree only works well when there aren't too many possibilities.
• "When I combine things I always multiply." Only in both-and situations, where you take one thing from each set. If you're only picking one thing in total, either this or that, you add the options instead.
• "The factorial is a new kind of calculation I have to learn." It isn't a new operation at all. It's just a shorter way of writing a chain of multiplications, made because the long version gets very long.

Related guides

• The product rule for counting
• What is a factorial?
• Tree diagrams in probability, the same tree with green and red branches
• What is probability?