서로 다른 것을 늘어놓는 순열과 고르는 조합은 확률과 통계에서 이미 다루었다. 이산수학에서는 원순열, 염주순열처럼 ‘같은 것으로 보는 배열’을 세는 방법과 조합의 항등식을 중심으로 다룬다.
핵심 개념
- ${}_nP_r=\frac{n!}{(n-r)!}$, ${}_nC_r=\frac{n!}{r!(n-r)!}$
- 원순열: $(n-1)!$
- 염주순열(뒤집어도 같은 것): $\frac{(n-1)!}{2}$ ($n\ge3$)
- 같은 것이 있는 순열: $\frac{n!}{p!q!r!}$
핵심 정리
- 원순열의 수는 $\frac{n!}{n}=(n-1)!$이다.
- 방데르몽드 항등식: ${}_{m+n}C_r=\sum_{k}{}_mC_k\cdot{}_nC_{r-k}$
증명 보기
원순열. $n$명을 일렬로 세우는 $n!$가지의 각 배열을 원형으로 구부리면, 한 원형 배열은 시작점을 어디로 잡느냐에 따라 일렬 배열 $n$개에서 나온다. 즉 $n!$개의 일렬 배열이 $n$개씩 같은 원형 배열로 묶이므로 원형 배열은 $\frac{n!}{n}=(n-1)!$가지이다. 염주는 뒤집은 것도 같으므로 다시 $2$로 나눈다.
방데르몽드 항등식 (조합적 증명). 남학생 $m$명, 여학생 $n$명 중 $r$명을 뽑는 방법을 두 가지로 센다. 한꺼번에 세면 ${}_{m+n}C_r$이다. 남학생 수 $k$로 나누어 세면 남학생 $k$명, 여학생 $r-k$명을 뽑는 ${}_mC_k\cdot{}_nC_{r-k}$를 모든 $k$에 대해 더한 것이다. 같은 것을 센 것이므로 두 값이 같다. $\blacksquare$
예제
- 서로 다른 구슬 $6$개로 만드는 목걸이: $\frac{5!}{2}=60$
- 부모 $2$명과 자녀 $3$명이 원탁에 앉을 때 부모가 이웃하는 방법: 부모를 한 묶음으로 보면 $4$개의 원순열 $3!$, 부모끼리 자리 바꿈 $2$, 합 $12$가지
확인 문제
${}_nC_0^2+{}_nC_1^2+\cdots+{}_nC_n^2={}_{2n}C_n$임을 보이시오.
풀이 보기
방데르몽드 항등식에서 $m=n$, $r=n$으로 두면 ${}_{2n}C_n=\sum_k{}_nC_k\,{}_nC_{n-k}$이다. ${}_nC_{n-k}={}_nC_k$이므로 $\sum_k({}_nC_k)^2$이다.
정리
- 같은 것으로 보는 배열은 ‘몇 개씩 묶였는가’로 나눈다.
- 조합 항등식은 같은 대상을 두 방법으로 세어 증명한다.
