[Algebra · Core Concepts ⑨] The Essence of Combinations: Erasing Order (÷r!), Symmetry, Pascal's Identity, Partitioning (÷p!) & Function Counting Types

 

Algebra · Core Concepts ⑨ [Combinatorics Finale]

The Essence of Combinations: Erasing Order ($\div r!$), Symmetry, Partitioning & Function Counting

Permutation vs. Combination, Symmetry (${}_n\text{C}_r = {}_n\text{C}_{n-r}$), Pascal's Identity, Equal-Size Partitions ($\div p!$) & 5 Function Types

🎯 4 Golden Action Protocols for Combinations
  • A Combination is Simply a Permutation Stripped of Order ($\mathbf{\div r!}$): Permutation selects and arranges ($n\text{P}r = {}_n\text{C}_r \times r!$). Combination neutralizes arrangement order by dividing by $r!$ ($\mathbf{{}_n\text{C}_r = \dfrac{n\text{P}r}{r!}}$). Use combinations whenever committee selection, subset formation, or order-invariant tasks arise.
  • Reflectively Apply Symmetry ($\mathbf{{}_n\text{C}_r = {}_n\text{C}_{n-r}}$) to Halve Computations: Choosing 8 delegates out of 10 is mathematically identical to choosing the 2 to leave behind (${}_{10}\text{C}_8 = {}_{10}\text{C}_2 = 45$). Whenever $r > \dfrac{n}{2}$, flip directly to its complementary subset.
  • Eliminate Duplicate Order in Group Partitioning by Dividing by $\mathbf{p!}$ for Identical Group Sizes: When partitioning 6 items into three unlabelled groups of 2, 2, and 2, dividing by $\mathbf{3!}$ is non-negotiable. Without labels, permutations between equally sized bundles create artificial duplicates.
  • Enforced Order Equals Combination: When an inequality ordering is imposed on function values ($x_1 < x_2 \implies f(x_1) < f(x_2)$), your freedom to arrange is removed. Selecting the subset automatically assigns values from lowest to highest.

1. Permutation vs. Combination: Why Divide by $r!$? (Erasing Order)

Selecting $r$ items from $n$ distinct elements without regard to order is called a Combination, denoted by $\mathbf{{}_n\text{C}_r}$ or $\mathbf{\binom{n}{r}}$.

[Core Invariant 1] The Bridge Between Permutations and Combinations

Constructing a permutation $n\text{P}r$ decomposes into two distinct phases:
• Stage 1 (Selection): Choose an unordered subset of $r$ elements $\implies \mathbf{{}_n\text{C}_r}$
• Stage 2 (Arrangement): Line up those $r$ chosen elements $\implies \mathbf{r!}$
Since $n\text{P}r = {}_n\text{C}_r \times r!$, solving for the combination yields:
$$\mathbf{{}_n\text{C}_r = \dfrac{n\text{P}r}{r!} = \dfrac{n!}{r!(n - r)!}}$$

Domain Permutation ($n\text{P}r$) Combination (${}_n\text{C}_r$) Practical Criterion
Order Order matters Order does not matter If swapping roles changes the outcome $\to$ Permutation
Model Electing President & VP Electing 2 Committee Co-Chairs Hierarchical titles vs. equal-standing roles
Algebraic Set $(A, B) \neq (B, A)$ $\{A, B\} = \{B, A\}$ Set element selection is invariant under permutations

2. The 3 Invariant Identities of Combinations & Pascal's Identity

Beyond algebraic computation, combination formulas encapsulate elegant combinatorial arguments based on duality and binary partitioning.

[Core Invariant 2] Essential Combinatorial Identities

• 1. Boundary Conditions:
$${}_n\text{C}_0 = 1, \quad {}_n\text{C}_n = 1, \quad {}_n\text{C}_1 = n$$
• 2. Complementary Symmetry:
$$\mathbf{{}_n\text{C}_r = {}_n\text{C}_{n - r}}$$ Choosing $r$ objects to include is equivalent to choosing $n - r$ objects to exclude.

• 3. Pascal's Partition Identity:
$$\mathbf{{}_n\text{C}_r = {}_{n - 1}\text{C}_{r - 1} + {}_{n - 1}\text{C}_r}$$ Condition on a specific element $A$ among the $n$ items:
- Element $A$ is chosen: Pick remaining $r - 1$ items from $n - 1 \implies {}_{n-1}\text{C}_{r-1}$
- Element $A$ is rejected: Pick all $r$ items from remaining $n - 1 \implies {}_{n-1}\text{C}_r$

