순열과 조합

서로 다른 것을 늘어놓는 순열과 고르는 조합은 확률과 통계에서 이미 다루었다. 이산수학에서는 원순열, 염주순열처럼 ‘같은 것으로 보는 배열’을 세는 방법과 조합의 항등식을 중심으로 다룬다.

핵심 개념

  • ${}_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$이다.

정리

  • 같은 것으로 보는 배열은 ‘몇 개씩 묶였는가’로 나눈다.
  • 조합 항등식은 같은 대상을 두 방법으로 세어 증명한다.
알림: 보호된 콘텐츠입니다.