9장) 경우의 수와 확률 - 조합

■ 조합(Combination)의 수: 순서에 상관하지 않고 뽑는 경우의 수

순서대로 나열한 다음에 그 순서로 인해 중복된 경우들을 나눗셈으로 상쇄한다는 것을 이용하여 아래와 같은 수식으로 나타낼 수 있다.

$$\binom{n}{k}=\frac{_{n}\mathrm{P}_{k}}{k!}=\frac{n!}{(n-k)!}\cdot \frac{1}{k!}=\frac{n!}{k!(n-k)!}$$

 

곱셈은 교환법칙이 성립.

즉, k개를 뽑는 경우의 수는 결국 (n-k) 개를 뽑는 경우의 수와 같아짐.

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!k!}=\binom{n}{n-k}$$

 

◇ k에 몇몇 특정한 값을 넣으면 다음과 같은 결과를 얻음

$$\binom{n}{0}=1$$

$$\binom{n}{1}=\frac{n!}{(n-1)!}=n$$

$$\binom{n}{n-1}=\binom{n}{1}=n$$

$$\binom{n}{n}=\binom{n}{0}=1$$

 

예제: 4X3 격자 모양으로 된 길이 있다. 출발 지점에서 도착 지점으로 가는 최단 경로는 모두 몇 개나 있는가? 가장 왼쪽 상단 점: 출발지점
가장 오른쪽 하단 점: 도착지점

풀이: 최단 경로의 경우에는 오른쪽으로 4번, 아래로 3번 이동하는 경우일 것이다.

이것의 경우에는 순서와 상관 없이 적용된다.

오른쪽으로 이동하는 횟수 4번과 아래로 이동하는 횟수 3번을 순서 없이 나열하는 수라고 볼 수 있다.

$$\binom{7}{4}=\frac{7!}{4!\cdot (7-4)!}=35$$

 

■ 중복 조합: 한 번 포함된 대상이라도 계속해서 고를 수 있는 조합의 수

n종류의 대상 중에서 k개를 중복해서 고르는 중복 조합의 수는 다음과 같은 기호로 나타냄.

$$_{n}\mathrm{H}_{k}$$

 

일반적인 조합의 수 nPk에서는 고르려는 대상의 수 k가 전체 대상의 수 n 이하여야 한다.

하지만 중복 조합에서는 같은 대상이라도 거듭 고를 수 있으므로 그런 제한이 사라진다.

$$_{n}\mathrm{H}_{k}=\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$$

 

예제: 다음 방정식의 해는 모두 몇 개나 되는가? (단, x, y, z는 모두 음이 아니다.)

x+y+z = 4

풀이: 모두 음이 아니기 때문에 1씩 값을 부여할 대상을 3개중 4번 고른다고 보면 된다.

$$_{3}\mathrm{H}_{4}=\binom{6}{4}=\binom{6}{2}$$

이므로 다음과 같이 계산할 수 있다.

$$\binom{6}{2}=\frac{6!}{2!\cdot (6-2)!}=\frac{6!}{2!\cdot 4!}=\frac{5\cdot 6}{2!}=15$$