중복조합

과일 가게에서 사과, 배, 감 가운데 5개를 산다고 합시다. 같은 과일을 여러 개 골라도 되고, 고르는 순서는 상관없습니다. 중복을 허락하되 순서를 따지지 않는 선택이 중복조합입니다. 이 절에서는 중복조합을 공과 칸막이의 배열로 바꾸어 그 수가 \({}_{n+r-1}\mathrm{C}_{r}\)가 되는 까닭을 확인합니다. 같은 생각으로 방정식의 정수해 개수를 세 봅니다.

먼저 알면 좋은 것 조합 \({}_{n}\mathrm{C}_{r}\)중복순열 같은 것이 있는 순열

본문

중복조합

본문

빵집에 크림빵, 단팥빵, 소보로빵이 넉넉히 있고, 이 가운데 5개를 산다. 같은 빵을 여러 개 사도 되고, 어떤 빵은 하나도 안 사도 된다. 순서는 따지지 않는다. 고르는 방법은 몇 가지일까? 하나하나 쓰지 않고 셀 수 있을까?

크림빵 단팥빵

그림 1. 고른 빵 5개를 별 ★, 종류의 경계를 막대 | 2개로 나타내면, 고르는 방법 하나가 별 5개와 막대 2개를 늘어놓는 방법 하나와 짝지어진다.

먼저 알아야 할 것조합 \({}_n\mathrm{C}_r\)(공통수학1), 중복순열과 같은 것이 있는 순열(중복순열과 같은 것이 있는 순열).

1.2.1별과 막대로 바꾸기

크림빵 2개, 단팥빵 1개, 소보로빵 2개를 샀다면 ★★|★|★★로 나타내자. 첫 막대 앞의 별이 크림빵, 두 막대 사이가 단팥빵, 둘째 막대 뒤가 소보로빵의 개수이다. 크림빵을 안 사고 단팥빵 3개, 소보로빵 2개를 샀다면 |★★★|★★이다.

이렇게 하면 고르는 방법 하나마다 '별 5개와 막대 2개를 늘어놓은 줄' 하나가 정확히 짝지어지고, 거꾸로 줄 하나에서 고른 방법을 되찾을 수 있다. 따라서 고르는 방법의 수는 7개의 자리 가운데 막대 2개의 자리를 고르는 방법의 수 \({}_7\mathrm{C}_2 = 21\)이다. 그림 1의 슬라이더로 개수를 바꾸면 줄이 함께 바뀐다.

정리 1.2.1 중복조합

서로 다른 \(n\)개에서 중복을 허락하여 \(r\)개를 택하는 조합을 중복조합이라 하고, 그 수를 \({}_n\mathrm{H}_r\)로 나타낸다. \[{}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r\]

공식의 \(n + r - 1\)은 별 \(r\)개와 막대 \(n - 1\)개를 더한 자리 수이다. 종류가 \(n\)가지이면 경계는 \(n - 1\)개면 되기 때문이다.¹

1.2.2방정식의 정수해 세기

세 빵의 개수를 \(x\), \(y\), \(z\)라 하면 처음 질문은 \(x + y + z = 5\)를 만족하는 음이 아닌 정수 \((x, y, z)\)의 개수를 묻는 것과 같다. 그래서 중복조합은 이런 방정식의 해를 세는 도구가 된다. \(x + y + z = r\)의 음이 아닌 정수해의 개수는 \({}_3\mathrm{H}_r\)이다.

그림 2. 각 변수가 1 이상이라는 조건은 하나씩 미리 나누어 준 뒤 남은 수를 자유롭게 나누는 문제로 바꾼다.

1.2.3예제 풀이

예제 1.2.2

\(x + y + z = 8\)을 만족하는 양의 정수해 \((x, y, z)\)의 개수를 구하여라. 또 사과, 배, 감 세 종류에서 6개를 고르되 사과를 2개 이상 고르는 방법의 수를 구하여라.

