MGU Mathematics Series — Combinatorics
Part I: Foundations of Counting
Sum Rule · Product Rule · Complement · Casework · Inclusion-Exclusion
Chapter 2 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 2:
Basic Counting
Principles

The sum rule, the product rule, complement counting, casework, and inclusion-exclusion — the disciplined foundation on which all combinatorial reasoning is built

■ Part I: Foundations of Counting ■

■ 14 Sections  •  Chapter 2 of 14 ■

Follows Chapter 1: What Combinatorics Studies  ·  Prepares students for Chapters 3 through 14

Chapter 2 — Front Matter

Purpose and Overview

Chapter 1 introduced combinatorics as the mathematics of arrangements, selections, patterns, and finite structures. You learned that counting is not simply listing items one by one — it is disciplined reasoning about structure. You practiced listing systematically, building tree diagrams, organizing cases into tables, and using algebraic notation to represent counting problems.

This chapter builds the foundation you will use throughout the entire book. Every major counting technique in later chapters — permutations, combinations, binomial coefficients, stars and bars, inclusion-exclusion, the pigeonhole principle, recurrence relations, generating functions, and graph counting — depends on the ideas introduced here.

The core rules of counting are simpler than you might expect. There are essentially two fundamental rules: the sum rule and the product rule. From these two rules, and from careful attention to structure, almost everything else follows. The key skill is not memorizing which formula to apply — it is reading a problem carefully enough to understand what is being counted, whether the cases are separate or overlapping, how many choices are made at each step, and whether any restrictions apply.

This chapter will also introduce complement counting, casework, and inclusion-exclusion for two and three sets. These are strategies for handling situations where direct counting is awkward, where cases naturally separate, or where multiple categories overlap.

Opening Question

A university system administrator is designing student login credentials. Each credential consists of a four-character uppercase-letter code followed by a three-digit number. Repetition is allowed in both parts. How many distinct login credentials are possible? If the administrator adds a restriction — the code must not begin with the letter O because it looks too much like the digit 0 — how does the count change? And if two separate systems each have their own valid login format, how many total valid credentials exist across both systems? Each of these questions requires a different counting principle. By the end of this chapter, you will be able to answer all of them and explain why each answer is correct.

14Sections
11Objectives
11Key Terms
15+Worked Examples

Learning Objectives

  1. 1State and apply the sum rule for disjoint cases.
  2. 2State and apply the product rule for multi-step choices.
  3. 3Use complement counting to simplify problems with difficult restrictions.
  4. 4Organize a counting problem into cases using the casework strategy.
  5. 5Distinguish disjoint cases from overlapping cases.
  6. 6Apply inclusion-exclusion to count the union of two overlapping sets.
  7. 7Apply inclusion-exclusion to count the union of three overlapping sets.
  8. 8Use tables and diagrams to represent and verify small counting problems.
  9. 9Recognize and avoid common counting mistakes such as double-counting and missing cases.
  10. 10Apply basic counting principles to passwords, codes, and scheduling problems.
  11. 11Explain why a counting method gives a correct answer, not just state the number.
Chapter 2 — Contents

Sections at a Glance

Sections 2.1 – 2.4
The Two Fundamental Rules
Why Rules Are Needed · The Sum Rule · The Product Rule · Multi-Step Choices
Section 2.1

Why Counting Rules Are Needed

In Chapter 1, you learned to list outcomes systematically. Listing works well for small problems. If you want to know how many ways three students can be seated in three chairs, you can write out all six arrangements and count them. But listing quickly becomes impractical. If a password system uses six characters chosen from 62 possible symbols, listing all possible passwords would require more than 56 billion entries. No one does this by hand.

Counting rules let you find exact counts without listing. They replace exhaustive enumeration with algebraic reasoning. The goal is not to shortcut past understanding — it is to understand the structure of a counting problem well enough to compute the count directly.

This requires a particular discipline. Before applying any counting rule, you must answer several questions.

Question to AskWhy It Matters
What are the objects being counted?A count is only meaningful if you are clear about what you are counting.
Is order relevant?Ordered sequences and unordered groups are counted by different methods.
Are you choosing from separate categories or making sequential decisions?Determines whether to add (sum rule) or multiply (product rule).
Are there restrictions?Restrictions may reduce option counts at specific steps or require complement counting.
Do any cases overlap?Overlapping cases require inclusion-exclusion, not simple addition.
The Central Habit

Only after answering these questions should you choose a counting method. The most common mistake in combinatorics is choosing a method before understanding the structure. This chapter builds the habit of reading before computing.

Section 2.2

The Sum Rule

The Sum Rule

Suppose a task can be completed in exactly one of k ways, with n₁, n₂, …, nₖ options respectively, and no option belongs to more than one way. Then the total number of ways to complete the task is:

n₁ + n₂ + ⋯ + nₖ

Why this works. The sum rule applies when you are making a single choice, but the options fall into separate categories that do not overlap. The categories partition the set of all valid options. Because they are disjoint, you can count each category independently and add the results. In set notation: if A and B are disjoint, then |A ∪ B| = |A| + |B|.

When to use the sum rule. Use the sum rule when a problem involves choosing one option from several separate categories. The word or is often a signal — but only when the options are truly disjoint. If the options overlap, you need inclusion-exclusion instead.

