① Combination Formula
A combination selects r items from n distinct items where order does NOT matter.
Example: C(5,2) = 5!/(2!×3!) = (5×4)/(2×1) = 10
② Permutation Formula
A permutation arranges r items from n where order DOES matter.
Key: P(n,r) = C(n,r) × r! — permutation counts every ordering of each combination.
🧠 Essential Identities to Memorize
C(n,0) = 1
Choose none = 1 way
C(n,n) = 1
Choose all = 1 way
C(n,r) = C(n,n−r)
Symmetry identity
C(n,1) = n
Choose one = n ways
C(n,r) = C(n−1,r−1) + C(n−1,r)
Pascal's identity
Σ C(n,k) = 2ⁿ
Sum of all subsets
③ Key Problem Types
- Direct selection: Choose r from n → C(n,r)
- At least / at most: Use complement: Total − (unwanted)
- Committees with conditions: Break into cases or use inclusion-exclusion
- Geometric counting: Diagonals = C(n,2) − n; Triangles = C(n,3)
- Grid paths: Moving right a and up b → C(a+b, a)
- Dividing into groups: Divide n into groups, adjust for identical groups
📝 Worked Examples
Example 1 — Direct Combination
How many ways can a committee of 3 be chosen from 7 people?
C(7,3) = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35
Answer: 35
Example 2 — Complement Method
From 5 men and 4 women, choose 3 people with at least 1 woman.
Total: C(9,3) = 84
All men (no women): C(5,3) = 10
At least 1 woman = 84 − 10 = 74
Answer: 74
Example 3 — Diagonals of a Polygon
How many diagonals does a convex octagon (8 sides) have?
Connect any 2 vertices: C(8,2) = 28
Subtract the 8 sides of the polygon.
Diagonals = 28 − 8 = 20
Answer: 20