Unit 2, lesson 9

Sum and Product Rules for Counting

How the product rule counts outcomes built in stages and the sum rule counts disjoint alternatives, with cases, decision trees, selection with and without replacement, and restrictions.

  • Video 9
  • Ordered and Unordered Selections

A four-digit access code may use any of the ten digits in each position, and a leading zero is allowed. How many codes are there, and how does that number change when no digit may repeat or when the code may not start with zero? When every outcome is equally likely, a probability is a ratio of two such counts, so the counts have to be right. This lesson sets out when to multiply numbers of choices, when to add the sizes of separate cases, and which factors a restriction changes.

Key terms

Product rule for counting

Definition Suppose every outcome is built by a sequence of kk choices. The first choice has n1n_1 options, and for every way of making the first i−1i - 1 choices, the iith choice has exactly nin_i options. Suppose also that different sequences of choices produce different outcomes and that every outcome comes from some sequence. Then the number of outcomes is

n1⋅n2⋯nk.n_1 \cdot n_2 \cdots n_k .

The options available at a stage may depend on the earlier choices. Only their number has to be the same along every path. The factors are counts of options, not probabilities, and the rule assumes nothing about independence or about how an outcome is later selected.

In plain words When every outcome is assembled step by step in exactly one way, and at each step every partial outcome can be continued in the same number of ways, multiply those numbers. Each factor answers one question, namely how many options remain at that step.

Example A workshop label is one letter from A, B, C and D followed by one digit from 0 to 9. Each of the 4 letters can be followed by any of the 10 digits, so there are 4⋅10=404 \cdot 10 = 40 labels. If a mechanism picks one label uniformly, each label has probability 1/401/40. A mechanism that favors labels starting with A assigns different probabilities, but the set still holds 40 labels.

Sum rule for counting

Definition If a finite set SS is the union of sets S1,…,SkS_1, \dots, S_k that are pairwise disjoint, so that no outcome lies in two of them, then

∣S∣=∑i=1k∣Si∣,\lvert S \rvert = \sum_{i=1}^{k} \lvert S_i \rvert ,

where ∣S∣\lvert S \rvert is the number of elements of SS. When the sets overlap, the plain sum counts every shared outcome more than once. For two sets the corrected count is

∣S1∪S2∣=∣S1∣+∣S2∣−∣S1∩S2∣.\begin{aligned} \lvert S_1 \cup S_2 \rvert &= \lvert S_1 \rvert + \lvert S_2 \rvert \\[0.4em] &\quad - \lvert S_1 \cap S_2 \rvert . \end{aligned}

In plain words When each outcome belongs to exactly one of several separate formats or cases, count each case and add. The addition is correct because no outcome is counted twice.

Example A registration tag is either two letters or three digits, with all 26 letters and all 10 digits allowed and repetition permitted. There are 262=67626^2 = 676 letter tags and 103=100010^3 = 1000 digit tags. No tag is of both kinds, so there are 676+1000=1676676 + 1000 = 1676 tags. The product 676⋅1000676 \cdot 1000 would instead count a two-letter part followed by a three-digit part, which is a different, five-character format.

Counting by cases and decision trees

Definition Counting by cases splits the set of outcomes into cases that do not overlap and together cover every outcome, counts each case separately, often with the product rule, and adds the case counts by the sum rule. A decision tree draws the choices in stages. Each branch leaving a node is one available option, and each complete path from the root to a leaf is one outcome. When different paths give different outcomes and every outcome has a path, the number of outcomes is the number of leaves. If every node at each stage has the same number of branches, the leaves can be counted with the product rule. If not, split the tree into cases by the earlier branches that change a later count, count the leaves in each case separately and add.

In plain words When the number of options at some step depends on what happened earlier, that step has no single factor, so the steps in that order do not give one product. Split into cases by the earlier choice that changes the count, count each case on its own and add. A small tree shows which numbers to multiply and which to add, and it lists actual outcomes to compare with the final count.

Example A worker chooses a workstation and then a tool available there. Workstation A has 2 permitted tools and workstation B has 3. The tree has 2 leaves under A and 3 under B, so there are 2+3=52 + 3 = 5 workstation and tool pairs. The product 2⋅3=62 \cdot 3 = 6 would invent a third tool at A.

Selection with and without replacement

Definition Choose kk items one after another from nn distinct items and record the order. In selection with replacement, every item stays available at every stage, so items can repeat and there are nkn^k ordered selections. In selection without replacement, each item can be used at most once, so the stage counts are n,n−1,…,n−k+1n, n - 1, \dots, n - k + 1 and the number of ordered selections is

n(n−1)⋯(n−k+1).n(n - 1) \cdots (n - k + 1).

If k>nk > n, this product contains the factor 00 and so equals 00, which matches the fact that the items run out before the last stage. The names come from drawing objects from a box and returning them or not, but the same counts apply to symbols, such as digits that may or may not repeat in a code.

