1 왜 조합론인가

유한 표본공간 \(\Omega\) 에서 모든 결과가 동등하게 가능(equally likely)하면:

\[ P(A) = \frac{|A|}{|\Omega|} \]

확률 계산이 경우의 수 세기 문제로 환원된다. 조합론(combinatorics)은 이 세기를 체계적으로 수행하는 도구다.

이 포스트와 앞 포스트의 관계

39-calculus-of-probabilities: 조합론을 확률 계산에 적용하는 관점
이 포스트: 조합론 자체를 체계적으로 다룸 — 정의, 공식, 증명, 심화 기법

조합론이 실무에서 등장하는 순간들

조합론은 “수학 퍼즐”이 아니라 실제 시스템 설계에서 반복적으로 등장한다:

암호학: 비밀번호 \(n\) 자리, 문자 종류 \(k\) 가지 → 탐색 공간 \(k^n\). 이 숫자가 충분히 커야 브루트포스가 불가능하다
A/B 테스트: \(n\) 명을 처치군/대조군으로 나누는 방법 \(\binom{n}{k}\) — 순열 검정(permutation test)의 기반
딥러닝: 드롭아웃에서 \(n\) 개 뉴런 중 \(k\) 개를 활성화하는 마스크 수 \(= \binom{n}{k}\)
추천 시스템: 후보 \(n\) 개 중 \(k\) 개를 순서대로 추천하는 방법 \(= P(n,k)\)
게놈학: 4가지 염기로 길이 \(r\) 인 코돈 \(= 4^r = 64\) 가지

공식을 외우는 것보다 “이 문제는 순열인가 조합인가, 복원인가 비복원인가”를 판별하는 능력이 핵심이다.

2 기본 계수 원리

2.1 곱의 법칙 (Multiplication Principle)

정리: 곱의 법칙 (Fundamental Counting Principle)

작업 1을 수행하는 방법이 \(n_1\) 가지, 이후 작업 2를 수행하는 방법이 \(n_2\) 가지, …, 작업 \(k\) 를 수행하는 방법이 \(n_k\) 가지이면, 전체를 순서대로 수행하는 방법의 수는:

\[ n_1 \times n_2 \times \cdots \times n_k \]

예시: 상의 3벌, 하의 4벌, 신발 2켤레로 만들 수 있는 코디 수 \(= 3 \times 4 \times 2 = 24\)

예시: 비밀번호가 영문 대문자 → 숫자 2자리 → 특수문자 구조이면: \(26 \times 10 \times 10 \times 32 = 83{,}200\) 가지

2.2 합의 법칙 (Addition Principle)

정리: 합의 법칙

두 작업이 동시에 수행될 수 없을 때(mutually exclusive), 작업 1의 방법이 \(n_1\) 가지, 작업 2의 방법이 \(n_2\) 가지이면 둘 중 하나를 선택하는 방법의 수: \(n_1 + n_2\)

예시: 공학 전공 학생 15명, 통계 전공 학생 12명 중 대표 1명 선출: \(15 + 12 = 27\) 가지

곱의 법칙 vs 합의 법칙

곱의 법칙: “그리고(AND)” — 둘 다 해야 한다 → 곱
합의 법칙: “또는(OR), 배타적” — 하나만 한다 → 합

3 순열 (Permutations)

3.1 반복 없는 순열

정의: 순열 \(P(n, r)\)

\(n\) 개의 서로 다른 원소에서 \(r\) 개를 순서 있게 나열하는 경우의 수:

\[ P(n, r) = {}_nP_r = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1) \]

\(r = n\) 이면: \(P(n,n) = n!\)

증명: 첫 자리에 \(n\) 가지, 두 번째 자리에 \(n-1\) 가지, …, \(r\) 번째 자리에 \(n-r+1\) 가지. 곱의 법칙 적용:

\[ P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!} \quad\blacksquare \]

예시

문제	계산	결과
8명 중 1등·2등·3등	\(P(8,3) = 8\times7\times6\)	336
5권 책을 책장에 나열	\(5! = 5\times4\times3\times2\times1\)	120
10자리 중 앞 4자리 PIN	\(P(10,4) = 10\times9\times8\times7\)	5,040

3.2 반복 있는 순열

정의: 반복 순열

\(n\) 가지 종류에서 중복을 허용하여 \(r\) 개를 순서 있게 나열하는 경우의 수:

\[ n^r \]

증명: 각 자리마다 \(n\) 가지 선택이 독립적으로 가능. 곱의 법칙: \(\underbrace{n \times n \times \cdots \times n}_{r} = n^r\) \(\quad\blacksquare\)

예시

문제	계산	결과
동전 5번 던질 때 결과 수	\(2^5\)	32
주사위 3번 굴릴 때 결과 수	\(6^3\)	216
4자리 PIN (0-9, 중복 허용)	\(10^4\)	10,000

3.3 같은 것이 있는 순열

정리: 중복 원소가 있는 순열

\(n\) 개의 원소 중 종류 1이 \(n_1\) 개, 종류 2가 \(n_2\) 개, …, 종류 \(k\) 가 \(n_k\) 개 (\(n_1 + n_2 + \cdots + n_k = n\))일 때, 이들 전체를 나열하는 경우의 수:

\[ \frac{n!}{n_1!\, n_2!\, \cdots\, n_k!} \]

증명: 전체 \(n!\) 에서 같은 원소끼리 자리를 교환해도 구별 불가하므로 각 종류 \(i\) 에 대해 \(n_i!\) 로 나눈다. \(\quad\blacksquare\)

