순열과 조합

서로 다른 대상을 순서를 생각하여 늘어놓으면 순열, 순서를 생각하지 않고 고르면 조합이다. 반장·부반장 뽑기는 순열, 대표 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$ (파스칼의 법칙)
파스칼 삼각형과 위의 두 수를 더해 아래 수를 만드는 규칙
파스칼 삼각형의 각 수는 조합 ${}_nC_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!}$
  • 파스칼의 법칙은 ‘특정 원소를 포함하는가’로 나누어 센 결과이다.
알림: 보호된 콘텐츠입니다.