Back to the on-screen lesson ·
Independent choices multiply and disjoint alternatives add; how to tell which is which, and how counting one set two ways proves an identity.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to describe what one object being counted looks like, build it as a sequence of choices, and decide whether the situation calls for the product rule or the sum rule by asking how many choices are being made. You will also be able to notice deliberate overcounting and divide it out, to use inclusion and exclusion when the alternatives overlap, and to prove an identity by counting one set two ways.
Lesson 12 counted subsets and pairs by multiplying independent choices, and lesson 15 counted functions and injections the same way. This lesson names the rules those counts used, and adds the one that is easy to confuse with them: when to add instead.
The product rule: if a thing is built by making one choice from $m$ options and then another from $n$, there are $mn$ such things. The sum rule: if a thing is one of $m$ alternatives or one of $n$ others, and no thing is both, there are $m + n$. A combinatorial proof establishes an identity by counting one set in two ways.
Almost every count in this unit is these two rules applied several times, so the difficulty is never the arithmetic — it is saying which rule the situation calls for.
The product rule applies when an object is built by a sequence of choices, each made regardless of the last. Three positions from a five-letter alphabet: $5 \times 5 \times 5$. A president then a treasurer from ten people: $10 \times 9$, because the second choice has one fewer option — the rule survives the options changing, as long as the number of options at each step does not depend on which way the earlier choices went.
The sum rule applies when an object is one of several kinds and the kinds do not overlap. A book from a shelf of $7$ novels and $5$ biographies: $12$. If the kinds do overlap, the sum rule does not apply and lesson 11's inclusion and exclusion does.
The question that chooses: how many choices am I making? One choice from combined alternatives adds. Two choices in a row multiply. Said out loud before any arithmetic, this settles nearly every case, and said afterwards it settles none.
Overcounting on purpose. Sometimes the easy count is the wrong one by a known factor. There are $n(n-1)$ ways to choose an ordered pair from $n$ people, and each unordered pair has been counted twice, so there are $n(n-1)/2$ unordered pairs. Count the easy thing, then divide by the number of times each answer appeared. That move — count with order, divide it out — is the whole of the next lesson.
Another way: steps
To set up a count:
Another way: example
How many four-letter strings from an alphabet of $26$ have no repeated letter? Build one: $26$ choices, then $25$, then $24$, then $23$ — each step's count is the same whatever the earlier letters were, so multiply. $26 \times 25 \times 24 \times 23 = 358{,}800$.
If two different counting arguments describe the same set, their answers are equal — and that equation is a theorem, proved without algebra.
The cleanest example is in this lesson's transfer question. A set of $n$ elements has $2^n$ subsets. Fix one element and pair each subset with the subset that differs only in whether that element is present. The pairing always changes the size by one, so it matches the even-sized subsets exactly with the odd-sized ones. Two counts of the same $2^n$ subsets: as a total, and as two equal halves. Hence $2^{n-1}$ of each.
The algebraic proof of the same fact — an alternating sum of binomial coefficients is zero — is true, and it explains nothing. The pairing explains it, and the habit of looking for the pairing is worth more than any formula in this unit.
Adding when the choices are independent. Two choices from $3$ and $4$ options give $12$ objects, not $7$.
Summing over overlapping kinds. The sum rule requires that nothing is of both kinds; otherwise use inclusion and exclusion.
Multiplying when the options depend on the route. If choosing a red hat leaves three coats available and a blue hat leaves five, the product rule does not apply as stated; split into cases and add.
Overcounting silently. Counting committees by choosing members one at a time counts each committee once per ordering. Say how many times each object was built before dividing.
'And' in a problem does not mean multiply and 'or' does not mean add. 'A starter and a main course' multiplies; 'a number that is even and less than ten' does not multiply anything. What decides is whether one object being counted is built by a sequence of choices, or is one alternative among disjoint kinds. Describing one object out loud, in full, before reaching for arithmetic is the habit that prevents this, and it prevents almost nothing else.
How many two-digit numbers have distinct digits? The first digit has nine options — not ten, since it cannot be zero.
Note the restriction before multiplying.
The second may be anything except the first: ten digits less one, so nine options, and that count is nine whichever first digit was chosen.
The number of options is constant even though the options differ.
So $9 \times 9 = 81$. The product rule needed the number of second options to be the same each time, which it is — it did not need them to be the same options.
That is exactly what the rule requires, and no more.
A menu offers $4$ starters, $6$ mains and $3$ desserts. How many three-course meals? Three independent choices: $4 \times 6 \times 3 = 72$.
Product rule, three factors.
How many meals of exactly one course? A single choice from the combined pool of $4 + 6 + 3 = 13$ dishes.
Sum rule: one choice, disjoint kinds.
Same menu, two questions, two rules. Nothing about the words picked the rule; how many choices the diner makes did.
The structure chooses, not the vocabulary.
Count each condition separately. Beginning with $a$: one choice for the first letter and four each for the others, so $1 \times 4 \times 4 = 16$.
Product rule, once per condition.
Ending with $d$: $4 \times 4 \times 1 = 16$. Adding gives $32$ — but the strings doing both have been counted twice.
The kinds overlap, so the sum rule does not apply.
Those are the strings beginning with $a$ and ending with $d$, of which there are $1 \times 4 \times 1 = 4$. So the answer is $16 + 16 - 4 = 28$. The sum rule needed disjoint kinds, did not get them, and inclusion and exclusion from lesson 11 finished the job.
A code is written from an alphabet of $3$ symbols, and symbols may repeat. Fill in how many codes there are of each length.
| How many codes | |
|---|---|
| Length $1$ | |
| Length $2$ | |
| Length $3$ |
How many strings of length $5$ can be written from an alphabet of $3$ symbols, with repeats allowed?
Answer:
A shelf holds $5$ novels and $6$ biographies. Fill in the two counts.
One of each kind: both ways. One book, of either kind: either ways.
Match each counting question to the rule it needs.
| A permutation of all five | A combination | The product rule | An ordered choice of two | A combination | |
|---|---|---|---|---|---|
| How many ways to seat five people in a row | |||||
| How many ways to choose three books from ten to take on holiday | |||||
| How many three-letter codes from a 26-letter alphabet, letters repeatable | |||||
| How many ways to pick a president and then a treasurer from a club | |||||
| How many two-element subsets a set of nine has |
A set has $6$ elements. How many of its subsets have an even number of elements?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A code is written from an alphabet of $5$ symbols, and symbols may repeat. Fill in how many codes there are of each length.
| How many codes | |
|---|---|
| Length $1$ | |
| Length $2$ | |
| Length $3$ |
You can set up a count by describing one object and the choices that build it, and choose between the product and the sum rule. Say in your own words what the product rule requires of the second choice, and why the sum rule needs the alternatives to be disjoint. Next: the counts where order matters and the counts where it has to be divided out.
10. Your turn: how many three-letter strings from $\{a, b, c, d\}$ begin with a vowel or end with $d$?, step 3