Example 2.2.1
Choosing a language course
  • ProblemA university offers 5 evening courses in Spanish and 3 evening courses in Mandarin. A student wants to enroll in exactly one evening language course this semester. How many choices does the student have?
  • ThinkThe student is making one choice. The Spanish and Mandarin courses are completely separate — no course belongs to both categories.
  • RepresentLet S = Spanish courses, M = Mandarin courses. |S| = 5, |M| = 3. The sets are disjoint.
  • Count|S ∪ M| = |S| + |M| = 5 + 3 = 8
  • CheckThere are 5 options in one group and 3 in another, with no overlap. Adding gives the correct total.
Answer: The student has 8 possible choices.
Example 2.2.2
Choosing a form of transportation
  • ProblemA student can travel to the library by one of 4 bus routes, one of 2 shuttle routes, or by 1 walking path. How many ways can the student travel?
  • RepresentLet B, H, W be the sets of bus, shuttle, and walking options. |B| = 4, |H| = 2, |W| = 1. The categories are disjoint.
  • Count|B| + |H| + |W| = 4 + 2 + 1 = 7
Answer: The student has 7 different ways to travel to the library.
Practice 2.2Sum Rule
  1. A student can satisfy a language requirement by taking French (4 courses offered), Spanish (6 courses), or German (3 courses). How many choices does the student have?
  2. A menu offers 5 vegetarian entrées, 7 meat entrées, and 3 seafood entrées. A diner ordering exactly one entrée has how many choices?
  3. A code begins with either a single uppercase letter or a single digit. How many choices are there for the first character?
  4. A library has 120 books in the history section and 85 books in the science section, with no book in both sections. How many books are in either section?
Section 2.3

The Product Rule

The Product Rule

Suppose a task is completed in a sequence of k steps. Step 1 can be done in n₁ ways, step 2 in n₂ ways (regardless of the first step), and so on. Then the total number of ways to complete the task is:

n₁ × n₂ × ⋯ × nₖ

Why this works. For each of the n₁ ways the first step can go, there are n₂ ways for the second step — giving n₁ × n₂ ordered pairs. Extending through k steps gives the full product. A tree diagram makes this concrete: if step 1 has 3 branches and step 2 has 4 branches from each node, the tree has 3 × 4 = 12 leaves, one per complete outcome.

When to use the product rule. Use it when a problem involves making a sequence of choices where each choice is independent — the number of options at each step does not change based on what was chosen before. The phrase "and then" often signals a multi-step sequence where the product rule applies.

Example 2.3.1
Building a login credential (the opening question)
  • ProblemA credential consists of a four-character uppercase-letter code followed by a three-digit number. Repetition is allowed. How many distinct credentials are possible?
  • ThinkA credential is built by making seven sequential choices: four letter choices and three digit choices. Each choice is independent because repetition is allowed — the options at each position do not change based on previous selections.
  • Represent26 choices for each letter position; 10 choices for each digit position.
  • Count 26 × 26 × 26 × 26 × 10 × 10 × 10 = 26⁴ × 10³ 26⁴ = 456,976 10³ = 1,000 456,976 × 1,000 = 456,976,000
  • CheckThe four letter positions each contribute 26; the three digit positions each contribute 10. Since repetition is allowed, no step count decreases. The product counts all valid ordered sequences.
Answer: 456,976,000 possible login credentials.
Example 2.3.2
Menu combinations
  • ProblemA cafeteria offers a lunch combination: one soup, one sandwich, one drink. There are 4 soups, 6 sandwiches, and 5 drinks. How many distinct combinations are possible?
  • RepresentSoup choices: 4. Sandwich choices: 6. Drink choices: 5. Each choice is independent.
  • Count4 × 6 × 5 = 120
  • CheckThe tree diagram would have 4 top branches, each splitting into 6, each splitting into 5, giving 4 × 6 × 5 = 120 leaves. Correct.
Answer: 120 distinct lunch combinations.
Section 2.4

Multi-Step Choices

Many counting problems involve several sequential decisions, each with a fixed number of options. The product rule applies to all of them, as long as the number of options at each step does not depend on earlier choices in a way that changes step-by-step counts.

When the number of options at a step does depend on earlier choices — such as when you are selecting objects without replacement — you will need to track how many options remain at each step. This is a central theme in Chapter 3 on permutations. For now, focus on problems where the number of options at each step is fixed.

Example 2.4.1
Course scheduling
  • ProblemA student must choose one course from each of four departments: Mathematics (8 options), History (5 options), Biology (6 options), and Philosophy (4 options). How many different four-course schedules are possible?
  • ThinkFour independent selections, one per department. Each department's selection does not affect the others.
  • Count 8 × 5 × 6 × 4 = 960 (8 × 5 = 40, 40 × 6 = 240, 240 × 4 = 960)
  • CheckThe product accounts for all combinations of one course from each department. No department's selection affects another.
Answer: 960 different four-course schedules.
Practice 2.3 – 2.4Product Rule
  1. A sandwich shop offers 4 types of bread, 6 types of filling, and 3 types of sauce. How many distinct sandwiches can be made using one of each?
  2. A license plate uses 3 uppercase letters followed by 3 digits. Repetition is allowed. How many plates are possible?
  3. A multiple-choice test has 5 questions, each with 4 options. How many different answer sheets are possible?
  4. A room security system uses a 5-digit code (digits 0–9, repetition allowed). How many codes are there?
  5. A restaurant offers a prix-fixe dinner: 3 choices for appetizer, 5 for entrée, 4 for dessert, and 3 for beverage. How many distinct dinners are possible?
