중복조합이 어렵니? 설명과 문제로 알아볼까?

프로필

2016. 8. 11. 18:38

이웃추가

Intro                                   

오늘은 중복조합에 대해서 알아보겠어요~ 저번 시간엔 조합을 했죠? 조합은 서로 다른 n개에서 r개를 뽑는 경우의 수인데요, 그럼 중복이란 말이 붙어서 중복조합이 되면 어떻게 다르냐? 앞에 중복이란 말이 들어있는게 중복순열이 있었죠? 이 것과 비슷해요~ 한가지 종류의 무언가를 뽑는 횟수가 몇번이 되어도 상관이 없다는 이야기이죠. 그런데 중복순열은 같은걸 여러번 뽑되, 순서를 신경써야했던 것이고 중복조합은 중복해서 뽑아도 되는데 순서는 신경쓰지 않는다는 이야기입니다.

예를 들어 과일상점에 가서 과일을 사는데, 과일이 사과와 귤과 배가 있다고 해봅시다. 그럼 3개의 서로 다른 과일이 있는거죠. 어떤 종류를 사도 상관이 없는데 8개를 사야한다고 해보죠~ 그럼, 같은 과일을 여러번 사게 될 일이 생기겠죠? 물론, 1개만 살 수도 있고 전혀 사지 않을 수도 있어요. 1가지의 과일만 8개를 다 살 수도 있다는 이야기이죠~ 이런 경우는 어떻게 경우의 수를 셀까요? 이런 중복조합을 세는 방법을 유도하는 방법은 보통 두가지인데요.두가지 다 생각을 하는 아이디어라는 점에 있어서 중요하니 둘 다 알아두는 걸로 해보아요!

목차                                    

1. 중복조합 설명1 - 중복을 없애자
2. 중복조합 설명2 - 칸막이를 치자
3. 문제 응용

1. 중복조합 설명1 - 중복을 없애자

자 중복조합에 들어가 봅시다~~ 중복조합은 경우의 수를 세려면 어떻게 해야하냐? 일단, 중복조합의 경우의 수를 일반적으로 세기엔 쉽지않다는게 먼저 느껴져야 해요. 왜냐? 중복으로 뽑아도 되기 때문에 경우의 수를 셀 때 분류를 많이 해줘야 하기 때문이죠. 분류를 많이 해줘야하는 이유는? 경우의 수를 세는데 있어서 각 사건의 경우의 수를 셀 때 규칙이 있으면 곱의 법칙을 쓸 수 있죠. 하지만 규칙이 없으면 분류한 후 합의 법칙을 써야한다고 이야기 했어요. 무슨 말인지 잘 이해가 안되면 합의법칙과 곱의법칙에 대한 설명이 있는 포스팅을 보고 오도록 해요~!

위에서 말했던 사과, 귤, 배 3가지 과일을 8개를 사는 경우의 수를 그냥 앞에서 배웠던 방법대로 분류를 해서 구하려면,

과일을 1종류만 사는 경우, 과일을 2종류만 사는 경우, 과일을 3종류만 사는 경우로 크게 분류를 해야할테고, 그 안에서도 여러가지 케이스로 분류한 후 각각 구해서 더해야겠죠. 이 과정이 만만치가 않을꺼에요. 그래서 다른 방법을 생각하게 됩니다. 그 중 첫 번째가 중복을 없애서 생각하자는 건데요. 중복을 없애면? 바로 조합이 되어버리기 때문이죠. 예를 들어볼까요?

단, 3개의 숫자 1, 2, 3에서 2개를 중복을 허락해서 택하는 경우의 수를 직접 써볼께요. 그럼 {1, 1}, {2, 2}, {3, 3}, {1, 2}, {1, 3}, {2, 3} 이렇게 여섯가지가 되겠네요. 일일이 세었더니 6개라는 걸 알 수 있는데, 여기서 이걸 셀 때, 우의 경우들인 {a, b}가 있으면 {a+0,b+1}이렇게 만들어 주는거에요~ 즉,

