Count outcomes without listing them. Choices made in stages multiply, as a tree shows; cases that cannot happen together add; and an overlap is subtracted once. Worked on pairs, strings of bits, the subsets of a set and a grid of training runs.
Count the outcomes of a choice made in stages by multiplying the numbers of options, and draw the matching tree.
Count the pairs from two sets, the strings of length k from n symbols and the subsets of a set of n elements.
Find the size of a union of two sets by adding their sizes and subtracting the size of their overlap.
Decide whether a count needs multiplying (one choice and then another) or adding (one case or another).
In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
The question
Before a model is trained, a few settings have to be fixed by hand. Say there are three: the learning rate (0.1, 0.01 or 0.001), the batch size (16, 32, 64 or 128) and the optimiser, the method that does the training (SGD or Adam). Trying every combination is called a grid search. How many training runs does it need, and how can you be sure without writing them all out?
Intuition
Start small. Leave the batch size aside for a moment: three learning rates, then two optimisers. Draw the choices as a tree. From a starting dot, one branch goes to each learning rate. From each learning rate, one branch goes to each optimiser. Every path from the dot to the right-hand end is one training run.
M01.8.1-F1
The same six runs counted twice. On the left, one path from the dot to each run; on the right, one cell for each pair of a learning rate and an optimiser. Both pictures hold \({3 \times 2}\) outcomes.
Count the paths. Each of the 3 learning-rate branches splits into the same 2 optimiser branches. That gives 2 paths, then 2 more, then 2 more. Adding the same number 3 times is exactly what multiplying means, so there are \({3 \times 2}\) runs, which is 6. The grid on the right says the same thing in another way: 3 rows and 2 columns make a rectangle of 6 cells.
That is the whole idea of this lesson, and it has two halves.
Choices made one after another multiply. If the second choice always has the same number of options, whatever the first choice was, the two counts multiply.
Cases that cannot happen together add. Every run uses SGD or Adam, never both. So the six runs split into three SGD runs and three Adam runs, and the two counts add up to six.
The rest of the lesson makes both halves exact, and repairs the one thing that can go wrong with adding: cases that overlap.
Build it up
Step 1. Pairs. Choose one element of a set \(A\), then one element of a set \(B\). The result is an ordered pair \((a, b)\), as in lesson M01.2.1, with the element of \(A\) written first. The set of all such pairs is the Cartesian product of \(A\) and \(B\), written \({A \times B}\) and read “\(A\) cross \(B\)”. Take the course’s sets \({A = \{2, 4, 6, 8\}}\) and \({B = \{1, 2, 3, 4\}}\). There are 4 choices for the first entry and, whatever it was, 4 choices for the second, so
\[
\abs{A \times B} = 4 \times 4 = 16.
\]
Order matters inside a pair: \((2, 4)\) and \((4, 2)\) both belong to \({A \times B}\), and they are two different pairs.
Step 2. Strings. A string of length \(k\) is a row of \(k\) symbols, such as the word “cab” or the bits 0110. If every place may hold any of \(n\) symbols, the choice is made in \(k\) stages with \(n\) options each. That is \(n\) multiplied by itself \(k\) times:
With the two symbols 0 and 1 there are \(2^k\) strings of \(k\) bits. As \(k\) runs from 0 to 10 this is the doubling sequence 1, 2, 4, and so on up to \({2^{10} = 1024}\) strings of ten bits. A PIN of four digits is a string of length 4 made from 10 symbols, so there are \({10^4 = 10{,}000}\) of them.
Step 3. Subsets. How many subsets does \(\{a, b, c\}\) have? Build a subset by asking each element in turn: in, or out? That is three stages with two options each. Write “in” as 1 and “out” as 0, and each subset turns into a string of 3 bits.
M01.8.1-F2
A subset is a row of in-or-out decisions. Three elements give three decisions with two options each, so there are \({2^3 = 8}\) subsets, from the empty set to the whole set.
Every subset gives exactly one string of bits, and every string gives back exactly one subset. So there are as many subsets as strings: \({2^3 = 8}\). The same argument, with \(n\) decisions instead of 3, shows that a set of \(n\) elements has \(2^n\) subsets. Machine learning meets this number when it decides which features a model should use: 20 candidate features have \({2^{20} = 1{,}048{,}576}\) subsets, far too many to try one at a time.
Step 4. Separate cases add. Pick one photo from a folder that holds 5 photos labelled “cat” and 3 labelled “dog”, where no photo has both labels. The photos split into two groups that share nothing, so there are 8 photos to pick from. Such groups are disjoint (lesson M01.6.1).
Step 5. Overlapping cases. Now let a photo carry both labels, as the images of a multi-label data set can. Number eight photos 1 to 8. The cat photos are \({A = \{2, 4, 6, 8\}}\) and the dog photos are \({B = \{1, 2, 3, 4\}}\). How many photos show a cat or a dog? Adding the two sizes gives 8, but photos 2 and 4 are in both sets and have been counted twice. Take the overlap away once:
\[
\abs{A \cup B} = 4 + 4 - 2 = 6.
\]
The six photos are 1, 2, 3, 4, 6 and 8. Photos 5 and 7 show neither animal.
The formal statement
NoteThe multiplication principle
Suppose a choice is made in \(k\) stages. The first stage has \(n_1\) options. Whatever was chosen before it, the second stage has \(n_2\) options, the third has \(n_3\), and so on up to \(n_k\). Then the whole choice can be made in
\[
n_1 \, n_2 \cdots n_k \text{ ways.}
\]
Why. Follow the tree one stage at a time. After stage 1 there are \(n_1\) paths. At stage 2 each of them splits into \(n_2\) branches, so every old path becomes \(n_2\) new ones, and there are \(n_1 n_2\) paths. Each further stage multiplies the number of paths by its own number of options. After stage \(k\) there are \({n_1 n_2 \cdots n_k}\) paths, one for each way of making the choice.
Three counts follow at once.
Pairs.\(\abs{A}\) choices and then \(\abs{B}\), so \({A \times B}\) has \(\abs{A}\,\abs{B}\) elements.
Strings. There are \(n^k\) strings of length \(k\) from \(n\) symbols: \(k\) stages of \(n\).
Subsets. A set of \(n\) elements has \(2^n\) subsets: \(n\) stages of in or out.
NoteThe addition principle
If a set is split into pieces and no element lies in two pieces, then the size of the set is the sum of the sizes of its pieces.
Why. Cut \({A \cup B}\) into three pieces that share nothing: the elements in \(A\) only, the elements in both, and the elements in \(B\) only. Call their sizes \(p\), \(q\) and \(r\), so that \(q\) is the size of the overlap \({A \cap B}\). By the addition principle,
\[
\abs{A \cup B} = p + q + r.
\]
Each set is made of two of the pieces, so
\[
\abs{A} = p + q, \qquad \abs{B} = q + r.
\]
Add these two lines. The overlap appears in both, so it is counted twice:
Subtract \(\abs{A \cap B}\) from both sides and the result follows. For the photos, \({p = 2}\) (photos 6 and 8), \({q = 2}\) (photos 2 and 4) and \({r = 2}\) (photos 1 and 3), which gives 6 again. When \(A\) and \(B\) are disjoint the overlap is empty, \({q = 0}\), and the formula becomes the addition principle.
Go deeper: three sets, and what the rule is called
The rule is called inclusion-exclusion: the overlap is included twice and then excluded once. For three sets the same bookkeeping gives
An element in exactly two of the sets is added twice, then taken away once. An element in all three is added three times, taken away three times and put back once. Either way it counts once.
Worked example
How many runs does the grid search of the question need? Make the choice in three stages.
M01.8.1-F3
The count, stage by stage. Each row is a learning rate, each pair of columns a batch size, and each half of a pair an optimiser. Every small box is one run; the yellow one is the run with learning rate 0.001, batch size 64 and Adam.
The learning rate: 3 options.
The batch size: 4 options, whichever learning rate was chosen. So far \({3 \times 4}\), which is 12.
The optimiser: 2 options, whatever came before. In all,
\[
3 \times 4 \times 2 = 24 \text{ runs.}
\]
How many of these runs use batch size 16, or Adam, or both? Let \(S\) be the runs with batch size 16 and \(T\) the runs with Adam. Each is a smaller grid, counted by the same principle:
\(S\): 3 learning rates, 1 batch size and 2 optimisers, so \({\abs{S} = 6}\).
\(T\): 3 learning rates, 4 batch sizes and 1 optimiser, so \({\abs{T} = 12}\).
\({S \cap T}\): 3 learning rates, 1 batch size and 1 optimiser, so \({\abs{S \cap T} = 3}\).
By the union rule,
\[
\abs{S \cup T} = 6 + 12 - 3 = 15.
\]
Check by counting the rest. A run is outside \({S \cup T}\) when its batch size is not 16 (3 options) and its optimiser is SGD (1 option). With the 3 learning rates,
\[
24 - 3 \times 3 \times 1 = 24 - 9 = 15.
\]
Two different routes give the same answer.
Code
First from scratch. Three loops, one inside another, make the choice in three stages, and each pass through the innermost loop adds one run to a list.
rates = [0.1, 0.01, 0.001]batches = [16, 32, 64, 128]optimisers = ["SGD", "Adam"]# Start with an empty list of runs.runs = []# Stage 1: each learning rate ...for rate in rates:# stage 2: ... with each batch size ...for batch in batches:# stage 3: ... with each optimiser.for opt in optimisers:# One run, kept as a tuple. runs.append((rate, batch, opt))print(len(runs), "runs")print("the first three:", runs[:3])
24 runs
the first three: [(0.1, 16, 'SGD'), (0.1, 16, 'Adam'), (0.1, 32, 'SGD')]
Now the union. Python’s set type has | for union and & for intersection, so the rule can be checked directly on the photos, and then on the runs of the worked example.
# Photos with a cat, and photos with a dog.A = {2, 4, 6, 8}B = {1, 2, 3, 4}union =len(A | B)rule =len(A) +len(B) -len(A & B)print(union, "=", rule)# Runs with batch size 16, and runs with Adam.S =set()T =set()for run in runs:if run[1] ==16: S.add(run)if run[2] =="Adam": T.add(run)print(len(S), len(T))print(len(S & T), len(S | T))
6 = 6
6 12
3 15
Next, the subsets of \(\{a, b, c\}\), built from strings of in-or-out bits exactly as in the figure. itertools.product([0, 1], repeat=3) hands out the 8 strings of 3 bits, in the order 000, 001, and so on up to 111. Each subset is kept as a list, so that it prints in the order a, b, c.
import itertoolsitems = ["a", "b", "c"]subsets = []# Every string of 3 bits: (0, 0, 0), (0, 0, 1), ...for bits in itertools.product([0, 1], repeat=3): subset = []# Positions 0, 1 and 2 of the string.for i inrange(3):# A 1 means "in".if bits[i] ==1: subset.append(items[i]) subsets.append(subset)print(len(subsets), "subsets:", subsets)print("subsets of 20 features:", 2**20)
Finally the library version of the three loops. itertools.product takes the lists of options and returns every combination, cycling through them like the digits of a mileage counter, the last list fastest. It is the same grid in the same order.
This module’s interactive, the choose-and-arrange explorer, lives in lesson M01.8.3. Switch on both “order matters” and “repeats allowed” there, and it lists the strings of this lesson: \(n\) symbols in each of \(k\) places, \(n^k\) in all.
Pitfalls
M01.8.1-F4
Wrong beside right. Adding the sizes of two sets counts every element of the overlap twice; subtracting the overlap once gives the true size of the union.
“Two sets of 4 elements make 8 elements together.”
Only when they share nothing. If they overlap, the elements in the overlap are counted once in each set. For \({A = \{2, 4, 6, 8\}}\) and \({B = \{1, 2, 3, 4\}}\) the union has 6 elements, not 8. A data set built by merging two sources has the same trap: rows that appear in both sources are counted twice unless the overlap is removed.
“Several stages, so multiply.”
The multiplication principle needs the same number of options at a stage whatever was chosen before it. Suppose Adam is tried only with the two smaller learning rates. Then the tree is lopsided: after 0.1 the optimiser stage has 1 option, after the others it has 2, so the 24 of the worked example is wrong. Split into cases and add. Learning rate 0.1 gives 4 batch sizes with SGD alone, 4 runs. The other two rates give 2 rates, 4 batch sizes and 2 optimisers, 16 runs. In all, 20 runs, not 24.
“And or or, it is all just arithmetic.”
The words decide. Choosing a learning rate and then a batch size is two stages, and the counts multiply: 12 runs. Picking a value for one setting only, either a learning rate or a batch size, is one case or the other, and the counts add: 3 options plus 4 options, 7 choices. Ask whether the outcome is made of one choice after another (multiply) or is one case out of several (add).
Check yourself
Recall
1. State the multiplication principle in your own words.
Show answer
If a choice is made in stages, and each stage has the same number of options whatever was chosen before it, the number of ways to make the whole choice is the product of those numbers.
2. How many strings of 8 bits are there?
Show answer
\({2^8 = 256}\): two options for each of 8 places. (Eight bits make one byte, which is why a byte holds 256 different values.)
3. Why does a set with \(n\) elements have \(2^n\) subsets?
Show answer
A subset is made by deciding, for each of the \(n\) elements, whether it is in or out. That is \(n\) stages with 2 options each, so there are \(2^n\) ways.
4. When is the size of \({A \cup B}\) simply \({\abs{A} + \abs{B}}\)?
Show answer
When \(A\) and \(B\) are disjoint, that is, \({A \cap B}\) is empty. Otherwise the size of the overlap must be subtracted once.
5. With \({A = \{2, 4, 6, 8\}}\) and \({B = \{1, 2, 3, 4\}}\), how many pairs does \({A \times B}\) have, and how many elements does \({A \cup B}\) have?
Show answer
\({A \times B}\) has 16 pairs: 4 choices for the first entry, then 4 for the second. The union \({A \cup B = \{1, 2, 3, 4, 6, 8\}}\) has 6 elements: 4 plus 4, minus the 2 in the overlap.
Exercises
1.★ A model is tuned over 5 learning rates, 3 depths and 2 loss functions. How many runs does a full grid search need? If each run takes 4 minutes, how long does the search take?
Show solution
Three stages with 5, 3 and 2 options give
\[
5 \times 3 \times 2 = 30 \text{ runs.}
\]
At 4 minutes each, 30 runs take 120 minutes, which is 2 hours.
2.★★ How many subsets does a set of 6 elements have? How many of them contain one particular element, say \(a\)?
Show solution
In all, \({2^6 = 64}\) subsets. For those containing \(a\), the decision about \(a\) is already made (in), and the other 5 elements each still have 2 options, so there are \({2^5 = 32}\) such subsets: exactly half. The other 32 leave \(a\) out.
3.★★★ How many of the whole numbers from 1 to 100 are divisible by 2 or by 5? How many are divisible by neither?
Show solution
Let \(E\) be the numbers divisible by 2 and \(F\) those divisible by 5. Every second number is in \(E\), so \({\abs{E} = 50}\), and every fifth is in \(F\), so \({\abs{F} = 20}\). A number is divisible by both 2 and 5 exactly when it is divisible by 10, so \({\abs{E \cap F} = 10}\). By the union rule,
\[
\abs{E \cup F} = 50 + 20 - 10 = 60.
\]
The numbers divisible by neither are the other 40.
Summary card
Stages multiply, separate cases add, and an overlap is subtracted once.
M01.8.1-F1
Three choices, then two for each: six.
Multiplication principle.\(n_1\) options, then \(n_2\), and so on: \({n_1 n_2 \cdots n_k}\) ways.
Three counts.\(\abs{A}\,\abs{B}\) pairs, \(n^k\) strings, \(2^n\) subsets.
Addition principle. Pieces that share nothing: add their sizes.
Union of two sets. Add the two sizes, then subtract the overlap once:
Sources. Each was opened and checked against this lesson on 12 November 2026.
Richard Hammack, Book of Proof, third edition (free PDF). Section 1.2: the Cartesian product and the size of \({A \times B}\) (Fact 1.1). Section 1.3: an in-or-out tree of subsets, and \(2^n\) subsets (Fact 1.3). Section 3.2: the multiplication principle (Fact 3.1). Section 3.3: the addition principle (Fact 3.2). Section 3.7: inclusion-exclusion for two sets (Fact 3.6) and for three (Equation 3.5).
Jay Abramson and others, Algebra and Trigonometry 2e, Section 13.5 (OpenStax). The addition principle, the multiplication principle, and \(2^n\) subsets of a set of \(n\) distinct objects.
Python 3.12 documentation, itertools.product: “roughly equivalent to nested for-loops”, cycling “like an odometer”, with repeat.
James Bergstra and Yoshua Bengio, Random Search for Hyper-Parameter Optimization, Journal of Machine Learning Research 13 (2012), 281 to 305. Section 1 writes the number of trials of a grid search as a product, which grows exponentially with the number of settings; Figure 1 shows a grid testing the one setting that matters at only three values. The abstract finds that few settings matter on most data sets, and that random search does as well or better in a small fraction of the time.
Frontier note: why grid search gives way to random search
A grid over 10 settings with 3 values each needs \({3^{10} = 59{,}049}\) runs, and every extra setting multiplies the bill again. Bergstra and Bengio (2012) found that usually only a few settings matter much. A grid keeps repeating the same few values of those, while random trials try a new value of every setting each time, so random search finds good settings with far fewer runs.