양의 정수이므로 \(x = x' + 1\), \(y = y' + 1\), \(z = z' + 1\)(\(x', y', z' \ge 0\))로 둔다. 그러면 \(x' + y' + z' = 5\)이므로 해의 개수는 \({}_3\mathrm{H}_5 = {}_7\mathrm{C}_5 = 21\)이다. 처음 질문의 빵 고르기와 같은 수가 나온 것은 두 문제가 같은 구조이기 때문이다.

두 번째 질문은 사과 2개를 먼저 골라 두고, 남은 4개를 세 종류에서 자유롭게 고르면 된다. 따라서 \({}_3\mathrm{H}_4 = {}_6\mathrm{C}_4 = 15\)가지이다.

확인으로 사과의 개수별로 세어 보자. 사과가 2개이면 나머지 4개를 배와 감에 나누는 5가지, 3개이면 4가지, 4개이면 3가지, 5개이면 2가지, 6개이면 1가지이다. 합은 \(5 + 4 + 3 + 2 + 1 = 15\)로 같다. 아래 탐구 카드에서 별과 막대를 직접 옮기며 중복조합을 세어 보자.

중복조합에서는 \(r\)이 \(n\)보다 커도 된다. 같은 것을 여러 번 고를 수 있기 때문이다. 반면 조합 \({}_n\mathrm{C}_r\)에서는 \(r \le n\)이어야 한다.

마무리

중복을 허락해 순서 없이 고르는 방법은, 고른 것을 별로, 종류의 경계를 막대로 늘어놓는 방법과 하나씩 짝지어지므로 \({}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r\)이다. 방정식의 정수해를 세는 문제도 같은 구조이다. 그래서 처음 질문의 빵 5개를 고르는 방법은 \({}_3\mathrm{H}_5 = {}_7\mathrm{C}_2 = 21\)가지이다.

탐구 1

종류마다 몇 개씩 고를지는 몇 가지로 정할 수 있을까?

중복조합 · 공과 칸막이

과일 종류 \(n\) = 3

사는 개수 \(r\) = 5

—

\({}_{n}\mathrm{H}_{r}\): —
지금 경우의 순서: —
\({}_{n}\mathrm{C}_{r}\): —
\({}_{n}\Pi_{r}\): —

세로 막대(칸막이)를 끌어서 다른 칸으로 옮겨 보자. 칸막이는 서로 지나칠 수 없다.

질문사과, 배, 감 세 종류에서 과일 5개를 사려고 한다. 같은 과일을 여러 개 사도 되고, 한 종류를 사지 않아도 된다. 담는 순서는 상관없다면 살 수 있는 방법은 몇 가지일까?
복원서로 다른 \(n\)개에서 순서 없이 \(r\)개를 고르는 조합의 수는 \({}_{n}\mathrm{C}_{r}\)이다. 그리고 같은 것이 있는 순열에서는 공 \(r\)개와 막대 \(k\)개를 한 줄로 늘어놓는 방법이 \(\frac{(r + k)!}{r!k!}\)가지이다.
설명서로 다른 \(n\)종류에서 중복을 허락하여 순서 없이 \(r\)개를 택하는 조합을 중복조합이라 하고, 그 수를 \({}_{n}\mathrm{H}_{r}\)로 나타낸다. 고른 결과는 '종류마다 몇 개'만으로 정해진다. 그래서 고른 \(r\)개를 공으로 그리고 종류 사이에 칸막이 \(n - 1\)개를 세우면, 고르는 방법 하나가 공과 칸막이의 배열 하나와 짝지어진다. 첫 칸막이 앞의 공 수가 첫째 종류의 개수, 두 칸막이 사이의 공 수가 다음 종류의 개수이다. 이 배열의 수는 \(r + n - 1\)개의 자리에서 공이 놓일 \(r\)자리를 고르는 수와 같으므로 \({}_{n}\mathrm{H}_{r} = {}_{n+r-1}\mathrm{C}_{r}\)이고, 사과, 배, 감 5개이면 \({}_{3}\mathrm{H}_{5} = {}_{7}\mathrm{C}_{5} = 21\)가지이다.
연결중복을 허락하므로 \({}_{n}\mathrm{H}_{r}\)에서는 \(r\)가 \(n\)보다 커도 되고, 여기에 순서까지 따지면 중복순열 \({}_{n}\Pi_{r} = n^r\)가 된다. 똑같은 사탕 \(r\)개를 \(n\)명에게 나누어 주는 방법, 같은 색 공 \(r\)개를 서로 다른 상자 \(n\)개에 넣는 방법도 모두 \({}_{n}\mathrm{H}_{r}\)가지이다. 또 집합 \(\{1, 2, \cdots, r\}\)에서 \(\{1, 2, \cdots, n\}\)으로 가는 함수 가운데 \(f(1) \le f(2) \le \cdots \le f(r)\)인 것의 개수도 \({}_{n}\mathrm{H}_{r}\)인데, 함숫값 \(r\)개를 중복을 허락해 고르면 크기 순서는 저절로 정해지기 때문이다.
적용\(n = 3\), \(r = 5\)로 두고 칸막이를 끌어 '사과 0, 배 5, 감 0'을 만들어 보고, 칸막이가 맨 앞에 붙어 있을 때 무엇을 뜻하는지 생각해 보자. '다음 경우'를 계속 눌러 마지막 경우가 몇 번째인지 보고 \({}_{3}\mathrm{H}_{5}\)와 비교한 뒤, \(r\)를 \(n\)보다 작게 했을 때와 크게 했을 때 \({}_{n}\mathrm{C}_{r}, {}_{n}\mathrm{H}_{r}, {}_{n}\Pi_{r}\)가 각각 어떻게 되는지도 확인해 보자.
판단\({}_{n}\mathrm{H}_{r}\)를 \({}_{n+r-1}\mathrm{C}_{n}\)으로 쓰는 실수가 흔하다. 전체 자리 \(n + r - 1\)개 가운데 고르는 것은 공 \(r\)자리 또는 칸막이 \(n - 1\)자리이므로, \({}_{n+r-1}\mathrm{C}_{r} = {}_{n+r-1}\mathrm{C}_{n-1}\)이다. 또 '종류마다 적어도 하나씩' 같은 조건이 붙으면 그만큼 먼저 하나씩 담아 두고, 남은 개수로 중복조합을 센다.

확인조건이 달라지면

사과, 배, 감 세 종류에서 과일 5개를 사는데, 종류마다 적어도 하나씩 사려고 한다. 사는 방법의 수는?

탐구 2

\(x + y + z = r\)를 만족하는 정수해는 몇 개일까?

중복조합 · 방정식의 해 세기

합 \(r\) = 6

각 변수 \(\ge k\), \(k\) = 0

고른 해 \((x, y, z)\): —
이 \(x\)에서 가능한 \(y\)의 개수: —
해의 개수 (점의 수): —
중복조합으로 계산: —

진한 점이 조건을 만족하는 해이고, 흐린 점은 음이 아닌 정수해 가운데 조건을 만족하지 않는 것이다. 진한 점을 끌어 다른 해를 골라 보자.

질문방정식 \(x + y + z = 6\)을 만족하는 음이 아닌 정수 \(x, y, z\)의 순서쌍은 몇 개일까? 자연수해만 세면 몇 개로 줄어들까?
복원서로 다른 \(n\)종류에서 중복을 허락하여 \(r\)개를 고르는 방법의 수는 \({}_{n}\mathrm{H}_{r} = {}_{n+r-1}\mathrm{C}_{r}\)이다. 그리고 고른 결과는 종류마다 몇 개를 골랐는지로 정해진다.
설명해 \((x, y, z)\)를 'x, y, z 세 종류에서 모두 \(r\)개를 고를 때, x를 \(x\)개, y를 \(y\)개, z를 \(z\)개 고른 것'으로 읽으면 해 하나가 중복조합 하나와 짝지어진다. 그래서 음이 아닌 정수해의 개수는 \({}_{3}\mathrm{H}_{r}\)이고, \(r = 6\)이면 \({}_{3}\mathrm{H}_{6} = {}_{8}\mathrm{C}_{6} = 28\)개이다. 그림에서도 셀 수 있다. \(x\)를 정하면 \(y\)는 0부터 \(r - x\)까지 \(r - x + 1\)개이므로 \(1 + 2 + \cdots + (r + 1)\)개이다. 또 자연수해처럼 변수마다 최솟값 \(k\)가 있으면 \(x = x' + k\)처럼 바꾸어 \(x' + y' + z' = r - 3k\)의 음이 아닌 정수해를 세고, 자연수해\((k = 1)\)는 \({}_{3}\mathrm{H}_{r-3}\)개이다.
연결변수가 \(n\)개인 \(x_1 + x_2 + \cdots + x_n = r\)의 음이 아닌 정수해는 \({}_{n}\mathrm{H}_{r}\)개이고, 이것은 똑같은 공 \(r\)개를 서로 다른 상자 \(n\)개에 나누어 넣는 방법의 수와 같은 문제이다. 부등식 \(x + y + z \le r\)은 남는 양을 \(w \ge 0\)으로 두고 \(x + y + z + w = r\)로 바꾸어 \({}_{4}\mathrm{H}_{r}\)로 센다.
적용\(r = 6\), \(k = 0\)에서 점을 하나씩 끌어 \(x\)를 바꾸어 가며 '이 \(x\)에서 가능한 \(y\)의 개수'를 적고, 그 합이 중복조합 값과 같은지 보자. \(k\)를 1로 올리면 진한 점의 삼각형이 줄어드는데, 그 삼각형이 \(r\)가 얼마일 때의 그림과 같은 모양인지도 찾아보자.
판단\({}_{3}\mathrm{H}_{6}\)을 \({}_{6}\mathrm{H}_{3}\)으로 바꾸어 쓰는 실수가 흔하다. H 앞의 수는 고를 종류의 수(변수의 개수)이고, 뒤의 수는 고르는 개수(합)이다. 실제로 \({}_{3}\mathrm{H}_{6} = 28\)이고 \({}_{6}\mathrm{H}_{3} = 56\)이어서 값이 다르다. 또 조건이 '\(x \ge 1\)'처럼 일부 변수에만 붙으면 그 변수만 바꾸어 합에서 빼야 한다.

확인조건이 달라지면

방정식 \(x + y + z + w = 8\)을 만족하는 자연수 \(x, y, z, w\)의 순서쌍의 개수는?

AI 출제 문항연습문제 풀어보기13문항 수능·모의평가·학력평가기출문제 풀어보기144문항