In plain words With replacement, a used option goes back into the pool. Without replacement, the pool shrinks by one at each stage, so each factor is one less than the factor before it.

Example For four-digit codes with a leading zero allowed, repetition gives 104=1000010^4 = 10000 codes, and no repetition gives

10⋅9⋅8⋅7=504010 \cdot 9 \cdot 8 \cdot 7 = 5040

codes. If a code is chosen uniformly from all 10000, the probability that it has no repeated digit is 5040/10000=0.5045040/10000 = 0.504.

Counting with restrictions

Definition A restriction is a condition that every valid outcome must satisfy. It can remove outcomes from the set being counted, and when the valid outcomes form the sample space, it changes that sample space too. To count valid outcomes with the product rule, give each stage the number of options that satisfy every restriction applying to that stage, given the earlier choices. Each restriction has a scope, the positions or stages it applies to. If the resulting stage counts are not the same along every path, split into cases.

In plain words Write each position’s rule in words before writing its factor, and ask how many options are still allowed after the earlier choices. A rule about one position limits only that position, so a ban on a leading zero does not ban zero from the other positions.

Example For four-digit codes with a nonzero first digit and repetition allowed, the first position has 9 options and each other position 10, giving 9⋅103=90009 \cdot 10^3 = 9000 codes. With a nonzero first digit and no repeated digit anywhere, the count is

9⋅9⋅8⋅7=4536.9 \cdot 9 \cdot 8 \cdot 7 = 4536.

The second factor is 9, not 8, because zero is banned only from the first position, so after the first digit is chosen nine digits remain, zero among them. The two restrictions together also change probabilities. A code chosen uniformly from all 10000 codes ends in 0 with probability 1/101/10, and so does a code chosen uniformly under either restriction alone. Among the 4536 codes that satisfy both, 9⋅8⋅7=5049 \cdot 8 \cdot 7 = 504 end in 0, so a code chosen uniformly from them ends in 0 with probability 504/4536=1/9504/4536 = 1/9.

Check yourself

  1. Use only the letters A, B, C and D and the digits 0, 1 and 2. A tag is either two different letters followed by a digit, or one letter followed by two digits that may repeat. How many tags are there? How does the total change if the two digits in the second format must differ?
Show the answer

The first format has 4 choices for the first letter, 3 for the second because it must differ, and 3 for the digit, so it has 4⋅3⋅3=364 \cdot 3 \cdot 3 = 36 tags. The second format has 4 letter choices and 3 choices for each digit, again 4⋅3⋅3=364 \cdot 3 \cdot 3 = 36 tags. The second character is a letter in the first format and a digit in the second, so the formats are disjoint and the total is 36+36=7236 + 36 = 72.

If the two digits must differ, only the last factor of the second format changes, from 3 to 2. That format then has 4⋅3⋅2=244 \cdot 3 \cdot 2 = 24 tags, and the new total is 36+24=6036 + 24 = 60.

  1. A classmate counts four-digit codes with a nonzero first digit and no repeated digit as 9⋅8⋅7⋅6=30249 \cdot 8 \cdot 7 \cdot 6 = 3024. Find the mistake and the correct count.
Show the answer

The classmate treats zero as banned from every position. The restriction applies to the first position only. After a nonzero first digit is chosen, 9 digits remain for the second position, zero among them, then 8 and then 7. The correct count is 9⋅9⋅8⋅7=45369 \cdot 9 \cdot 8 \cdot 7 = 4536. In fact 3024 is the number of valid codes that contain no zero at all, so the other 4536−3024=15124536 - 3024 = 1512 valid codes contain a zero in one of the last three positions.

  1. How many whole numbers from 100 to 999 are even and have three different digits? Explain why a single product does not give the count.
Show the answer

Choose the last digit first, because evenness restricts it, and split into two cases.

If the last digit is 0, the first digit has 9 options (1 to 9) and the middle digit has 8 options (any digit not yet used), giving 9⋅8=729 \cdot 8 = 72 numbers.

If the last digit is 2, 4, 6 or 8, there are 4 options for it. The first digit cannot be 0 or the last digit, which leaves 8 options, and the middle digit can be any of the 8 digits not yet used. That gives 4⋅8⋅8=2564 \cdot 8 \cdot 8 = 256 numbers.

The cases are disjoint and cover every possibility, so the total is 72+256=32872 + 256 = 328. A single product fails in this order because once the last digit is chosen, the first digit has 9 options in one case and 8 in the other, so the stage count is not fixed. Choosing the first digit first runs into the same problem, since the last digit then has 4 even options if the first digit was even and 5 if it was odd. In fact no product of three stage counts can work in any order, because 328=8⋅41328 = 8 \cdot 41 and the prime 41 is larger than the 10 digits any stage can offer.

How this lesson connects