Sections 7.1 – 7.5
The Challenge of Counting: Listing, Adding, Multiplying
Why Counting Is Hard · Listing · Sum Rule · Product Rule · Tree Diagrams
Section 7.1
Why Counting Can Be Difficult
Most of the arithmetic you have done in school involved a single number and a procedure: multiply these two values, divide this quantity by that one, take the square root. Counting problems look different. You are not given numbers and told to operate on them. You are given a situation and asked how many ways it can occur — and before you can compute anything, you must understand the situation itself.
This is the source of difficulty in counting. The challenge is almost never arithmetic. The challenge is representation: what, exactly, are you counting? Are the objects ordered or not? Are there repetitions? Are there restrictions? Does picking object A rule out object B? If you set up the problem incorrectly, the arithmetic can be perfect and the answer still completely wrong.
Three specific traps arise repeatedly in counting problems. The first is double-counting: including the same outcome more than once because it fits into two of your categories. The second is under-counting: missing a category or case entirely. The third is misrepresenting the situation: applying an ordered-counting formula to an unordered situation, or ignoring a restriction that changes the structure of the problem. All three can be avoided by reading the problem precisely and representing it before computing.
The Fundamental Habit
Before writing a single number, ask: What am I counting? What counts as one outcome? Are outcomes ordered or not? Are there restrictions? Could I list all outcomes for a very small version of this problem and check my reasoning? This habit — reading and representing before computing — is the foundation of all counting work in this chapter and beyond.
- A student is asked to count the number of ways to arrange two letters chosen from {A, B, C}. The student lists AB, AC, BC and concludes the answer is 3. Is this correct? What might the student be missing?
- Describe in your own words the difference between double-counting and under-counting. Give a brief example of each.
- A teacher asks: "How many students play either soccer or basketball?" Is it possible for the answer to be less than the number who play soccer? Explain.
Section 7.2
Listing Outcomes Carefully
For small problems, listing every possible outcome is both feasible and valuable. A systematic list guarantees completeness and reveals the structure of the problem. The discipline of building an organized list — rather than a random one — is also training for the more general counting principles that follow.
When listing, choose an order and stick to it. If you are listing pairs from {1, 2, 3, 4}, go through all pairs beginning with 1, then all beginning with 2, and so on. This prevents accidental gaps and makes it easy to verify that no outcome appears twice.
Example 7.2.1
Listing all outcomes for a two-coin flip
- ProblemA fair coin is flipped twice. List all possible outcomes.
- ThinkEach flip has two results: H (heads) or T (tails). The two flips are independent. List systematically by fixing the first flip and varying the second.
- Solve
First flip H: HH, HT
First flip T: TH, TT
- CheckFour outcomes, none repeated. Each is a distinct ordered pair. ✓
Answer: HH, HT, TH, TT — four outcomes in total.
Example 7.2.2
Listing ordered pairs from a small set
- ProblemList all ordered pairs (a, b) where a and b are chosen from {1, 2, 3} and a ≠ b.
- ThinkFix the first element and list all valid second elements. Then move to the next first element. Since a ≠ b, skip the case where both are equal.
- Solve
a = 1: (1,2), (1,3)
a = 2: (2,1), (2,3)
a = 3: (3,1), (3,2)
- CheckSix outcomes. Each is an ordered pair with distinct elements. ✓
Answer: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) — six ordered pairs.
Listing as a Check
Even when you plan to use a formula or rule, listing all outcomes for a small version of the problem is an excellent check. If your formula gives a count that matches your list, you have strong evidence the reasoning is correct. If they disagree, something is wrong in either the list or the formula — and the list is usually easier to verify.
- List all outcomes when a standard six-sided die is rolled once and a coin is flipped once. How many outcomes are there?
- List all two-letter strings using the letters {A, B, C} where repetition is allowed. How many are there?
- List all two-element subsets of {1, 2, 3, 4}. How many are there? How does this differ from listing ordered pairs?
- List all ways to assign one of three prizes (gold, silver, bronze) to two people chosen from {Alice, Bob, Carol} if the two people must receive different prizes and each person receives at most one prize.
Section 7.3
Sum Rule
When a task can be accomplished in one of several distinct, mutually exclusive ways, and those ways do not overlap, the total number of ways to accomplish the task is the sum of the counts for each way. This is the Sum Rule.
The key requirement is mutual exclusivity: choosing one way genuinely rules out all others. If two categories can overlap — if some outcome could be counted in both — then the sum rule overcounts and must be corrected by inclusion-exclusion (Section 7.7).
Sum Rule
If a task can be performed in one of k mutually exclusive ways — way 1 in n₁ outcomes, way 2 in n₂ outcomes, …, way k in nₖ outcomes — then the total number of outcomes is:
n₁ + n₂ + ⋯ + nₖ
Mutual exclusivity means no outcome belongs to more than one category.
Example 7.3.1
Choosing a course from two departments
- ProblemA student must choose exactly one elective: either one of 4 history courses or one of 6 art courses. How many choices does the student have?
- ThinkChoosing a history course and choosing an art course are mutually exclusive — the student picks exactly one. The Sum Rule applies.
- Solve
4 + 6 = 10
- CheckAny specific history course or art course is a valid choice, and no course belongs to both lists. Ten choices total. ✓
Answer: 10 choices.
Example 7.3.2
Choosing a password character from multiple types
- ProblemA single password character must be chosen from the 26 lowercase letters, 10 digits, or 8 special symbols. How many valid characters are there?
- ThinkThe three categories are mutually exclusive — a character is a letter, a digit, or a symbol, never more than one at once.
- Solve
26 + 10 + 8 = 44
- CheckThree disjoint sets. The total is their union size. ✓
Answer: 44 valid characters.
Student Warning — Checking Mutual Exclusivity
The Sum Rule fails when categories overlap. If a student can choose a course that is cross-listed in both history and art, the sum 4 + 6 = 10 would count that course twice. Always verify that no outcome belongs to two categories before applying the Sum Rule. If there is overlap, use inclusion-exclusion (Section 7.7).
- A menu offers 5 soups and 8 salads as starters. How many starter choices are there?
- A variable name must begin with a letter (26 options) or an underscore (1 option). How many valid first characters are there?
- A die is rolled. How many outcomes give either a prime number or an even number? Are these categories mutually exclusive?
- A library has 120 fiction books, 85 nonfiction books, and 40 reference books. A patron checks out exactly one book. How many choices?
- A committee can be chaired by any of 3 faculty members or any of 2 administrators. How many choices for chair?
- Two categories overlap: 30 students play basketball, 25 play soccer, and 10 play both. If a student is selected who plays at least one sport, can you use the Sum Rule directly? What should you do instead?
Section 7.4
Product Rule
When a task consists of a sequence of stages, and each stage is independent of the others — meaning the number of options at any stage does not depend on what was chosen at earlier stages — then the total number of ways to complete the task is the product of the number of options at each stage. This is the Product Rule.
The key requirement is independence: what you choose at stage one does not limit your choices at stage two. If one choice does restrict another — for example, if you cannot repeat an element — the product rule may still apply, but you must carefully count how many options remain at each stage after earlier choices have been made.
Product Rule
If a task consists of k stages — stage 1 in n₁ ways, stage 2 in n₂ ways, …, stage k in nₖ ways — and the stages are independent, then the total number of ways to complete the task is:
n₁ × n₂ × ⋯ × nₖ
Independence means the count at each stage does not change based on prior choices.
Example 7.4.1
Choosing a meal from a fixed menu
- ProblemA meal consists of one soup (4 choices), one entrée (6 choices), and one dessert (3 choices). How many distinct meals are possible?
- ThinkThree independent stages. The soup choice does not limit the entrée, and neither limits the dessert. Product Rule applies.
- Solve
4 × 6 × 3 = 72
- CheckWith a small example: if there were 2 soups and 2 entrées, we could list all 4 meals (S1E1, S1E2, S2E1, S2E2). The product matches. ✓
Answer: 72 distinct meals.
Example 7.4.2
Creating a password with character types
- ProblemA 4-character password must use exactly: one uppercase letter (26), one lowercase letter (26), one digit (10), and one special character (8), in that fixed order. How many such passwords are there?
- ThinkFour stages. The choice at each position is drawn from its own independent pool. Product Rule applies.
- Solve
26 × 26 × 10 × 8 = 54,080
- CheckEach position is filled independently. The full count is the product. ✓
Answer: 54,080 passwords.
Example 7.4.3
Product Rule with non-repetition
- ProblemFrom five candidates, a president and vice president must be chosen. No person can hold both roles. How many ways are there?
- ThinkStage 1: choose president — 5 options. Stage 2: choose vice president — only 4 options remain (the president is excluded). The count at stage 2 depends on stage 1, but the number of available options (4) is the same regardless of who was chosen as president. The Product Rule still applies.
- Solve
5 × 4 = 20
- CheckWith 3 candidates {A,B,C}: AB, AC, BA, BC, CA, CB — 6 outcomes = 3 × 2. ✓ Pattern holds.
Answer: 20 ordered pairs (president, vice president).
Combining Sum and Product Rules
Many problems require both rules. You might multiply for each stage within a category, then add across categories. The approach is always the same: identify independent stages (multiply), identify mutually exclusive categories (add). Clarity about which rule applies where is the key skill.
- A lock has 3 dials, each with digits 0–9. How many combinations?
- A student takes 4 courses, each with a grade of A, B, C, D, or F. How many grade sequences are possible?
- A car is customized with 4 body colors, 3 interior colors, and 2 engine options. How many configurations?
- A PIN consists of 6 digits (0–9). How many PINs are there if repetition is allowed? If no digit may repeat?
- A committee selects a chair, secretary, and treasurer from 10 members (no one can hold two roles). How many ways?
- A restaurant offers a daily special: one of 3 soups (changes each day, Monday through Friday) plus one of 4 entrées. How many distinct daily-special meal types are possible across a 5-day week?
Section 7.5
Tree Diagrams
A tree diagram is a visual representation of multi-stage choices. Each branch at a stage represents one option. Following a path from the root to any leaf traces one complete outcome. The total number of leaves equals the total number of outcomes.
Tree diagrams are most useful when the number of outcomes is small enough to draw, when different stages have different numbers of options, or when some branches contain restrictions that apply only to certain paths. They make structure visible and prevent errors from misunderstanding the problem.
The product rule is visible in a complete tree: if each stage branches into the same number of options, the total leaves equal the product of the branch counts at each level.
Example 7.5.1
Tree diagram for a two-stage choice
- ProblemA student chooses a shirt (Red, Blue) and pants (Black, Gray, White). Draw a tree and count outfits.
- ThinkStage 1: two shirt choices. Stage 2: three pants choices for each shirt.
- Solve
Shirt Pants Outfit
Red ──── Black → Red/Black
├─── Gray → Red/Gray
└─── White → Red/White
Blue ──── Black → Blue/Black
├─── Gray → Blue/Gray
└─── White → Blue/White
- Check6 leaves. Matches 2 × 3 = 6 by the Product Rule. ✓
Answer: 6 possible outfits.
Example 7.5.2
Tree diagram with a restriction on one branch
- ProblemA student takes two courses in sequence from {Math, English, History}. A student who takes Math first cannot take History second (scheduling conflict). How many valid sequences?
- ThinkDraw the tree. At stage 2, the Math branch has a restriction; the other branches do not.
- Solve
First Second Valid?
Math ──── English → Math/English ✓
├─── History → Math/History ✗ (conflict)
└─── Math → Math/Math ✓ (if repetition allowed)
English──── Math → English/Math ✓
├─── English → (repetition)
└─── History → English/History ✓
History──── Math → History/Math ✓
├─── English → History/English ✓
└─── History → (repetition)
Assuming no repetition and applying the restriction:
Math → English or Math → Math excluded (no repeats):
Math → English ✓
English → Math ✓, English → History ✓
History → Math ✓, History → English ✓
- CheckWithout restriction and no repeats: 3 × 2 = 6. Removing Math → History: 5 valid sequences. ✓
Answer: 5 valid course sequences.
- A coin is flipped three times. Draw a complete tree diagram and list all 8 outcomes.
- A student chooses one of three appetizers (A1, A2, A3) and then one of two desserts (D1, D2), but combination A3/D2 is unavailable. Draw the tree and count valid meal choices.
- A system generates a 2-character code. The first character is a letter (A, B, C) and the second is a digit (1, 2). Draw the tree and verify the Product Rule applies.
- Explain in words why the number of leaves in a complete tree with 3 stages — 4 branches at stage 1, 3 branches at stage 2, 2 branches at stage 3 — equals 4 × 3 × 2 = 24.
Sections 7.6 – 7.8
Counting by Exclusion: Complements and Inclusion-Exclusion
Complement Counting · Inclusion-Exclusion for Two Sets · Inclusion-Exclusion for Three Sets
Section 7.6
Complement Counting
Sometimes the outcomes you want are complicated to count directly, but the outcomes you do not want are easy. In that case, complement counting is the right strategy: count the total number of outcomes, count the outcomes that violate your condition, and subtract.
The key formula is simple. If S is the set of all outcomes and A is the set of outcomes you want, then the set of outcomes you do not want is the complement of A, written Ac or Ā. The count you want is:
Complement Counting
|A| = |S| − |Ac|
Count the total, subtract the unwanted. Use this when the complement is much easier to count than A itself — especially for "at least one" problems, where the complement is "none."
Example 7.6.1
At least one head in four coin flips
- ProblemA coin is flipped four times. How many outcomes include at least one head?
- ThinkCounting "at least one head" directly requires counting outcomes with exactly 1 head, exactly 2 heads, exactly 3 heads, and exactly 4 heads — four cases. The complement, "no heads at all" (all tails), is just one outcome: TTTT.
- Solve
Total outcomes: 2⁴ = 16
Complement (no heads, i.e. TTTT): 1
At least one head: 16 − 1 = 15
- CheckListing all 16 outcomes of 4 flips and removing TTTT leaves 15. ✓
Answer: 15 outcomes include at least one head.
Example 7.6.2
Passwords containing at least one digit
- ProblemA 4-character password uses only lowercase letters (26) and digits (10), with repetition allowed. How many passwords contain at least one digit?
- ThinkDirectly counting passwords with at least one digit requires casework (exactly 1 digit, exactly 2, etc.). The complement — passwords with no digits at all — is simple: all four characters are letters.
- Solve
Total (letters and digits, 36 chars each): 36⁴ = 1,679,616
Complement (only letters, 26 chars each): 26⁴ = 456,976
At least one digit: 1,679,616 − 456,976 = 1,222,640
- CheckThe complement is about 27% of total. Passwords with no digit at all are less common than those with at least one — reasonable. ✓
Answer: 1,222,640 passwords contain at least one digit.
When to Use Complement Counting
Reach for complement counting whenever the problem says "at least one," "not all," "at least two," or uses a condition that excludes only a small, easy-to-count set of outcomes. If the complement is a single case or a very simple condition, the subtraction approach is almost always faster than direct counting.
- A die is rolled twice. How many outcomes give at least one six?
- A 3-digit number (100–999) is chosen at random. How many contain at least one zero?
- A 5-character password uses uppercase letters only (26). How many contain at least one vowel (A, E, I, O, U)?
- A committee of 3 is chosen from 4 men and 3 women. How many committees include at least one woman? (Use complement; total committees is C(7,3) = 35.)
- A binary string of length 6 is formed from {0, 1}. How many strings contain at least two 1s?
- Explain in words why complement counting tends to be most efficient for "at least one" problems. Give an example where direct counting would require four separate cases.
Section 7.7
Inclusion-Exclusion for Two Sets
When two categories overlap — when some outcomes belong to both — the Sum Rule overcounts those overlapping elements. Counting A gives 30, counting B gives 25, but simply adding 30 + 25 = 55 is wrong if some outcomes are in both A and B, because those were counted twice. Inclusion-exclusion corrects this by subtracting the overlap once.
Inclusion-Exclusion for Two Sets
|A ∪ B| = |A| + |B| − |A ∩ B|
Add the sizes of the two sets, then subtract the size of their intersection — the elements that were counted twice. This gives the correct count for the union.
Example 7.7.1
Students who play soccer or basketball
- ProblemIn a school of 100 students, 40 play soccer, 30 play basketball, and 15 play both. How many play soccer or basketball (or both)?
- ThinkThe categories overlap — 15 students are in both groups. Adding 40 + 30 would count those 15 twice. Subtract the intersection.
- Solve
|Soccer ∪ Basketball| = |Soccer| + |Basketball| − |Soccer ∩ Basketball|
= 40 + 30 − 15
= 55
- CheckSoccer only: 40 − 15 = 25. Basketball only: 30 − 15 = 15. Both: 15. Total: 25 + 15 + 15 = 55. ✓
Answer: 55 students play soccer or basketball (or both).
Example 7.7.2
Counting integers divisible by 2 or 3
- ProblemAmong the integers from 1 to 30, how many are divisible by 2 or by 3?
- ThinkLet A = multiples of 2 up to 30. Let B = multiples of 3 up to 30. Their intersection is multiples of 6 (since lcm(2,3) = 6).
- Solve
|A| = ⌊30/2⌋ = 15
|B| = ⌊30/3⌋ = 10
|A ∩ B| = ⌊30/6⌋ = 5
|A ∪ B| = 15 + 10 − 5 = 20
- CheckListing: multiples of 2 or 3 from 1 to 30 are 2,3,4,6,8,9,10,12,14,15,16,18,20,21,22,24,26,27,28,30 — 20 values. ✓
Answer: 20 integers from 1 to 30 are divisible by 2 or 3.
- |A| = 18, |B| = 12, |A ∩ B| = 5. Find |A ∪ B|.
- |A ∪ B| = 45, |A| = 28, |B| = 30. Find |A ∩ B|.
- 80 students study French, 60 study Spanish, 20 study both. How many study at least one language?
- Among integers 1–50, how many are divisible by 3 or 5?
- A class has 30 students. Every student takes either algebra or geometry (or both). 22 take algebra and 18 take geometry. How many take both?
- A survey of 200 people finds 130 own a car, 90 own a bicycle, and 50 own both. How many own neither?
Section 7.8
Inclusion-Exclusion for Three Sets
When three overlapping categories are involved, the reasoning extends naturally. Adding |A| + |B| + |C| counts elements in all three pairwise intersections twice and counts elements in the triple intersection three times. Correcting by subtracting the three pairwise intersections over-corrects for the triple intersection. Adding the triple intersection back in gives the correct total.
Inclusion-Exclusion for Three Sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Add all three sets, subtract all three pairwise intersections, add back the triple intersection.
Example 7.8.1
Survey of language speakers
- ProblemA survey of 150 people finds: 80 speak English (E), 70 speak French (F), 60 speak Spanish (S), 40 speak both E and F, 30 speak both E and S, 25 speak both F and S, and 15 speak all three. How many speak at least one of these languages?
- Solve
|E ∪ F ∪ S| = |E| + |F| + |S|
− |E ∩ F| − |E ∩ S| − |F ∩ S|
+ |E ∩ F ∩ S|
= 80 + 70 + 60 − 40 − 30 − 25 + 15
= 210 − 95 + 15
= 130
- CheckA Venn diagram approach: fill in the triple region (15), then each pairwise-only region, then each single-language region, then total. All regions sum to 130. ✓
Answer: 130 people speak at least one of the three languages.
Venn Diagram Method as a Check
For three-set inclusion-exclusion, drawing a Venn diagram with three overlapping circles and filling in each of the seven regions (A only, B only, C only, A∩B only, A∩C only, B∩C only, all three) provides a powerful visual check. Start with the innermost region (all three) and work outward. The sum of all seven regions should equal |A ∪ B ∪ C|.
- |A| = 40, |B| = 35, |C| = 30, |A ∩ B| = 15, |A ∩ C| = 10, |B ∩ C| = 12, |A ∩ B ∩ C| = 5. Find |A ∪ B ∪ C|.
- Among integers 1–120, how many are divisible by 2, 3, or 5? (Use lcm pairs and triple.)
- A class of 40 students takes biology (B), chemistry (C), or physics (P): |B| = 22, |C| = 18, |P| = 14, |B∩C| = 8, |B∩P| = 6, |C∩P| = 4, |B∩C∩P| = 2. How many take at least one of the three sciences? How many take none?
- In the previous problem, use the Venn diagram method to find how many students take exactly one science.
Sections 7.9 – 7.12
Order, Restrictions, Casework, and Real Applications
Ordered vs. Unordered · Restrictions · Casework · Passwords and Scheduling
Section 7.9
Ordered Versus Unordered Outcomes
One of the most consequential questions in any counting problem is: does sequence matter? Are you counting arrangements — where the order of the elements matters — or selections — where only which elements are chosen matters?
The outcome (Alice, Bob) and the outcome (Bob, Alice) are the same selection but different arrangements. If you are choosing a committee of two, order does not matter: Alice and Bob on a committee is the same as Bob and Alice. But if you are choosing a president and secretary, order matters: (Alice as president, Bob as secretary) is different from (Bob as president, Alice as secretary).
Confusing these two cases is one of the most common errors in counting. Chapter 8 will develop the formulas for permutations (ordered) and combinations (unordered). For now, the goal is to recognize the distinction and reason clearly about which applies.
| Situation | Order Matters? | Type |
|---|
| Assigning president, VP, secretary | Yes — different roles | Ordered (arrangement) |
| Choosing a 3-person committee | No — same people, same committee | Unordered (selection) |
| A 4-digit PIN code | Yes — 1234 ≠ 4321 | Ordered |
| A group of 4 items in a bag | No — same items regardless of add order | Unordered |
| A ranked top-3 list from 10 candidates | Yes — 1st differs from 2nd | Ordered |
| A 3-person prize pool where all prizes are identical | No — everyone wins the same thing | Unordered |
Student Warning — Read the Problem Precisely
Ordered and unordered counts differ by a factor of the number of ways to arrange the selected objects. For selecting 3 from 10: the ordered count is 10 × 9 × 8 = 720, while the unordered count is 720 ÷ 6 = 120 (since 3 objects can be arranged in 3! = 6 ways). The correct interpretation of the problem determines which number is the right answer. Read the question with care: "arrange," "list," "rank," and "order" signal ordered; "choose," "select," "group," and "committee" signal unordered.
- For each situation, state whether outcomes are ordered or unordered and explain your reasoning.
a. Choosing 5 books from a shelf of 20 to pack for a trip.
b. Awarding first, second, and third prize to 3 runners from a field of 20.
c. Selecting a 4-person team from a group of 12 volunteers.
d. Creating a 3-digit code from digits 1–9 with no repetition.
e. Picking any 2 flavors from 8 to put on a pizza.
- The set {A, B, C} can be arranged in 6 ordered sequences. It forms only 1 unordered set. Explain this difference and list all 6 arrangements.
- A teacher picks 2 students from a class of 20 to give a presentation, assigning one as "speaker" and one as "visual aid operator." Is this ordered or unordered? How does the count change compared to picking any 2 students for a group with no designated roles?
Section 7.10
Counting with Restrictions
Many realistic counting problems involve restrictions: certain elements cannot be chosen, certain positions cannot be filled by certain items, certain combinations are forbidden, or certain elements must be included. There are two main approaches.
The subtraction method counts all outcomes without the restriction, then subtracts those that violate it. This works best when the restriction eliminates a well-defined, easy-to-count group of outcomes.
The direct method enforces the restriction from the start, choosing only from valid options at each stage. This often works well when the restriction applies to one specific position or choice and does not interact with many other stages.
Example 7.10.1
A forbidden element — subtraction method
- ProblemA 3-person committee is chosen from {A, B, C, D, E}. A and B refuse to serve together. How many valid committees are there?
- ThinkTotal committees from 5 people: 10 (since there are C(5,3) = 10 three-element subsets). Committees containing both A and B: if A and B are both on the committee, the third member is one of the 3 remaining people — 3 such committees.
- Solve
Total committees: 10
Committees with both A and B: 3
Valid committees: 10 − 3 = 7
- CheckList all 10 committees: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Removing those with both A and B (ABC, ABD, ABE): 7 remain. ✓
Answer: 7 valid committees.
Example 7.10.2
A required element — direct method
- ProblemA 4-character password uses digits (0–9) only, with repetition allowed. The password must start with 1. How many such passwords are there?
- ThinkThe first position is fixed (only the digit 1 is valid). The remaining three positions are free.
- Solve
Position 1: 1 choice (must be 1)
Position 2: 10 choices
Position 3: 10 choices
Position 4: 10 choices
Total: 1 × 10 × 10 × 10 = 1,000
- CheckThis is one-tenth of all 10,000 four-digit passwords (since exactly 1 in 10 starts with 1). ✓
Answer: 1,000 passwords start with 1.
Example 7.10.3
Adjacency restriction
- ProblemHow many 3-digit numbers (100–999) have no two adjacent digits equal?
- ThinkDirect method. The hundreds digit: 9 choices (1–9, not 0). The tens digit: 9 choices (0–9, not equal to hundreds). The units digit: 9 choices (0–9, not equal to tens).
- Solve
Hundreds: 9 choices (1–9)
Tens: 9 choices (0–9, ≠ hundreds)
Units: 9 choices (0–9, ≠ tens)
Total: 9 × 9 × 9 = 729
- CheckTotal 3-digit numbers: 900. With restriction — direct count gives 729. Complement (at least two adjacent equal): 900 − 729 = 171. Manually checking small cases supports the structure. ✓
Answer: 729 three-digit numbers have no two adjacent digits equal.
- A 5-person committee is chosen from 8 people. Person X must be included. How many committees?
- A 5-person committee is chosen from 8 people. Person X cannot be included. How many committees?
- A 4-digit password uses digits 1–9 (no zero). How many passwords have no repeated digit?
- From the 26 letters, a 3-letter string is formed with no vowels (A,E,I,O,U). Repetition allowed. How many strings?
- A committee of 4 is chosen from 5 men and 6 women. At least 2 women must be on the committee. How many committees? (Use complement or casework.)
- 5 people are seated in a row. Two specific people (X and Y) must not sit adjacent to each other. How many valid arrangements? (Total arrangements: 5! = 120. Arrangements with X and Y adjacent: treat XY as a block.)
Section 7.11
Casework in Counting
Casework is the method of partitioning a counting problem into distinct, non-overlapping cases, counting each case separately, and adding the results. It is appropriate when no single rule applies to all situations simultaneously, or when a restriction creates outcomes of meaningfully different types.
For casework to give the correct total, two conditions must hold. The cases must be mutually exclusive: no outcome belongs to more than one case. And the cases must be exhaustive: every possible outcome belongs to at least one case. Violating either condition produces an incorrect count.
Casework Checklist
Before adding case counts, verify:
1. Mutual exclusivity: No outcome can be assigned to two different cases.
2. Exhaustiveness: Every valid outcome is captured by exactly one case.
3. Internal correctness: The count within each case is accurate.
Example 7.11.1
Committees with at least one woman
- ProblemA committee of 3 is chosen from 4 men and 3 women. How many committees include at least one woman?
- ThinkCases by number of women: exactly 1 woman, exactly 2 women, exactly 3 women. These are mutually exclusive (a committee can't have both exactly 1 and exactly 2 women) and exhaustive (all committees with at least 1 woman are covered).
- Solve
Exactly 1 woman: choose 1 from 3 women × choose 2 from 4 men
= C(3,1) × C(4,2) = 3 × 6 = 18
Exactly 2 women: choose 2 from 3 women × choose 1 from 4 men
= C(3,2) × C(4,1) = 3 × 4 = 12
Exactly 3 women: choose 3 from 3 women × choose 0 from 4 men
= C(3,3) × C(4,0) = 1 × 1 = 1
Total: 18 + 12 + 1 = 31
- CheckTotal committees: C(7,3) = 35. All-male committees: C(4,3) = 4. Committees with at least one woman: 35 − 4 = 31. ✓ (Complement confirms casework.)
Answer: 31 committees include at least one woman.
Example 7.11.2
Counting outcomes by digit sum
- ProblemHow many two-digit numbers (10–99) have a digit sum that is odd?
- ThinkA sum of two digits is odd when one digit is odd and the other is even. Two cases: (odd tens, even units) or (even tens, odd units).
- Solve
Case 1: Odd tens digit, even units digit
Odd tens digits: 1,3,5,7,9 → 5 choices
Even units digits: 0,2,4,6,8 → 5 choices
Subtotal: 5 × 5 = 25
Case 2: Even tens digit, odd units digit
Even tens digits: 2,4,6,8 → 4 choices (not 0)
Odd units digits: 1,3,5,7,9 → 5 choices
Subtotal: 4 × 5 = 20
Total: 25 + 20 = 45
- CheckTwo-digit numbers: 90 total. Digit sum odd: 45. Digit sum even: 45. Reasonable by symmetry. ✓
Answer: 45 two-digit numbers have an odd digit sum.
- A team of 4 is chosen from 5 seniors and 4 juniors. The team must have at least 2 seniors. Count by casework (2 seniors, 3 seniors, or 4 seniors).
- How many 3-digit numbers (100–999) have exactly two equal digits? Set up cases based on which two positions contain equal digits.
- A game score of exactly 10 points is achieved using only 1-point and 3-point plays. How many sequences of plays achieve a score of 10? (Casework by number of 3-point plays.)
- Verify that your cases in problem 1 above are both mutually exclusive and exhaustive. Explain how you know.
Section 7.12
Counting in Passwords, Codes, and Scheduling
The counting principles of this chapter are not abstract exercises. They answer real questions in security, design, and planning. This section shows how to apply them to three common real-world domains.
Passwords and Password Strength
A password's security depends on the number of possible passwords an attacker must try. The larger this number — the password space — the stronger the password. Counting techniques determine password space directly.
Example 7.12.1
Comparing password policies
- ProblemCompare the password spaces of: (a) any 8-character password from 26 lowercase letters, and (b) any 8-character password from 26 lowercase letters + 10 digits + 8 special characters (44 total characters).
- Solve
(a) 26⁸ = 208,827,064,576 (about 209 billion)
(b) 44⁸ = 814,730,589,921,024 (about 815 trillion)
- CheckAdding more character types multiplies security by a factor of (44/26)⁸ ≈ 3,902. A much larger space. ✓
Answer: The larger character set increases the password space roughly 3,900-fold.
Codes and Identification Systems
Identification codes — product SKUs, ZIP codes, ISBN components, license plates — are typically built from characters drawn from a defined alphabet, subject to length and character-type rules. The counting principles of this chapter determine how many distinct codes a system can generate and whether it is large enough for its intended purpose.
Example 7.12.2
License plate capacity
- ProblemA state's license plate format is: 3 uppercase letters followed by 3 digits. How many distinct plates are possible?
- Solve
Letters: 26 × 26 × 26 = 17,576
Digits: 10 × 10 × 10 = 1,000
Total: 17,576 × 1,000 = 17,576,000
Answer: 17,576,000 distinct license plates.
Scheduling
Scheduling problems ask how many ways a set of tasks or events can be assigned to time slots, rooms, or personnel. The structure matches the product rule: for each task (stage), how many valid assignments (options) are available?
Example 7.12.3
Scheduling courses in time slots
- ProblemFive courses must be scheduled into 8 available time slots, with no two courses in the same slot. How many schedules are possible?
- ThinkAssign the first course to any of 8 slots, the second to any of 7 remaining slots, and so on. This is an ordered selection of 5 from 8 time slots.
- Solve
8 × 7 × 6 × 5 × 4 = 6,720
Answer: 6,720 possible schedules.
- A 6-digit PIN uses digits 0–9. How many PINs are possible (a) with repetition, (b) without repetition?
- A product code begins with 2 uppercase letters (no repetition) followed by 3 digits (repetition allowed). How many codes are possible?
- A school assigns 4 classes to 6 available classrooms, one class per room. How many room assignments are possible?
- A cybersecurity system requires passwords of exactly 10 characters drawn from 26 lowercase letters, 26 uppercase letters, and 10 digits. How many possible passwords are there? How does this compare to a 6-character password from the same alphabet?
- An event schedule has 6 speakers and 6 time slots. If speaker A must go first and speaker B must go last, how many schedules are possible for the remaining 4 speakers?
Section 7.13
Common Counting Mistakes
Mistake 1 — Double-Counting with the Sum Rule
Students who play math OR science: 30 + 25 = 55 (when 10 play both)
Error: categories overlap. Students in both groups are counted twice. Apply inclusion-exclusion: 30 + 25 − 10 = 45. Always check whether categories are truly mutually exclusive before adding.
Mistake 2 — Misapplying the Product Rule to Non-Independent Stages
Choose 3 people from 5, ordered, with no repeats: 5 × 5 × 5 = 125
Error: after choosing the first person, only 4 remain for the second stage, and 3 for the third. The correct count is 5 × 4 × 3 = 60. When repetition is not allowed, the count at each stage decreases.
Mistake 3 — Treating Unordered Outcomes as Ordered
Choosing a 2-person committee from {A, B, C, D}: 4 × 3 = 12 committees
Error: 4 × 3 = 12 counts ordered pairs (arrangements). A committee {A, B} is the same as {B, A}. Divide by 2 (since 2 people can be arranged in 2 ways): 12 ÷ 2 = 6 committees. Check by listing: AB, AC, AD, BC, BD, CD — 6 ✓
Mistake 4 — Forgetting the Restriction
A 3-digit number where no digit repeats: 10 × 10 × 10 = 1,000
Error: the "no repeat" restriction reduces options at each stage. Hundreds digit: 9 choices (1–9). Tens: 9 choices (0–9, not the hundreds digit). Units: 8 choices (remaining). Correct: 9 × 9 × 8 = 648.
Mistake 5 — Incomplete Casework
A committee needs at least 2 women. Cases: "2 women" and "3 women" — but the committee has 4 slots and the student forgets "4 women."
Error: missing a case means under-counting. Always verify exhaustiveness: list all possible case labels (0, 1, 2, 3, 4 women), cross out those that don't satisfy the condition, and confirm the rest are all accounted for.
Mistake 6 — Wrong Total in Complement Counting
3-character codes from {A, B, C}, no repeats, complement of "starts with A": complement count = 3³ − (codes starting with A) = 27 − 9 = 18
Error: the "no repeats" restriction changes the total. Without repeats: 3 × 2 × 1 = 6 total codes, not 27. Codes starting with A with no repeats: 1 × 2 × 1 = 2. Correct complement: 6 − 2 = 4. Always use the correct total (unrestricted or already-restricted) as the base for complement counting.
Each problem contains an error. Identify it and write the correct solution.
- A student computes the number of 3-person committees from {A, B, C, D, E} as 5 × 4 × 3 = 60. Is this correct? If not, what is the correct count and why does the student's approach overcount?
- A student says: "There are 36 students who take history or economics. 20 take history and 16 take economics, so 0 take both." Is this correct? What would the correct conclusion be if 5 take both?
- A student counts 4-character strings from {0,1} as 4 × 4 = 16 instead of 2⁴ = 16. The answer is the same, but the reasoning is wrong. Explain the error in the student's reasoning and why it happens to give the right answer here.
- A student uses complement counting: "How many 3-digit numbers have all three digits distinct? Total = 999; numbers with repeated digits = 999 − answer." What is wrong with this setup? What should the total and complement be?
Section 7.14
Preparing for Permutations and Combinations
The tools of this chapter — sum rule, product rule, complements, inclusion-exclusion, casework — are powerful for many problems, but they become unwieldy when the number of items or positions grows large. Manually multiplying out 20 × 19 × 18 × ⋯ × 1 or setting up a six-case casework solution is possible, but there are more efficient and more general tools.
Chapter 8 introduces two of the most important counting formulas in all of discrete mathematics: permutations and combinations. Permutations count ordered selections; combinations count unordered selections. Both are built on the factorial function, which compacts products like 10 × 9 × 8 × ⋯ × 1 into compact notation. The binomial theorem — one of the most useful algebraic identities in mathematics — emerges directly from combinations.
The conceptual groundwork for Chapter 8 is already laid. The distinction between ordered and unordered outcomes (Section 7.9), the product rule for independent stages (Section 7.4), and the complement and casework strategies (Sections 7.6 and 7.11) all carry forward directly. Chapter 8 will give you compact formulas where Chapter 7 relied on explicit multiplication.
- A student council elects a president, vice president, and secretary from 10 candidates (no person holds two offices). Write out the product 10 × 9 × 8 and explain why each factor is what it is.
- A 5-person committee is chosen from 10 candidates. How many ordered selections of 5 are there? How many of those represent the same unordered committee? What does dividing give you?
- What is 6 × 5 × 4 × 3 × 2 × 1? What would you call this product using notation you will learn in Chapter 8?
- A problem says "how many ways can you arrange all 7 books on a shelf?" Set this up as a product using this chapter's tools. Then explain why Chapter 8's factorial notation would simplify the expression.
- Explain in your own words the difference between "choosing 3 from 10 where order matters" and "choosing 3 from 10 where order does not matter." Which gives a larger count, and by what factor?
Chapter Summary
- Sec 7.1The central difficulty in counting is not arithmetic but representation. Common traps include double-counting, under-counting, and misrepresenting whether outcomes are ordered. Reading the problem precisely and representing it before computing are the fundamental habits of systematic counting.
- Sec 7.2Listing outcomes systematically — by fixing earlier choices and varying later ones — guarantees completeness and prevents repetition. Listing is both a counting technique for small problems and a verification tool for all problems.
- Sec 7.3The Sum Rule: when a task can be accomplished in mutually exclusive ways, the total count is the sum of the individual counts. Mutual exclusivity — no outcome in two categories simultaneously — is the required condition for direct addition.
- Sec 7.4The Product Rule: when a task consists of independent sequential stages, the total count is the product of the options at each stage. When stages are not independent (non-repetition), the count at later stages decreases, but the product structure still applies.
- Sec 7.5Tree diagrams represent multi-stage processes visually. Each path from root to leaf is one complete outcome. Trees are especially useful when stages have different numbers of options or when restrictions affect only some branches. The total leaves equal the product of branch counts at each stage when the tree is complete.
- Sec 7.6Complement counting: count all outcomes, subtract those that violate the condition. Most powerful for "at least one" problems, where the complement is "none" — a single, easy case. The formula is |A| = |S| − |Ac|.
- Sec 7.7Inclusion-exclusion for two overlapping sets: |A ∪ B| = |A| + |B| − |A ∩ B|. Adding A and B separately double-counts their intersection; subtracting it once gives the correct union size. Required whenever two categories overlap.
- Sec 7.8Inclusion-exclusion for three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. The Venn diagram method — filling in each of seven regions from the inside out — provides an effective visual check.
- Sec 7.9Ordered outcomes count arrangements (sequence matters); unordered outcomes count selections (only which elements are chosen matters). The ordered count exceeds the unordered count by a factor equal to the number of arrangements of the selected objects. Reading the problem precisely determines which applies.
- Sec 7.10Restrictions are handled by subtraction (count all, subtract violations) or directly (enforce the restriction at each stage). Subtraction works best when violations form a simple, countable set. Direct enforcement works best when the restriction applies to one stage and does not interact with others.
- Sec 7.11Casework partitions a problem into mutually exclusive and exhaustive cases, counts each separately, and adds. Before adding case totals, verify that no outcome belongs to two cases (exclusivity) and every outcome belongs to some case (exhaustiveness).
- Sec 7.12Counting applies directly to password security (password space), code construction (capacity), and scheduling (assignment counts). These applications use product and sum rules together with restrictions to answer real design and security questions.
- Sec 7.13Six recurring errors: double-counting overlapping categories; misapplying the product rule when stages are not independent; treating unordered outcomes as ordered; forgetting restrictions; leaving casework incomplete; using the wrong base total in complement counting.
- Sec 7.14Chapter 8 introduces factorials, permutations, and combinations — compact formulas that extend the product rule to ordered and unordered selections of any size. The distinction between ordered and unordered outcomes (Section 7.9) and all the reasoning strategies of Chapter 7 carry forward directly.
Key Terms Review
Sum Rule
If a task can be done in one of k mutually exclusive ways with n₁, n₂, …, nₖ outcomes respectively, the total is n₁ + n₂ + ⋯ + nₖ.
Product Rule
If a task has k independent sequential stages with n₁, n₂, …, nₖ options per stage, the total number of outcomes is n₁ × n₂ × ⋯ × nₖ.
Mutually Exclusive
Two categories or events are mutually exclusive if no outcome belongs to both simultaneously. Mutual exclusivity is required for the Sum Rule to apply directly.
Tree Diagram
A visual representation of multi-stage choices in which branches represent options and paths from root to leaf represent complete outcomes.
Complement Counting
Counting desired outcomes by subtracting unwanted outcomes from the total: |A| = |S| − |Aᶜ|. Most effective for "at least one" problems.
Complement
The set of all outcomes in the sample space that do not belong to a given set A. Denoted Aᶜ or Ā.
Inclusion-Exclusion
A formula for the size of a union of overlapping sets that corrects for double-counting of elements in multiple sets.
Union
The set of all elements that belong to at least one of two or more sets. Written A ∪ B.
Intersection
The set of elements that belong to all of two or more sets simultaneously. Written A ∩ B.
Ordered Outcome
An outcome in which the sequence of elements matters. (A, B) and (B, A) are different ordered outcomes.
Unordered Outcome
An outcome in which only the set of chosen elements matters, not their order. {A, B} and {B, A} are the same unordered outcome.
Restriction
A constraint on which outcomes are valid, such as "no repetition," "A and B cannot both be chosen," or "must start with a vowel."
Subtraction Method
Counting valid outcomes by starting from all outcomes and subtracting those that violate a restriction.
Casework
Organizing a counting problem into mutually exclusive and exhaustive cases, counting each separately, and summing the results.
Exhaustive
A set of cases is exhaustive if every valid outcome belongs to at least one case. Together with mutual exclusivity, exhaustiveness guarantees that casework counts each outcome exactly once.
Sample Space
The set of all possible outcomes in a counting or probability problem. The total from which subsets are counted.
Double-Counting
A counting error in which the same outcome is included in two or more categories and counted more than once in the total.
Password Space
The total number of possible passwords under a given set of rules. A larger password space means greater security against exhaustive search.
Concept Review Questions
- Explain in your own words why the main difficulty in counting problems is representation, not arithmetic.
- What condition must be satisfied before you can apply the Sum Rule? Give an example where this condition fails and explain how to fix it.
- A task has three stages with 4, 3, and 2 options. Explain why the total is 24 and not 4 + 3 + 2 = 9.
- When should you use complement counting rather than direct counting? Give one example of each type of problem.
- In inclusion-exclusion for two sets, why is |A ∩ B| subtracted? What would go wrong if it were not?
- Explain the difference between an ordered outcome and an unordered outcome. Give an example of a problem that requires each type.
- What two conditions must a casework partition satisfy for the resulting sum to be a correct total count?
- Why does adding special characters to a password alphabet increase security more than simply making the password one character longer?
Skill Practice
- Choose one item from 7 books or 4 magazines.
- Choose a shirt (5 colors) and a tie (12 patterns).
- A 5-digit zip code from digits 0–9, repetition allowed.
- A 4-letter word from {A–Z}, no repetition allowed.
- A meal: 1 of 3 soups, 1 of 5 entrées, 1 of 4 desserts.
- A password: 2 letters then 3 digits, repetition allowed.
- 3-character strings from {A,B,C,D}, repetition: at least one A.
- Roll two dice: at least one shows 5 or 6.
- |A|=50, |B|=40, |A∩B|=15. Find |A∪B| and |A only|.
- 1–100 integers divisible by 4 or 6.
- 200 students: 110 like math, 90 like science, 40 like both. How many like neither?
- |A∪B∪C|=80, |A|=40, |B|=35, |C|=30, pairwise intersections 12, 10, 8. Find |A∩B∩C|.
- 4-digit PINs from 1–9, no repeats, must start with an odd digit.
- 3-person committee from 6 people; persons X and Y cannot both serve.
- 5-letter strings, no vowels, no repeats (vowels: A,E,I,O,U).
- Outcomes when rolling 3 dice with at least two equal values.
- 2-digit numbers (10–99) where both digits are odd.
- Teams of 4 from 5 men and 5 women with exactly 2 men.
Error Analysis
Problem 1
A student counts 2-person committees from {A,B,C,D,E} as 5 × 4 = 20.
What error has the student made? What is the correct count? How many times has each committee been counted?
Problem 2
Passwords with at least one digit (6 chars, 26 letters + 10 digits): student subtracts 26⁶ from (26+10)⁶ but uses 36⁶ − 10⁶.
Identify the error in the complement. What should be subtracted, and why?
Problem 3
60 students study French or Spanish. 35 study French, 25 study Spanish, so 0 study both, says the student.
Show why this conclusion is wrong. What does the inclusion-exclusion formula tell you about |A ∩ B| when |A ∪ B| = |A| + |B|?
Problem 4
Casework for committees of 3 from 5 with at least 1 woman (3 women, 2 men in pool): student sets up cases "0 women" and "at least 1 woman" and adds 1 + 6 = 7. But only counts 0-women case as 1 committee.
Verify whether the total is correct using a different method, and identify any error in the student's casework structure.
Chapter 7 Checkpoint
Chapter 7 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 7
Section 1 — Vocabulary and Concepts
- State the Sum Rule and the condition required for it to apply.
- State the Product Rule and explain what "independence" means in this context.
- Explain the difference between ordered and unordered outcomes. Give one example of each.
Section 2 — Core Skills
- A student can choose one elective from 6 mathematics courses or 4 science courses. How many elective choices are there?
- A lock has 4 dials, each showing digits 0–9. How many combinations are there with repetition? Without repetition?
- A 5-flip coin sequence: how many outcomes include at least two heads? (Use complement.)
- Among integers 1–60, how many are divisible by 4 or 6?
- In a class of 50, 28 play an instrument, 22 do art, and 10 do both. How many do neither?
- A 4-person committee is chosen from 6 engineers and 4 designers. How many committees have at least one designer?
Section 3 — Restrictions and Casework
- A 5-character password uses only the letters A–Z (no digits), with repetition. How many passwords begin with a vowel (A, E, I, O, U)?
- 6 people are seated in a row. Two specific people must not sit next to each other. How many valid arrangements are there? (Hint: 6! = 720; treat the two as a block to count invalid arrangements.)
- A team of 4 is chosen from 5 juniors and 6 seniors. Using casework, count the number of teams with exactly 2 seniors and exactly 2 juniors. Then count teams with at least 2 seniors.
Section 4 — Applications
- A system generates 6-character codes using uppercase letters (26) and digits (10), with repetition allowed. How many codes are possible? How many contain at least one digit?
- A conference has 5 speakers and 5 time slots. Speaker A must go before Speaker B (but not necessarily immediately before). How many valid schedules are there? (Hint: count all schedules, then use symmetry to determine how many have A before B.)
Section 5 — Error Analysis
- A student says: "Choosing a 3-letter arrangement from {A, B, C, D, E} gives 5 + 4 + 3 = 12 outcomes." Identify the error and compute the correct answer.
- A student computes |A ∪ B| = 80 when |A| = 45, |B| = 50, and |A ∩ B| = 20. Identify and correct the error.
Looking Ahead
Chapter 8: Permutations, Combinations, and Discrete Probability
Chapter 7 gave you the foundational reasoning strategies for counting: the sum and product rules, complements, inclusion-exclusion, restrictions, and casework. Chapter 8 extends this toolkit with compact, general formulas. The factorial function will compress products like 10 × 9 × 8 × ⋯ × 1 into a single symbol. Permutation formulas will count ordered selections efficiently. Combination formulas will count unordered selections. Pascal's Triangle and the binomial theorem will connect counting to algebraic identities. And discrete probability — probability built entirely on counting, without calculus — will give these techniques direct applications in prediction, risk, and data analysis.
MGU Library Connection
- Counting Rules Formula Sheet — Appendix I of this textbook
- Set Theory Reference — Appendix D of this textbook (for inclusion-exclusion foundations)
- Chapter 8: Permutations, Combinations, and Discrete Probability (continues directly)
- Chapter 9: Advanced Counting — Pigeonhole Principle, Stars and Bars, Recurrence Relations
- Cybersecurity and Cryptography — MGU Computer Science Library: password strength, key space analysis, brute-force complexity
- Algorithm Analysis — Chapter 12: Counting Operations and Big-O Notation builds on combinatorial reasoning
- MGU Dictionary entries: sum rule, product rule, complement, inclusion-exclusion, permutation, combination, casework