Sections 2.5 – 2.8
Restrictions, Complement Counting, and Casework
Counting with Restrictions · Complement Counting · Casework · Disjoint vs. Overlapping Cases
Section 2.5

Counting with Restrictions

A restriction is a condition that eliminates some otherwise valid outcomes. There are two general strategies for handling restrictions.

StrategyWhen to UseMethod
Build in the restrictionThe restriction applies cleanly to one or more specific stepsAt each restricted step, count only the valid options
Complement countingCounting violating outcomes is easier than counting valid onesTotal count minus count of outcomes violating the restriction
Example 2.5.1
Restricted credential — no leading letter O
  • ProblemA credential is a four-character uppercase-letter code followed by a three-digit number (repetition allowed). The first letter must not be O. How many credentials are valid?
  • ThinkThe restriction applies only to the first position. One letter is excluded, leaving 25 options there. All other positions are unrestricted.
  • Count 25 × 26 × 26 × 26 × 10 × 10 × 10 = 25 × 26³ × 10³ = 25 × 17,576 × 1,000 = 439,400,000
  • CheckThe unrestricted count was 456,976,000. The difference is 26³ × 10³ = 17,576,000 — exactly the credentials whose first letter is O. Reducing the first position from 26 to 25 choices removes precisely one twenty-sixth of the original total.
Answer: 439,400,000 valid credentials.
Example 2.5.2
Restriction on two steps — PIN with first and last digit rules
  • ProblemA four-digit PIN uses digits 0–9 (repetition allowed). The first digit must not be 0, and the last digit must be even. How many valid PINs are there?
  • RepresentFirst digit: 9 choices (digits 1–9). Second and third: 10 choices each. Last digit: 5 choices (0, 2, 4, 6, 8).
  • Count9 × 10 × 10 × 5 = 4,500
  • CheckThe unrestricted count is 10⁴ = 10,000. Fractions retained: 9/10 × 5/10 = 45/100. So 45% of 10,000 = 4,500. Consistent.
Answer: 4,500 valid PINs.
Section 2.6

Complement Counting

Sometimes counting what you do want directly is difficult, but counting what you do not want is easy. Complement counting exploits this. The complement of a set A within a universal set U is the set of all elements of U that are not in A. The key relationship is:

Complement Counting Formula
|A| = |U| − |Aᶜ|
The number of outcomes satisfying condition A equals the total number of outcomes minus the number of outcomes that do not satisfy condition A.
When to Use Complement Counting

Complement counting is most useful when the condition involves "at least one," when counting the direct cases requires many sub-cases, or when the restriction excludes a small and easily described portion of the total. Always be precise about what the complement means — the complement of "at least one" is "none at all," not "exactly one."

Example 2.6.1
At least one vowel
  • ProblemA two-letter code is formed using the 26 uppercase letters (repetition allowed). How many codes contain at least one vowel? (Vowels: A, E, I, O, U — five letters.)
  • Think"At least one vowel" includes codes with exactly one vowel and codes with two vowels. Counting directly requires splitting into cases. The complement — codes with no vowels at all — is a single clean calculation.
  • Count |U| = 26 × 26 = 676 (all two-letter codes) |Aᶜ| = 21 × 21 = 441 (both letters are consonants) |A| = 676 − 441 = 235
  • Check235 + 441 = 676. The two groups partition the total. Consistent.
Answer: 235 two-letter codes contain at least one vowel.
Example 2.6.2
At least one even digit
  • ProblemA three-digit number is formed using digits 1 through 9 (repetition allowed). How many contain at least one even digit?
  • ComplementThe complement is: all three digits are odd. Odd digits from 1–9: {1, 3, 5, 7, 9} — five digits.
  • Count |U| = 9³ = 729 |Aᶜ| = 5³ = 125 (all odd digits) |A| = 729 − 125 = 604
  • Check604 + 125 = 729. Correct.
Answer: 604 three-digit numbers contain at least one even digit.
Practice 2.5 – 2.6Restrictions and Complement Counting
  1. A three-character code from {A, B, C, D, E} uses letters with repetition. How many codes do not consist entirely of A's?
  2. A five-digit PIN uses digits 0–9 (repetition allowed). How many PINs contain at least one zero?
  3. A four-character password uses only lowercase letters (repetition allowed). How many passwords are not all vowels?
  4. Two-letter codes are formed from the 26-letter alphabet (repetition allowed). How many codes are not "AA"?
  5. A four-digit PIN uses digits 1–9 (no zero, repetition allowed). The first digit must not be 1 and the last digit must not be 9. How many valid PINs are there?
Section 2.7

Casework

Casework is the strategy of dividing a counting problem into mutually exclusive and exhaustive cases, counting each case separately, and adding the results. Mutually exclusive means no outcome belongs to more than one case. Exhaustive means every valid outcome belongs to at least one case. Together, these conditions ensure the sum rule applies — you can add the case counts and get the correct total without double-counting or missing anything.

Casework is not a single formula. It is a strategy. The skill is finding a case division that makes each case straightforward to count.

