26-01 — Counting Principles

Phase: Combinatorics | Subject: 26-01 Prerequisites: 00-01-whole-number-arithmetic.md, basic set theory Next subject: 26-02-permutations.md

Learning Objectives

By the end of this subject, you will be able to:

1. State and apply the Addition Principle (Rule of Sum)
2. State and apply the Multiplication Principle (Rule of Product)
3. Solve counting problems involving "and" vs "or" logic
4. Use tree diagrams to enumerate possibilities
5. Solve multi-stage counting problems with dependencies

Core Content

The Rule of Sum (Addition Principle)

If a task can be performed in one of $m$ mutually exclusive ways, OR in one of $n$ mutually exclusive ways, then the task can be performed in $m + n$ ways.

Formally: If $A$ and $B$ are disjoint sets ($A \cap B = \emptyset$), then $|A \cup B| = |A| + |B|$.

Example: A menu offers 5 pasta dishes and 7 salad dishes. How many ways to choose ONE meal? Answer: $5 + 7 = 12$ ways.

The Rule of Product (Multiplication Principle)

If a procedure consists of $k$ independent stages, where stage $i$ has $n_i$ choices, then the total number of ways to perform the procedure is:

$$n_1 \times n_2 \times \cdots \times n_k$$

Example: A license plate has 3 letters followed by 3 digits. How many possible plates? $26 \times 26 \times 26 \times 10 \times 10 \times 10 = 26^3 \times 10^3 = 17,576,000$

"And" vs "Or" in Counting

⚠️ CRITICAL — The Addition Principle requires disjoint cases. If cases overlap, you double-count. Use the Inclusion-Exclusion Principle (see 26-06) to correct for overlaps.

Tree Diagrams

A visual tool for enumerating multi-stage choices.

Example: Flip a coin then roll a die (if heads) or pick a color from {red, blue} (if tails).

        ┌── Heads
Coin ───┤
        └── Tails

Heads → 6 die outcomes. Tails → 2 color choices. Total: $6 + 2 = 8$ outcomes.

A tree diagram with $n$ levels and $b$ branches per level represents $b^n$ outcomes.

Multi-Stage Counting with Dependencies

When choices at one stage affect choices at later stages, the product rule still applies but the count for each stage changes.

Example: From 20 people, choose a president, vice-president, and secretary (no person holds two offices). Stage 1: 20 choices for president. Stage 2: 19 choices for vice-president (president unavailable). Stage 3: 18 choices for secretary. Total: $20 \times 19 \times 18 = 6840$.

The Bijection Principle

If there is a one-to-one correspondence (bijection) between two finite sets, they have the same size. Use this to transform hard counting problems into easier ones.

Example: Counting subsets of size $k$ from an $n$-element set equals counting binary strings of length $n$ with exactly $k$ ones. Both equal $\binom{n}{k}$.

Key Terms

• Rule of Sum (Addition Principle)
• Rule of Product (Multiplication Principle)
• Tree Diagram
• Bijection Principle

Worked Examples

Example 1: Password Counting

A password must be 6-8 characters long, using only lowercase letters. How many possible passwords?

Solution: 6 chars: $26^6$ 7 chars: $26^7$ 8 chars: $26^8$ By the addition principle: $26^6 + 26^7 + 26^8 = 26^6(1 + 26 + 26^2) = 308,915,776 \times 703 = 217,180,147,328 \approx 2.17 \times 10^{11}$

Example 2: Seating Arrangement Constraints

6 people sit at a round table. The host and hostess must sit opposite each other. Count the arrangements.

Solution: Fix the host's position (eliminates rotational symmetry). The hostess must sit opposite — only 1 choice. The remaining 4 people can sit in $4! = 24$ ways. Total: $1 \times 1 \times 4! = 24$.

Example 3: Counting with Restrictions

How many 4-digit numbers (no leading zero) have all digits distinct?

Solution: Stage 1 (thousands digit): 9 choices (1-9). Stage 2 (hundreds): 9 choices (0-9, excluding the thousands digit). Stage 3 (tens): 8 choices. Stage 4 (units): 7 choices. Total: $9 \times 9 \times 8 \times 7 = 4536$.

Quiz

Q1: What does the concept of Rule of Sum (Addition Principle) primarily refer to in this subject?

