7.1 Counting principles

Counting is the first step in many probability and discrete-reasoning problems. The challenge is rarely counting to a large number by hand. It is deciding which choices form separate cases, which happen in sequence, and whether the same outcome has been counted twice.

This is foundational to intermediate work. OpenStax's counting-principles section develops the rules with examples. You only need arithmetic to begin, but careful wording matters.

A basic idea: “or” and “then”

If you can choose one of $2$ blue badges or one of $3$ red badges, there are $2+3=5$ choices. If you then choose one of $4$ shirts, each badge choice can pair with every shirt: $5\cdot4=20$ outfits. The first decision joins separate cases; the second pairs every badge with every shirt.

A quick tour of counting rules

Count by addition when one outcome comes from one of several separate cases. If case $A$ has $a$ outcomes and case $B$ has $b$, then there are $a+b$ outcomes in “$A$ or $B$,” provided the cases are disjoint: no outcome belongs to both. For example, choosing one of $2$ blue badges or one of $3$ red badges gives $2+3=5$ badge choices. If cases overlap, subtract the overlap rather than counting it twice.

Use the fundamental rule of multiplication when a complete outcome requires a choice at every stage. If stage $1$ has $n_1$ choices, stage $2$ has $n_2$ choices after each first choice, and so on, then

$$\text{number of complete outcomes}=n_1n_2\cdots n_k.$$

This is also called the fundamental counting principle. Use it when every combination of stage choices is allowed and counted once, with the stated number of options available at each stage. Choosing one of $5$ badges and then one of $4$ shirts gives $5\cdot4=20$ outfits. Four positions with $2$ options each give $2^4$ strings: a repeated application of the same rule.

Do not decide from the words “or” and “and” alone. Check that separate cases do not overlap and that every stage combination is valid. If later choices vary with an earlier choice, draw a short tree and add the counts at its final branches instead of using one fixed product.

Before calculating, define what makes two outcomes different. If order changes the outcome, count ordered sequences; if it does not, a later module's combinations rule will remove duplicate orderings.

Application 1: assembling a menu

A meal has one main dish, either one of $2$ vegetarian dishes or one of $3$ other dishes. Vegetarian mains come with a choice of $4$ sides; the others come with a choice of $3$ sides. How many different meals are possible?

1. Split by main-dish type. The cases do not overlap, and the number of sides depends on the case, so a single product will not work.
2. Multiply inside each case. Vegetarian: $2\cdot4=8$. Other: $3\cdot3=9$.
3. Add the cases. $8+9=17$ meals.

Multiplying $5\cdot4=20$ would overcount: it gives every other main four sides when only three are available.

Application 2: at least one positive flag

Four separate checks each produce either “yes” or “no.” How many four-answer strings contain at least one “yes”?

1. Count every string. Each of the four positions has $2$ options, giving $2^4=16$ strings.
2. Count the complement. Exactly one string has no “yes”: no, no, no, no.
3. Subtract. The answer is $16-1=15$.

Directly counting strings with exactly one, two, three, and four “yes” answers also works, but the complement is shorter. No probability assumption is needed here: we are counting possible strings, not how likely they are.