Example 2.7.1
Passwords with a specified length range
  • ProblemA password consists of between 1 and 3 lowercase letters (exactly 1, 2, or 3 letters). Repetition is allowed. How many passwords are there?
  • ThinkDivide into cases by length. A 1-letter password and a 2-letter password are structurally different objects. The cases are mutually exclusive (different lengths) and exhaustive (all lengths from 1 to 3 are covered).
  • Count Case 1 (1 letter): 26¹ = 26 Case 2 (2 letters): 26² = 676 Case 3 (3 letters): 26³ = 17,576 Total: 26 + 676 + 17,576 = 18,278
  • Check"a" and "aa" are distinct passwords even though they share the letter a. The cases are genuinely disjoint. Adding is correct.
Answer: 18,278 possible passwords.
Example 2.7.2
Seating based on a condition
  • ProblemFive students — Alex, Brianna, Carlos, Dana, and Evan — are seated in a row of five chairs. Carlos must be in either the first chair or the last chair. In how many ways can they be seated?
  • ThinkDivide by Carlos's position. Carlos cannot occupy both the first and last chair simultaneously, so the two cases are disjoint.
  • CountThe remaining 4 students can be arranged in 4 chairs in 4 × 3 × 2 × 1 = 24 ways. Case 1 (Carlos in chair 1): 24 arrangements Case 2 (Carlos in chair 5): 24 arrangements Total: 24 + 24 = 48
  • CheckThe two cases are mutually exclusive and exhaustive (the only two positions allowed for Carlos). Sum rule applies.
Answer: 48 valid seating arrangements.
Section 2.8

Disjoint and Overlapping Cases

The sum rule requires that the cases being added are disjoint — no outcome belongs to more than one case. This requirement is easy to overlook when a problem has natural-sounding categories that actually share some outcomes.

Disjoint cases share no outcomes. You can safely add their counts. Overlapping cases share some outcomes. If you add their counts directly, you will count the shared outcomes more than once. This is overcounting, and it requires correction.

Recognizing Overlap

When dividing a problem into cases, always ask: could an outcome belong to more than one of my cases? If so, the cases overlap. For example, if Case 1 is "passwords containing A" and Case 2 is "passwords containing B," then a password like "AB" belongs to both cases. Adding the counts would double-count "AB." The tool for this is inclusion-exclusion.

Example 2.8.1
Recognizing overlap — using complement instead
  • ProblemA three-letter code uses letters A through F. How many codes contain the letter A or the letter B (or both)?
  • ThinkThe natural case split ("codes with A" and "codes with B") overlaps. A code like ABB belongs to both cases. Instead, use complement counting.
  • Count |U| = 6³ = 216 (all three-letter codes from A–F) |Aᶜ| = 4³ = 64 (codes using only C, D, E, F — neither A nor B) |A ∪ B| = 216 − 64 = 152
  • CheckWe will verify this result using inclusion-exclusion in Section 2.9.
Answer: 152 three-letter codes contain at least one A or at least one B.
Practice 2.7 – 2.8Casework
  1. A code is formed using between 1 and 4 digits (digits 0–9, repetition allowed). How many codes are possible?
  2. Five students must sit in a row of five chairs. Student A must sit at one end (the leftmost or rightmost chair). How many valid arrangements are there?
  3. A two-digit number is formed using digits 1–9. The number must be either less than 30 or greater than 70. How many such numbers are there?
  4. Explain why adding "codes with an A" and "codes with a B" would give an incorrect count for three-letter codes from {A, B, C, D}. Identify what is being double-counted.
Sections 2.9 – 2.12
Inclusion-Exclusion, Diagrams, and Applications
Two-Set Formula · Three-Set Formula · Tables and Diagrams · Passwords, Codes, and Scheduling
Section 2.9

Inclusion-Exclusion for Two Sets

When two sets A and B overlap, adding |A| and |B| counts every element of A ∩ B twice. Subtracting |A ∩ B| once corrects the double-counting and gives the size of the union.

Inclusion-Exclusion — Two Sets
|A ∪ B| = |A| + |B| − |A ∩ B|
Adding |A| and |B| counts everything in A ∩ B twice. Subtracting |A ∩ B| once removes the extra count. The result is the number of elements in A, B, or both.
A only A ∩ B (counted twice) B only A B |A ∪ B| = |A| + |B| − |A ∩ B|
Example 2.9.1
Courses in two departments
  • Problem15 courses are classified as Mathematics, 12 as Computer Science, and 5 appear under both classifications. How many distinct courses are in Mathematics or Computer Science (or both)?
  • RepresentLet M = Math courses, C = CS courses. |M| = 15, |C| = 12, |M ∩ C| = 5.
  • Count|M ∪ C| = 15 + 12 − 5 = 22
  • Check10 Math-only + 5 cross-listed + 7 CS-only = 22. Consistent.
Answer: 22 distinct courses in Mathematics or Computer Science.
Example 2.9.2
Student club membership
  • ProblemIn a group of 50 students, 28 are in the Chess Club and 23 are in the Science Club. 10 students are in both. How many are in at least one club?
  • Count|Ch ∪ Sc| = 28 + 23 − 10 = 41
  • CheckChess only: 28 − 10 = 18. Science only: 23 − 10 = 13. Both: 10. Total: 18 + 13 + 10 = 41. Consistent.