A) A computational error related to Rule of Sum (Addition Principle) B) A visual representation of Rule of Sum (Addition Principle) C) The definition and application of Rule of Sum (Addition Principle) D) A historical anecdote about Rule of Sum (Addition Principle)

Correct: C)

• If you chose A: This is incorrect. Rule of Sum (Addition Principle) is defined as: the definition and application of rule of sum (addition principle). The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Rule of Sum (Addition Principle) is defined as: the definition and application of rule of sum (addition principle). The other options describe different aspects that are not the primary focus.
• If you chose C: Rule of Sum (Addition Principle) is defined as: the definition and application of rule of sum (addition principle). The other options describe different aspects that are not the primary focus. Correct!
• If you chose D: This is incorrect. Rule of Sum (Addition Principle) is defined as: the definition and application of rule of sum (addition principle). The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) A simplified version of A \cap B = \emptyset... B) An unrelated formula from a different topic C) The inverse operation of the formula in question D) A \cap B = \emptyset

Correct: D)

• If you chose A: This is incorrect. The formula A \cap B = \emptyset is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula A \cap B = \emptyset is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula A \cap B = \emptyset is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: The formula A \cap B = \emptyset is central to this subject. The other options are either simplified versions or unrelated. Correct!

Q3: What is the primary purpose of Rule of Product (Multiplication Principle)?

A) It is primarily a historical notation system B) It is used only in advanced research contexts C) It is used to rule of product (multiplication principle) in mathematical analysis D) It replaces all other methods in this domain

Correct: C)

• If you chose A: This is incorrect. Rule of Product (Multiplication Principle) serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Rule of Product (Multiplication Principle) serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: Rule of Product (Multiplication Principle) serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose D: This is incorrect. Rule of Product (Multiplication Principle) serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Tree Diagram is TRUE?

A) Tree Diagram is an advanced topic beyond this subject's scope B) Tree Diagram is not related to this subject C) Tree Diagram is a fundamental concept covered in this subject D) Tree Diagram is mentioned only as a historical footnote

Correct: C)

• If you chose A: This is incorrect. Tree Diagram is a fundamental concept covered in this subject. This subject covers Tree Diagram as part of its core content.
• If you chose B: This is incorrect. Tree Diagram is a fundamental concept covered in this subject. This subject covers Tree Diagram as part of its core content.
• If you chose C: Tree Diagram is a fundamental concept covered in this subject. This subject covers Tree Diagram as part of its core content. Correct!
• If you chose D: This is incorrect. Tree Diagram is a fundamental concept covered in this subject. This subject covers Tree Diagram as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) An unrelated numerical value C) 12$ ways. D) A different result from a common mistake

Correct: C)

• If you chose A: This is incorrect. The worked examples show that the result is 12$ ways.. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is 12$ ways.. The other options represent common errors.
• If you chose C: The worked examples show that the result is 12$ ways.. The other options represent common errors. Correct!
• If you chose D: This is incorrect. The worked examples show that the result is 12$ ways.. The other options represent common errors.

Q6: How are Tree Diagram and Bijection Principle related?

A) Tree Diagram and Bijection Principle are closely related concepts B) Tree Diagram is the inverse of Bijection Principle C) Tree Diagram is a special case of Bijection Principle D) Tree Diagram and Bijection Principle are completely unrelated topics

Correct: A)

• If you chose A: Both Tree Diagram and Bijection Principle are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Tree Diagram and Bijection Principle are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Tree Diagram and Bijection Principle are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Tree Diagram and Bijection Principle are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with The Rule Of Sum (Addition Principle)?

A) The Rule Of Sum (Addition Principle) has no common misconceptions B) The main error with The Rule Of Sum (Addition Principle) is using it when it is not needed C) The Rule Of Sum (Addition Principle) is always computed the same way in all contexts D) A common mistake is confusing The Rule Of Sum (Addition Principle) with a similar concept

Correct: D)

• If you chose A: This is incorrect. Students often confuse The Rule Of Sum (Addition Principle) with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse The Rule Of Sum (Addition Principle) with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: This is incorrect. Students often confuse The Rule Of Sum (Addition Principle) with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: Students often confuse The Rule Of Sum (Addition Principle) with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!

