[Algebra · Core Concepts ⑨] The Essence of Combinations: Erasing Order (÷r!), Symmetry, Pascal's Identity, Partitioning (÷p!) & Function Counting Types
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
- 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}}$.
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.
• 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$
- (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)
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).
• 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!$$
View Solution & Answer (Click to Expand)
${}_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.
• 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}$$
- 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)
${}_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 |
(a) $x_1 < x_2 \implies f(x_1) < f(x_2)$
(b) $f(3) = 5$
View Solution & Answer (Click to Expand)
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
• 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}$.
• Fact Check: Those 4 points form a single shared line, not zero lines. Always append $\mathbf{+1}$ to restore the line itself.
• Fact Check: Once values are selected, sorting is deterministic. You have zero arrangement freedom. Enforced order always requires combinations (${}_n\text{C}_r$).
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
Post a Comment