Mathematics · Introduction to Probability and Combinatorics · Fundamental Counting and Probability Models

Sum & Product Rules

Last edited 9/25/2026, 5:48:25 AM

Consider the following scenario. A meal begins with soup or salad. Soup permits three main dishes; salad permits two. Every permitted main dish can be followed by either of two desserts. How many meals are possible?

Having two differing branches after one picks a soup or salad complicates the problem slightly. Consider the case that a meal begins with soup or salad, either permits three main dishes, and has two options for dessert. Now, simply multiplying $2\cdot3\cdot2 = 12$ would give us the total number of options. This motivates a need to retain branch information long enough to count correctly.

The Sum Rule

Theorem (Sum Rule)

If finite sets $A_1,\ldots,A_r$ are pairwise disjoint, then

$\left|\bigcup_{i=1}^r A_i\right|=\sum_{i=1}^r|A_i|.$

Proof

List each set's elements once, placing $A_i$ 's list after the lists for $A_1,\ldots,A_{i-1}$ .

No element is missing. Every element of $\bigcup_iA_i$ belongs to some $A_i$ by definition of union, so it appears in that set's list.
No element is repeated. Disjointness means no element belongs to two different $A_i$ 's, so no element can appear on two different lists.

The concatenated list therefore names each element of $\bigcup_iA_i$ exactly once, so its length ( the sum of the list lengths $|A_1|+\cdots+|A_r|$ ) equals $\left|\bigcup_iA_i\right|$ .

∎

A case split must answer two questions then, matching the two steps above: does every valid object enter a case (step 1), and does it enter only one (step 2)? Cases that are exhaustive but overlap still overcount.

The Product Rule

Theorem (Product Rule)

Suppose a construction has $r$ stages, indexed $j=1,\ldots,r$ . For every valid prefix of length $j-1$ (a partial choice sequence made in stages $1,\ldots,j-1$ ), there are exactly $n_j$ permitted choices at stage $j$ . If each completed choice sequence of length $r$ represents exactly one desired object, and each desired object has exactly one such sequence, then the number of objects is

$n_1n_2\cdots n_r.$

Proof

By induction on the number of stages considered.

Base case ( $j=1$ ). There are $n_1$ length-one prefixes, by hypothesis.
Inductive step. Suppose there are $n_1n_2\cdots n_{j-1}$ prefixes of length $j-1$ . Each has exactly $n_j$ extensions to length $j$ (by hypothesis, since the count of stage- $j$ choices is the same $n_j$ for every prefix). The extensions of different prefixes are distinct sequences and disjoint as sets of extensions, so the sum rule gives $n_1n_2\cdots n_{j-1}$ disjoint groups of size $n_j$ , hence $n_1n_2\cdots n_{j-1}n_j$ prefixes of length $j$ .
Conclusion. Repeating step 2 for $j=2,\ldots,r$ gives $n_1n_2\cdots n_r$ prefixes of length $r$ , i.e. complete choice sequences. The unique-representation hypothesis (one sequence per object, one object per sequence) turns this count of sequences into the count of objects.

The available choices may change with previous choices. Their number $n_j$ must be constant across all prefixes of length $j-1$ — the hypothesis the product rule actually needs. For example, after choosing one of four distinct symbols, there are three choices of a different second symbol; which three symbols are available depends on the first choice, but the count stays three.

No probabilities occur in this proof. A constant branching count is not an assumption of probabilistic independence.

∎

Example: Meals

We resolve the opening question: A meal begins with soup or salad. Soup permits three main dishes; salad permits two. Every permitted main dish can be followed by either of two desserts. How many meals are possible?

Match this to the Sum Rule and the Product Rule. Separate soup meals and salad meals: these two cases are disjoint (a meal has one starter) and exhaustive (soup and salad are the only starters), so the sum rule applies to their union.

Within each case, apply the product rule with two stages: main dish then dessert. Soup allows $n_1=3$ main dishes and $n_2=2$ desserts per main, giving $3\cdot2=6$ completions. Salad allows $n_1=2$ and $n_2=2$ , giving $2\cdot2=4$ . By the sum rule, the total is $6+4=10$ .

Here is the counting tree in text:

starter
  soup  -> 3 mains -> 2 desserts for each main -> 6 meals
  salad -> 2 mains -> 2 desserts for each main -> 4 meals

The optimal choice was to split where the number of options changed (soup and salad have different $n_1$ ) so that the product rule's constant-count hypothesis holds within each branch.

