[5분 고등수학] 중복조합의 직관적 이해

 

 

중복조합은 n개 중에서 중복을 허락하여 r개를 택하는 경우의 수 입니다.

 

예를들어 a,b,c 라는 세개의 문자가 있다고 해봅시다. 중복을 허락하여 5개를 택하는 경우를 써봅시다. 

 

abbcc

abccc
abbbc
...
aaaaa
bbbbb
cccccc

 

등이 있을 것입니다. 이 모든 경우가 몇가지인지 구하는 것이 중복조합입니다. 위와 같은 상황은 중복조합으로 아래와 같이 나타냅니다.

 

$_3{H}_5$

n개 중에서 중복을 허락하여 r개를 뽑는 경우의 수는 아래와 같이 나타냅니다. 

 

$_n{H}_r$n​Hr​​

 

직접 세려고 하면 너무 많은데요. 놀랍게도, 이 중복조합을 계산하는 식을 사람들이 발견했습니다. 그 식을 발견해가는 과정을 말씀드리겠습니다. 

 

위 경우를 예로들어봅시다. 아래와 같이 문자와 문자 사이에 칸막이가 있다고 생각해봅시다. 

 

a/bb/cc

 

칸막이는 총 2개입니다. 칸막이를 다 쳐보면 아래와 같이 됩니다. 

 

a/bb/cc

a/b/ccc

a/bbb/c
...

aaaaa//

/bbbbb/

//cccccc

 

이 상황을 아래와 같이 표현해봅시다. 다섯개의 빈 칸이 있고, 두개의 칸막이가 있는 상황입니다. 

 

ㅁㅁㅁㅁㅁ   / /

 

위와 같은 조건에서 다섯개의 빈칸과 두개의 칸막이를 배열하는 겁니다. 같은 것이 있는 순열이 됩니다. 

 

한가지 경우를 예로 들어봅시다. 

 

ㅁㅁ / ㅁㅁ / ㅁ

 

위 경우는 아래와 같은 경우와 매칭됩니다. 

 

a a b b c

 

또 다른 예를 들어봅시다. 

 

 // ㅁㅁ ㅁ ㅁ ㅁ

 

위 경우는 아래와 같은 경우와 매칭됩니다. 

 

c c c c c

 

이와 같이 빈칸 다섯개와 칸막이 2개로, 위 예시의 모든 경우를 표현할 수 있습니다.  

 

따라서 아래 등식이 성립합니다. 

 

$_3{H}_5=\frac{7!}{5!2!}$

 

그리고 같은 것이 있는 순열을 조합으로 바꿔서 표현할 수 있습니다. 전체 자리가 7자리가 있구요. 이 중 칸막이가 들어갈 두개의 자리를 고르는 것으로도 바꿔서 생각할 수 있습니다. 또는 일곱 자리 중에서, 칸막이가 들어갈 2개의 자리를 제외한 5개의 빈칸을 고르는 것으로 생각할 수도 있습니다. 따라서 아래 등식이 성립합니다. 

 

$_3{H}_5=\frac{7!}{5!2!}=_7{C}_2=_7{C}_5$

 

일반화시켜봅시다.

 

$_n{H}_r$

위 식에 대해 생각해봅시다. 문자가 n개 있는 것이니까. 칸막이는 n-1개가 있습니다. 그리고 r개를 뽑는 것이니까, 빈칸은 r개 있습니다. 따라서 전체 자리 수는 r+n-1개 이구요. 여기서 빈칸의 자리 r개를 뽑으면 됩니다. 

$_n{H}_r=_{n-1+r}{C}_r$