중복조합 - 공식 유도, 아이디어, 적용

중복조합 - 공식 유도, 아이디어, 적용

 

이 포스팅은 중복조합의 공식 유도와 아이디어, 그 적용에 관한 글 입니다.

 

 

중복조합은 교육과정이 개편되면서 새로 추가된 내용으로, 미적분과 통계기본에서 처음 소개됩니다. 경우의 수를 다루는 툴 중에는 순열, 중복순열, 조합, 중복조합 등이 있는데요. 이 중 중복조합이라는 개념은 기존의 조합의 개념을 다소 새로운 접근을 통해 확장해 나가는 게 특징입니다.

 

이 글이 필요한 학생은

1. 중복조합 공식이 궁금한 학생

2. 중복조합 공식 유도 과정이 궁금한 학생

3. 중복조합 관련 응용문제를 해결함에 있어서 어려움을 느끼는 학생

4. 경우의 수 단원을 헤매는 학생

입니다.

 

제 글이 많은 학생들에게 도움이 됐으면 하는 바람입니다.

 

---

중복조합 공식과 유도

 

1) 중복조합

중복조합은 서로 다른 n개를 중복을 허락하여 r개 선택하는 모든 경우의 수를 뜻합니다. 여기서 r은 (중복을 허락하기 때문에) n보다 커도 상관없습니다. (ex, 세 개중 중복을 허락해서 다섯개를 뽑을 수 있습니다.)

 

 

 

n개중 r개를 뽑는 중복조합은 nHr로 표현하며, 이를 구하는 공식은 아래와 같이 주어집니다.

 

2) 중복조합의 공식 유도

지금부터 중복조합의 공식을 유도해드리겠습니다..

 

공식을 유도하다보면 거기에 녹아있는 아이디어를 배울 수가 있고 그 아이디어를 다른 문제에 적용 할 수 있기 때문에 공식을 직접 유도해 보는 것은 좋은 공부방법이라 할 수 있습니다.

 

<중복조합 공식 유도>

세 변수 x, y, z를 중복해서 5개 뽑는 경우의 수를 구해봅시다. 순서를 고려하지 않기 때문에 중복순열과는 다릅니다. 어떤 조합이 있을 수 있을까요?

 

(x, x, y, y, z)

(x, y, y, y, z)

(y, y, z, z, z)

(x, x, x, y, y)

(x, x, x, x, x)

 

예로 든 조합들은 모두 3개 중 5개를 뽑는 중복조합에 포함되는 것들입니다. 편의상 동종(同種)끼리는 한데 모아서 쓰고, 이종(異種)끼리는 구분할 수 있게 색깔로 표시했습니다. 이 조합들을 어떻게 하면 하나도 빠짐없이 카운트 할 수 있을까요?

 

중복조합의 핵심 아이디어는 바로 '구획 나누기' 입니다. 동종(같은 문자)끼리는 같은 구획에 몰아넣되, 이종(다른 문자)사이에는 구획을 구분해주는 '슬롯'을 집어넣어주면 됩니다. 위에서 든 다섯 가지 경우를 가지고 이 아이디어를 구현해보겠습니다.

 

 

세 개의 문자 중(n=3) 다섯 개를 (r=5) 중복 허락하여 뽑아야 하기 때문에 다섯 개의 칸이 필요합니다. (그림에서 검은색 사각형) 한편, 세 가지의 종(種)이 있기 때문에 구획을 나누기 위한 슬롯(칸막이)은 최소 두 개가 필요합니다.(그림에서 보라색 점선)

다섯 개의 칸과 두 개의 칸막이만 있으면 예로든 모든 중복조합을 헤아릴 수 있습니다.

 

첫 번째 경우에는 하나의 x와 세 개의 y, 하나의 z가 들어갈 구획 사이에 두 개의 칸막이를 넣었습니다.

두 번째 경우에는 두개의 x와 두개의 y, 세개의 z가 들어갈 구획 사이에 두 개의 칸막이를 넣었습니다.

세 번째 경우에는 두 개의 y와 세 개의 z를 구분짓는 구획에 칸막이 하나를 넣되, 들어가지 않은 x를 표현하기 위해서 y가 들어간 구획의 왼쪽에 칸막이를 배치해줬습니다.

