Fundamental principle of counting

Before any formula, before any factorial, the entire subject of combinatorics rests on one statement: the multiplication principle. Get this right, and every later formula falls into place.

The two basic principles

Multiplication principle (FPC)

Statement. If a task can be performed in two independent stages , the first in $m$ ways, the second in $n$ ways , then the whole task can be performed in $m \cdot n$ ways.

More generally, if a task consists of $k$ stages with $n_1, n_2, \dots, n_k$ choices independently at each stage, the total number of ways is $n_1 \cdot n_2 \cdot \cdots \cdot n_k.$

Addition principle

Statement. If a task can be done in $m$ ways or in $n$ ways (the two collections being disjoint , no overlap), then the task can be done in $m + n$ ways.

Multiplication is for sequential choices: do this and then that. Addition is for exclusive alternatives: either this or that, but not both at once.

When to multiply vs add

A typical pitfall: deciding which principle applies.

• "Choose a shirt and then a pant": multiplication (both are chosen).
• "Choose either a shirt or a pant (not both)": addition.
• "Form a $3$-letter code from $26$ letters with repetition allowed": multiplication, $26 \cdot 26 \cdot 26$.
• "How many integers between $1$ and $1000$ are multiples of $2$ or $3$?": addition (with inclusion–exclusion to handle overlap).

Worked examples

Example 1. A boy has $4$ shirts and $5$ pants. In how many ways can he dress?

Independent stages: choose shirt (4 ways), then choose pant (5 ways). Total: $4 \cdot 5 = 20$ ways.

Example 2. How many $4$-digit numbers can be formed using digits $1, 2, 3, 4, 5$ (a) with repetition? (b) without repetition?

(a) Each of $4$ positions independently chosen: $5^4 = 625$.

(b) First position: $5$ choices. Second: $4$ (no repetition). Third: $3$. Fourth: $2$. Total: $5 \cdot 4 \cdot 3 \cdot 2 = 120$.

Example 3. How many $4$-letter codes can be formed from the letters $A, B, C, D, E, F$ if (a) no letter is repeated, (b) the first letter is a vowel?

(a) $6 \cdot 5 \cdot 4 \cdot 3 = 360$.

(b) Vowels in the set: only $A, E$, so $2$ choices for the first position. The remaining three positions: $5 \cdot 4 \cdot 3 = 60$ (no repetition). Total: $2 \cdot 60 = 120$.

Example 4. Five people are to stand in a row. In how many ways can this be done if two particular people, $A$ and $B$, always stand together?

Treat $\{A, B\}$ as a single block. Now there are $4$ units to arrange: $4! = 24$ ways. Within the block, $A$ and $B$ can be in $2!$ orders: $2$. Total: $24 \cdot 2 = 48$.

Example 5 (harder). Find the number of $5$-digit numbers (no leading zero) using only digits $0, 1, 2, 3, 4, 5$ if no digit is repeated.

First digit: cannot be $0$. So $5$ choices (from $\{1, 2, 3, 4, 5\}$). Remaining four positions: from the remaining $5$ digits (including $0$ now, since we used one of $1$–$5$). So $5 \cdot 4 \cdot 3 \cdot 2 = 120$.

Total: $5 \cdot 120 = 600$.

Try it yourself

1. A coin is tossed $5$ times. How many possible outcomes?
2. How many $3$-letter words (any sequence) can be formed from $26$ English letters with repetition allowed?
3. From a list of $7$ books, in how many ways can a top-3 (in order) be selected?
4. A car number plate consists of two letters followed by three digits. How many distinct plates are possible if letters/digits can repeat?
5. In a class of $25$, in how many ways can a captain and a vice-captain be chosen (one person to each role)?
6. How many even $3$-digit numbers can be formed from $1, 2, 3, 4, 5$ with no repetition?
7. There are $4$ paths from $X$ to $Y$ and $3$ from $Y$ to $Z$. How many routes go $X \to Y \to Z$?
8. How many integers from $1$ to $999$ have at least one digit equal to $0$? (Complement counting.)
9. How many four-letter words can be made from the letters $A, B, C, D$ if (a) repetition is allowed, (b) not allowed?
10. In how many ways can $5$ books be put on a shelf in a row, all five used?
11. From a group of $4$ boys and $3$ girls, a committee of $2$ boys and $1$ girl is to be formed. How many ways? (Multiplication of independent choices.)
12. How many $4$-digit numbers use digits $0$–$9$ (with no leading zero), with no other restriction (repetition allowed)?

Pitfalls / Tricks

• "And" usually means multiply; "or" with disjoint cases usually means add.
• For "no repetition", the count at each step decreases by one.
• The first digit of a number can never be zero , separate it out.
• Insight. Before computing, write down each independent stage of the task with its number of options. Then multiply. This staged approach makes nine out of ten problems easy.