중복조합 정의와 공식, 예시와 중복순열 차이 정리

📐 개념 정리

중복조합은 서로 다른 n종류에서 중복을 허락해 순서 없이 r개를 고르는 경우의 수다. 중복조합 정의와 공식, 칸막이로 하는 유도, 방정식의 정수해와 함수 개수 예시, 중복순열과 차이를 고등수학 눈높이로 정리했다.

중복조합은 서로 다른 n종류 중에서 같은 것을 여러 번 골라도 되고 순서는 따지지 않을 때, r개를 뽑는 경우의 수다. 기호로는 \({}_n\mathrm{H}_r\)로 쓰고, 공식은 \({}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r\)이다. 공 r개와 칸막이 n-1개를 한 줄로 세우는 그림 하나로 공식이 유도되고, 방정식의 정수해 개수나 다항식 항의 개수 문제에 그대로 쓰인다.

중복조합 정의 — 같은 것을 여러 번 고를 수 있는 조합

조합 \({}_n\mathrm{C}_r\)는 서로 다른 n개에서 순서 없이 r개를 고르는 경우의 수로, 한 번 고른 것은 다시 고를 수 없다. 중복조합은 여기서 '중복 금지'라는 조건 하나를 푼 것이다. 고르는 대상이 n개의 물건이 아니라 n종류이고, 같은 종류를 몇 번이든 고를 수 있다.

아이스크림 가게에서 바닐라·초코·딸기 세 가지 맛 중 두 스쿱을 컵에 담는다고 하자. 같은 맛 두 스쿱도 되고, 컵 안에서 순서는 의미가 없다. 경우를 직접 세면 바닐라 둘, 초코 둘, 딸기 둘, 바닐라·초코, 바닐라·딸기, 초코·딸기로 6가지다. 이것이 \({}_3\mathrm{H}_2 = 6\)이다.

중복조합에서는 조합과 달리 r이 n보다 커도 된다. 세 가지 맛으로 다섯 스쿱을 담는 것도 가능하기 때문이다. 이 점이 중복조합 정의에서 가장 자주 놓치는 부분이다.

중복조합 공식과 유도 — 칸막이 방법

중복조합 공식의 핵심 아이디어는 '종류별 개수'만 기록하면 된다는 것이다. 세 종류에서 다섯 개를 고른 결과를 공 ○ 다섯 개와 칸막이 | 두 개로 나타내 보자. ○○|○|○○는 첫째 종류 2개, 둘째 1개, 셋째 2개를 뜻하고, |○○○○○|는 둘째 종류만 5개를 뜻한다.

일반적으로 n종류를 나누려면 칸막이가 n-1개 필요하다. 그러면 고르는 방법 하나하나가 공 r개와 칸막이 n-1개, 모두 n+r-1개의 자리를 한 줄로 늘어놓는 방법 하나와 정확히 대응한다. 그중 공이 들어갈 r자리만 정하면 나머지는 칸막이이므로 다음 공식이 나온다.

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

공 r개와 칸막이 n-1개가 놓일 n+r-1자리 중 공의 자리 r개를 고르는 수

계승으로 풀어 쓰면 다음과 같다. 문제에 따라 \(r\)과 \(n-1\) 중 작은 쪽으로 조합을 계산하면 손계산이 빨라진다.

$${}_n\mathrm{H}_r = \frac{(n+r-1)!}{r!\,(n-1)!}$$

앞의 아이스크림 예는 3H2 = 4C2 = 6으로 직접 센 값과 일치한다

중복조합 예시 — 방정식의 정수해 개수

중복조합이 가장 많이 출제되는 형태는 방정식의 해의 개수다. \(x+y+z=10\)을 만족하는 음이 아닌 정수 \(x, y, z\)의 순서쌍 개수를 구해 보자. 1이라는 같은 단위 10개를 x, y, z 세 종류에 나눠 주는 것과 같으므로 중복조합이다.

$${}_3\mathrm{H}_{10} = {}_{12}\mathrm{C}_{10} = {}_{12}\mathrm{C}_{2} = 66$$

음이 아닌 정수해의 개수

