[Algebra · Core Concepts ⑦] The Foundations of Counting Principles: Addition vs. Multiplication, Divisor Sums & Multiples, Payment Methods vs. Total Values & Network Paths

 

Secondary Algebra · Core Concepts ⑦ [Foundations of Combinatorics]

The Foundations of Counting Principles: Addition vs. Multiplication & 5 Essential Core Frameworks

Expansion Terms, Divisor Counts & Sums, Currency Exchange Reductions, Network Routing & Constrained Mappings

🎯 3 Golden Action Protocols for Fundamental Counting
  • Decide Addition ($+$) vs. Multiplication ($\times$) by Stage Completion: If Event $A$ completely terminates the trial with no shared outcomes, apply the Addition Principle ($A + B$). If Event $A$ leaves the trial incomplete, requiring Event $B$ to follow sequentially, apply the Multiplication Principle ($A \times B$).
  • For Distinct Payable Amounts, Check if Smaller Denominations Cover Larger Ones: If the total sum of a smaller denomination can equal or exceed the value of a single larger denomination, decompose (exchange) the larger bills into the smaller unit to prevent duplicate counting.
  • Prioritize Constrained Slots in Network Routes and Mappings: Always anchor the most restrictive requirements first—such as mandatory waypoints, closed roads, or specific function values—before multiplying the unconstrained choices.

1. Addition Principle vs. Multiplication Principle: Tree Diagram Branching

Do not rely merely on semantic keywords like "or" versus "and." Instead, examine the trial's state: Has the overall selection concluded, or is it an ongoing sequence of interdependent stages?

Start Bus (3 routes) Train (2 routes) Addition: 3 + 2 = 5 (Mutually Exclusive · Direct Completion) Outfit Shirt A Shirt B 3 Pants 3 Pants Multiplication: 2 × 3 = 6 (Sequential Stages · Uniform Branching)
[Figure 1] Addition Principle (Mutually Exclusive) vs. Multiplication Principle (Sequential Branching)

2. [Type 1] Distinct Terms in Polynomial Expansions

✏️ [Standard Example 1] Algebraic Term Expansion without Like Terms
Find the total number of distinct terms obtained upon expanding $(a + b + c)(x + y + z) + (p + q)(x + y)$.
💡 Yul's Pro-Tip: The first product contains variables $\{a, b, c\}$ while the second contains $\{p, q\}$. Since no like terms can possibly arise between the two groups, compute each product's term count by multiplication and sum them by addition.
View Solution & Answer (Click to Expand)
1. Terms from $(a + b + c)(x + y + z)$: $3 \times 3 = 9$.
2. Terms from $(p + q)(x + y)$: $2 \times 2 = 4$.
3. Since all terms are mutually distinct: $9 + 4 = 13$.
Answer: $13$
📝 [Diagnostic Check 1]

Find the number of distinct terms when expanding $(a + b)(p + q + r)(x + y)$.

Check Diagnostic Answer
$2 \times 3 \times 2 = 12$ distinct terms.
Answer: $12$

3. [Type 2] Number of Divisors, Multiple Restrictions & Divisor Sums

✏️ [Standard Example 2] Complete Divisor Analysis of 720
For the integer $720 = 2^4 \times 3^2 \times 5^1$, compute:
(1) The total number of positive divisors
(2) The number of even divisors (multiples of 2)
(3) The number of divisors that are multiples of 3
(4) The number of divisors that are multiples of 6
(5) The sum of all positive divisors
💡 Yul's Pro-Tip: To find multiples of $k$, exclude the exponent $0$ for the required prime factors. For a multiple of 6, both the exponent of 2 and 3 must be at least 1.
View Solution & Answer (Click to Expand)
(1) Total Divisors: $(4 + 1)(2 + 1)(1 + 1) = 5 \times 3 \times 2 = 30$.
(2) Even Divisors (Exponent of 2 is in $\{1, 2, 3, 4\}$): $4 \times 3 \times 2 = 24$.
(3) Multiples of 3 (Exponent of 3 is in $\{1, 2\}$): $5 \times 2 \times 2 = 20$.
(4) Multiples of 6 (Exponents: 2 in $\{1, 2, 3, 4\}$, 3 in $\{1, 2\}$): $4 \times 2 \times 2 = 16$.
(5) Divisor Sum: $(1 + 2 + 4 + 8 + 16)(1 + 3 + 9)(1 + 5) = 31 \times 13 \times 6 = 2418$.
Answer: (1) 30 / (2) 24 / (3) 20 / (4) 16 / (5) 2418
📝 [Diagnostic Check 2]

For $540 = 2^2 \times 3^3 \times 5^1$, find the number of odd divisors and the number of multiples of 6.

Check Diagnostic Answer
Odd divisors ($2^0$ only): $(3 + 1)(1 + 1) = 8$.
Multiples of 6: $2 \times 3 \times 2 = 12$.
Answer: 8 odd divisors, 12 multiples of 6

4. [Type 3] Payment Methods vs. Payable Amounts (Currency Reductions)

