서로 다른 대상을 순서를 생각하여 늘어놓으면 순열, 순서를 생각하지 않고 고르면 조합이다. 반장·부반장 뽑기는 순열, 대표 2명 뽑기는 조합이다.
핵심 개념
- 순열: ${}_nP_r=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}$
- 조합: ${}_nC_r=\frac{{}_nP_r}{r!}=\frac{n!}{r!(n-r)!}$
- 중복순열: ${}_n\Pi_r=n^r$
- 같은 것이 있는 순열: $n$개 중 같은 것이 $p,q,\dots$개이면 $\frac{n!}{p!q!\cdots}$
- 원순열: 서로 다른 $n$개를 원형으로 배열하는 방법 $(n-1)!$
핵심 정리
- ${}_nC_r={}_nC_{n-r}$
- ${}_nC_r={}_{n-1}C_{r-1}+{}_{n-1}C_r$ (파스칼의 법칙)
증명 보기
조합 공식. $n$개에서 $r$개를 순서대로 뽑는 순열 ${}_nP_r$가지를 생각하자. 같은 $r$개를 고른 경우가 순서만 다르게 $r!$번씩 세어졌으므로 ${}_nC_r=\frac{{}_nP_r}{r!}$이다.
대칭성. $r$개를 고르는 것은 남길 $n-r$개를 고르는 것과 같으므로 ${}_nC_r={}_nC_{n-r}$이다.
파스칼의 법칙. $n$개 중 특정한 하나 $a$를 생각하자. $r$개를 고르는 방법은 ‘$a$를 포함하는 경우'(나머지 $n-1$개에서 $r-1$개 선택)와 ‘$a$를 포함하지 않는 경우'(나머지 $n-1$개에서 $r$개 선택)로 나뉜다. 합의 법칙에 의해 ${}_nC_r={}_{n-1}C_{r-1}+{}_{n-1}C_r$이다. $\blacksquare$
이처럼 ‘세는 방법을 두 가지로 생각해서 같다고 놓는’ 증명을 조합적 증명이라 한다.
예제
- $5$명 중 반장, 부반장을 뽑는 방법: ${}_5P_2=20$, 대표 $2$명을 뽑는 방법: ${}_5C_2=10$
- MISSISSIPPI의 문자를 늘어놓는 방법: $\frac{11!}{1!4!4!2!}=34650$
- $6$명이 원탁에 앉는 방법: $5!=120$
확인 문제
남학생 $4$명, 여학생 $3$명 중 $3$명을 뽑을 때 여학생이 적어도 한 명 포함되는 방법의 수를 구하시오.
풀이 보기
전체 ${}_7C_3=35$에서 남학생만 뽑는 경우 ${}_4C_3=4$를 빼면 $31$가지이다. (‘적어도’는 여사건으로 세는 것이 편하다.)
정리
- 순서가 있으면 순열 ${}_nP_r$, 없으면 조합 ${}_nC_r=\frac{{}_nP_r}{r!}$
- 파스칼의 법칙은 ‘특정 원소를 포함하는가’로 나누어 센 결과이다.