Answer: 41 students are in at least one club.
Example 2.9.3
Verifying Example 2.8.1 with inclusion-exclusion
  • ProblemThree-letter codes from A–F. Verify: how many contain A or B?
  • Count each set |U| = 6³ = 216 |A| (at least one A) = 216 − 5³ = 216 − 125 = 91 |B| (at least one B) = 216 − 5³ = 91 (by symmetry) |A ∩ B| (at least one A and at least one B): = 216 − 125 − 125 + 64 = 30 (using complement: total minus no-A minus no-B plus neither)
  • Union|A ∪ B| = 91 + 91 − 30 = 152
  • CheckThis matches the complement-counting answer of 152 from Example 2.8.1. Both methods agree.
Answer: 152. Both methods give the same result.
Section 2.10

Inclusion-Exclusion for Three Sets

Inclusion-Exclusion — Three Sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Add individual counts → subtract pairwise intersections → add the triple intersection. The pattern alternates in sign. Chapter 7 develops the general formula for any number of sets.

Why the signs alternate. When you add |A| + |B| + |C|, elements in exactly two sets are counted twice (subtract once each) and elements in all three sets are counted three times (subtract three times, then add back once). After the full formula, every element is counted exactly once regardless of how many sets it belongs to.

A only B only C only A∩B A∩C B∩C A∩B∩C A B C
Example 2.10.1
Three club memberships
  • ProblemIn a group of 100 students: 45 in Math Club, 38 in Science Club, 30 in History Club. Pairwise overlaps: Math ∩ Science = 18, Math ∩ History = 12, Science ∩ History = 14. All three: 6. How many students are in at least one club?
  • Count |M ∪ S ∪ H| = 45 + 38 + 30 − 18 − 12 − 14 + 6 = 113 − 44 + 6 = 75
  • CheckBreaking into seven regions:
    All three: 6 · M∩S only: 12 · M∩H only: 6 · S∩H only: 8
    M only: 21 · S only: 12 · H only: 10
    Sum: 6 + 12 + 6 + 8 + 21 + 12 + 10 = 75. Confirmed.
Answer: 75 students are members of at least one club.
Example 2.10.2
Database records with multiple labels
  • ProblemA database has 200 records. 110 have label X, 80 have label Y, 75 have label Z. Pairwise overlaps: X∩Y = 40, X∩Z = 30, Y∩Z = 25. All three: 15. How many records have at least one label?
  • Count |X ∪ Y ∪ Z| = 110 + 80 + 75 − 40 − 30 − 25 + 15 = 265 − 95 + 15 = 185
  • Check200 − 185 = 15 records have no label at all. This is a reasonable residual.
Answer: 185 records carry at least one label.
Practice 2.9 – 2.10Inclusion-Exclusion
  1. In a class of 35 students, 20 passed the midterm and 25 passed the final. 15 students passed both. How many passed at least one exam?
  2. A database has 500 records. 200 have tag X, 150 have tag Y, and 80 have both tags. How many records have tag X or tag Y?
  3. A survey of 100 people found: 60 own a car, 45 own a bicycle, and 28 own both. How many own a car or a bicycle?
  4. Among 80 students: 30 study French, 25 study German, 40 study Spanish. Overlaps: French ∩ German = 10, French ∩ Spanish = 12, German ∩ Spanish = 8. All three = 5. How many study at least one language?
  5. A city data set: 500 businesses have a website (W), 300 have social media (S), 200 have a mobile app (M). Overlaps: W∩S = 150, W∩M = 100, S∩M = 80. All three = 50. How many businesses have at least one digital presence?
Section 2.11

Counting with Tables and Diagrams

Tables and diagrams are not just visual aids — they are computational tools. For small problems, constructing a table or tree diagram serves two purposes: it organizes the count and provides direct verification.

ToolBest ForHow to Read the Count
Two-way tableTwo-step sequential choicesTotal cells = rows × columns (confirms product rule)
Venn diagramOverlapping sets (2 or 3 sets)Fill in each region; sum all regions for the union
Tree diagramMulti-step sequential choicesCount leaves (terminal nodes) for the total
Example 2.11.1
Verifying a count with a table
  • ProblemA two-character code uses a vowel (A, E, I, O, U) as the first character and a digit (1, 2, 3) as the second. Construct a table and confirm the count.
  • TableRows represent vowels (5 rows: A, E, I, O, U). Columns represent digits (3 columns: 1, 2, 3). Each cell is one code. Codes: A1 A2 A3 | E1 E2 E3 | I1 I2 I3 | O1 O2 O3 | U1 U2 U3 Total cells: 5 × 3 = 15
  • CheckEach of the 15 codes appears exactly once. The product rule gives the same count directly.
Answer: 15 two-character codes. The table confirms the product rule count.
Section 2.12

Counting in Passwords, Codes, and Scheduling

The counting principles of this chapter arise naturally in systems where rules determine which objects are valid. Passwords, access codes, scheduling systems, and assignment problems all involve choices constrained by rules. This section applies the chapter's tools to realistic scenarios.

Example 2.12.1
Password strength analysis
  • ProblemA system requires passwords of exactly 8 characters. Each character can be a lowercase letter (26), uppercase letter (26), or digit (10) — 62 total. Repetition is allowed. The password must include at least one digit. How many valid passwords are there?
  • ThinkUse complement counting: total passwords minus passwords with no digits at all.
  • Count Total: 62⁸ = 218,340,105,584,896 No digits: 52⁸ = 53,459,728,531,456 At least one digit: 164,880,377,053,440
  • InterpretApproximately 1.65 × 10¹⁴ valid passwords. Requiring at least one digit eliminates roughly 24.5% of otherwise valid passwords, illustrating how character-type requirements affect key space size.
