Discrete Math › Section D · Counting › Topic D.2
The sum and product principles
Almost every counting argument is built from two moves: add when the outcomes split into separate cases, and multiply when an outcome is built in stages. Knowing exactly when each move is allowed is what keeps counts honest.
Counting without listing
How many six-character passwords can be made from lowercase letters and digits? Listing them is hopeless: there are more than two billion. Counting means finding the size of a set of outcomes without writing the set down. Each outcome here is one finished password, and the question asks for the number of elements in the set of all of them. Two principles do most of the work, and both are statements about sets. The sum principle handles outcomes that fall into separate groups. The product principle handles outcomes assembled from a sequence of choices. Combined with care, they answer questions that look complicated at first sight.
The sum principle
If one event can happen in \(m\) ways and a second in \(n\) ways, and the two cannot both happen, then one or the other can happen in \(m + n\) ways. In set language, if \(A\) and \(B\) are disjoint, meaning \(A \cap B = \emptyset\), then
A café offering 4 hot drinks and 3 cold drinks, with no drink on both lists, offers \(4 + 3 = 7\) drinks. The condition matters. If one drink appeared on both lists, adding would count it twice. Overlapping sets need a correction, which is the subject of the next topic, "Overlaps and inclusion-exclusion".
The product principle
If an outcome is built by first doing something in \(m\) ways and then, whatever happened first, doing a second thing in \(n\) ways, then the pair can be done in \(m \cdot n\) ways. In set language, the Cartesian product \(A \times B\), the set of ordered pairs \((a, b)\), has
A drink from the café's 7 and a pastry from 5 make \(7 \cdot 5 = 35\) orders. The principle extends to any number of stages. Each password character has 36 options, 26 letters plus 10 digits, so six characters give \(36^6 = 2{,}176{,}782{,}336\) passwords.
Same number of choices, not the same choices
The product principle needs only the number of options at each stage to be fixed. The options themselves may change. Count three-digit numbers with no repeated digit. 1. The first digit cannot be 0, so it has 9 options. 2. The second digit can be anything except the first, including 0: again 9 options. 3. The third digit avoids the first two: 8 options. Which digits remain depends on the earlier picks, but how many remain does not. So there are \(9 \cdot 9 \cdot 8 = 648\) such numbers. A brute-force check over 100 to 999 confirms 648.
Worked example: two styles of code
A warehouse labels bins with four-character codes of two styles: one letter followed by three digits, or two letters followed by two digits. How many labels are possible? 1. Style one: \(26 \cdot 10 \cdot 10 \cdot 10 = 26{,}000\), by the product principle. 2. Style two: \(26 \cdot 26 \cdot 10 \cdot 10 = 67{,}600\). 3. No label has both styles, because the second character is a digit in one and a letter in the other. The sets are disjoint. 4. By the sum principle, the total is \(26{,}000 + 67{,}600 = 93{,}600\). Notice the order of the moves: multiply inside each case, then add across cases.
Counting functions and subsets
A function \(f: A \to B\) assigns each element of \(A\) exactly one element of \(B\). Deciding where each element of \(A\) goes is one stage per element, each with \(|B|\) options, so there are \(|B|^{|A|}\) functions. From \(\{1, 2, 3\}\) to \(\{a, b, c, d, e\}\) that is \(5^3 = 125\). Subsets work the same way. To pick a subset of a 7-song album for a playlist, decide in or out for each song: two options, seven times, so \(2^7 = 128\) playlists, including the empty one. This agrees with the row sums of Pascal's triangle from "Pascal's triangle and the binomial theorem": row 7 adds up to 128.
Counting the complement
The sum principle also works backwards. If every outcome in a universe \(U\) either has a property or does not, then \(|U| = |A| + |\overline{A}|\), where \(\overline{A}\) is the complement, the outcomes not in \(A\). So \(|A| = |U| - |\overline{A}|\). This is the right tool for "at least one" questions. How many five-letter strings contain at least one vowel (a, e, i, o, u)? All strings: \(26^5 = 11{,}881{,}376\). Strings with no vowel use only the 21 consonants: \(21^5 = 4{,}084{,}101\). The difference, \(7{,}797{,}275\), is the answer. Counting "at least one" directly would mean juggling many overlapping cases.
Worked example: when multiplying fails
How many two-digit numbers have a second digit larger than the first? 1. Try the product principle: the first digit has 9 options, but the number of options for the second depends on the first. After 1 there are 8 choices (2 to 9); after 8 there is only 1 (9); after 9 there are none. The principle does not apply. 2. Split into cases instead, one for each first digit. The cases are disjoint, so add: \(8 + 7 + \cdots + 1 + 0 = 36\). 3. Check another way: each such number is a choice of 2 different digits from 1 to 9, written in increasing order, and \(\binom{9}{2} = 36\) from row 9 of Pascal's triangle.
Common mistakes to avoid
First, adding sets that overlap: the sum principle requires disjoint cases, or shared outcomes are counted twice. Second, multiplying when the number of options at a stage depends on an earlier choice; split into cases instead. Third, mixing up the base and exponent when counting functions: \(f: A \to B\) gives \(|B|^{|A|}\), so a 3-element domain and a 5-element codomain give \(5^3\), not \(3^5\). Fourth, attacking "at least one" head-on with overlapping cases; subtract the "none" count from the total instead. Fifth, forgetting a restriction such as a leading digit that cannot be 0.
Key takeaways
The sum principle: for disjoint sets, \(|A \cup B| = |A| + |B|\), so add across separate cases. The product principle: \(|A \times B| = |A| \cdot |B|\), so multiply across stages, provided the number of options at each stage does not depend on earlier choices. There are \(|B|^{|A|}\) functions from \(A\) to \(B\) and \(2^n\) subsets of an \(n\)-element set. Complements turn "at least one" into total minus none. When a stage's count varies, split into disjoint cases and add.
Flashcards
Flashcard
If A and B are disjoint, |A ∪ B| = |A| + |B|
Test your understanding
Question 1 of 5
A lunch deal is one starter, either one of 5 soups or one of 4 salads, followed by one of 6 mains. How many different lunches are there?
Question 2 of 5
How many functions are there from a 4-element set A to a 3-element set B?
Question 3 of 5
How many strings of 4 digits (0 to 9, repeats allowed) contain at least one 7?
Question 4 of 5
How many four-digit numbers (1000 to 9999) have four different digits?
Question 5 of 5
When does the sum principle |A ∪ B| = |A| + |B| give the correct count?
