组合zǔhé

Core Concept

A Combination is a selection of $m$ elements ($m \leq n$) from $n$ distinct elements without regard to order.

Key Characteristics

1. Order doesn't matter: Same elements in different orders count as one combination
2. No repetition: Each element used at most once
3. Selection: Choose $m$ from $n$ elements ($m \leq n$)

Difference from Permutation

• Permutation: Ordered, $\{A, B, C\}$ and $\{B, A, C\}$ are different
• Combination: Unordered, $\{A, B, C\}$ and $\{B, A, C\}$ are the same

Combination Formula

Number of combinations of $m$ elements from $n$ distinct elements, denoted $C_n^m$ or $\binom{n}{m}$ or $C(n,m)$:

$C_n^m = \frac{A_n^m}{A_m^m} = \frac{n!}{m!(n-m)!}$

Understanding:

• Arrange first: $A_n^m = \frac{n!}{(n-m)!}$
• Remove internal order: $A_m^m = m!$
• Result: $C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$

Properties of Combinations

1. Symmetry

$C_n^m = C_n^{n-m}$

Meaning: Selecting $m$ from $n$ = Leaving $n-m$ from $n$

2. Pascal's Identity

$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$

Meaning: Include specific element + Exclude specific element

3. Special Values

• $C_n^0 = 1$ (select none, one way)
• $C_n^1 = n$ (select one, $n$ choices)
• $C_n^n = 1$ (select all, one way)

4. Binomial Sum

$C_n^0 + C_n^1 + C_n^2 + \cdots + C_n^n = 2^n$

(Total ways to select any number of elements from $n$)

Calculation Techniques

Technique 1: Use Symmetry

$C_{100}^{98} = C_{100}^{2} = \frac{100 \times 99}{2} = 4950$

Technique 2: Pascal's Identity

$C_5^3 = C_4^2 + C_4^3 = 6 + 4 = 10$

Technique 3: Simplify by Cancellation

$C_8^3 = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

CSCA Practice Problems

[Example 1] Basic (Difficulty ★★☆☆☆)

Calculate $C_7^3$.

Solution:

$C_7^3 = \frac{7!}{3! \cdot 4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$

Answer: $35$

---

[Example 2] Intermediate (Difficulty ★★★☆☆)

From 10 boys and 8 girls, select 5 people for a team with at least 2 girls. How many ways?

Solution:

Case analysis:

Case 1: 2 girls, 3 boys: $C_8^2 \cdot C_{10}^3 = 28 \times 120 = 3360$

Case 2: 3 girls, 2 boys: $C_8^3 \cdot C_{10}^2 = 56 \times 45 = 2520$

Case 3: 4 girls, 1 boy: $C_8^4 \cdot C_{10}^1 = 70 \times 10 = 700$

Case 4: 5 girls, 0 boys: $C_8^5 = 56$

Answer: $3360 + 2520 + 700 + 56 = 6636$

Common Misconceptions

❌ Misconception 1: Confusing combination with permutation

Wrong: Using $C_n^5$ for arranging 5 people in a line

Correct: Line has order, should use $A_n^5$

❌ Misconception 2: Forgetting case analysis

Wrong: Directly calculating "at least 2 girls"

Correct: Break into cases: 2 girls, 3 girls, 4 girls, 5 girls

Relationship with Permutation

$A_n^m = C_n^m \times m!$

$C_n^m = \frac{A_n^m}{m!}$

Study Tips

1. ✅ Understand essence: Combination ignores order
2. ✅ Master formula: $C_n^m = \frac{n!}{m!(n-m)!}$
3. ✅ Remember properties: Symmetry, Pascal's identity
4. ✅ Case analysis: "At least", "at most" require cases
5. ✅ Distinguish from permutation: Check if order matters

---

💡 Exam Tip: Combination is key to combinatorics, mandatory in CSCA! Accounts for about 60% of counting problems. Case analysis and inclusion-exclusion are essential techniques.