🔢 Permutation (순열)
P(n, r) = n! / (n−r)!
= n × (n−1) × (n−2) × ⋯ × (n−r+1)
Circular Permutation: (n−1)!
Permutation with Repetition: n^r
⭐ Must Memorize
- Order MATTERS → use Permutation
- P(n,r): choosing r items from n, order counts
- Circular: fix one person, arrange (n−1) others
- Adjacent items: treat as ONE block first
Note: 0! = 1 | n! = n × (n−1)!
🎯 Combination (조합)
C(n, r) = n! / (r! × (n−r)!)
= P(n,r) / r!
C(n,0) = C(n,n) = 1
C(n,r) = C(n, n−r) [Symmetry]
C(n,r) = C(n−1,r−1) + C(n−1,r) [Pascal]
⭐ Must Memorize
- Order does NOT matter → use Combination
- C(n,r) = C(n, n−r): always use the smaller r
- Pascal's Identity: C(n,r) = C(n−1,r−1) + C(n−1,r)
- Diagonal count: n(n−3)/2 for n-gon
📐 Key Formulas to Memorize
Probability using Combo:
P(event) = C(favorable) / C(total)
"At least one" probability:
P(≥1) = 1 − P(none)
Shortest Path (grid m×n):
C(m+n, m) or C(m+n, n)
Handshakes (n people):
C(n, 2) = n(n−1)/2
Diagonals of n-gon:
C(n,2) − n = n(n−3)/2
💡 Worked Examples
Example 1 — Permutation
How many 3-letter arrangements from {A,B,C,D,E}?
P(5,3) = 5×4×3 = 60
Example 2 — Combination
Choose 3 students from 7 for a committee (order doesn't matter)?
C(7,3) = 7!/(3!×4!) = 35
Example 3 — Probability
Draw 2 from 4 red + 2 blue. P(both red)?
C(4,2)/C(6,2) = 6/15 = 2/5