수학시간
고등학교 확률과 통계 · 경우의 수

중복을 허용하는 경우의 수와 이항정리

같은 대상을 여러 번 선택하거나 서로 같은 대상을 나열할 때의 계산 원리를 알아보고, 조합이 이항전개의 계수로 이어지는 과정을 살펴봅니다.

중복순열
같은 것이 있는 순열
중복조합
이항정리

1 중복순열

서로 다른 \(n\)개에서 중복을 허용하여 \(r\)개를 택해 일렬로 나열하는 경우를 중복순열이라고 합니다. 각 자리에서 \(n\)개 중 하나를 독립적으로 선택할 수 있습니다.

중복순열의 수
\({}_n\Pi_r=n^r\)

\(n\)은 선택할 대상의 종류 수, \(r\)은 나열할 자리 수입니다.

왜 \(n^r\)일까요?

  1. 첫째 자리에 놓을 수 있는 대상은 \(n\)개입니다.
  2. 중복을 허용하므로 나머지 각 자리도 모두 \(n\)가지입니다.
  3. 곱의 법칙에 따라 \(n\)을 \(r\)번 곱합니다.

예제 · 깃발 신호

청색 깃발과 백색 깃발 중 하나를 한 번에 하나씩 세 번 들어 올려 만들 수 있는 서로 다른 신호는 몇 가지일까요?

  1. 매번 청색 또는 백색을 선택하므로 각 횟수의 선택은 \(2\)가지입니다.
  2. 같은 색을 다시 들어도 되므로 중복을 허용합니다.
\({}_2\Pi_3=2^3=8\text{가지}\)

2 같은 것이 있는 순열

서로 같은 대상끼리는 자리를 바꾸어도 새로운 나열이 되지 않습니다. 따라서 전체 순열의 수에서 같은 대상끼리 자리를 바꾸는 경우를 나누어 줍니다.

같은 것이 있는 순열의 수
\(\displaystyle \frac{n!}{p!q!\cdots}\)

\(p+q+\cdots=n\)이고, 같은 대상이 각각 \(p\)개, \(q\)개, \(\cdots\)개인 경우입니다.

예제 · 숫자 카드 나열

숫자 \(1\)이 적힌 카드 \(2\)장과 숫자 \(2\)가 적힌 카드 \(4\)장을 모두 나열하여 만들 수 있는 여섯 자리 자연수는 몇 개일까요?

\(\displaystyle \frac{6!}{2!4!}=\frac{720}{2\times24}=15\text{개}\)

최단 경로 바꾸어 보기

오른쪽과 위쪽 이동 횟수를 바꾸면 격자와 최단 경로의 수가 함께 변합니다.

전체 최단 경로

3 중복조합

서로 다른 \(n\)개에서 중복을 허용하여 \(r\)개를 선택하되 선택 순서를 생각하지 않는 경우를 중복조합이라고 합니다.

중복조합의 수
\({}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r\)

선택한 대상 \(r\)개와 칸막이 \(n-1\)개를 나열하는 원리를 이용합니다.

중복순열과 구별하기

초코-바닐라와 바닐라-초코를 서로 다른 결과로 보면 중복순열이고, 맛별 개수만 같으면 같은 결과로 보면 중복조합입니다.

시뮬레이션 · 세 가지 맛에서 다섯 개 선택하기

각 맛을 \(0\)개 이상 선택할 수 있습니다. 서로 다른 배분 결과를 만들어 합이 항상 \(5\)인지 확인해 보세요.

초코
0개
바닐라
0개
딸기
0개

현재 배분

가능한 전체 배분은 \({}_3\mathrm{H}_5={}_7\mathrm{C}_5=21\)가지입니다.

칸막이 모델

같은 아이스크림 \(5\)개를 별표로, 세 맛을 나누는 칸막이 \(2\)개를 막대로 나타내면 \(7\)자리에서 별표 \(5\)개의 자리를 고르는 문제와 같습니다.

\(\displaystyle {}_3\mathrm{H}_5=\frac{7!}{5!2!}={}_7\mathrm{C}_5=21\)

예제 · 학용품 선택

연필, 지우개, 공책의 세 종류에서 합하여 \(6\)개를 고르는 방법은 몇 가지일까요? 각 종류는 충분히 있고, 어떤 종류는 하나도 고르지 않아도 됩니다.

  1. 세 종류에서 중복을 허용하여 \(6\)개를 선택합니다.
  2. 선택한 순서는 생각하지 않으므로 중복조합을 이용합니다.
\({}_3\mathrm{H}_6={}_8\mathrm{C}_6=28\text{가지}\)

4 이항정리와 파스칼의 삼각형

\((a+b)^n\)을 전개할 때 \(a^{n-r}b^r\)가 만들어지는 횟수는 \(n\)개의 인수 중 \(b\)를 선택하는 방법의 수 \({}_n\mathrm{C}_r\)와 같습니다.

이항정리
\(\displaystyle (a+b)^n=\sum_{r=0}^{n}{}_n\mathrm{C}_r a^{n-r}b^r\)

\({}_n\mathrm{C}_r\)를 이항계수라고 합니다.

예제 · 전개식의 계수

\((x+2y)^4\)의 전개식에서 \(x^2y^2\)의 계수를 구해 봅시다.

  1. \(x^{4-r}(2y)^r\)에서 \(y\)의 지수가 \(2\)이므로 \(r=2\)입니다.
  2. \({}_4\mathrm{C}_2x^2(2y)^2=6\times4x^2y^2=24x^2y^2\)입니다.
따라서 \(x^2y^2\)의 계수는 \(24\)입니다.

시뮬레이션 · 파스칼의 삼각형

양 끝은 \(1\), 그 사이의 수는 바로 위의 두 수를 더하여 만듭니다.

관찰할 규칙
  1. \({}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}\)이므로 각 행은 좌우 대칭입니다.
  2. \(n\)번째 행의 합은 \((1+1)^n=2^n\)입니다.

5 경우의 수 선택 기준

순서를 생각하는지와 같은 대상을 다시 선택할 수 있는지를 먼저 확인하면 알맞은 계산 방법을 고를 수 있습니다.

순서 고려 · 중복 허용 안 함

순열

\({}_n\mathrm{P}_r\)
순서 고려 안 함 · 중복 허용 안 함

조합

\({}_n\mathrm{C}_r\)
순서 고려 · 중복 허용

중복순열

\({}_n\Pi_r=n^r\)
순서 고려 안 함 · 중복 허용

중복조합

\({}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r\)

6 스스로 확인하기

문제 1

네 개의 숫자 \(1,2,3,4\)를 중복하여 사용할 수 있을 때 만들 수 있는 세 자리 자연수는 몇 개인가요?

문제 2

문자 \(\mathrm{A},\mathrm{A},\mathrm{B},\mathrm{B},\mathrm{C}\)를 모두 나열하는 방법은 몇 가지인가요?

문제 3

\((x+2y)^5\)의 전개식에서 \(x^3y^2\)의 계수를 구해 보세요.