One Choice After Another

Everything in counting comes from one rule: choices made one after another multiply. The rule is obvious, its condition is not, and the condition is where every counting error begins.

Here is a question that can be answered by writing out every possibility, and

one that cannot.

A café offers three sandwiches and two drinks. How many lunches are possible?

Six, and you can list them in ten seconds.

A password is eight characters, each a lowercase letter. How many passwords are

possible? Listing is out of the question, and yet the answer is as easy to

produce as the first one, because both use the same rule.

FIG 1Choices one after another multiply

: the number of possible results, which is what we are after
: the number of stages, meaning how many separate choices are made to build one result
: the number of options at the first stage
: the number of options at stage i, which must be the same count whatever was chosen at the earlier stages. This is the condition, and it is the only thing that can go wrong

Three sandwiches and two drinks gives six lunches. Twenty six letters chosen eight times gives twenty six multiplied by itself eight times, which is about two hundred thousand million. The second calculation is no harder than the first and that is the point of having a rule: counting by listing stops working at about twenty, and counting by multiplying never stops working. Everything else in this course is this rule applied repeatedly, or this rule applied and then corrected for something that got counted more than once.

The rule

The justification is worth seeing once, because it also makes the condition

visible. Draw the choices as a tree.

FIG 2Why it is a product, drawn as a tree

step	depth	what happens	how many at this level
1	the trunk	nothing chosen yet	1
2	first branching	pick one of three sandwiches	3
3	second branching	from each of those three, pick one of two drinks	3 times 2, which is 6
4	third branching	from each of those six, pick one of four pastries	6 times 4, which is 24
5	the leaves	each leaf is one complete lunch, and no two leaves are the same lunch	24 lunches
6	the pattern	each level multiplies the count by its own branching factor	3 times 2 times 4

6 steps

The tree is not an illustration of the rule, it is the proof of it. Each existing branch sprouts a full set of new ones, so the count at each level is the previous count multiplied by the branching factor. Two things are worth noticing. The leaves are all distinct, which is why nothing is counted twice, and every lunch appears somewhere, which is why nothing is missed. Those two properties are what a correct count needs, and the second half of this course is about situations where one of them quietly fails.

The condition

The rule as usually remembered is just multiply, and the thing dropped is the

condition under which multiplying is right.

The number of options at each stage has to be the same no matter what was

chosen earlier. Not the options themselves, only how many there are. That

distinction does most of the work in practice.

FIG 3Does the multiplication rule apply?

	options at stage one	options at stage two	same count every time?	may we multiply?
three sandwiches then tw	3	2	1	1
deal a card, then deal a	52	51	1	1
pick a main, then a dess	4	0	0	0
pick a letter, then a di	26	25	1	1
pick any three digit cod	10	10	1	1

The second row is the one that teaches the distinction. After the first card is dealt the remaining cards are a different set depending on what came out, but there are always fifty one of them, so the count is fixed and multiplying is allowed. The marked row is the failure: if some mains have three matching desserts and others have five, then the second count depends on the first choice and the product is meaningless. A nought in the second column means the count varies rather than that it is nought. The repair is never to abandon counting, it is to split into cases, count each case with the rule, and add the cases up.

When the condition fails, the situation has not become uncountable. It has

become two or three situations, each of which satisfies the condition. Count

each separately and add. That manoeuvre, splitting into cases and adding, is

the only other tool in counting besides multiplying, and the two of them

together handle almost everything.

The same choice, repeated

The special case where every stage offers the same number of options is worth

its own name, because it is where the counts stop being imaginable.

If each of $k$ stages has $n$ options, the product is $n$ multiplied by itself

$k$ times, which is $n^k$ . The base counts how many ways one stage can go. The

exponent counts the stages. Mixing up which is which is the most common

mechanical error in the subject, and the cure is to say the two numbers aloud

with their units attached: twenty six letters, eight positions.

FIG 4Counting by listing and counting by multiplying, compared

python

from itertools import product

lunches = list(product(['ham', 'cheese', 'egg'], ['tea', 'water']))
print(len(lunches))                      # 6, by listing them all

print(3 * 2)                             # 6, by the rule

print(26 ** 8)                           # 208827064576 possible passwords
print(26 ** 8 / 1e6 / 3600 / 24 / 365)   # 6.6 years to list at a million a second

print(26 ** 9 / 26 ** 8)                 # 26: one more character is 26 times more work

The first block lists every possibility and counts them, which is honest, slow and correct. The second computes the same number by the rule. They agree, which is the point: the rule is not an approximation or a shortcut that loses something, it is the same count obtained without doing the work. The third block shows why the shortcut is not optional. Listing eight character passwords at a million per second would take about six years, and the rule answers it instantly.

The last line of that code is the point of the whole lesson. Adding one stage

does not add to the total, it multiplies it. A password one character longer is

twenty six times harder to guess. A search one move deeper is many times

bigger. A model with one more binary setting has twice as many configurations.

This is the multiplicative growth of the previous course, arriving from a

completely different direction, and the connection is exact: the number of

stages is an exponent, so the only way to talk about these counts comfortably

is through their logarithms. A password space of twenty six to the eight is

about ten to the eleven, or around thirty seven bits, and that is the form in

which security people quote it, for precisely the reasons the previous course

gave.

What to do with a confusing problem

Three habits settle most counting arguments before they start.

Say what one result looks like. Not how many there are, but what a single

complete outcome is: one lunch, one password, one seating plan. Until that is

clear the stages cannot be identified, and most confusion in counting is

confusion about what is being counted.

Name the stages in order and the number of options at each. Writing them as a

list of numbers, three then two then four, makes the product obvious and makes

a missing stage visible.

Check the condition on the stage you are least sure about, and if it fails,

split into cases. Then multiply within each case and add the cases.

The next lesson applies the rule to the situation where the options run out as

you go, which gives the factorial and, with it, the first count in this course

that grows faster than anybody expects.

Recap

When a thing is built by making one choice after another, the number of possible results is the product of the number of options at each stage. This single rule generates every other counting formula in the course, which is why it is worth stating carefully rather than assuming.
The rule requires that the number of options at each stage does not depend on what was chosen earlier. The options themselves may change; only the count has to stay fixed. Checking that condition is the whole skill, because when it fails the multiplication silently gives the wrong answer.
When every stage offers the same number of options, the product becomes a power, and the number of stages sits in the exponent. That is where the explosive growth of search spaces comes from, and it is the same exponent the previous course taught you to reach with a logarithm.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextPutting Things in Order →