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

개요

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

첫 포스팅에서 알아봤듯이 중복 조합은 "n개에서 r개를 뽑되, 순서를 신경쓰지 않고, 복원 추출하는 경우의 수"입니다.

 

중복 조합의 경우의 수를 계산할 때는 보통 "막대기를 배치하는 경우의 수"로 치환해서 생각합니다.

"막대기를 배치"한다는게 어떤 의미인지 알아보기 위해 예제를 한 번 들어보겠습니다.

막대기 배치 예시

a, b, c라고 써있는 영어 카드가 있다고 생각해봅시다.

이때 순서를 신경쓰지 않고 4번 복원 추출로 뽑았을 때 나올 수 있는 경우의 수는 몇 개일까요?

 

먼저 생각할 수 있는 것은

a가 네 번 나오는 경우 -> aaaa

b가 네 번 나오는 경우 -> bbbb

c가 네 번 나오는 경우 -> cccc입니다.

그 외에 baaa, abaa, aaba, aaab등이 있습니다.

하지만 "조합"이므로 baaa와 abaa, aaba, aaab는 같은 경우로 칩니다.

abbc와 cbab도 같은 경우로 칠텐데 이런 것들을 다 고려하기 조금 복잡합니다.

 

그래서 대신에 막대기라는 개념을 도입합니다.

왜 막대기를 도입하고 왜 이런식으로 해석하는지 처음에는 이해가 안 갈테지만 일단 진행해봅시다.

 

먼저 뽑아야 하는 갯수만큼 카드를 배치합니다. 예제에서는 4번이므로 4개입니다.

그리고 막대기를 알파벳 갯수 - 1개 만큼 배치합니다. 예제에서는 3 -1 = 2개 입니다.

 

문자로 간략하게 표현하기 위해 카드를 X로 두고, 막대기를 I로 둡시다.

만약 막대기를 앞에 전부 배치하고 카드를 뒤에 배치한다고 하면 IIXXXX처럼 될 것입니다.

여기서 막대기끼리 구분하지 않고, 카드끼리 구분하지 않습니다.

 

그리고 "막대기와 카드가 배열된 순서에 따라 특정 형태로 카드를 뽑았다"고 생각하는 것입니다.

예를 들어 XXIXIX 이런식으로 카드들 사이에 막대기가 2개 있는 경우

모든 막대기 왼쪽에 있는 카드들은 a

막대기 두 개 사이에 있는 카드는 b

모든 막대기 오른쪽에 있는 카드는 c라고 보는 겁니다.

그럼 XXIXIX라는 상황은 aabc가 됩니다.

 

카드를 배열하는 또 다른 예를 들어보자면

XIXXIX -> abbc

IXXXIX -> bbbc

XXIIXX -> aacc

이렇게 됩니다.

 

그리고 마지막으로는 이렇게 배치할 수 있는 경우의 수를 계산하는 것입니다.

이렇게 계산된 결과가 a, b, c 알파벳 카드를 중복 조합으로 뽑는 경우의 수와 같습니다.

막대기를 배치하는 경우의 수가 중복 조합의 경우의 수와 같은 이유

먼저 aabc를 뽑은 경우에 대해서 생각해봅시다.

aabc는 중복 조합으로 봤을 때 abca, acba, aacb 순서로 뽑은 경우와 같은 경우로 칩니다.

즉, "a를 두 번 뽑고, b를 한 번 뽑고, c를 한 번 뽑는 모든 경우"를 세고 나서 중복되는 것들을 없애고 하나로 남겨야 중복 조합의 경우의 수를 알 수 있게 됩니다.

 

모든 경우의 수를 세보고 중복되는 것을 제거하는 것은 어렵기 때문에 막대기를 배치하는 방식을 사용하는 것입니다.

생각해보면 "a를 두 번 뽑고, b를 한 번 뽑고, c를 한 번 뽑는 모든 경우" 을 막대기 방식을 통해서 표현할 수 있는 유일한 방법은 XXIXIX 이렇게 배치하는 경우 밖에 없습니다.

막대기를 하나라도 다른 위치에 배치한다면 "a를 두 번 뽑고, b를 한 번 뽑고, c를 한 번 뽑는" 상황을 대응할 수 없습니다.

예를 들어 XIXXIX 이렇게 바꿔버리면 미리 설정한 규칙에 의해서 "a를 한 번 뽑고, b를 두 번 뽑고, c를 한 번 뽑는" 상황이 되어버립니다.

막대기 방식으로 배치할 수 있는 모든 경우의 수만 보는 것은 결국 중복 조합에서 제거되어야 하는 모든 경우의 수를 제거한 경우만 보게 되는 것입니다.

따라서 막대기를 배치하는 경우의 수가 중복 조합의 경우의 수와 같게 되는 것입니다.

막대기를 배치하는 경우의 수를 계산하는 법

이제 다음으로 알아야 할 것은 막대기를 배치하는 경우의 수를 어떻게 계산하느냐입니다.

이것은 막대기의 위치를 뽑는 경우의 수로 생각할 수 있습니다.

 

위 예제에서 문자의 수는 X가 4개, I가 2개 해서 총 6개였습니다.

아직 문자들이 배치되지 않았다고 생각했을 때 막대기 하나를 배치할 수 있는 선택지는 6자리 중에 하나입니다.

그리고 다음 막대기를 배치할 수 있는 선택지는 나머지 5자리 중에 하나입니다.

첫 번째 막대기와 두 번째 막대기는 서로 다르다고 구분하지 않기 때문에 이 과정은 저번 포스팅에서 이야기한 "조합"과 같다는 것을 아실 수 있을 겁니다.

즉, 6자리 중에 2개를 뽑는 것 \(_{6}C_{2}\)가 됩니다.

막대기를 뽑으면 자동으로 카드의 위치가 정해지는 것이기 때문에, 카드의 위치를 정하는 경우의 수인 \(_{6}C_{4}\)와 같습니다.

 

여기서 6이라는 숫자는 문자의 수이므로, 가장 처음 막대기 예제를 이야기할 때 나온 규칙에 의해서 n + r - 1로부터 도출된 수입니다.

4라는 숫자는 뽑는 숫자이므로 r로부터 도출된 숫자입니다.

 

위 예제를 일반화해서 "n개에서 r개를 중복 조합으로 뽑는 경우의 수"를 수식으로 표현하면 아래와 같습니다.

$$_{n}H_{r}=_{n+r-1}C_{r}=_{n+r-1}C_{n-1}$$

결론

지금까지 순열, 조합, 중복 순열, 중복 조합에 대해서 알아봤습니다.

공식을 외우는 것도 중요하지만 기왕이면 어떻게 공식이 유도되었는지까지 알아두면 좋을 것 같습니다.