이 포스트는 경우의 수와 조합론 의 심화편이다. 순열·조합·이항 정리를 먼저 학습한 뒤 읽는 것을 권장한다.
기초편(순열·조합)만으로 충분하지 않은 상황은 실무에서 빈번하다:
- 별과 막대(중복 조합): 서버 3대에 요청 10개를 분배하는 경우의 수 → 자원 배분 문제의 기본
- 다항계수: 자연어 처리에서 문서 내 단어 빈도 조합의 수 → 다항 분포의 기초
- 비둘기집 원리: 해시 함수에 \(n+1\) 개 키를 넣으면 충돌이 반드시 발생 → 해시 테이블 설계의 이론적 근거
- 포함-배제 원리: “A 또는 B 또는 C 중 하나라도 해당”하는 사용자 수 → 마케팅 캠페인 도달률 계산
이 기법들은 확률론·통계학뿐 아니라 알고리즘 분석, 암호학, 네트워크 설계에서도 핵심 도구다.
1 중복 조합 (Combinations with Repetition)
1.1 별과 막대 (Stars and Bars)
\(n\) 가지 종류에서 중복을 허용하여 \(r\) 개를 선택하는 경우의 수 (순서 무관):
\[ \binom{n+r-1}{r} = \binom{n+r-1}{n-1} \]
증명 (별과 막대 방법):
\(r\) 개의 별(\(\star\))을 \(n\) 개의 구간(종류)으로 나누는 문제로 환원. \(n-1\) 개의 막대(\(|\))를 이용해 \(r\) 개의 별을 \(n\) 개 그룹으로 나눈다.
총 기호 수: \(r + (n-1) = r+n-1\) 개 중 막대의 위치 \(n-1\) 개를 선택:
\[ \binom{r+n-1}{n-1} = \binom{n+r-1}{r} \quad\blacksquare \]
예시: 별과 막대 시각화
3가지 음료(콜라·사이다·주스)에서 중복 허용으로 4캔 선택: - \(n=3\), \(r=4\) → \(\binom{3+4-1}{4} = \binom{6}{4} = 15\)
| 콜라 | 사이다 | 주스 | 기호 표현 |
|---|---|---|---|
| 4 | 0 | 0 | \(\star\star\star\star\,\|\,\|\) |
| 2 | 1 | 1 | \(\star\star\,\|\,\star\,\|\,\star\) |
| 0 | 0 | 4 | \(\,\|\,\|\,\star\star\star\star\) |
| 1 | 2 | 1 | \(\star\,\|\,\star\star\,\|\,\star\) |
응용: 방정식 \(x_1 + x_2 + \cdots + x_n = r\) (비음 정수해의 수) \(= \binom{n+r-1}{r}\)
2 다항계수 (Multinomial Coefficients)
\(n\) 개의 원소를 \(k\) 개의 그룹으로 각각 \(n_1, n_2, \ldots, n_k\) 개씩 나누는 경우의 수 (\(n_1 + n_2 + \cdots + n_k = n\), \(n_i \geq 0\)):
\[ \binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1!\, n_2!\, \cdots\, n_k!} \]
이항계수와의 관계: \(k=2\) 이면 \(\binom{n}{n_1, n_2} = \binom{n}{n_1}\)
다항 정리 (Multinomial Theorem):
\[ (x_1 + x_2 + \cdots + x_k)^n = \sum_{\substack{n_1+n_2+\cdots+n_k=n \\ n_i \geq 0}} \binom{n}{n_1, n_2, \ldots, n_k}\, x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \]
예시
52장 카드를 4명에게 13장씩 나눠주는 방법의 수: \[ \binom{52}{13,13,13,13} = \frac{52!}{(13!)^4} \approx 5.36 \times 10^{28} \]
“STATISTICS” 철자 나열 (S×3, T×3, A×1, I×2, C×1): \[ \frac{10!}{3!\,3!\,1!\,2!\,1!} = 50{,}400 \]
3 비둘기집 원리 (Pigeonhole Principle)
\(n+1\) 마리의 비둘기를 \(n\) 개의 집에 넣으면, 적어도 하나의 집에는 비둘기가 2마리 이상 들어간다.
일반화: \(kn+1\) 개의 물체를 \(n\) 개의 범주에 넣으면 적어도 하나의 범주에 \(k+1\) 개 이상의 물체가 존재한다.
증명: 모든 집에 비둘기가 1마리 이하이면 총 비둘기 수 \(\leq n < n+1\). 모순. \(\quad\blacksquare\)
응용 예시
| 예시 | 비둘기 | 집 | 결론 |
|---|---|---|---|
| 서울 인구 (약 950만) vs 머리카락 수 (최대 20만) | 인구 | 머리카락 수 | 같은 수의 머리카락을 가진 사람이 반드시 존재 |
| 임의의 367명 | 사람 | 365일 (+ 윤년) | 생일이 같은 쌍 반드시 존재 |
| 5개 점을 2×2 정사각형에 찍으면 | 점 | 4개 사분면 | 같은 사분면 내 2점 반드시 존재 |
| 13명 중 월별 생일 | 사람 | 12개월 | 같은 달 생일이 2명 이상 반드시 존재 |
4 포함-배제 원리 (Inclusion-Exclusion for Counting)
유한 집합 \(A_1, A_2, \ldots, A_n\) 에 대해:
\[ \left|\bigcup_{i=1}^n A_i\right| = \sum_i |A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}\left|\bigcap_{i=1}^n A_i\right| \]
예시: 1부터 100 사이에서 2 또는 3의 배수의 개수
- \(|A_2|\) = 2의 배수: \(\lfloor 100/2 \rfloor = 50\)
- \(|A_3|\) = 3의 배수: \(\lfloor 100/3 \rfloor = 33\)
- \(|A_2 \cap A_3|\) = 6의 배수: \(\lfloor 100/6 \rfloor = 16\)
\[ |A_2 \cup A_3| = 50 + 33 - 16 = 67 \]
완전 순열 (Derangements):
\(n\) 개의 원소를 나열할 때 어느 원소도 원래 자리에 오지 않는 순열의 수 \(D_n\):
\[ D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = n!\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right) \]
| \(n\) | \(D_n\) | \(D_n/n!\) |
|---|---|---|
| 1 | 0 | 0.000 |
| 2 | 1 | 0.500 |
| 3 | 2 | 0.333 |
| 4 | 9 | 0.375 |
| 5 | 44 | 0.367 |
| 10 | 1,334,961 | 0.368 |
| \(\infty\) | — | \(1/e \approx 0.368\) |
\(n \to \infty\) 이면 \(D_n/n! \to 1/e\): 무작위 순열이 완전 순열일 확률은 약 36.8%.
5 응용 분야
| 분야 | 조합론의 역할 | 구체적 예시 |
|---|---|---|
| 통계 | 이항·다항 분포 도출 | \(P(X=k) = \binom{n}{k} p^k(1-p)^{n-k}\) |
| 암호학 | 키 공간 크기 | AES-128: \(2^{128}\) 가지 키, 브루트포스 불가 |
| 알고리즘 | 조합 최적화 | 외판원 문제: \((n-1)!/2\) 가지 경로 |
| 딥러닝 | 드롭아웃 마스크 수 | \(n\) 개 뉴런에서 \(k\) 개 활성: \(\binom{n}{k}\) 가지 |
| 게놈 | 코돈 조합 | 4가지 염기, 3자리: \(4^3 = 64\) 가지 코돈 |
| A/B 테스트 | 순열 검정 | 처치/대조 배정 방법의 수로 p-value 계산 |
6 예시: 확률과 조합론의 통합
6.1 로또 확률 (45개 중 6개)
\[ |\Omega| = \binom{45}{6} = \frac{45!}{6!\,39!} = 8{,}145{,}060 \]
\[ P(\text{1등}) = \frac{1}{8{,}145{,}060} \approx 1.23 \times 10^{-7} \]
6.2 포커 풀하우스 확률
풀하우스 = 3장 같은 수 + 2장 같은 수
- 3장짜리 숫자 선택: \(\binom{13}{1} = 13\)
- 그 숫자에서 무늬 3개 선택: \(\binom{4}{3} = 4\)
- 2장짜리 숫자 선택 (3장짜리 제외): \(\binom{12}{1} = 12\)
- 그 숫자에서 무늬 2개 선택: \(\binom{4}{2} = 6\)
\[ |\text{풀하우스}| = 13 \times 4 \times 12 \times 6 = 3{,}744 \]
\[ P(\text{풀하우스}) = \frac{3{,}744}{2{,}598{,}960} \approx 0.00144 = 0.144\% \]
7 코드 예시
7.1 Step 1: 순수 Python — 조합론 공식 직접 구현
import math
from functools import reduce
# ── 기본 공식 ───────────────────────────────────────────────────
def factorial(n):
return math.factorial(n)
def perm(n, r):
"""반복 없는 순열 P(n,r)"""
if r > n: return 0
return factorial(n) // factorial(n - r)
def comb(n, r):
"""이항계수 C(n,r)"""
if r < 0 or r > n: return 0
return factorial(n) // (factorial(r) * factorial(n - r))
def multicomb(n, r):
"""중복 조합 H(n,r) = C(n+r-1, r)"""
return comb(n + r - 1, r)
def multinomial(*ns):
"""다항계수: n! / (n1! * n2! * ...)"""
n = sum(ns)
denom = reduce(lambda a, b: a * b, [factorial(k) for k in ns])
return factorial(n) // denom
# ── 검증 ─────────────────────────────────────────────────────────
print(f"P(8,3) = {perm(8,3)}") # 336
print(f"C(52,5) = {comb(52,5):,}") # 2,598,960
print(f"H(3,4) = {multicomb(3,4)}") # 15
print(f"C(45,6) 로또 = {comb(45,6):,}") # 8,145,060
# STATISTICS 철자 나열
print(f"STATISTICS = {multinomial(3,3,1,2,1):,}") # 50,400
# ── 파스칼의 삼각형 ───────────────────────────────────────────────
print("\n파스칼의 삼각형 (n=0..7):")
for n in range(8):
row = [comb(n, r) for r in range(n+1)]
print(" " * (7-n) + " ".join(f"{x:3d}" for x in row))
# ── 이항 정리 검증 ─────────────────────────────────────────────────
# (1+1)^n = sum C(n,r) = 2^n
for n in [3, 5, 10]:
lhs = 2**n
rhs = sum(comb(n, r) for r in range(n+1))
print(f"n={n}: 2^n={lhs}, sum C(n,r)={rhs}, 일치: {lhs==rhs}")
# ── 완전 순열(교란 순열) ───────────────────────────────────────────
def derangement(n):
"""D_n = n! * sum_{k=0}^{n} (-1)^k / k!"""
return round(factorial(n) * sum((-1)**k / factorial(k) for k in range(n+1)))
print("\n완전 순열:")
for n in range(1, 9):
Dn = derangement(n)
ratio = Dn / factorial(n)
print(f" D({n}) = {Dn:6d}, D_n/n! = {ratio:.6f}")
# D_n/n! → 1/e ≈ 0.3678797.2 Step 2: scipy·itertools — 실무 조합 계산
import numpy as np
from scipy.special import comb as sp_comb, factorial as sp_fact
from itertools import combinations, permutations, product
import math
# ── 포커 핸드 확률 계산 ─────────────────────────────────────────────
total_hands = int(sp_comb(52, 5, exact=True))
# 풀하우스
full_house = 13 * int(sp_comb(4,3)) * 12 * int(sp_comb(4,2))
# 플러시 (순수, 스트레이트 플러시 제외)
flush = 4 * int(sp_comb(13,5)) - 4 * 10
# 스트레이트 (순수)
straight = 10 * 4**5 - 4 * 10 - 36 # 스트레이트 - 로열/스트레이트 플러시
hands = {
"로열 플러시": 4,
"스트레이트 플러시": 36,
"포카드": 13 * int(sp_comb(4,4)) * 12 * 4,
"풀하우스": full_house,
"플러시": flush,
"원페어": 13 * int(sp_comb(4,2)) * int(sp_comb(12,3)) * 4**3,
}
print(f"{'핸드':<15} {'경우의 수':>12} {'확률(%)':>10}")
print("-" * 40)
for name, count in hands.items():
prob = count / total_hands * 100
print(f"{name:<15} {count:>12,} {prob:>10.6f}")
# ── 포함-배제: 1~100에서 2 또는 3의 배수 ───────────────────────────
N = 100
A2 = set(range(2, N+1, 2)) # 2의 배수
A3 = set(range(3, N+1, 3)) # 3의 배수
# 직접 계산
direct = len(A2 | A3)
# 포함-배제
incl_excl = len(A2) + len(A3) - len(A2 & A3)
print(f"\n1~{N}에서 2 또는 3의 배수: {direct} (직접), {incl_excl} (포함-배제)")
# ── 비둘기집: 생일 충돌 시뮬레이션 ──────────────────────────────────
np.random.seed(42)
n_sim = 100_000
group_size = 23
collision_count = 0
for _ in range(n_sim):
birthdays = np.random.randint(1, 366, size=group_size)
if len(set(birthdays)) < group_size:
collision_count += 1
empirical_prob = collision_count / n_sim
# 이론값
p_no_collision = 1.0
for k in range(group_size):
p_no_collision *= (365 - k) / 365
theoretical_prob = 1 - p_no_collision
print(f"\n생일 문제 (n={group_size}):")
print(f" 이론값: {theoretical_prob:.4f}")
print(f" 시뮬레이션: {empirical_prob:.4f}")8 관련 주제
선행 지식
- 경우의 수와 조합론 — 곱의 법칙, 순열, 조합, 이항 정리 (기초편)
- 확률론의 언어: 집합론 — 집합 연산, 멱집합
- 확률의 계산 규칙 — 조합론의 확률 적용
후속 주제
- Binomial Distribution — 이항계수가 확률 가중치로 등장
- Poisson Distribution — 이항 분포의 극한
- Conditional Probability — 경우의 수 기반 조건부 확률
관련 개념
- Convergence in Probability — 큰 수의 법칙: 반복 실험의 극한
- MLE — 다항 분포의 MLE에서 다항계수 등장