Example: Disproportionate Branches at Multiple stages

A project has a topic, a format and a review route. Topic A allows a poster with one review route or a report with three routes. Topic B allows a model with two routes. Topic C allows a poster with two routes or a report with two routes. Count complete projects, including the chosen review route.

The three topics are disjoint, exhaustive cases, so the sum rule applies to their union. Within topic A, the format branches (poster, report) are themselves disjoint sub-cases, contributing $1+3=4$ by the sum rule again. Topic B contributes $2$ . Topic C contributes $2+2=4$ . Summing the three topic totals by the sum rule gives $4+2+4=10$ . A single three-factor product would apply the product rule where its hypothesis fails: the number of review routes is not the same $n_j$ for every prefix.

Example: Codes with Repeating elements

A length-three code uses symbols $a,b,c,d$ , with neighboring symbols different. Match this to the product rule with $r=3$ stages: $n_1=4$ (any of the four symbols), $n_2=3$ (any symbol but the first, whatever the first was), $n_3=3$ (any symbol but the second, whatever the second was — it may equal the first). Each $n_j$ is genuinely constant across all prefixes even though which symbols are excluded depends on the prefix, so the product rule still applies: $4\cdot3\cdot3=36$ codes.

The restriction is local (only to the immediately preceding symbol). Requiring all three symbols to differ would instead make $n_3=2$ (excluding both earlier symbols) and produce $24$ codes.

Example: Cases with overlap

Count two-digit strings over $\{0,1,2\}$ having at least one zero. Counting "first digit zero" and "second digit zero" gives $3+3$ , but these cases are not disjoint ( $00$ belongs to both) so the sum rule does not apply directly and the naive sum overcounts $00$ twice.

A clever disjoint split does directly apply the sum rule: first digit zero (giving $00,01,02$ ), or first digit nonzero and second digit zero (giving $10,20$ ). These two cases share no string, so the sum rule gives $3+2=5$ .

Another method counts all strings, $3\cdot3=9$ by the product rule with $n_1=n_2=3$ , then subtracts the $2\cdot2=4$ with no zero, by the product rule again with $n_1=n_2=2$ (excluding $0$ at each position). Every string belongs to exactly one of "has a zero" and "has no zero," so these two cases are disjoint and their union is all $9$ strings; Now, the sum rule gives $9=|\text{has a zero}|+4$ , hence $|\text{has a zero}|=9-4=5$ , matching the direct count. This is a technique known as complementary counting, the counting analogue of Lesson 2's probability complement rule. We will discuss this further in later sections.

Info: A counting answer is not yet a probability model

The meal example has ten possible records. This does not say customers choose each one with probability $1/10$ . They might prefer soup, or one main dish. To convert a favorable-meal count into a probability by dividing by ten, the model must assign equal weights to complete meals. This follow's by Lesson 1's uniform-model assumption, not a consequence of the sum rule or product rule.

Whenever you multiply, name the object built at each stage and justify the number of extensions, citing the product rule. Whenever you add, state why the cases are exhaustive and disjoint, citing the sum rule. These short explanations are the proof of the count.

Exercise

For strings of length two over $\{a,b,c\}$ , consider the cases “starts with a” and “ends with a.” Do they form a partition of all strings? Explain both possible failures.

Exercise

After choosing one of five symbols, you choose a different second symbol. May the product rule use $5\cdot4$ even though the available second symbols depend on the first?

Exercise

How many length-four strings over $\{0,1,2\}$ have neighboring digits different? Repetition at nonneighboring positions is allowed.

Exercise

Route A offers two morning sessions, each followed by three afternoon sessions. Route B offers one morning session followed by five afternoon sessions. A record includes route and both sessions. Count the records.

Exercise

How many length-three strings over $\{a,b,c,d\}$ contain at least one a? Choose a disjoint complementary count.

Exercise

A nonempty code has length one, two or three over $\{0,1\}$ . Codes of different lengths are distinct. How many codes are possible?

Exercise

Two buttons, red and blue, both display the same word GO. Press exactly one button. Explain the counts if the recorded outcome is the button pressed and if it is the displayed word.

Exercise

A registration form allows one of two tracks. In the first track a student chooses one of three workshops; in the second one of four. Each then chooses online or in-person attendance. Specify an outcome record and derive its count.

Exercise

