순열, 조합, 중복 순열, 중복 조합 (4/5)

이번 포스팅에서는 조합에 대해 알아보겠습니다.

조합은 순열을 통해서 유도할 수 있습니다.

 

먼저 첫 포스팅에서 알아 보았던 조합의 정의에 대해서 다시 한 번 생각해봅시다.

조합은 "n개 중에서 r개를 뽑을 때, 순서를 고려하지 않고, 비복원 추출하는 경우의 수"입니다.

순열과 조합의 다른 점은 순서를 고려하냐 마냐입니다.

 

저번 포스팅의 예제인, 3개의 카드에서 2개를 뽑는 경우의 수를 다시 한 번 생각해봅시다.

위 이미지에서 결과중 하나인 (1,2)와 다른 결과인 (2,1)은 조합 입장에서는 순서를 신경쓰지 않기 때문에 같은 "경우"입니다.

즉, 경우의 수를 계산할 때 2개가 아닌 1개로 친다는 의미이죠

똑같이, (1,3)과 (3,1)도 같은 것으로 치고, (2,3)과 (3,2)도 같은 것으로 칩니다.

결론적으로 위 예제에서 순열의 모든 경우의 수에서 2를 나누면 조합의 경우의 수가 됩니다.

이로써 순열과 조합이 어느 정도 연관성이 있음을 알 수 있습니다.

 

n과 r의 개수를 늘려 1~5까지의 숫자가 있는 5장의 카드 중에서 3장을 뽑는 경우의 수를 생각해보겠습니다.

나올 수 있는 경우 중에는 1번, 2번, 3번 카드만 뽑았다고 가정했을 때 (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)가 있을 겁니다.

순열 입장에서는 모두 다른 경우이지만, 조합 입장에서는 같은 경우입니다.

순열의 경우의 수를 계산할 때는 6개이지만, 조합의 경우의 수를 계산할 때는 1개가 된다는 의미입니다.

 

먼저 6이라는 숫자가 어떻게 나온 것인지 생각해봅시다.

이는 1~3번 카드를 재배열하는 경우의 수와 같습니다.

저번 포스팅에서 알아봤듯이 결과는 \(3!=6\)이 됩니다.

 

또한 이렇게 중복되는 경우는 1번 2번 4번 카드를 뽑았을 때, 1번 2번 5번 카드를 뽑았을 때, 2번 3번 4번 카드를 뽑았을 때도 존재합니다. 즉, 서로 다른 3장을 뽑는 모든 경우에 중복이 있으므로 전체의 경우의 수에서 6으로 나눠줘야 한다는 의미입니다.

 

결론적으로 "n개 중에 r개를 순서 상관없이 뽑는 경우의 수"는 "n개 중에 r개를 순서 상관있이 뽑는 경우의 수"에서 "r개를 재배열하는 경우의 수를 나눈 수"가 됩니다.

수식으로 표현하면 아래와 같이 됩니다.

$$_{n}C_{r}=\frac{_{n}P_{r}}{n!}=\frac{n!}{(n-r)!r!}$$

수식이 조금 복잡해보일 수 있지만 천천히 생각해보면 많이 어렵지 않습니다.

 

이로써 조합에 대해서 알아보았습니다.

다음 포스팅에서는 마지막으로 "중복 조합"에 대해서 알아보도록 하겠습니다.