네 번째 경우에는 세 개의 x와 두 개의 y가 들어가는 구획을 구분하는 칸막이를 하나 넣고, z를 제외하기 위해 y구획 오른쪽에 칸막이를 배치해줬습니다.

다섯번 째 경우에는 오로지 x만 들어갈 구획만이 있게하기 위하여 칸막이 두 개를 x구획 오른쪽에 배치하였습니다.

 

이런 식으로 하면, 칸막이의 위치만 바꿔줌으로써 모든 중복조합을 빠짐없이 카운트할 수 있습니다. 가능한 모든 칸막이의 위치를 생각하려면 조합(Combination)의 힘을 빌리면 됩니다.

 

다섯 개의 칸과 두 개의 칸막이를, 일단 동일한 일곱개의 실체로 봅시다.

 

이 일곱 개의 흰색 돌들 중에서 두 개를 뽑아 칸막이로 활용해봅시다.

 

위 그림에서 검은색으로 칠한 게 앞서 예로 든 중복조합 중 첫번째 경우에서의 칸막이가 됩니다. 흰 색으로 표현되는 '구획'에 각각 x, y, z 세 문자를 집어넣으면 (x, y, y, y, z)가 구현됩니다.

나머지 네 경우도 아래와 같이 표현할 수 있습니다.

 

일곱 개의 흰 원 중에서 칸막이로 쓸 두 개를 택하는 조합을 이용하면 예로든 모든 중복조합을 표현할 수 있습니다.

 

조합 7C2에서 7이 나온 경위를 생각해보면, 세 개의 서로 다른 문자(n=3)를 구획별로 나누기 위해 필요한 칸막이의 수는 두 개(n-1=2), 중복을 허락해서 다섯 개(r=5)뽑아야 하므로 칸이 다섯 칸 필요합니다. 이들의 합(2+5=7)만큼의 동일한 흰색 돌을 생각할 수 있습니다. 한편, 조합 7C2에서 숫자 2는 일곱 개의 흰 돌들 중 칸막이로 쓸 두 개의 돌을 뽑아(n-1=2) 검은색 돌로 바꿔주면서 나왔습니다.

 

정리하면, n개 중 r개를 중복 허락해서 뽑을 수 있는 중복조합의 총 가지수는 n-1개의 칸막이와 r개의 칸이 필요한데, 이들의 합을 일단은 같은 흰색 돌로 보고(n-1+r), 그들 중 칸막이의 숫자만큼 뽑은 뒤(n-1) 검은 돌로 치환해줌으로써 구할 수 있습니다. 수식으로 표현하면,

 

한편 조합(Combination)에서 다음 중요한 공식이 있습니다.

 

위 식의 의미는, n개 중 r개를 뽑는 경우의 수나 나머지 n-r개를 뽑는 경우의 수나 같다는 것입니다. 이를 중복조합 공식에 적용하면 식이 다음과 같이 간단히 됩니다.

 

즉, n-1+r 개의 흰색 돌 중에서 n-1개를 뽑아 검은 돌을 만드나, 나머지 r개를 뽑아 흰색 돌로 그대로 두나 같은 경우의 수인 것입니다.

//공식 유도 완료

 

---

이번 포스팅에서는

1. 중복조합의 개념 과

2. 중복조합의 공식유도 과정 및

3. 공식 유도 과정에 녹아 있는 아이디어

를 되짚어보고, 이를 문제에 적용했습니다.

 

중복조합의 핵심은 「구획을 구분지을 수 있는 슬롯(칸막이)의 도입」입니다.

중복조합의 공식 자체는 간단하나, 문제에 응용되면 어려워 질 수 있는 소재입니다. 공식 유도 과정 속에 쓰인 아이디어를 제대로 이해하지 못하면 풀 지 못하는 경우가 많습니다. 따라서 중복 조합을 다루는 핵심 아이디어를 파악한 뒤 이를 문제에 적용할 수 있어야겠습니다.

 

기존의 개념을 토대로 확장된 중복조합. 중복조합을 구하는 과정을 공부하다보면, 경우의 수를 다룰 때 수학이라는 툴이 어떤 참신한 아이디어로 접근하는 지 느낄 수 있습니다.

 

제 글이 많은 학생들에게 도움이 됐으면 합니다.