{1, 1}, {2, 2}, {3, 3}, {1, 2}, {1, 3}, {2, 3}를
{1, 2}, {2, 3}, {3, 4}, {1, 3}, {1, 4}, {2, 4} 이렇게 만들어주는거죠.

왜 구지 순서쌍의 앞에는 더해주지도 않을껀데 +0이라고 했냐? 그건 밑에 일반화해서 설명할 때 이야기 해줄테니 조금만 참기~^^ 그럼, 왜 이렇게 숫자들을 더했냐? 뽑았던 숫자가 다른 경우는 원래부터 각각의 숫자가 다르니 크게 신경 쓸 필요가 없지만, {1, 1}, {2, 2}, {3, 3}같은 경우는 중복이 있기 때문에 중복을 없애려고 이렇게 해준 거랍니다. 각각 0과 1을 더해줬더니, 모두 다 다른 수가 되어버렸네요~ 그리고 신기하게도 1, 2, 3, 4 중에 중복을 허락하지 않고 그냥 뽑기만 한, 즉, 4개 중 2개를 뽑는 조합의 수가 되었군요! 어차피 값을 더해주거나 빼주거나 해도 가짓수 자체가 바뀌지않기 때문에 이렇게 바꿔서 세어도 전혀 문제가 없겠죠?

그럼 이걸 조금 일반화 해서 생각하자면요?

왼쪽은 1에서 n까지의 자연수 중 중복을 허락하여 r개를 뽑은 경우를 쭉 다 나열한거에요. 그럼 오른쪽은? {a, b, c, d, e, ...} 이 있다면 {a+0, b+1, c+2, d+3, e+4, ...} 이렇게 바꿔준거죠. 여기서는 0, 1, 2, 3, ...을 각각 더했지만, 이건 서로 다른 것으로 구분해주기 위한 것에 불과하기 때문에 3, 4, 5, 6, 7...을 각각 더해줘도 전혀 무방하답니다~

그리하여 각각 수를 더한 순서쌍들을 보자면, 최종적으로는 서로 다른 (n+r-1)개의 수 중, r개를 뽑는 경우의 수가 되는군요!

이런 상황을 위처럼 쓴답니다. 서로 다른 n개중 중복을 허락하여 뽑는 경우의 수를 nHr이라 쓰고, 조합으로 바꿔서 생각을 하는거죠. 이 부분 이해 되시나요? 이게 문제 어떻게 쓰이는지는 2번째 설명까지 하고나서 들어가볼께요~

2. 중복조합 설명2 - 칸막이를 치자 

두번째 설명입니다. 제목이 이상하죠? 칸막이를 치자니.. 이게 무슨소리인가.. ㅋㅋ

문자 a, b, c가 있는데 중복을 생각해서 4개를 뽑는 경우의 수를 생각을 해볼껀데요. 이를 조금 발상을 바꿔보겠습니다. 구분이 안되는 구슬 4개를 a, b, c라는 구슬통에 자유롭게 넣는 경우의 수를 생각해보는거에요. 예를들어, 구슬을 a에 4개 몰아넣으면 aaaa, a에 2개와 b에 1개, c에 1개를 넣으면 aabc가 되는거죠. 여기서 넣는 순서를 다르게 했다고 문자의 순서가 달라지나요? 그건 아니죠? 이건 조합이기 때문에 문자의 배열, 즉 뽑는(구슬을 넣는)순서는 고려하지 않는거에요.

왼쪽 그림에서는 구슬통에 구슬을 넣는걸로 생각했지만 오른쪽 그림은 이렇게 한번 생각해보죠. 구슬 4개를 그냥 일렬로 나열을 하는거에요. 그 다음 문자를 3종류로 구분하기 위해 칸막이를 2개를 쳐주는거랍니다. (a의 개수) l (b의 개수) l (c의 개수) 이렇게 되는거죠. ← 여기서 l은 칸막이이구요~ 즉, 위 사진의 첫번째 구슬배열처럼 oolool 이렇게 되어있으면 a자리에 2개, b자리에 2개가 있으니 aabb가 되는거에요.(위 그림 다시 확인 해보세요) 이해 되시나요?