✏️ [Standard Example 3] Payment Combinations with Partial Currency Overlap
Suppose you have one $10 bill, three $5 bills, and four $1 bills. Excluding a payment of $0, determine:
(1) The number of different payment methods
(2) The number of distinct payable amounts
💡 Yul's Pro-Tip: Four $1 bills cannot form $5 ($4 < $5), so $1 bills stay unchanged. However, three $5 bills ($15) exceed one $10 bill, creating overlap. Convert the single $10 bill into two $5 bills, giving five $5 bills and four $1 bills.
View Solution & Answer (Click to Expand)
(1) Payment Methods: $(1 + 1)(3 + 1)(4 + 1) - 1 = 2 \times 4 \times 5 - 1 = 39$.

(2) Payable Amounts:
Exchange the $10 bill into two $5 bills $\implies$ five $5 bills and four $1 bills.
Payable amounts $= (5 + 1)(4 + 1) - 1 = 6 \times 5 - 1 = 29$.
Answer: (1) 39 / (2) 29
📝 [Diagnostic Check 3]

With two $5 bills and three $1 bills, find the number of payment methods $a$ and payable amounts $b$.

Check Diagnostic Answer
Three $1 bills cannot form $5. No overlap exists.
$a = (2 + 1)(3 + 1) - 1 = 11$. $b = a = 11$.
Answer: a = 11, b = 11

5. [Type 4] Network Routing: Waypoints, Round-Trips & Non-Crossing Paths

✏️ [Standard Example 4] Round-Trip without Reusing Paths
Between towns $A$ and $D$, there are 3 paths from $A$ to $B$, 2 paths from $A$ to $C$, 2 paths from $B$ to $D$, and 3 paths from $C$ to $D$ (no road connects $B$ and $C$).
(1) Find the number of paths from $A$ to $D$.
(2) For a round trip from $A$ to $D$ and back to $A$, find the number of routes such that no road used on the forward journey is reused on the return trip.
💡 Yul's Pro-Tip: Split the round trip into two cases: Case 1 where different intermediate towns are visited ($B$ going, $C$ returning), and Case 2 where the same intermediate town is visited (reducing available path choices by 1).
View Solution & Answer (Click to Expand)
(1) $A \to D$: $(3 \times 2) + (2 \times 3) = 6 + 6 = 12$.

(2) Round trip without path reuse:
- Different intermediate towns: $A \to B \to D \to C \to A$: $3 \times 2 \times 3 \times 2 = 36$.
$A \to C \to D \to B \to A$: $2 \times 3 \times 2 \times 3 = 36$.
- Same intermediate towns: $A \to B \to D \to B \to A$: $3 \times 2 \times (2 - 1) \times (3 - 1) = 12$.
$A \to C \to D \to C \to A$: $2 \times 3 \times (3 - 1) \times (2 - 1) = 12$.
Total $= 36 + 36 + 12 + 12 = 96$.
Answer: (1) 12 / (2) 96
📝 [Diagnostic Check 4]

From $A$ to $B$ there are 2 paths, $B$ to $C$ has 4 paths, and a direct express road connects $A$ to $C$. Find all possible paths from $A$ to $C$.

Check Diagnostic Answer
Via $B$: $2 \times 4 = 8$. Direct: 1. Total $= 8 + 1 = 9$.
Answer: $9$

6. [Type 5] Counting Functions under Range & Inequality Constraints

✏️ [Standard Example 5] Constrained Function Mapping
Let $X = \{1, 2, 3, 4\}$ and $Y = \{1, 2, 3, 4, 5, 6\}$. Find the number of functions $f: X \to Y$ satisfying:
(1) $f(1) = 3$
(2) $f(1) \ge 4$ and $f$ is an injective (one-to-one) function
💡 Yul's Pro-Tip: Secure the constrained input $f(1)$ first. For an injective function, reduce available choices sequentially for the remaining inputs.
View Solution & Answer (Click to Expand)
(1) $f(1) = 3$ is fixed. Inputs $2, 3, 4$ have 6 choices each $\implies 1 \times 6^3 = 216$.

(2) $f(1) \in \{4, 5, 6\}$ (3 choices). For an injective function:
$f(2)$ has 5 choices, $f(3)$ has 4 choices, $f(4)$ has 3 choices.
Count $= 3 \times (5 \times 4 \times 3) = 3 \times 60 = 180$.
Answer: (1) 216 / (2) 180
📝 [Diagnostic Check 5]

For $X = \{1, 2, 3\}$ and $Y = \{1, 2, 3, 4, 5\}$, find the number of injective functions such that $f(2) = 4$.

Check Diagnostic Answer
$f(2)$ is fixed. $f(1)$ has 4 remaining choices, $f(3)$ has 3 choices.
$1 \times 4 \times 3 = 12$.
Answer: $12$
🌿 Yul's Masterclass Perspective
"True combinatoric mastery lies not in memorizing formulas, but in dissecting trials into mutually exclusive and exhaustive sub-cases."

When you identify stage boundaries, handle currency reductions cleanly, and isolate constraints before counting unconstrained variables, challenging questions become direct and manageable.

Comments

Popular posts from this blog

Authentic Reference Models Beyond Basic Rulers

[Math Column]Studying Alongside Dedicated Peers: Becoming Each Other’s Lifelong Catalyst

[High School Math] Coordinate Geometry: 15 Essential Practice Problems on Section Formulas (Internal & External Division)