Combinations | 조합

우리에게 nCr로 더욱 친숙한 조합은, 한 집합에서 특정 요소들을 뽑을 수 있는 가짓수를 칭합니다.

여기서 중요한 점은 permutation과는 다르게 순서가 중요하지 않다라는 점 입니다.

 

예를 들어 학교에서 우리 반의 대표 학생을 3명 뽑는다고 했을 때, 뽑히는 순서는 아무런 상관이 없겠죠? 

3명의 학생이 [김준수, 최나영, 박민지] 라고 하면, 이는 [김준수, 박민지, 최나영]을 뽑았을 때나 [박민지, 최나영, 김준수]를 뽑았을 때나 같은 조합입니다. 그렇죠?

 

Combinations 공식 nCr은 다음과 같습니다.

nCr = n! / (n-r)! * r!         (중복 허용 X)

 

우리의 예시에서 우리 반의 총 학생 수를 10명이라고 해봅시다.

그렇다면 n = 10, r = 3이 되고, 10C3 = 10! / 7! * 3! = 120 이므로,

10명의 학급에서 3명의 대표 학생을 뽑는 조합의 수는 총 120가지가 존재합니다.

 

 

nCr의 값을 그래프로 나타내보면, n / 2를 기준으로 대칭을 이룹니다.

한가지 예시를 들어 설명하겠습니다.

 

총 6개의 과일중에 피크닉에 가져갈 과일 조합을 정하고 있습니다.

2개의 과일을 가져갈 때, 가능한 조합은 6C2 = 15개 입니다.

3개의 과일을 가져갈 때, 가능한 조합은 6C3 = 20개 입니다.

4개의 과일을 가져갈 때, 가능한 조합은 6C4 = 15개 입니다.

0개, 1개, 5개, 6개에 대해서도 계산해보면 정확하게 3개의 과일을 가져갈때를 기준으로 대칭을 이룹니다.

 

이는 문제를 다르게 해석하면 당연한 일입니다.

6개의 과일 중 4개의 과일의 조합을 계산하는 6C4는 다르게 말하면 2개의 놓고갈 과일 조합을 계산함과 같습니다.

즉, 6C2 = 6C4일 수 밖에 없는 것 입니다.

 

확장해서 보자면, nCr = nC(n-r)입니다.

이러한 특성을 잘 이해하고 활용하면 확률 계산에 있어 더욱 용이하겠죠?

 

 

지금까지 알아본 조합 nCr은 중복을 허용하지 않는 조합입니다.

예를 들어 A, B, C, D, E 중에서 3개를 고르는 조합이라면, 

[A, A, B]는 존재할 수가 없습니다.

 

만약 중복을 허용하는 조합의 경우에는 값이 어떻게 될까요?

중복을 허용하는 경우의 조합은 (n + r -1)Cr 로 계산하고, 또는 nHr로 표기합니다.

 

위의 예시에서 중복을 허용하지 않는다면: 5C3 = 10 이지만,

중복을 허용한 조합의 수는: 7C3 = 35 입니다.