Answer: 164,880,377,053,440 valid passwords.
Example 2.12.2
Tournament scheduling with a restriction
  • ProblemA tournament has 4 teams. Each team is assigned to one of 4 time slots. Each slot holds exactly one team. Team Red cannot be in the 9AM slot. How many valid schedules are there?
  • ThinkUse complement counting. Total schedules: 4! = 24. Schedules where Red is in 9AM: Red is fixed, the remaining 3 teams arrange in 3 slots: 3! = 6.
  • Count Valid schedules = 24 − 6 = 18
  • CheckCasework: Red can be in slot 11AM, 1PM, or 3PM (3 choices). Remaining 3 teams arrange in 3 slots: 6 ways each. 3 × 6 = 18. Consistent.
Answer: 18 valid tournament schedules.
Example 2.12.3
Access codes with two formats — sum and product rules combined
  • ProblemA building uses access codes of two types: Type A (3 uppercase letters followed by 2 digits, repetition allowed) or Type B (2 digits followed by 4 uppercase letters, repetition allowed). How many distinct codes are there in total?
  • ThinkType A and Type B codes are different structures and different lengths — they never overlap. Use the sum rule after computing each count with the product rule.
  • Count Type A: 26³ × 10² = 17,576 × 100 = 1,757,600 Type B: 10² × 26⁴ = 100 × 456,976 = 45,697,600 Total: 1,757,600 + 45,697,600 = 47,455,200
  • CheckThe two types are disjoint (Type A is 5 characters; Type B is 6 characters). No code appears in both groups. The sum rule applies.
Answer: 47,455,200 distinct access codes across both types.
Practice 2.12Applications
  1. Password security. A web account requires a password of exactly 6 characters from 62 options (repetition allowed). (a) How many total passwords are possible? (b) How many contain no uppercase letters? (c) How many contain at least one uppercase letter?
  2. Scheduling. An event coordinator must schedule 5 speakers into 5 time slots. Speaker A cannot be scheduled in the first or last slot. How many valid schedules are there?
  3. Database query. A query returns records with at least one of: "urgent" (320 records), "reviewed" (210), "flagged" (180). Overlaps: urgent ∩ reviewed = 85, urgent ∩ flagged = 60, reviewed ∩ flagged = 50, all three = 25. How many records appear?
  4. Cryptography preview. A code uses 4-character strings from an alphabet of 10 symbols (repetition allowed). (a) How many strings are possible in total? (b) How many begin and end with the same symbol? (c) How many do not begin with symbol 1 and do not end with symbol 2?
Sections 2.13 – 2.14
Common Mistakes and the Road Ahead
Eight Common Counting Errors · Preparing for Permutations and Combinations
Section 2.13

Common Basic Counting Mistakes

Mistake 1 — Adding when you should multiply
"There are 3 letter choices and 4 digit choices, so there are 3 + 4 = 7 codes."

The sum rule applies when choosing one option from one of several groups. The product rule applies when completing several sequential steps. A code with one letter and one digit is a two-step selection: 3 × 4 = 12 codes.

Mistake 2 — Multiplying when you should add
"In one situation there are 5 options, in another there are 7 options, so the total is 5 × 7 = 35."

If the two situations are separate alternatives for how to complete a task, the total is 5 + 7 = 12. The product rule applies to sequential steps, not to separate alternatives.

Mistake 3 — Double-counting overlapping cases
"40 students play chess and 30 play piano, so 70 students play chess or piano."

If 10 students play both, adding 40 + 30 counts those 10 students twice. The correct count is 40 + 30 − 10 = 60. Always ask whether your cases overlap before adding.

Mistake 4 — Missing a case in casework
Cases defined as "password starts with A" and "password starts with B." No case covers passwords starting with C through Z.

If your cases are not exhaustive — they do not cover all valid outcomes — you will undercount. After listing cases, ask: does every valid outcome belong to at least one case?

Mistake 5 — Forgetting a restriction
"The first letter cannot be A. There are 26 letters, so there are 26 × 26 = 676 two-letter codes."

The restriction reduces the first position to 25 choices (A excluded). The correct count is 25 × 26 = 650.

Mistake 6 — Using the wrong complement
Treating the complement of "at least one A" as "exactly one A."

The complement of "at least one" is "none at all." The complement of "at most one" is "two or more." Always be precise about what the complement means in context.

Mistake 7 — Omitting the intersection in inclusion-exclusion
|A ∪ B| = |A| + |B| (no subtraction of |A ∩ B|)

The intersection must be explicitly subtracted. If you do not know |A ∩ B|, you cannot apply inclusion-exclusion — you may need to find the intersection indirectly using other information.

Mistake 8 — Assuming independence when it doesn't hold
Applying the product rule with fixed step counts when earlier choices eliminate later options.

If choosing option X at step 1 removes X from the options available at step 2, the number of options at step 2 is not fixed — it depends on the earlier choice. This is handled in Chapter 3 (permutations without repetition).

Section 2.14

Preparing for Permutations and Combinations