A finite first-stage set is $S$ . For each $s\in S$ , let $b(s)$ count permitted second-stage choices. Prove that the number of complete records is $\sum_{s\in S}b(s)$ . Explain when it reduces to $\lvert S\rvert b$ .

Exercise

A badge has a color and a symbol. Red and green each allow five symbols, while blue allows two. Choose an efficient counting decomposition and explain why it is valid.

Exercise

For two-digit strings over $\{0,1,2\}$ containing a zero, a learner adds three strings starting with zero and three ending with zero, obtaining six. Repair the reasoning.

Mathematics · Introduction to Probability and Combinatorics · Fundamental Counting and Probability Models

Sum & Product Rules

Last edited 9/25/2026, 5:48:25 AM

The Sum Rule

Theorem (Sum Rule)

If finite sets $A_1,\ldots,A_r$ are pairwise disjoint, then

$\left|\bigcup_{i=1}^r A_i\right|=\sum_{i=1}^r|A_i|.$

Proof

List each set's elements once, placing $A_i$ 's list after the lists for $A_1,\ldots,A_{i-1}$ .

No element is missing. Every element of $\bigcup_iA_i$ belongs to some $A_i$ by definition of union, so it appears in that set's list.
No element is repeated. Disjointness means no element belongs to two different $A_i$ 's, so no element can appear on two different lists.

The concatenated list therefore names each element of $\bigcup_iA_i$ exactly once, so its length ( the sum of the list lengths $|A_1|+\cdots+|A_r|$ ) equals $\left|\bigcup_iA_i\right|$ .

∎

The Product Rule

Theorem (Product Rule)

$n_1n_2\cdots n_r.$

Proof

By induction on the number of stages considered.

Base case ( $j=1$ ). There are $n_1$ length-one prefixes, by hypothesis.
Inductive step. Suppose there are $n_1n_2\cdots n_{j-1}$ prefixes of length $j-1$ . Each has exactly $n_j$ extensions to length $j$ (by hypothesis, since the count of stage- $j$ choices is the same $n_j$ for every prefix). The extensions of different prefixes are distinct sequences and disjoint as sets of extensions, so the sum rule gives $n_1n_2\cdots n_{j-1}$ disjoint groups of size $n_j$ , hence $n_1n_2\cdots n_{j-1}n_j$ prefixes of length $j$ .
Conclusion. Repeating step 2 for $j=2,\ldots,r$ gives $n_1n_2\cdots n_r$ prefixes of length $r$ , i.e. complete choice sequences. The unique-representation hypothesis (one sequence per object, one object per sequence) turns this count of sequences into the count of objects.

No probabilities occur in this proof. A constant branching count is not an assumption of probabilistic independence.

∎

Example: Meals

Here is the counting tree in text:

starter
  soup  -> 3 mains -> 2 desserts for each main -> 6 meals
  salad -> 2 mains -> 2 desserts for each main -> 4 meals

The optimal choice was to split where the number of options changed (soup and salad have different $n_1$ ) so that the product rule's constant-count hypothesis holds within each branch.

Example: Disproportionate Branches at Multiple stages

Example: Codes with Repeating elements

The restriction is local (only to the immediately preceding symbol). Requiring all three symbols to differ would instead make $n_3=2$ (excluding both earlier symbols) and produce $24$ codes.

Example: Cases with overlap

Info: A counting answer is not yet a probability model

Exercise

For strings of length two over $\{a,b,c\}$ , consider the cases “starts with a” and “ends with a.” Do they form a partition of all strings? Explain both possible failures.

Exercise

After choosing one of five symbols, you choose a different second symbol. May the product rule use $5\cdot4$ even though the available second symbols depend on the first?

Exercise

How many length-four strings over $\{0,1,2\}$ have neighboring digits different? Repetition at nonneighboring positions is allowed.

Exercise

How many length-three strings over $\{a,b,c,d\}$ contain at least one a? Choose a disjoint complementary count.

Exercise

A nonempty code has length one, two or three over $\{0,1\}$ . Codes of different lengths are distinct. How many codes are possible?

Exercise

Two buttons, red and blue, both display the same word GO. Press exactly one button. Explain the counts if the recorded outcome is the button pressed and if it is the displayed word.

Exercise

A badge has a color and a symbol. Red and green each allow five symbols, while blue allows two. Choose an efficient counting decomposition and explain why it is valid.

Exercise

For two-digit strings over $\{0,1,2\}$ containing a zero, a learner adds three strings starting with zero and three ending with zero, obtaining six. Repair the reasoning.