The Basic Principle of Counting

May 2026 · 15 min read

Almost every counting formula in this series — factorials, $P(n,r)$, $\binom{n}{r}$, the multinomial coefficient, and stars-and-bars — is built on top of one rule. Ross calls it the basic principle of counting and dedicates the very first section of Chapter 1 to it. Get this right, and the rest of combinatorics turns into bookkeeping.

Statement of the Rule

The phrase “for each outcome of the first experiment” is the part most students miss. The rule does not say "the first experiment has $m$ outcomes and the second has $n$ outcomes". It says: no matter what happens in the first experiment, the second experiment still has $n$ choices. In other words, the count of stage-two options must not depend on what stage one produced.

Why It Works

Imagine drawing a tree. The root branches into $m$ outcomes for stage 1. From each of those $m$ nodes, $n$ further branches sprout for stage 2. The leaves of the tree are exactly the (stage-1, stage-2) pairs.

Counting the leaves in two different ways forces the formula:

• Bottom up. Each of the $m$ stage-1 nodes has $n$ leaves below it. Total leaves $= n + n + \dots + n$ ($m$ times) $= m \cdot n$.
• Top down. Every leaf is uniquely determined by which of the $m$ stage-1 branches you took, and then which of the $n$ stage-2 branches. So leaves are in bijection with pairs $(a, b)$ where $a$ has $m$ values and $b$ has $n$ values. By the definition of a Cartesian product, the number of such pairs is $m \cdot n$.

The "for each outcome" clause is exactly what guarantees the second-stage subtree has the same size $n$ at every stage-1 node. If the size differed, the count would be a sum, not a product.

The Generalised Counting Rule

The proof is induction on $r$, repeatedly applying the two-stage rule. Each new stage multiplies the running total by its own $n_i$.

Worked Examples

Ross 1.2a — License plates

How many different 7-place license plates are possible if the first 3 places are letters and the final 4 places are digits?

Each of the 3 letter slots has 26 choices (independent of the others) and each of the 4 digit slots has 10 choices. By the generalised rule:

$26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 26^3 \cdot 10^4 = 175{,}760{,}000.$

Ross 1.2a (variation) — License plates without repetition

Same problem, but no letter and no digit may be repeated.

The first letter slot has 26 choices, the second has 25 (any of the 26 except the one we used), the third has 24. Similarly the digit slots have 10, 9, 8, 7. The independence required by the rule still holds — the count of remaining options at each stage is the same regardless of which specific letter or digit we previously picked. So:

$26 \cdot 25 \cdot 24 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 78{,}624{,}000.$

Ross 1.2b — Counting functions

How many functions $f: \{1, 2, \dots, n\} \to \{1, 2, \dots, m\}$ are there?

A function is determined by choosing $f(1), f(2), \dots, f(n)$. Each $f(i)$ can independently be any of $m$ values. So the total is $\underbrace{m \cdot m \cdots m}_{n\text{ times}} = m^n.$

Counting subsets

How many subsets does an $n$-element set have?

Build a subset $A$ by walking through each element and answering “include it?” — yes or no. There are $n$ independent yes/no decisions, so the count is $2^n$ (this counts the empty set and the full set as well).

The Addition Rule (Disjoint Cases)

The multiplication rule combines stages of a single experiment. The addition rule combines mutually exclusive cases of an experiment.

Whenever the multiplication rule's "no matter what" condition fails, splitting into cases that do satisfy it is the standard fix.

Worked: 6-character passwords with at least one digit

How many 6-character passwords use lowercase letters and digits with at least one digit?

It is easier to count by complement: total passwords minus passwords with no digit.

• Total: $36^6$ — six slots, 26 letters + 10 digits.
• No-digit passwords: $26^6$ — same slots, only letters allowed.
• Answer: $36^6 - 26^6 = 2{,}176{,}782{,}336 - 308{,}915{,}776 = 1{,}867{,}866{,}560.$

When Multiplication Quietly Fails

Beginners overuse multiplication. Two classic traps:

1. Stages that depend on each other. “How many ways to seat 4 people in a row so that Alice and Bob are not adjacent?” The number of allowed positions for Bob depends on where Alice sat, so direct multiplication overcounts. Either solve by complement (total seatings minus seatings where they are adjacent) or split into cases.
2. Order vs. no order confusion. “How many handshakes happen among 5 people?” You might say each person has 4 partners, so $5 \cdot 4 = 20$. But every handshake is counted twice (once from each shaker), so the answer is $\tfrac{20}{2} = 10$. Multiplication is correct; you also need a "remove order" step. We will formalise this next post.

A Template for Multi-Stage Problems

When a problem looks complicated, write down the stages explicitly:

Then check, for each row, whether the count is truly independent of what came before. If yes, multiply. If not, split into cases until each case satisfies the rule.

Worked: Counting paths on a grid

How many paths go from $(0,0)$ to $(3,2)$ using only steps right (R) and up (U)?

Every valid path is a sequence of 5 moves containing exactly 3 Rs and 2 Us. We could do this with combinations (and we will, in Part 4), but the basic rule already gives a brute-force route: at each of the 5 stages, the move depends on how many Rs and Us we have left. The stage counts are not constant — they vary by case. So we cannot just multiply $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$.

What we can do is rephrase the experiment: instead of choosing a move per stage, choose which 3 of the 5 stages will be R. Now stage one is “decide if move 1 is R” subject to having enough Rs, again messy. The cleanest approach is to wait for combinations. This example is a preview of why we need a separate “choose without order” tool.

Common Mistakes

• Forgetting independence. Always ask whether the next stage has the same count for every outcome of the previous stage.
• Double-counting orderless events. Multiplication preserves order. If your problem is order-blind (handshakes, committees, subsets of fixed size), you need to divide out by the symmetry of the unwanted ordering.
• Mixing addition and multiplication. Use multiplication within a single case (a single way of doing the experiment). Use addition between cases (different ways the experiment can split).
• Off-by-one on "first" decisions. “Pick a different one than before” reduces the count by 1, not by some clever trick — it is built into stage independence.

Summary

• Two-stage rule: $m$ then $n$ outcomes give $m \cdot n$ total, provided stage two has $n$ options for every stage-one outcome.
• Generalised rule: $n_1 \cdot n_2 \cdots n_r$ when stage $i$ has $n_i$ options regardless of earlier outcomes.
• Use addition for disjoint cases, multiplication within a single case.
• Use complement counting whenever “at least one” appears.

Practice Problems

• Ross 1.1. A small community has 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?
• Ross 1.4. John, Jim, Jay, and Jack have formed a band consisting of 4 instruments. If each of the boys can play all 4 instruments, how many different arrangements are possible? What if John and Jim can play all 4 instruments, but Jay and Jack can each play only piano and drums?
• Ross 1.5. For years, telephone area codes in the US and Canada had the form $(N_1, N_2, N_3)$ where $N_1$ could be any digit from 2 to 9, $N_2$ was 0 or 1, and $N_3$ was any digit from 1 to 9. How many area codes were possible?
• Ross 1.7. How many functions defined on $n$ points are possible if each functional value is either 0 or 1? How many of them assign 0 to at least one point?
• Practice — number with no two adjacent equal digits. How many 4-digit positive integers (no leading zero) have no two adjacent digits equal?
• Practice — bit strings. How many binary strings of length 8 contain at least one occurrence of 11? complement count those that never contain 11 (a Fibonacci-like recurrence).