경우의 수 — 순열과 조합의 모든 것

10개 도시를 여행하는 순서는 몇 가지일까요? $10!=3,628,800$가지입니다. 이 어마어마한 수를 한 식으로 표현하는 것이 순열이고, 순서 없이 고르면 조합입니다.

1. 합의 법칙과 곱의 법칙

법칙	조건	경우의 수
합의 법칙	사건 A, B가 동시에 일어나지 않음	$m+n$
곱의 법칙	사건 A, B가 독립적으로 일어남	$m\times n$

동전(앞/뒤)과 주사위(1~6):
동전 2가지, 주사위 6가지 → 2×6 = 12가지 (곱의 법칙)

1에서 50까지 중 3의 배수 또는 5의 배수:
3의 배수: 16개, 5의 배수: 10개, 15의 배수: 3개
→ 합의 법칙: 16+10−3 = 23개

2. 순열 (Permutation)

$n$개 중 $r$개를 순서 있게 나열하는 방법의 수:

$${}_n{P}_r=P(n,r)=\frac{n!}{(n-r)!}=n(n-1)(n-2)\cdots (n-r+1)$$

5명 중 3명을 뽑아 일렬로 세우는 방법:
₅P₃ = 5×4×3 = 60

n! = n×(n-1)×...×2×1
0! = 1 (정의)

₇P₂ = 7!/5! = 7×6 = 42
₅P₅ = 5! = 120

특수한 순열

이웃하는 조건: 묶어서 하나로 취급
KOREA를 나열할 때 K와 A가 항상 이웃:
→ [KA]OREA: 5개를 나열 = 5! = 120
→ KA 또는 AK = ×2
→ 총 120×2 = 240

원형배열: n명을 원형 배치 = (n-1)!
목걸이(뒤집어도 같음): (n-1)!/2

3. 조합 (Combination)

$n$개 중 $r$개를 순서 없이 고르는 방법의 수:

$${}_n{C}_r=C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}=\frac{{}_n{P}_r}{r!}$$

10명 중 3명 위원 선출 (순서 없음):
₁₀C₃ = 10!/(3!×7!) = (10×9×8)/(3×2×1) = 120

조합의 성질:
ₙCᵣ = ₙCₙ₋ᵣ   (대칭성)
ₙC₀ = ₙCₙ = 1
ₙC₁ = n

5C2 = 5C3 = 10
₁₀C₄ = ₁₀C₆ = 210

4. 중복순열과 중복조합

중복순열: n가지에서 중복 허용 r개 선택 → nΠr = n^r
예) 비밀번호 4자리 (0~9): 10⁴ = 10000가지

중복조합: n가지에서 중복 허용, 순서 무관 r개 → ₙHᵣ = ₍ₙ₊ᵣ₋₁₎Cᵣ
예) 사과·배·귤 중 중복허용 3개: ₃H₃ = ₅C₃ = 10

5. 이항정리

$$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$$

(a+b)⁴ = C(4,0)a⁴ + C(4,1)a³b + C(4,2)a²b² + C(4,3)ab³ + C(4,4)b⁴
       = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

파스칼의 삼각형:
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

(1+x)^n의 x^k 계수 = ₙCₖ

(2x−1)⁶에서 x³ 계수:
k=3: C(6,3)×(2x)³×(−1)³ = 20×8×(−1) = −160