The counting principles of this chapter are foundational, but they are only the beginning. Chapter 3 extends the product rule to the setting of ordered arrangements, where you select objects from a set and place them in a specific order. The number of options at each step changes depending on what was selected before, because repetition is not allowed.

This leads to factorials and permutation formulas — structured products where the factors decrease step by step. For example, arranging all five students in a row gives 5 × 4 × 3 × 2 × 1 = 120 arrangements, because each student chosen eliminates one option for the next position.

Chapter 4 addresses unordered selections, where the order of the choices does not matter. The key insight will be that an unordered selection corresponds to many ordered arrangements, and dividing by the number of arrangements corrects the count — this correction is the combination formula.

The ideas most important for the transition to Chapter 3 are the product rule for sequential independent choices, the meaning of restrictions at individual steps, and the recognition that changing the number of available options at one step — because something has already been chosen — affects the product. Keep asking: are these sequential steps, or are these separate alternatives?

MGU Library Connection
  • The sum rule parallels the Law of Total Probability for disjoint events in MGU Probability and Statistics, Chapter 3
  • The product rule parallels the Multiplication Rule for independent events in MGU Probability and Statistics, Chapter 4
  • Set union and intersection, which underlie inclusion-exclusion, are treated in full in MGU Discrete Mathematics, Chapter 2
  • Key space analysis using the product rule is previewed in the MGU Cryptography unit on symmetric cipher security
  • MGU Dictionary entries: sum rule, product rule, complement, inclusion-exclusion, disjoint sets, overcounting
Chapter 2 — Back Matter

Chapter Summary

Key Terms Review

sum rule
When a task can be done in exactly one of several mutually exclusive ways, the total count is the sum of the option counts.
product rule
When a task is completed by a sequence of independent choices, the total count is the product of the options at each step.
disjoint cases
Cases that share no outcomes. Disjoint case counts can be added directly without correction.
overlapping cases
Cases that share some outcomes. Overlapping case counts require inclusion-exclusion to avoid double-counting.
complement
The set of all outcomes in the universal set that are not in A. Written Aᶜ or Ā.
complement counting
Valid count = total count − invalid count. Most useful for "at least one" conditions.
casework
Dividing a counting problem into mutually exclusive and exhaustive cases, counting each, and adding the results.
inclusion-exclusion
Formula correcting for overcounting in overlapping set unions: |A ∪ B| = |A| + |B| − |A ∩ B|.
restriction
A condition limiting which outcomes are valid. Restrictions reduce the option count at specific steps.
overcounting
Counting the same outcome more than once. Inflates the answer and must be corrected by inclusion-exclusion or another method.
undercounting
Failing to count some valid outcomes. Deflates the answer; caused by missing cases or an overly narrow model.

Concept Review Questions

Answers may be placed in the answer key.

  1. What condition must hold for the sum rule to apply correctly?
  2. What condition must hold for the product rule to apply correctly?
  3. Explain in your own words why inclusion-exclusion subtracts the intersection when counting |A ∪ B|.
  4. What is the complement of "at least two"?
  5. What is the difference between mutually exclusive cases and exhaustive cases? Why must cases be both for casework to work correctly?
  6. A student argues that the number of 3-character codes from {A, B, C} containing A or B is 3³ + 3³ = 54. Identify the error.
  7. When is complement counting a better strategy than direct counting?
  8. A product rule gives 4 × 3 × 2 = 24. Explain what changes at each step and why the factors decrease. What type of situation does this represent? (Preview: Chapter 3.)

Skill Practice

Part ASum Rule Practice
  1. A student can fulfill a language requirement with French (4), Spanish (6), or German (3) courses. How many choices?
  2. A menu offers 5 vegetarian, 7 meat, and 3 seafood entrées. Exactly one entrée: how many choices?
  3. A code begins with one uppercase letter or one digit. How many choices for the first character?
  4. A library has 120 history books and 85 science books with no overlap. How many are in either section?
  5. A vending machine has 3 chips, 4 crackers, and 2 pretzels. Exactly one snack: how many choices?
Part BProduct Rule Practice
  1. 4 breads, 6 fillings, 3 sauces. One of each: how many sandwiches?
  2. License plate: 3 letters then 3 digits, repetition allowed. How many plates?
  3. 5 questions, 4 options each. How many different answer sheets?
  4. Password: 6 characters from 62 options, repetition allowed. How many passwords?
  5. Prix-fixe: 3 appetizers, 5 entrées, 4 desserts, 3 beverages. How many dinners?
  6. 5-digit code, digits 0–9, repetition allowed. How many codes?
Part CCasework Practice
  1. A code uses between 1 and 4 digits (0–9, repetition allowed). How many codes are possible?
  2. Five students sit in a row of five chairs. Student A must sit at one end. How many valid arrangements?
  3. A two-digit number is formed using digits 1–9. The number must be less than 30 or greater than 70. How many such numbers are there?
Part DComplement Counting Practice
  1. Three-character codes from {A, B, C, D, E} with repetition. How many do not consist entirely of A's?
  2. Five-digit PIN, digits 0–9, repetition allowed. How many contain at least one zero?
  3. Two-letter codes from the 26-letter alphabet, repetition allowed. How many are not "AA"?
  4. Four-character password, lowercase letters only, repetition allowed. How many are not all vowels?