예시

단어	계산	결과
STATISTICS (S×3, T×3, A×1, I×2, C×1)	\(\frac{10!}{3!\,3!\,1!\,2!\,1!}\)	50,400
MISSISSIPPI (M×1, I×4, S×4, P×2)	\(\frac{11!}{1!\,4!\,4!\,2!}\)	34,650
AABB	\(\frac{4!}{2!\,2!}\)	6

3.4 원형 순열 (Circular Permutations)

정리: 원형 순열

\(n\) 명을 원형으로 나열하는 경우의 수 (회전 동치 고려):

\[ (n-1)! \]

목걸이처럼 뒤집기도 동치이면: \(\dfrac{(n-1)!}{2}\)

증명: 한 사람을 기준(고정)으로 놓고 나머지 \(n-1\) 명을 나열. \((n-1)!\) \(\quad\blacksquare\)

예시: 6명이 원형 테이블에 앉는 경우의 수 \(= 5! = 120\)

4 조합 (Combinations)

4.1 이항계수

정의: 조합과 이항계수 \(\binom{n}{r}\)

\(n\) 개의 서로 다른 원소에서 \(r\) 개를 순서 없이 선택하는 경우의 수:

\[ \binom{n}{r} = \frac{n!}{r!\,(n-r)!}, \quad 0 \leq r \leq n \]

\(\binom{n}{0} = \binom{n}{n} = 1\), 관례적으로 \(\binom{n}{r} = 0\) if \(r < 0\) or \(r > n\).

순열과의 관계:

\[ P(n,r) = \binom{n}{r} \times r! \quad\Rightarrow\quad \binom{n}{r} = \frac{P(n,r)}{r!} \]

\(r\) 개를 선택하는 방법 × 선택된 \(r\) 개를 나열하는 방법 = 순열

예시

문제	계산	결과
10명 중 위원회 3명 선발	\(\binom{10}{3} = \frac{10!}{3!\,7!}\)	120
52장 카드에서 5장 패	\(\binom{52}{5}\)	2,598,960
로또 45개 중 6개	\(\binom{45}{6}\)	8,145,060

4.2 이항계수의 성질

정리: 이항계수의 주요 성질

\[ \begin{aligned} \text{대칭성:}& \quad \binom{n}{r} = \binom{n}{n-r} \\ \text{파스칼의 항등식:}& \quad \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \\ \text{반데르몽드의 항등식:}& \quad \binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} \\ \text{합:}& \quad \sum_{r=0}^n \binom{n}{r} = 2^n \\ \text{교대합:}& \quad \sum_{r=0}^n (-1)^r \binom{n}{r} = 0 \\ \end{aligned} \]

파스칼의 항등식 증명:

\(n\) 개에서 \(r\) 개를 선택할 때, 특정 원소 \(x\) 를 기준으로 분리: - \(x\) 를 포함하는 경우: 나머지 \(n-1\) 개에서 \(r-1\) 개 선택 → \(\binom{n-1}{r-1}\) - \(x\) 를 포함하지 않는 경우: \(n-1\) 개에서 \(r\) 개 선택 → \(\binom{n-1}{r}\)

합산하면 \(\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\) \(\quad\blacksquare\)

파스칼의 삼각형 (Pascal’s Triangle):

n=0:          1
n=1:        1   1
n=2:      1   2   1
n=3:    1   3   3   1
n=4:  1   4   6   4   1
n=5: 1  5  10  10   5   1

각 항은 위 두 항의 합 (파스칼의 항등식).

4.3 이항 정리 (Binomial Theorem)

정리: 이항 정리

임의의 실수 \(x, y\) 와 음이 아닌 정수 \(n\) 에 대해:

\[ (x + y)^n = \sum_{r=0}^n \binom{n}{r} x^r y^{n-r} \]

증명 (조합론적):

\((x+y)^n = \underbrace{(x+y)(x+y)\cdots(x+y)}_{n\text{개}}\) 를 전개할 때 \(x^r y^{n-r}\) 항은 \(n\) 개의 인수 중 \(r\) 개에서 \(x\) 를, 나머지 \(n-r\) 개에서 \(y\) 를 선택할 때 생긴다. 그 방법의 수가 \(\binom{n}{r}\) 이다. \(\quad\blacksquare\)

주요 특수값:

\[ x=y=1: \quad \sum_{r=0}^n \binom{n}{r} = 2^n \quad\text{(전체 부분집합의 수)} \]

\[ x=1, y=-1: \quad \sum_{r=0}^n (-1)^r\binom{n}{r} = 0 \]

\[ x=1, y=1, \text{미분}: \quad \sum_{r=0}^n r\binom{n}{r} = n \cdot 2^{n-1} \]

5 관련 주제

선행 지식

확률론의 언어: 집합론 — 집합 연산, 멱집합
확률론의 공리적 기초 — 유한 표본공간과 균등 분포
확률의 계산 규칙 — 조합론의 확률 적용

심화 주제

조합론 심화 — 중복조합, 다항계수, 비둘기집 원리, 포함-배제 원리, 코드 예시

후속 주제

Binomial Distribution — 이항계수가 확률 가중치로 등장
Poisson Distribution — 이항 분포의 극한
Conditional Probability — 경우의 수 기반 조건부 확률

관련 개념

Convergence in Probability — 큰 수의 법칙: 반복 실험의 극한
MLE — 다항 분포의 MLE에서 다항계수 등장