[Integrated Math 1 · Core Concepts ⑫-3] Combinations: Foundations of nCr, Algebraic Proofs, Group Partitions, Tournament Brackets & Monotonic Functions

2022 Revised Curriculum · Integrated Math 1 · Core Concepts ⑫-3 [Combinations]

Combinations: Foundations of $_n\mathrm{C}_r$, Algebraic Proofs, Group Partitions, Tournament Brackets & Monotonic Functions

Master the absolute principle of order-free selection: rigorous algebraic proof of $_n\mathrm{C}_r$, collinear geometric counting, equal-size group partition division ($p!$), tournament bracket modeling, and monotonic function bijections.

🌿 Teacher Yulcho's Philosophy: "Combinations are the art of purging order. Decoupling selection from arrangement is the hallmark of mathematical maturity."
While permutations ($_n\mathrm{P}_r$) select and arrange items in a sequence, combinations ($_n\mathrm{C}_r$) disregard order entirely to focus solely on the chosen subset.

High-tier students struggle with challenging counting problems not because formulas are difficult, but because they attempt to select and line up elements simultaneously. Executing a "Two-Stage Decoupling Protocol: First choose subsets via $_n\mathrm{C}_r$, then allocate or permute them according to given constraints" turns complex tournament trees and digit-inequality problems into straightforward calculations!

1. Definition of Combinations & Algebraic Proof: Connecting $_n\mathrm{P}_r$ and $_n\mathrm{C}_r$

📐 Operational Definition & Algebraic Derivation
① Definition & Permutation Connection:
Selecting $r$ distinct elements from $n$ distinct elements without regard to order is called a combination, denoted by $_n\mathrm{C}_r$ ($0 \le r \le n$).
The number of ways to choose $r$ items is $_n\mathrm{C}_r$. Arranging those chosen $r$ items linearly gives $r!$ ways. By the multiplication principle, this two-step process equals the permutation $_n\mathrm{P}_r$:
$$_n\mathrm{C}_r \times r! = _n\mathrm{P}_r \quad \implies \quad \mathbf{_n\mathrm{C}_r = \dfrac{_n\mathrm{P}_r}{r!} = \dfrac{n!}{r!(n - r)!}}$$ Example: $_7\mathrm{C}_3 = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$
② Standard Boundary Values:
$$_n\mathrm{C}_0 = 1, \quad _n\mathrm{C}_n = 1, \quad _n\mathrm{C}_1 = n \quad \text{(Consistent with $_n\mathrm{P}_0 = 1$ and $0! = 1$)}$$
③ Two Fundamental Combinatorial Identities:
• Complementary Symmetry: $_n\mathrm{C}_r = _n\mathrm{C}_{n - r} \quad (0 \le r \le n)$
Choosing $r$ elements to take is equivalent to choosing the $(n - r)$ elements to leave behind. (e.g., $_{10}\mathrm{C}_8 = _{10}\mathrm{C}_2 = 45$)
• Pascal's Recurrence (Element Partitioning):
$$_n\mathrm{C}_r = _{n - 1}\mathrm{C}_r + _{n - 1}\mathrm{C}_{r - 1} \quad (1 \le r < n)$$ Partitions into cases where a specific element is excluded ($_{n-1}\mathrm{C}_r$) versus included ($_{n-1}\mathrm{C}_{r-1}$).

2. Conditional Selections: Inclusion, Exclusion & "At Least" Complements

1. Mandatory Inclusion of Specific $k$ Items
• Pre-assign the $k$ items into the selection basket.
• Select the remaining $(r - k)$ seats from the $(n - k)$ candidates.
$$\implies \mathbf{_{n - k}\mathrm{C}_{r - k}}$$
2. Absolute Exclusion of Specific $k$ Items
• Strike the $k$ forbidden items off the candidate roster completely.
• Select all $r$ seats from the remaining $(n - k)$ candidates.
$$\implies \mathbf{_{n - k}\mathrm{C}_r}$$
3. "At Least" Conditions via Complements
• Subtract the opposite event where the condition never occurs.
$$\text{Valid Selections} = (\text{Total } _n\mathrm{C}_r) - (\text{Complement})$$
4. Invariant Ordering ($a < b < c$)
• Selecting $r$ numbers to satisfy strict inequality requires only $_n\mathrm{C}_r$.
• Relative order is determined automatically without permutation.

3. Set Partitions, Named Distribution & Tournament Brackets