Part EInclusion-Exclusion Practice
  1. In a class of 35: 20 passed the midterm, 25 passed the final, 15 passed both. How many passed at least one?
  2. A database has 500 records. 200 have tag X, 150 have tag Y, 80 have both. How many have X or Y?
  3. A survey of 100: 60 own a car, 45 own a bicycle, 28 own both. How many own a car or bicycle?
  4. Among 80 students: French = 30, German = 25, Spanish = 40. Overlaps: F∩G = 10, F∩S = 12, G∩S = 8, all three = 5. How many study at least one language?
  5. Businesses: W = 500, S = 300, M = 200. Overlaps: W∩S = 150, W∩M = 100, S∩M = 80, all three = 50. How many have at least one digital presence?

Error Analysis

Each problem contains an error. Identify it and write a corrected solution.

Problem 1
A cafeteria offers 4 soups and 3 salads. One soup and one salad: 4 + 3 = 7 ways.

What is the error? What is the correct answer and reasoning?

Problem 2
3-character codes from {1, 2, 3, 4, 5}. Codes with 3 or 5: "codes with a 3" = 27, "codes with a 5" = 27, total = 54.

Has the student correctly counted codes with at least one 3 and codes with at least one 5? Has the overlap (codes with both 3 and 5) been handled? Correct the error.

Problem 3
In a group of 50 people, 25 like coffee and 20 like tea. By inclusion-exclusion: |C ∩ T| = 25 + 20 − 50 = −5, so nobody likes both.

Identify the logical error. What does a negative value of |C ∩ T| actually signal? What additional information is needed to solve this problem correctly?

Problem 4
A password must contain at least one digit. Complement: exactly zero digits. Count passwords with no digits and subtract... but the student computes "passwords with exactly one digit" as the complement.

Identify the wrong complement. State the correct complement. Write the correct complement-counting setup.

Problem 5
5(2x − 3) = 5x − 3

(This error is from Algebra I — included here as a reminder that distributing a factor applies to every term. How does the same logic appear in counting? Can you identify a counting analogy?)

Chapter 2 Checkpoint

Chapter 2 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 2
Part A — Concept Questions
  1. A task can be completed by choosing exactly one item from category P (6 options) or exactly one item from category Q (9 options). The categories do not overlap. How many ways can the task be completed?
  2. A task is completed in three sequential steps with 4, 5, and 3 options at each step. The options at each step are independent of earlier steps. How many ways can the task be completed?
  3. A three-digit code uses digits 1–9 (repetition allowed). How many codes do not start with the digit 1?
  4. A three-digit code uses digits 1–9 (repetition allowed). How many codes contain at least one digit equal to 5?
Part B — Multi-Step Problems
  1. A student ID consists of one uppercase letter followed by four digits 0–9 (repetition allowed). How many student IDs are possible?
  2. A system accepts codes of two types: Type I (2 letters then 3 digits, repetition allowed) or Type II (4 letters, repetition allowed). How many distinct codes are there in total?
  3. A survey of 200 people: 120 use social media daily, 90 read news online daily, 55 do both. How many do at least one of these daily?
  4. Among 150 employees: 60 have completed module A, 75 have completed module B, 50 have completed module C. Overlaps: A∩B = 25, A∩C = 20, B∩C = 30, all three = 10. How many employees have completed at least one module?
Part C — Modeling and Explanation
  1. A scheduling system assigns exactly one instructor from a pool of 5 to each of 3 classrooms. No instructor can be assigned to more than one classroom. How many valid assignments are there? (Hint: treat each classroom as a sequential step, and track how many instructors remain after each assignment. This previews Chapter 3.)
  2. Explain why the following argument is incorrect: "There are 10 even integers and 10 odd integers from 1 to 20. So there are 10 × 10 = 100 integers from 1 to 20." Write a correct statement of what 10 × 10 does count in this context.
Part D — Error Analysis
  1. A student computes: "There are 4 bus routes and 6 train routes, so the number of ways to take one bus and one train on the same day is 4 + 6 = 10." Identify the error. What is the correct answer and reasoning?
  2. A student counts "passwords with at least one uppercase letter" as passwords where the first character is uppercase: 26 × 62⁵. Explain precisely what this count includes and what it misses. What is the correct approach?
Looking Ahead
Chapter 3: Permutations and Arrangements

Chapter 2 established the two fundamental counting rules and the strategies that correct for restrictions and overlap. Chapter 3 extends the product rule into the setting of ordered arrangements, where each selection removes an option from the available pool. You will develop factorials, permutation formulas, circular arrangements, and restricted arrangement methods including the gap and block strategies. Every idea from this chapter — especially the product rule, restrictions, and casework — reappears in Chapter 3 in a richer form. The central question of Chapter 3 is not just how many choices exist at each step, but how those choices interact when repetition is forbidden and order determines the identity of each arrangement.

MGU Library Connection
  • Sum rule and product rule: MGU Discrete Mathematics, Chapter 5 — Counting Fundamentals
  • Inclusion-exclusion (full development): MGU Combinatorics, Chapter 7 — Inclusion-Exclusion and Overlapping Structures
  • Probability connections: MGU Probability and Statistics, Chapter 3 — Sample Spaces and Counting
  • Key space analysis: MGU Cryptography unit on symmetric cipher security strength
  • Set theory background: MGU Discrete Mathematics, Chapter 2 — Sets, Relations, and Functions
  • MGU Dictionary entries: sum rule, product rule, complement, inclusion-exclusion, disjoint, overcounting