순열과 조합 — 경우의 수 체계

💡 왜 필요할까요?

비밀번호(순열)와 로또(조합)는 같은 숫자로도 경우의 수가 완전히 다릅니다. 암호학에서 128비트 키의 가짓수는 $2^{128} \approx 3.4 \times 10^{38}$으로, 우주의 원자 수보다 많습니다.

📜 역사 이야기

1654년 프랑스의 귀족 도박사 슈발리에 드 메레(Chevalier de Méré)가 수학자 블레즈 파스칼(Blaise Pascal, 1623~1662)에게 편지를 보냈습니다. "주사위를 4번 던질 때 6이 최소 한 번 나오는 것에 베팅하면 수익이 있는데, 두 주사위를 24번 던질 때 두 주사위 모두 6이 나오는 것에 베팅하면 왜 손해인가?" 이 질문이 확률론과 조합론의 역사를 바꾸었습니다. 파스칼은 친구 페르마(Fermat)와 서신을 주고받으며 이 문제를 해결했고, 그 과정에서 **파스칼의 삼각형(Pascal's Triangle)**을 체계화했습니다. 삼각형의 각 항은 $_nC_r$값과 정확히 일치하며, 위 두 항의 합이 아래 항이 되는 성질이 조합론의 핵심 항등식 $_nC_r + _nC_{r+1} = _{n+1}C_{r+1}$을 표현합니다. 이 삼각형은 사실 중국의 양휘(楊輝, 1238~1298)와 페르시아의 오마르 하이얌이 수백 년 전에 알고 있었지만, 파스칼이 이를 확률론과 결합하여 근대 수학의 언어로 정리했습니다. 순열(Permutation)과 조합(Combination)의 구분은 수학적으로 단순하지만 현실에서 매우 중요합니다. 비밀번호는 순열(순서 중요), 로또는 조합(순서 무관)입니다. 현대 암호학, 알고리즘 설계, 머신러닝의 특성 선택(Feature Selection), 임상시험의 표본 설계까지 조합론이 기반을 이룹니다. DNA 염기 배열 분석도 순열과 조합으로 경우의 수를 계산합니다.

"인간은 자연에서 가장 연약한 갈대에 불과하다. 그러나 그것은 생각하는 갈대다." — 블레즈 파스칼

🔬 직접 발견하기

📐 공식 이해하기

**순열** $_nP_r$: $n$개 중 $r$개를 **순서 있게** 나열하는 방법의 수. **조합** $_nC_r$: $n$개 중 $r$개를 **순서 없이** 선택하는 방법의 수. $_nC_r = \dfrac{_nP_r}{r!}$ — 같은 선택에서 순서 $r!$가지를 하나로 통합.

$n$

전체 원소의 수

$r$

선택하는 원소의 수 $(0 \le r \le n)$

$n!$

n 팩토리얼 = $n \times (n-1) \times \cdots \times 1$, $0! = 1$

_nP_r

순열 — $n$개에서 $r$개를 순서 있게 나열

_nC_r

조합 — $n$개에서 $r$개를 순서 없이 선택

1. 1
   $n!$ (팩토리얼): $n$개를 모두 나열하는 방법 = $n \times (n-1) \times \cdots \times 1$
2. 2
   순열: 첫 자리 $n$가지, 둘째 자리 $n-1$가지, ..., $r$번째 자리 $n-r+1$가지 → $\dfrac{n!}{(n-r)!}$
3. 3
   조합: 순열에서 순서 $r!$가지를 같은 것으로 보면 → $\dfrac{_nP_r}{r!} = \dfrac{n!}{r!(n-r)!}$
4. 4
   파스칼 항등식: $_nC_r + _nC_{r+1} = _{n+1}C_{r+1}$ (파스칼의 삼각형)

📝 퀴즈로 확인하기

📋 수능 기출 문제