👥 The Principles of Partitioning & Bracket Construction
① Partitioning $n$ distinct objects into 3 groups of sizes $p, q, r$ ($p + q + r = n$):
• When $p, q, r$ are all distinct:
$$_n\mathrm{C}_p \times _{n - p}\mathrm{C}_q \times _r\mathrm{C}_r$$ • When two sizes are equal: (Nameless bundles of equal size are indistinguishable; divide by $2!$)
$$_n\mathrm{C}_p \times _{n - p}\mathrm{C}_q \times _r\mathrm{C}_r \times \mathbf{\dfrac{1}{2!}}$$ • When all three sizes are equal:
$$_n\mathrm{C}_p \times _{n - p}\mathrm{C}_q \times _r\mathrm{C}_r \times \mathbf{\dfrac{1}{3!}}$$ 💡 Reason: Splitting 4 people $\{A, B, C, D\}$ into $(AB, CD)$ vs $(CD, AB)$ produces identical nameless groupings. Dividing by $2!$ removes this duplication.
② Distribution: Distributing $n$ partitioned bundles to $n$ distinct recipients:
$$(\text{Number of Partition Groupings}) \times \mathbf{n!}$$
③ Tournament Bracket Construction (Top-Down Bisection Protocol):
• (i) Bisect the bracket into two macro-groups from the championship finals.
• (ii) Sub-partition each branch into smaller matches recursively down to pairs.
• (iii) Multiply the partition counts across all hierarchical levels.
Example: 6 teams split into (4 teams, 2 teams), with 4 teams subdivided into (2, 2): $(_6\mathrm{C}_4 \times _2\mathrm{C}_2) \times (_4\mathrm{C}_2 \times _2\mathrm{C}_2 \times \frac{1}{2!}) = 15 \times 3 = 45$ ways.

4. Geometric Counting: Straight Lines, Triangles & Parallelograms

When counting figures from discrete planar points, lines containing 3 or more collinear points require distinct handling.

📐 3 Essential Geometric Counting Formulas
• Distinct Straight Lines:
Subtract redundant pairs ($_k\mathrm{C}_2$) along collinear lines from $_n\mathrm{C}_2$, then add $+1$ back to preserve the unique underlying line itself.
$$\text{Lines} = _n\mathrm{C}_2 - \sum (_k\mathrm{C}_2) + (\text{Number of Collinear Lines})$$

• Distinct Triangles:
Subtract triples chosen entirely along collinear lines ($_k\mathrm{C}_3$) from $_n\mathrm{C}_3$. (Triangles cannot form on a straight line; do NOT add $+1$ back!)
$$\text{Triangles} = _n\mathrm{C}_3 - \sum (_k\mathrm{C}_3)$$

• Parallelograms from Intersecting Grids:
Choose 2 horizontal lines from $m$, and 2 vertical lines from $n$ $\implies \mathbf{_m\mathrm{C}_2 \times _n\mathrm{C}_2}$.

5. Benchmark Drills: 5 Advanced Scenarios & Yulcho's Tips

