Counting Principle and Multiplication Principle

The multiplication principle says that if a task consists of several independent steps with n₁, n₂, …, n_k choices, the total number of ways to complete it is n₁ · n₂ ⋯ n_k; the addition principle says that if two choices are mutually exclusive, the numbers of ways add. In brief: with 3 shirts and 4 pairs of trousers there are 3 · 4 = 12 outfits. A 4-digit PIN has 10 · 10 · 10 · 10 = 10,000 possibilities. If you may choose either 1 of 5 books or 1 of 3 magazines, there are 5 + 3 = 8 choices.

Counting is the foundation of combinatorics and probability. Before learning permutations and combinations, you need to master the two basic principles, since all other formulas are shortcuts derived from them. This guide explains both principles with tree diagrams, shows how to handle restrictions, how to count with complementary counting (total minus unwanted) and the inclusion–exclusion idea, and gives a table of the growth of the number of outcomes.

What is the multiplication principle?

Suppose that a task is done in k steps, where step 1 can be done in n₁ ways, and for each choice in step 1 there are n₂ ways to do step 2, and so on. Then the whole task can be done in n₁n₂⋯n_k ways. A tree diagram shows why: each of the 3 shirts branches into 4 pairs of trousers, giving 3 · 4 = 12 leaves.

Example 1: licence plates

A plate has 2 letters followed by 3 digits. With 26 letters and 10 digits, and repetition allowed: 26 · 26 · 10 · 10 · 10 = 676,000 plates. If letters and digits cannot repeat: 26 · 25 · 10 · 9 · 8 = 468,000.

Example 2: binary strings

The number of strings of length 8 made of 0 and 1 is 2⁸ = 256. This is the number of values that a byte can take.

Example 3: a menu

A restaurant offers 4 starters, 6 main courses and 3 desserts. A full meal can be chosen in 4 · 6 · 3 = 72 ways. If you may also skip the dessert, there are 4 choices for the dessert step, so 4 · 6 · 4 = 96 meal options.

What is the addition principle?

If a task can be done in one of two ways that cannot occur together, with m ways for the first and n ways for the second, then the number of ways is m + n. It is the principle of “or” for disjoint cases, just as the multiplication principle is the principle of “and”.

Example 4

You can travel from A to B by train (3 routes), by bus (2 routes) or by plane (1 route). The total is 3 + 2 + 1 = 6 ways. If you travel from A to B and then from B to C, with 6 ways for the first part and 4 for the second, the total is 6 · 4 = 24.

Example 5: using both principles

How many 3-letter strings using A, B, C, D, E (no repetition) start with a vowel? Cases: the first letter is A or E (2 choices), then 4 choices and 3 choices for the others: 2 · 4 · 3 = 24.

How do you count with restrictions?

Handle the most restricted step first. This avoids overcounting and saves work.

Example 6: an even number

How many 3-digit numbers (no leading zero) are even? The last digit: 0, 2, 4, 6 or 8 (5 choices). The first digit: 1–9 (9 choices). The middle digit: 10 choices. The total is 9 · 10 · 5 = 450. This agrees with the count: there are 900 three-digit numbers, and half are even.

Example 7: distinct digits

How many 3-digit even numbers have distinct digits? Split by the last digit. If the last digit is 0: the first digit has 9 choices and the middle digit 8, giving 72. If the last digit is 2, 4, 6 or 8 (4 choices): the first digit has 8 choices (not 0, not the last digit) and the middle digit has 8 choices (not the first and not the last), giving 4 · 8 · 8 = 256. The total is 72 + 256 = 328.

Example 8: seating with a condition

Five friends sit in a row, and Anna must sit at one end. Anna has 2 choices for the position, and the other four can be arranged in 4 · 3 · 2 · 1 = 24 ways, so 2 · 24 = 48. Without the condition, there would be 5 · 4 · 3 · 2 · 1 = 120 arrangements.

What is complementary counting?

Sometimes it is easier to count the unwanted cases and subtract them from the total: the number of ways with a property = total − the number of ways without it.

Example 9

How many 4-digit PINs contain at least one 7? The total is 10⁴ = 10,000. The PINs without 7 have 9⁴ = 6,561. So there are 10,000 − 6,561 = 3,439 PINs with at least one 7.

Example 10: inclusion–exclusion

Among 100 students, 60 study French, 45 study German and 20 study both. How many study at least one language? 60 + 45 − 20 = 85. The overlap must be subtracted, since it was counted twice. The numbers who study neither: 100 − 85 = 15.

Table of numbers of outcomes

Where do these principles come from?

Counting problems appear in ancient Indian mathematics: the Sanskrit texts on prosody counted the possible patterns of long and short syllables, which gave results equivalent to the binomial coefficients and to powers of 2. The systematic study of combinatorics began with Pascal and Fermat in the seventeenth century in connection with games of chance.

Where are they used today?

The multiplication principle gives the size of search spaces in computer science: a password of 8 characters from 62 letters and digits has 62⁸ ≈ 2.18 × 10¹⁴ possibilities. It is used in genetics (the number of genotypes), in telephone numbering plans and in the design of experiments. In probability, the favourable and the total number of outcomes are counted with these principles.

Which mistakes are common?

Adding instead of multiplying

For steps that happen one after another (“and”), multiply. Add only for alternative, exclusive cases (“or”).

Forgetting that the number of choices can depend on earlier choices

With no repetition, the number of options decreases at each step: 26 · 25 · 24, not 26 · 26 · 26.

Double counting

When cases overlap, subtract the overlap (inclusion–exclusion) or split the cases so that they are disjoint.

Handling the restricted step last

Start with the step that has a restriction, such as the first digit that cannot be 0.