✏️ [Standard Example 1] Specific Element Restraints and "At Least One" Conditions
From a group of 6 boys and 4 girls, a 4-person committee is to be formed. Determine the number of ways to select the committee if (1) a specific boy $A$ must be included while a specific girl $B$ is excluded, and (2) at least one girl must be included.
💡 Yul's Pro-Tip:
- (1) Seat boy $A$ in advance and remove girl $B$ from eligibility. Choose the remaining $4 - 1 = 3$ spots from the remaining $10 - 2 = 8$ candidates: ${}_8\text{C}_3 = 56$.
- (2) "At least one" is best handled via complementary counting: $\text{Total Committees} - \text{All-Boy Committees} = {}_{10}\text{C}_4 - {}_6\text{C}_4$.
View Solution & Answer (Click to Expand)
1. Evaluating Condition (1):
Exclude $A$ and $B$, leaving 8 available candidates. Pick 3: ${}_8\text{C}_3 = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$.

2. Evaluating Condition (2):
- Total 4-person combinations: ${}_{10}\text{C}_4 = 210$.
- Committees with only boys: ${}_6\text{C}_4 = {}_6\text{C}_2 = 15$.
- Complementary count: $210 - 15 = 195$.
Answer: (1) 56 / (2) 195

3. Set Partitions & Distribution: Why Divide Equal-Sized Groups by $p!$?

A common exam trap is confusing an unlabelled set partition (grouping items into anonymous piles) with a labelled distribution (assigning piles to named recipients or locations).

[Core Invariant 3] Partition vs. Distribution Protocol

• Phase 1: Partitioning into Unlabelled Bundles
Splitting $n$ distinct objects into group sizes of $p, q, r$ ($p + q + r = n$):
- All sizes distinct: ${}_n\text{C}_p \times {}_{n-p}\text{C}_q \times {}_r\text{C}_r$
- Exactly two groups have identical sizes ($p = q \neq r$): multiply by $\mathbf{\dfrac{1}{2!}}$
- All three groups have identical sizes ($p = q = r$): multiply by $\mathbf{\dfrac{1}{3!}}$
*(Crucial: In unlabelled groups, the selection order generates $p!$ redundant copies of the exact same partition)*

• Phase 2: Distribution to Named Entities
Distributing $k$ unlabelled bundles among $k$ distinct recipients multiplies the result by $\mathbf{k!}$:
$$\text{Distribution Count} = (\text{Partition Count}) \times k!$$

✏️ [Standard Example 2] Partitioning 6 Students into Triads & Hotel Rooms
In how many ways can 6 distinct students be (1) partitioned into three anonymous groups of 2, and (2) assigned to three distinct hotel suites $A, B$, and $C$?
💡 Yul's Pro-Tip: The three group sizes are identical ($2, 2, 2$). The raw product ${}_6\text{C}_2 \times {}_4\text{C}_2 \times {}_2\text{C}_2$ orders the groups as "First, Second, Third," which overcounts by a factor of $3!$. Dividing by $\mathbf{3!}$ corrects this. Part (2) simply assigns the 3 bundles to rooms $A, B, C$, restoring the factor of $\mathbf{\times 3!}$.
View Solution & Answer (Click to Expand)
1. Anonymous Partitioning into $(2, 2, 2)$:
${}_6\text{C}_2 \times {}_4\text{C}_2 \times {}_2\text{C}_2 \times \dfrac{1}{3!} = 15 \times 6 \times 1 \times \dfrac{1}{6} = 15$.

2. Distribution to Distinct Rooms $A, B, C$:
$15 \times 3! = 15 \times 6 = 90$.
Answer: (1) 15 / (2) 90

4. Geometric Configurations: Lines, Triangles & Parallelograms

Geometric determinations provide direct applications of combinations. Managing collinearity overcounts is the core operational skill.

[Core Invariant 4] Standard Geometric Counting Formulas

• 1. Distinct Lines: Select any 2 points $\implies \mathbf{{}_n\text{C}_2}$.
*(If $k$ points lie on a common line: subtract ${}_k\text{C}_2$ and add back $\mathbf{+1}$ for the single shared line!)*

• 2. Distinct Triangles: Select any 3 non-collinear points $\implies \mathbf{{}_n\text{C}_3}$.
*(If $k$ points are collinear: subtract ${}_k\text{C}_3$ entirely; 3 collinear points cannot form a triangle)*

• 3. Parallelograms in a Grid: Formed by intersecting $m$ horizontal and $n$ vertical parallel lines:
$$\mathbf{{}_m\text{C}_2 \times {}_n\text{C}_2}$$

✏️ [Standard Example 3] Lines and Triangles on a Semicircle
Seven points are positioned such that 3 lie along the arc of a semicircle and 4 lie along the diameter (including the endpoints). Find (1) the number of distinct lines, and (2) the number of triangles that can be formed by these points.
💡 Yul's Pro-Tip: The 4 collinear points on the diameter dictate the solution:
- Lines: Calculate ${}_7\text{C}_2$, subtract the overcounting ${}_4\text{C}_2$, and add back $+1$ for the diameter itself.
- Triangles: Calculate ${}_7\text{C}_3$ and subtract ${}_4\text{C}_3$ (do not add back anything; collinear points yield 0 triangles).
View Solution & Answer (Click to Expand)
1. Number of Distinct Lines:
${}_7\text{C}_2 - {}_4\text{C}_2 + 1 = 21 - 6 + 1 = 16$.