Q8: When should you apply The Rule Of Product (Multiplication Principle)?

A) Use The Rule Of Product (Multiplication Principle) only in pure mathematics contexts B) The Rule Of Product (Multiplication Principle) is not practically useful C) Apply The Rule Of Product (Multiplication Principle) to solve problems in this subject's domain D) Avoid The Rule Of Product (Multiplication Principle) unless explicitly instructed

Correct: C)

• If you chose A: This is incorrect. The Rule Of Product (Multiplication Principle) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. The Rule Of Product (Multiplication Principle) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: The Rule Of Product (Multiplication Principle) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. The Rule Of Product (Multiplication Principle) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. A restaurant offers 3 soups, 5 mains, and 4 desserts. How many different 3-course meals (one of each)?
   

   Click for answer

   $3 \times 5 \times 4 = 60$ meals (Rule of Product).

2. How many ways to choose one item from a menu with 8 appetizers, 12 mains, and 6 desserts? (Choose exactly one item total.)
   

   Click for answer

   $8 + 12 + 6 = 26$ ways (Rule of Sum — you pick from appetizer OR main OR dessert).

3. A PIN is 4 digits. First digit cannot be 0. Last digit must be even. How many possible PINs?
   

   Click for answer

   $9 \times 10 \times 10 \times 5 = 4500$. Stage 1: 9 choices (1-9). Stages 2,3: 10 each. Stage 4: 5 choices (0,2,4,6,8).

4. From 15 students, choose a committee of president, treasurer, and secretary (all distinct). How many?
   

   Click for answer

   $15 \times 14 \times 13 = 2730$ — all distinct, order matters.

5. How many 3-letter strings use only vowels (a,e,i,o,u) with repetition allowed? Without repetition?
   

   Click for answer

   With repetition: $5^3 = 125$. Without: $5 \times 4 \times 3 = 60$.

Summary

Key takeaways:

• Addition Principle ($m+n$): count disjoint OR cases
• Multiplication Principle ($m \times n$): count multi-stage AND procedures
• Tree diagrams visualize multi-stage choices
• When choices at later stages depend on earlier ones, adjust the stage counts accordingly
• Always check whether cases are disjoint before adding — overlaps cause double-counting

Pitfalls

• Using addition when multiplication is needed (confusing OR with AND): "Choose a main AND a drink" uses the product rule ($5 \times 7 = 35$); "Choose a main OR a drink" uses the sum rule ($5 + 7 = 12$). A one-word difference changes the operation entirely. Always pause to identify the logical connective: sequential independent stages (AND) → multiply; mutually exclusive alternatives (OR) → add.
• Applying the product rule when later choices depend on earlier ones without adjusting counts: "Choose a president AND a vice-president from 20 people" looks like $20 \times 20$ if you treat the stages as independent — but the same person cannot hold both offices, so the second stage has only 19 choices. The product rule still applies, but the count at each stage must reflect the actual number of remaining options after prior choices. Always ask: "Does this choice reduce the pool for the next stage?"
• Double-counting by not verifying disjointness: "How many ways to pick a card that is a heart OR a face card?" A naive sum $13 + 12 = 25$ double-counts the 3 face cards that are also hearts (J♥, Q♥, K♥). The correct count is $13 + 12 - 3 = 22$. Before adding, always check for overlap. If overlap exists, use Inclusion-Exclusion or partition into truly disjoint cases.
• Forgetting leading-digit restrictions: "How many 3-digit numbers?" is not $10 \times 10 \times 10 = 1000$ — numbers starting with 0 are 2-digit, not 3-digit. The first digit is restricted to 1–9 (9 choices), then 10 choices each for the remaining digits: $9 \times 10 \times 10 = 900$. Always identify implicit constraints (no leading zeros, distinctness requirements, parity conditions) before multiplying.
• Assuming all multi-stage problems are simple product-rule applications: Some problems require breaking into cases with different stage structures. Example: counting 3-letter strings from {A,B,C,D,E} with at least one vowel requires either (a) the complement method (total minus no-vowel), or (b) separate cases by vowel count. The product rule alone is insufficient when "at least one" or "exactly $k$" conditions are involved.

Next Steps

Next up: 26-02-permutations.md — ordered arrangements, factorial notation, and the permutation formula.