[Benchmark Drill 01] Digit Inequalities Involving Zero Digit Ordering
From $\{0, 1, 2, 3, 4, 5\}$, choose 3 distinct digits to form 3-digit integers with hundreds digit $a$, tens digit $b$, and units digit $c$. Let $m$ be the count satisfying $a < b < c$, and $n$ be the count satisfying $a > b > c$. Find $m + n$.
🌿 Teacher Yulcho's Strategy & Intuitive Logic:
• $a < b < c$: $a$ is the smallest, so choosing $0$ forces $a=0$, breaking the 3-digit condition. Exclude $0$ entirely ($_5\mathrm{C}_3$).
• $a > b > c$: $c$ is the smallest, so choosing $0$ safely places it in the units place without violating the hundreds digit ($_6\mathrm{C}_3$).
View In-Depth Solution & Answer (Click)
• $a < b < c$: Choose 3 from $\{1, 2, 3, 4, 5\} \implies m = _5\mathrm{C}_3 = 10$
• $a > b > c$: Choose 3 from $\{0, 1, 2, 3, 4, 5\} \implies n = _6\mathrm{C}_3 = 20$
$m + n = 10 + 20 = 30$
Answer: 30
[Benchmark Drill 02] "At Least One Officer" Committee Selection Complement Rule
From 8 students including a president and a vice president, a 5-member festival committee is selected. Find the number of ways where at least one of the two officers is included.
🌿 Teacher Yulcho's Strategy & Intuitive Logic:
The complement of "at least one officer included" is both officers excluded. Subtract selecting 5 members entirely from the remaining 6 students ($_6\mathrm{C}_5$) from total selections ($_8\mathrm{C}_5$).
View In-Depth Solution & Answer (Click)
Total selections: $_8\mathrm{C}_5 = _8\mathrm{C}_3 = 56$
Complement (no officers): $_6\mathrm{C}_5 = 6$
Valid committee selections $= 56 - 6 = 50$
Answer: 50
[Benchmark Drill 03] Tournament Bracket Construction via Bisection Brackets
Six teams compete in a tournament bracket structured into a left group of 4 teams (2 vs 2) and a right group of 2 teams (1 match). Find the number of valid bracket configurations.
🌿 Teacher Yulcho's Strategy & Intuitive Logic:
Bisect 6 teams into (4, 2) first ($_6\mathrm{C}_4$). Then sub-partition the 4 teams into two equal groups of 2 with $\frac{1}{2!}$.
View In-Depth Solution & Answer (Click)
1. Split into (4, 2): $_6\mathrm{C}_4 \times _2\mathrm{C}_2 = 15$
2. Sub-partition 4 teams into (2, 2): $_4\mathrm{C}_2 \times _2\mathrm{C}_2 \times \dfrac{1}{2!} = 3$
Total $= 15 \times 3 = 45$
Answer: 45
[Benchmark Drill 04] Triangles on a Semicircle Geometric Triangles
Four distinct points lie on the arc of a semicircle, and three distinct points lie on its diameter. Find the number of triangles formed by selecting 3 of these 7 points.
🌿 Teacher Yulcho's Strategy & Intuitive Logic:
Triangles fail to form if and only if all 3 points are chosen along the straight diameter ($_3\mathrm{C}_3 = 1$). Subtract this from total selections ($_7\mathrm{C}_3$).
View In-Depth Solution & Answer (Click)
Total point triples: $_7\mathrm{C}_3 = 35$
Collinear triples on diameter: $_3\mathrm{C}_3 = 1$
Triangles $= 35 - 1 = 34$
Answer: 34
[Benchmark Drill 05] Strictly Increasing Functions with Pivot Target Constraints Function Maps
For sets $X = \{1, 2, 3, 4, 5\}$ and $Y = \{1, 2, 3, 4, 5, 6, 7\}$, find the number of functions $f: X \to Y$ satisfying $x_1 < x_2 \implies f(x_1) < f(x_2)$ and $f(3) = 4$.
🌿 Teacher Yulcho's Strategy & Intuitive Logic:
Partition around $f(3)=4$. $\{f(1), f(2)\}$ must choose 2 targets from $\{1, 2, 3\}$ ($_3\mathrm{C}_2$), and $\{f(4), f(5)\}$ must choose 2 targets from $\{5, 6, 7\}$ ($_3\mathrm{C}_2$).
View In-Depth Solution & Answer (Click)
• Choose targets for $\{1, 2\}$ from $\{1, 2, 3\}$: $_3\mathrm{C}_2 = 3$
• Choose targets for $\{4, 5\}$ from $\{5, 6, 7\}$: $_3\mathrm{C}_2 = 3$
Total $= 3 \times 3 = 9$
Answer: 9
⚠️ Critical Exam Warnings: 3 Frequent Pitfalls in Combination Problems
1. Forgetting to restore $+1$ when counting straight lines!
• Subtracting $_4\mathrm{C}_2 = 6$ removes every pair from a collinear set, but completely erases the true underlying straight line itself.
👉 Remedy: Always add $+1$ back per collinear line, but do NOT add back for triangles!
2. Dropping $p!$ division in equal-size nameless partitions!
• Splitting 6 into bundles of $(2, 2, 2)$ without dividing by $3!$ duplicates group ordering.
👉 Remedy: Whenever $p$ bundles share identical sizes, multiply by $\times \dfrac{1}{p!}$.
3. Overlooking zero in ascending vs. descending digit problems!
• For $a < b < c$, $0$ cannot be selected because $a \ne 0$. For $a > b > c$, $0$ is safe because it falls into the units place $c=0$.
👉 Remedy: Check whether zero is assigned to the leading place-value slot.

Frequently Asked Questions (FAQ)

Q1. Why do we divide by $r!$ in the combination formula $_n\mathrm{C}_r$?
In permutations ($_n\mathrm{P}_r$), each chosen subset generates $r!$ different orderings. Because combinations disregard order, dividing by $r!$ collapses those $r!$ permutations into a single distinct subset.
Q2. How do you distinguish between Partitioning and Distributing?
"Splitting into 3 equal bundles" is a nameless partition ($\times \frac{1}{3!}$). Once those 3 bundles are assigned to named people (or rooms A, B, C), multiply by $3!$ for distribution.
Q3. Why does strict inequality ($x_1 < x_2 \implies f(x_1) < f(x_2)$) imply combinations?
Because the relative ordering is predetermined by the inequality. Once targets are selected from the codomain, the smallest automatically pairs with the smallest domain element, leaving exactly 1 valid assignment.
🌿 Teacher Yulcho's Coaching Insight
"The line separating permutations from combinations is not memory, but discerning whether relative order exists. When order is invariant or constrained, use combinations ($_n\mathrm{C}_r$), and divide by factorials for indistinguishable partitions. Mastering this algebraic discipline guarantees complete confidence across higher probability and statistics."
Integrated Math 1 Core Concepts ⑫-3 Combinations complete.
Coming up next: [Integrated Math 1 · Practice Lab ⑫-3] Combinations: 15 Benchmark Killers & CSAT Advanced Lab!

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)