2. Number of Triangles:
${}_7\text{C}_3 - {}_4\text{C}_3 = 35 - 4 = 31$.
Answer: (1) 16 / (2) 31

5. Counting Functions Under Constraints: Powers, Permutations & Combinations

Given sets $X = \{x_1, \dots, x_k\}$ and $Y = \{y_1, \dots, y_n\}$ ($k \le n$), the algebraic constraint placed on the mapping determines whether powers, permutations, or combinations are required.

Function Category Constraint Expression Formula Yul's Operational Insight
Unconstrained No restrictions $n^k$ Each of the $k$ inputs independently selects from $n$ targets
Injective (One-to-One) $x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$ ${}_n\text{P}_k$ Select $k$ outputs and assign them in linear order
Strictly Increasing $x_1 < x_2 \implies f(x_1) < f(x_2)$ ${}_n\text{C}_k$ Order is locked! Choosing $k$ elements fixes the assignments automatically
Increasing with Anchor $x_1 < x_2 \implies f(x_1) < f(x_2)$ with $f(a) = b$ ${}_{b-1}\text{C}_{a-1} \times {}_{n-b}\text{C}_{k-a}$ Anchor $(a, b)$ splits domain and codomain into two independent subproblems
Surjective (Onto) $\text{Range} = Y$ (All codomain hits) $S(k, n) \times n!$ Partition $k$ inputs into $n$ subsets, then distribute across $n$ outputs
✏️ [Standard Example 4] Counting Anchored Increasing Functions
For sets $X = \{1, 2, 3, 4, 5\}$ and $Y = \{1, 2, 3, 4, 5, 6, 7, 8\}$, find the number of functions $f : X \to Y$ satisfying:
(a) $x_1 < x_2 \implies f(x_1) < f(x_2)$
(b) $f(3) = 5$
💡 Yul's Pro-Tip: The condition $f(3) = 5$ acts as an immovable boundary! Inputs $\{1, 2\}$ must land in $\{1, 2, 3, 4\}$ (${}_4\text{C}_2$), while inputs $\{4, 5\}$ must land in $\{6, 7, 8\}$ (${}_3\text{C}_2$). By the multiplication rule: $6 \times 3 = 18$.
View Solution & Answer (Click to Expand)
1. Outputs for $\{1, 2\}$: Must satisfy $f(1) < f(2) < 5$. Choose 2 from $\{1, 2, 3, 4\} \implies {}_4\text{C}_2 = 6$.
2. Outputs for $\{4, 5\}$: Must satisfy $5 < f(4) < f(5)$. Choose 2 from $\{6, 7, 8\} \implies {}_3\text{C}_2 = 3$.
3. Total Valid Functions: $6 \times 3 = 18$.
Answer: 18

6. ⚠️ Three Traps That Cost 10 Points on Algebra Exams

🚨 [Trap 1] Forgetting to Divide by $p!$ in Equal-Sized Anonymous Partitions
• Common Pitfall: Dividing 8 students into two equal groups of 4 and writing ${}_8\text{C}_4 \times {}_4\text{C}_4 = 70$.
• Fact Check: Since the groups are unlabelled, $\{A, B, C, D\}$ and $\{E, F, G, H\}$ can swap without changing the partition. Divide by $2!$ to get $\dfrac{70}{2} = \mathbf{35}$.
🚨 [Trap 2] Failing to Restore $+1$ for Collinear Line Determinations
• Common Pitfall: Computing ${}_n\text{C}_2 - {}_4\text{C}_2$ when 4 points lie along a line, eliminating the line entirely.
• Fact Check: Those 4 points form a single shared line, not zero lines. Always append $\mathbf{+1}$ to restore the line itself.
🚨 [Trap 3] Using Permutations for Invariant Ordered Conditions
• Common Pitfall: Applying $n\text{P}r$ to count strictly increasing functions ($x_1 < x_2 \implies f(x_1) < f(x_2)$).
• Fact Check: Once values are selected, sorting is deterministic. You have zero arrangement freedom. Enforced order always requires combinations (${}_n\text{C}_r$).
🌿 Yul's Masterclass Perspective
"Combinatorics is mastered not through rote calculation, but by recognizing how dividing by $r!$ erases order and how structural symmetry clarifies complex problems."

You have established complete command over selection without replacement, complementary symmetry, equal-group partition corrections, and geometric configuration counting.

Next, put these principles to work against 15 competition-level problems in [Algebra · Practice Lab ⑨] 15 Ultra-Challenging Combinations Killers & 1:1 Diagnostic Twins.

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)