[모듈식 확률과 통계] 1.경우의 수 (11)중복조합

[확률과통계]-[1.경우의 수]-[①순열과 조합]-[(11)중복조합]

중복조합

서로 다른 n개의 문자가 있습니다. 이 중에서 r개를 택할건데, 중복을 허락해서 택하는 것입니다. 

예를들어봅시다. 

a,b

두 문자가 있습니다. 중복을 허락해서 문자 두개를 뽑는 것입니다. 어떤 경우가 있을까요??

aa

ab

bb

세가지가 있습니다. ba는요? 순열이 아니라 '조합'입니다. ab와 ba는 같은 경우입니다. 

이해되시나요? 문자를 셋으로 늘려봅시다. 

a,b,c 

세 문자에서 중복을 허락해서 문자 두개를 뽑아봅시다. 

aa

bb

cc

ab

ac

bc

입니다. 

n개 중에서 r개를 중복을 허락하여 뽑는 경우의 수를 '중복 조합'이라고 하고, 기호로 아래와 같이 나타냅니다. 

중복 조합은 아래와 같이 구합니다. 

[증명]

위 수식이 어떻게 성립하는지 이해해봅시다. 중복조합은 '이해생략기억'으로 풀게되는 영역이지만 그래도 이해하고 넘어갑시다. 한가지 예시를 통해 설명하고 일반화하겠습니다. 

a,b,c 세 문자에서 중복을 허락하여 5개의 문자를 뽑는 상황입니다. 아래와 같은 경우들이 있을 것입니다. 

aaaaa

bbbcc

aabbc

abccc

등이 있을텐데, 칸막이가 있다고 해봅시다. 문자와 문자의 경계를 나누는 칸막이입니다. 

aaaaa//

/bbb/cc

aa/bb/c

a/b/ccc

따라서 우리는 이 상황을 다섯개의 자리가 있고, 두개의 칸막이가 있는 상황으로 바꿔 생각할 수 있습니다. 

OOOOO  //

칸막이는 같은 곳에 두개가올 수도 있습니다. 예를들어 아래의 상황을 생각해봅시다. 

OOOO//O 

이건 어떤 배열일까요? 

OOOO//O → aaaac

입니다. 따라서 위 문제는 '같은 것이 있는 순열' 문제가 됩니다. 

여기서 7은 뽑는 수 5와 칸막이 수 2가 더해진 것입니다. 그런데 칸막이 수 2는 문자의 수에서 1을 뺀 값입니다. 

따라서 이렇게 일반화 할 수 있습니다. 

서로 다른 n개에서 중복을 허락하여 r개를 뽑는 경우의 수는 아래와 같다. 

위 식은 조합으로 나타낼 수 있고 아래 결론을 얻습니다.