1 왜 열거법인가
확률을 계산하려면 표본공간 \(\Omega\) 를 명확히 정의해야 한다. 표본공간이 작으면 직접 열거(enumeration) 가 가능하고, 이 과정에서 패턴을 발견하면 공식이 만들어진다.
\[ \text{실험 설계} \xrightarrow{\text{열거법}} \text{표본공간 } \Omega \xrightarrow{P(A)=|A|/|\Omega|} \text{확률} \]
조합론(40)이 “세는 공식”을 다뤘다면, 이 포스트는 “어떤 표본공간을 구성할 것인가” 를 다룬다.
표본공간 구성은 확률 계산의 첫 번째이자 가장 중요한 결정이다.
실패 사례 1: 동전 두 번 던져 앞면 수를 셀 때 \(\Omega = \{0, 1, 2\}\) 로 잡으면 \(P(\text{앞면 1개}) = 1/3\) 이 되지만, 실제로는 \(1/2\) 다. 결과를 “요약”하면 균등성이 깨진다.
실패 사례 2: 두 주사위의 합을 계산할 때 \(\Omega = \{2, 3, \ldots, 12\}\) 로 잡으면 \(P(\text{합}=2)\) 와 \(P(\text{합}=7)\) 이 같다고 착각한다. 실제로 합 7은 6가지 경우, 합 2는 1가지뿐이다.
원칙: 먼저 가장 세밀한(finest) 표본공간을 구성한 뒤, 필요하면 사건으로 묶는다.
2 트리 다이어그램 (Tree Diagrams)
작은 표본공간을 시각적으로 열거하는 가장 직관적인 방법이다.
2.1 기본 구조
각 단계에서 가능한 결과를 가지(branch)로 나타내고, 루트에서 잎(leaf)까지의 경로 하나가 근원사건(elementary outcome) 하나에 대응한다.
예시: 동전 두 번 던지기
┌── H → (H, H)
H ────┤
└── T → (H, T)
root ───┤
┌── H → (T, H)
T ────┤
└── T → (T, T)\(\Omega = \{HH, HT, TH, TT\}\), \(|\Omega| = 4\)
예시: 주사위 한 번, 동전 한 번
┌── H → (1, H)
1 ───────┤
└── T → (1, T)
┌── H → (2, H)
2 ───────┤
└── T → (2, T)
⋮
┌── H → (6, H)
6 ───────┤
└── T → (6, T)\(|\Omega| = 6 \times 2 = 12\) (곱의 법칙)
2.2 조건부 트리
각 단계의 확률이 다를 때 트리에 확률을 표기한다.
예시: 불량품 2개·양품 3개 중 비복원으로 2개 추출
P=2/5 ┌─ 불량 P=1/4 → P = 2/5 × 1/4 = 2/20
불량 ──────────────────┤
(D) └─ 양품 P=3/4 → P = 2/5 × 3/4 = 6/20
P=3/5 ┌─ 불량 P=2/4 → P = 3/5 × 2/4 = 6/20
양품 ──────────────────┤
(G) └─ 양품 P=2/4 → P = 3/5 × 2/4 = 6/20| 결과 | 확률 |
|---|---|
| (D, D) | 2/20 = 1/10 |
| (D, G) | 6/20 = 3/10 |
| (G, D) | 6/20 = 3/10 |
| (G, G) | 6/20 = 3/10 |
| 합계 | 20/20 = 1 ✓ |
3 4가지 추출 방식
표본공간의 크기는 순서를 고려하는가(ordered) 와 중복을 허용하는가(with replacement) 에 따라 결정된다.
\(n\) 개 원소에서 \(r\) 개 추출:
| 순서 있음 (Ordered) | 순서 없음 (Unordered) | |
|---|---|---|
| 복원 (With Replacement) | \(n^r\) | \(\dbinom{n+r-1}{r}\) |
| 비복원 (Without Replacement) | \(\dfrac{n!}{(n-r)!} = P(n,r)\) | \(\dbinom{n}{r}\) |
이 네 가지가 조합론의 뼈대를 이룬다. 각각을 “어떤 표본공간인가”의 관점으로 이해한다.
3.1 순서 있음 + 복원 (Ordered, With Replacement)
\[ \Omega = \{(a_1, a_2, \ldots, a_r) : a_i \in \{1,\ldots,n\}\} \] \[ |\Omega| = n^r \]
특징: - 같은 원소가 여러 번 등장 가능 - 순서가 다르면 다른 결과: \((1,2) \neq (2,1)\) - 각 시행이 독립적
실제 상황: - 주사위 \(r\) 번 굴리기 - 복원 추출 (뽑고 다시 넣기) - 비밀번호 생성 (중복 허용) - 문자열 생성
예시: \(n=3\) (A, B, C), \(r=2\), 순서 있음 + 복원
\[ \Omega = \{AA, AB, AC, BA, BB, BC, CA, CB, CC\}, \quad |\Omega| = 3^2 = 9 \]
3.2 순서 있음 + 비복원 (Ordered, Without Replacement)
\[ \Omega = \{(a_1, a_2, \ldots, a_r) : a_i \in \{1,\ldots,n\},\; a_i \neq a_j \text{ for } i \neq j\} \] \[ |\Omega| = P(n,r) = \frac{n!}{(n-r)!} \]
특징: - 같은 원소 두 번 등장 불가 - 순서가 다르면 다른 결과 - 각 시행이 조건부: 이전 결과에 영향받음
실제 상황: - 비복원 추출 (뽑고 돌려놓지 않기), 순위 기록 - 수상자 1등·2등·3등 선출 - 달리기 순위 기록
예시: \(n=3\) (A, B, C), \(r=2\), 순서 있음 + 비복원
\[ \Omega = \{AB, AC, BA, BC, CA, CB\}, \quad |\Omega| = P(3,2) = 6 \]
\(AA, BB, CC\) 제외됨.
3.3 순서 없음 + 비복원 (Unordered, Without Replacement)
\[ \Omega = \{S \subseteq \{1,\ldots,n\} : |S| = r\} \] \[ |\Omega| = \binom{n}{r} = \frac{n!}{r!\,(n-r)!} \]
특징: - 같은 원소 두 번 등장 불가 - 순서 무관: \(\{A,B\} = \{B,A\}\) - 가장 많이 쓰이는 표본공간
실제 상황: - 위원회 구성 (직책 없음) - 카드 패 (5장의 집합) - 로또 번호 선택
예시: \(n=3\) (A, B, C), \(r=2\), 순서 없음 + 비복원
\[ \Omega = \{\{A,B\},\; \{A,C\},\; \{B,C\}\}, \quad |\Omega| = \binom{3}{2} = 3 \]
3.4 순서 없음 + 복원 (Unordered, With Replacement)
\[ \Omega = \{(a_1, \ldots, a_r) : a_1 \leq a_2 \leq \cdots \leq a_r,\; a_i \in \{1,\ldots,n\}\} \] \[ |\Omega| = \binom{n+r-1}{r} \]
특징: - 같은 원소 여러 번 등장 가능 - 순서는 구분하지 않음 (멀티셋) - 별과 막대(Stars and Bars) 방법으로 도출
실제 상황: - 주사위 \(r\) 번 굴려 합계만 기록 - 품종 구분 없이 꽃 \(r\) 송이 고르기 - 비음 정수해의 수
예시: \(n=3\) (A, B, C), \(r=2\), 순서 없음 + 복원
\[ \Omega = \{\{A,A\},\{A,B\},\{A,C\},\{B,B\},\{B,C\},\{C,C\}\}, \quad |\Omega| = \binom{4}{2} = 6 \]
3.5 4가지 비교: \(n=3\), \(r=2\) 완전 예시
| 방식 | 표본공간 원소들 | 크기 |
|---|---|---|
| 순서O + 복원 | AA, AB, AC, BA, BB, BC, CA, CB, CC | 9 |
| 순서O + 비복원 | AB, AC, BA, BC, CA, CB | 6 |
| 순서X + 비복원 | {A,B}, {A,C}, {B,C} | 3 |
| 순서X + 복원 | {A,A}, {A,B}, {A,C}, {B,B}, {B,C}, {C,C} | 6 |
\[ \underbrace{n^r}_{\text{순서O, 복원}} \;\geq\; \underbrace{P(n,r)}_{\text{순서O, 비복원}} \;\geq\; \underbrace{\binom{n}{r}}_{\text{순서X, 비복원}} \]
순서X + 복원은 \(\binom{n+r-1}{r}\) 로, 위 부등식의 어느 위치에도 고정되지 않는다 (예: \(n=3, r=2\) 이면 6으로 순서O 비복원과 같음).
4 복합 실험의 표본공간 구성
두 개 이상의 실험을 결합하면 표본공간은 곱(product) 으로 표현된다.
4.1 곱 공간 (Product Space)
실험 1의 표본공간 \(\Omega_1\), 실험 2의 표본공간 \(\Omega_2\) 일 때, 두 실험을 순서대로 수행하는 복합 실험의 표본공간:
\[ \Omega = \Omega_1 \times \Omega_2 = \{(\omega_1, \omega_2) : \omega_1 \in \Omega_1,\; \omega_2 \in \Omega_2\} \] \[ |\Omega| = |\Omega_1| \times |\Omega_2| \]
예시
| 실험 1 | 실험 2 | 표본공간 크기 |
|---|---|---|
| 동전 (\(|\Omega_1|=2\)) | 주사위 (\(|\Omega_2|=6\)) | 12 |
| 주사위 2번 | — | \(6 \times 6 = 36\) |
| 성별 2가지 | 혈액형 4가지 | 8 |
| 카드 2장 비복원 | — | \(52 \times 51 = 2{,}652\) |
4.2 표본공간의 크기가 달라지는 경우
각 단계에서 가능한 결과의 수가 이전 결과에 의존하면 곱의 법칙을 단계별로 적용한다.
예시: 짝수가 나오면 동전을 던지고, 홀수가 나오면 멈추는 실험
주사위
짝수 (3가지) × 동전 (2가지) = 6가지 결과
홀수 (3가지) × 멈춤 (1가지) = 3가지 결과
총 |\Omega| = 95 실험별 표본공간 구성 패턴
Q1. 결과의 순서가 중요한가?
YES → 순서 있음
NO → 순서 없음
Q2. 뽑은 원소를 되돌려 놓는가?
YES → 복원 (with replacement)
NO → 비복원 (without replacement)
→ 4가지 중 하나 선택실전 판별 예시
| 문제 | 순서? | 복원? | 공식 | 표본공간 크기 |
|---|---|---|---|---|
| 6자리 PIN (0~9, 중복 가능) | O | O | \(10^6\) | 1,000,000 |
| 8명 중 금·은·동메달 | O | X | \(P(8,3)\) | 336 |
| 20명 중 위원 4명 선발 | X | X | \(\binom{20}{4}\) | 4,845 |
| 편의점 5종 음료 중 3캔 (중복 허용) | X | O | \(\binom{7}{3}\) | 35 |
| 주사위 3번 굴려 순서 기록 | O | O | \(6^3\) | 216 |
| 카드 5장 패 | X | X | \(\binom{52}{5}\) | 2,598,960 |
6 열거를 이용한 확률 계산
표본공간을 명확히 구성한 후 조건에 맞는 사건을 세면 확률이 나온다.
6.1 두 주사위의 합
\(\Omega = \{(i,j) : 1 \leq i,j \leq 6\}\), \(|\Omega| = 36\) (순서 있음 + 복원)
\(P(\text{합}=7)\):
\[ A = \{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}, \quad |A| = 6 \]
\[ P(\text{합}=7) = \frac{6}{36} = \frac{1}{6} \]
모든 합의 분포:
| 합 | 경우의 수 | 확률 |
|---|---|---|
| 2 | 1 | 1/36 |
| 3 | 2 | 2/36 |
| 4 | 3 | 3/36 |
| 5 | 4 | 4/36 |
| 6 | 5 | 5/36 |
| 7 | 6 | 6/36 |
| 8 | 5 | 5/36 |
| 9 | 4 | 4/36 |
| 10 | 3 | 3/36 |
| 11 | 2 | 2/36 |
| 12 | 1 | 1/36 |
6.2 카드 게임: 같은 숫자 쌍 확률
52장에서 2장 비복원 추출. 같은 숫자(페어)일 확률:
- \(|\Omega| = \binom{52}{2} = 1{,}326\)
- 숫자 13가지, 각각 4장 → 페어: \(13 \times \binom{4}{2} = 13 \times 6 = 78\)
\[ P(\text{페어}) = \frac{78}{1{,}326} = \frac{1}{17} \approx 5.88\% \]
6.3 생일 문제: 표본공간 관점
\(n\) 명의 생일을 순서 있게 기록. \(\Omega\): 각 사람의 생일이 365일 중 하나 → \(|\Omega| = 365^n\) (순서 있음 + 복원)
\(A^c\): 모든 생일이 다름 → \(|A^c| = P(365, n)\) (순서 있음 + 비복원)
\[ P(A) = 1 - \frac{P(365,n)}{365^n} = 1 - \frac{365!/(365-n)!}{365^n} \]
7 표본공간 구성 시 흔한 오류
7.1 표본공간을 균등하지 않게 구성
잘못된 예: 동전 두 번 던져 앞면 수 세기 \[ \Omega_{\text{wrong}} = \{0\text{개}, 1\text{개}, 2\text{개}\}, \quad P(\text{앞면 1개}) = 1/3 \;\text{???} \]
올바른 예: 순서 기록 \[ \Omega_{\text{correct}} = \{HH, HT, TH, TT\}, \quad P(\text{앞면 1개}) = 2/4 = 1/2 \]
균등 확률(equally likely) 가정을 적용하려면 표본공간의 모든 원소가 동등하게 가능해야 한다. 결과를 묶거나 요약하면 균등성이 깨진다.
7.2 순서 고려 여부 혼동
예: 두 주사위의 합이 4가 되는 확률
올바른 \(\Omega\): 순서 있음 \((i,j)\), \(|\Omega|=36\) → \((1,3), (2,2), (3,1)\): 3가지, \(P=3/36=1/12\)
잘못된 \(\Omega\): 순서 없음 \(\{i,j\}\) → \(\{1,3\}, \{2,2\}\): 2가지, \(P=2/?\) ← 균등하지 않음! (\(\{1,3\}\) 은 \((1,3)\) 과 \((3,1)\) 두 경우를 포함하므로 \(\{2,2\}\) 보다 두 배 가능)
8 응용 분야
| 분야 | 표본공간 구성 | 공식 |
|---|---|---|
| 유전학 | 멘델 유전: 부모 유전자 조합 | 곱 공간, \(2 \times 2\) 퍼네트 사각형 |
| 임상시험 | 처치 배정 방법의 수 | \(\binom{n}{k}\) (순서X, 비복원) |
| 암호학 | 키 공간 크기 | \(n^r\) (순서O, 복원) |
| 검색 알고리즘 | 상태 공간 탐색 | 트리 구조, 가지치기 |
| 통계 시뮬레이션 | 부트스트랩 | \(n^n\) (순서O, 복원) |
| 조합 최적화 | 경우의 수 상한 | 적절한 추출 방식 선택으로 복잡도 추정 |
9 코드 예시
9.1 Step 1: 순수 Python — 4가지 표본공간 직접 열거
from itertools import product, permutations, combinations, combinations_with_replacement
elements = ['A', 'B', 'C']
r = 2
# 순서 있음 + 복원: n^r = 3^2 = 9
ordered_with = list(product(elements, repeat=r))
print(f"순서O + 복원 ({len(ordered_with)}개):")
print(ordered_with)
# 순서 있음 + 비복원: P(n,r) = 6
ordered_without = list(permutations(elements, r))
print(f"\n순서O + 비복원 ({len(ordered_without)}개):")
print(ordered_without)
# 순서 없음 + 비복원: C(n,r) = 3
unordered_without = list(combinations(elements, r))
print(f"\n순서X + 비복원 ({len(unordered_without)}개):")
print(unordered_without)
# 순서 없음 + 복원: C(n+r-1, r) = 6
unordered_with = list(combinations_with_replacement(elements, r))
print(f"\n순서X + 복원 ({len(unordered_with)}개):")
print(unordered_with)
# 크기 검증
import math
n = len(elements)
print(f"\n크기 검증:")
print(f" 순서O + 복원: {n**r} == {len(ordered_with)}")
print(f" 순서O + 비복원: {math.factorial(n)//math.factorial(n-r)} == {len(ordered_without)}")
print(f" 순서X + 비복원: {math.comb(n,r)} == {len(unordered_without)}")
print(f" 순서X + 복원: {math.comb(n+r-1,r)} == {len(unordered_with)}")9.2 Step 2: 복합 실험 표본공간 구성과 확률 계산
from itertools import product
from collections import Counter
import numpy as np
# ── 두 주사위 합 분포 ─────────────────────────────────────────────
dice = range(1, 7)
Omega_dice = list(product(dice, dice)) # 순서O + 복원, 36가지
sums = [a + b for a, b in Omega_dice]
sum_counts = Counter(sums)
total = len(Omega_dice)
print("두 주사위 합 분포:")
print(f"{'합':>5} {'경우':>6} {'확률':>8}")
print("-" * 22)
for s in range(2, 13):
count = sum_counts[s]
prob = count / total
bar = "█" * count
print(f"{s:>5} {count:>6} {prob:>8.4f} {bar}")
# ── 카드 페어 확률 ────────────────────────────────────────────────
from itertools import combinations as combs
suits = ['S', 'H', 'D', 'C']
ranks = list(range(1, 14)) # 1=A, 11=J, 12=Q, 13=K
deck = [(r, s) for r in ranks for s in suits]
Omega_cards = list(combs(deck, 2)) # 순서X + 비복원, C(52,2)=1326
pair_hands = [(c1, c2) for c1, c2 in Omega_cards if c1[0] == c2[0]]
print(f"\n카드 2장 페어 확률:")
print(f" |Ω| = {len(Omega_cards)}")
print(f" 페어 수 = {len(pair_hands)}")
print(f" P(페어) = {len(pair_hands)/len(Omega_cards):.6f} (이론: {1/17:.6f})")
# ── 4가지 추출 방식별 표본공간 크기 비교 ───────────────────────────
import math
print(f"\n{'n':>4} {'r':>4} {'순서O복원':>12} {'순서O비복원':>14} {'순서X비복원':>14} {'순서X복원':>12}")
print("-" * 62)
for n, r in [(3,2), (5,3), (10,3), (52,5)]:
o_wr = n ** r
o_wor = math.perm(n, r)
u_wor = math.comb(n, r)
u_wr = math.comb(n + r - 1, r)
print(f"{n:>4} {r:>4} {o_wr:>12,} {o_wor:>14,} {u_wor:>14,} {u_wr:>12,}")
# ── 트리 다이어그램 시뮬레이션: 비복원 추출 확률 검증 ──────────────
np.random.seed(42)
n_sim = 100_000
bag = ['D', 'D', 'G', 'G', 'G'] # 불량 2, 양품 3
results = Counter()
for _ in range(n_sim):
draw1 = np.random.choice(bag, replace=False)
remaining = bag.copy()
remaining.remove(draw1)
draw2 = np.random.choice(remaining)
results[(draw1, draw2)] += 1
print("\n비복원 추출 결과 (시뮬레이션 vs 이론):")
theory = {('D','D'): 2/20, ('D','G'): 6/20, ('G','D'): 6/20, ('G','G'): 6/20}
for key in [('D','D'), ('D','G'), ('G','D'), ('G','G')]:
sim = results[key] / n_sim
th = theory[key]
print(f" {key}: 시뮬={sim:.4f}, 이론={th:.4f}")10 관련 주제
선행 지식
- 확률론의 언어: 집합론 — 표본공간, 사건의 정의
- 확률론의 공리적 기초 — 균등 분포, \(P(A)=|A|/|\Omega|\)
- 경우의 수와 조합론 — 4가지 공식의 도출
후속 주제
- Basics of Probability Theory - Probability — 열거된 표본공간에서 확률 계산
- Conditional Probability — 트리 다이어그램의 수학적 표현
- Bayes’ Rule — 조건부 트리의 역방향 계산
관련 개념
- Binomial Distribution — 순서O+복원 표본공간이 기반
- MLE — 다항 표본공간에서의 최대우도 추정