조건이 '양의 정수'로 바뀌면 한 단계가 더 필요하다. 각 변수에 먼저 1씩 나눠 주고 시작한다고 생각해 \(x = x'+1\)처럼 치환하면, \(x'+y'+z'=7\)의 음이 아닌 정수해 문제로 바뀐다.

$${}_3\mathrm{H}_{7} = {}_{9}\mathrm{C}_{7} = {}_{9}\mathrm{C}_{2} = 36$$

양의 정수해의 개수

같은 원리로 '같은 사탕 7개를 세 명에게 한 개 이상씩 나눠 주는 방법'은 먼저 한 개씩 주고 남은 4개를 나누는 \({}_3\mathrm{H}_4 = {}_6\mathrm{C}_4 = 15\)가지다. 사탕끼리는 구별되지 않고 받는 사람은 구별된다는 점이 중복조합 예시의 공통 구조다.

다항식 항의 개수와 함수의 개수도 중복조합

\((a+b+c)^4\)를 전개했을 때 서로 다른 항의 개수도 중복조합이다. 각 항은 \(a^p b^q c^r\) 꼴이고 \(p+q+r=4\)이므로, a·b·c 세 문자 중에서 중복을 허락해 4개를 고르는 것과 같다.

$${}_3\mathrm{H}_4 = {}_6\mathrm{C}_4 = 15$$

(a+b+c)의 4제곱을 전개했을 때 서로 다른 항의 개수

함수 문제에도 자주 나온다. 집합 \(X=\{1,2,3\}\)에서 \(Y=\{1,2,3,4\}\)로 가는 함수 중 \(f(1) \le f(2) \le f(3)\)을 만족하는 함수의 개수는 Y의 원소 4종류에서 중복을 허락해 3개를 고른 뒤 작은 순서대로 배정하는 수와 같아 \({}_4\mathrm{H}_3 = {}_6\mathrm{C}_3 = 20\)이다. 등호가 빠진 \(f(1) \lt f(2) \lt f(3)\)이라면 중복이 허락되지 않으므로 조합 \({}_4\mathrm{C}_3 = 4\)가 된다.

중복순열 중복조합 차이 — 헷갈릴 때 판단법

중복순열은 중복을 허락하되 순서까지 구별하는 경우의 수로, n종류에서 r개를 뽑아 일렬로 세우면 각 자리마다 n가지 선택이 있다.

$${}_n\Pi_r = n^r \qquad \text{vs} \qquad {}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$$

세 종류에서 5개를 고를 때 중복순열은 243, 중복조합은 21

경우의 수 네 가지 한눈에 정리

• 순열: 중복 없음, 순서 있음 → nPr
• 조합: 중복 없음, 순서 없음 → nCr
• 중복순열: 중복 있음, 순서 있음 → n의 r제곱
• 중복조합: 중복 있음, 순서 없음 → nHr = (n+r-1)Cr

분배 문제에서는 '나눠 주는 물건이 구별되는가'를 먼저 본다. 서로 다른 공 3개를 상자 2개에 넣는 방법은 공마다 상자를 고르므로 중복순열 \(2^3 = 8\)가지다. 같은 공 3개를 상자 2개에 넣는 방법은 상자별 개수만 정하면 되므로 중복조합 \({}_2\mathrm{H}_3 = {}_4\mathrm{C}_3 = 4\)가지다. 물건이 구별되면 중복순열, 구별되지 않으면 중복조합이다.

나는 처음 중복조합을 배울 때 공식 \({}_{n+r-1}\mathrm{C}_r\)만 외웠다가 n과 r 자리를 자주 뒤바꿨다. 칸막이 그림을 직접 그려 보고 나서야 '칸막이는 종류 수보다 하나 적다'는 사실이 손에 붙었다. 지금도 헷갈리는 문제를 만나면 ○와 |를 몇 개 그려 보는 것이 공식을 떠올리는 것보다 빠르다.

함께 읽으면 좋은 글

순열과 조합 차이, 공식과 실생활 예시 완벽 정리 이항정리 공식과 증명 — 일반항·파스칼의 삼각형까지 생일 문제란? 23명이면 50%를 넘는 확률 계산과 원리

참고 자료

Wikipedia — Stars and bars (combinatorics) Wolfram MathWorld — Multichoose 위키백과 — 조합