위에서 사과, 귤, 배 3종류의 과일에서 8개의 과일을 사는 것도 이렇게 생각할 수 있어요!

위의 검정색 동그라미는 구분이 안되는 과일 8개이고, 이 8개에 칸막이를 놓는 순간 과일이 구분이 되는거죠. 이해 되시나요? 위의 예에서, 칸막이를 놓는 경우의 수가 곧 과일을 사는 경우의 수가 일치하니, (과일 개수 8개)와 (칸막이 개수 2개)를 합한 10개 중, 칸막이를 놓을 위치 2개를 선택하는 경우의 수로 바뀐다는거에요~ 한번 더 그림을 볼까요?

이해 되시나요? 즉, 서로 다른 3개의 과일 중 중복을 허락하여 총 8개를 사는 경우의 수인 3H8은, 10개의 자리 중에 칸막이를 2개고르는 10C2로 바꿀 수 있는거에요. 10C210C8과 같으니, 3H8=(3+8-1)C8과 같다는 것 알 수 있겠죠? 이걸로 nHr=(n+r-1)Cr이라는게 한번 더 증명이 되는군요!

3. 문제 응용                       

몇가지 문제를 풀어볼까요?

음이 아닌 정수해, 즉 0과 자연수 중에 해를 찾으라는 이야기겠군요. 예를 들어 순서쌍 (1, 3, 2), (0, 4, 2), (3, 0, 3).. 이런 것들이 있겠죠?

이걸 위의 설명에 들었던 예처럼 x라는 바구니, y라는 바구니, z라는 바구니가 있고, 거기에 구분이 안되는 6개의 공을 넣는다고 생각하는거에요. 그럼 위의 경우와 같기 때문에 3H6=8C6=8C2=28이 되는거죠!

그 다음은요~

이번엔 자연수해라고 하네요. 앞과는 다르죠? 앞의 문제는 0도 포함하라고 했으니까요. 여기서 중요한 개념은, 중복조합은 중복해서 뽑을 수 있으면서도 안뽑을 수도 있다는거에요~ 그런데 자연수의 해라면 반드시 1개는 뽑으라는 이야기잖아요? 그렇기 때문에, 마찬가지 위의 예처럼 생각하기 위해서는 3개의 바구니에 먼저 1개씩 넣고 시작을 하는거에요~ 그렇게 되면? 남은 9개의 공을 각 바구니에 넣는 중복조합의 경우라고 생각하면 되겠고, 그래서 3H9=11C9=11C2=55가 되는거죠~

마지막 문제~ 이 항을 전개를 하면 어떤항이든 차수가 7이 될꺼에요~ x의 7제곱도 있을 것이고, x의 6제곱과 y의 곱도 있을 것이고, x의 제곱, y의 3제곱, z의 제곱의 곱도 있을꺼네요~ 즉, 이 상황도 서로 다른 3개의 문자 중 7개를 중복을 허락하여 택하는 경우이기 때문에, 3H7=9C7=9C2=36이 되는거죠!

이해 잘 되시나요? 자, 이렇게 중복조합의 설명과 몇가지 문제를 풀어봤어요~ 문제 종류가 더 있겠지만, 거의 다 방정식이거나, 위에 설명할 때 예를 들었던 것 처럼 물건이나 사람을 중복해서 고르는 경우이기 때문에, 이해가 되었으면 쉽게 풀 수 있을거라 생각해요~ 그럼 여기까지 하고, 다음 포스팅은 드디어 분할과 이항정리에 들어갑니다. 여기까지 하면 벌써 대단원 1단원이 끝이나는거에요~ 조금만 힘내서 공부하고 다음 시간에 봐요~ 안녕!



NGeneration
NGeneration

수학 선생님. 수업 방식, 공부 Tip, 수학 개념 등을 담고 있습니다.