← 목록으로 돌아가기
1. 중복조합이란?
중복조합(Combination with Repetition)은 서로 다른 \(n\)개에서
중복을 허용하여 \(r\)개를 선택하는 경우의 수입니다.
일반 조합과 달리 같은 것을 여러 번 선택할 수 있습니다.
실생활 예시:
아이스크림 가게에 3가지 맛(바닐라, 초콜릿, 딸기)이 있습니다.
5개의 아이스크림을 주문할 때, 같은 맛을 여러 개 선택할 수 있다면?
→ 바닐라 3개 + 초콜릿 2개, 딸기 5개 등 모두 가능합니다.
2. 중복조합과 같은 것이 있는 순열의 관계
중복조합은 "같은 것이 있는 순열"로 이해할 수 있습니다.
이것이 중복조합의 핵심 원리입니다!
2.1 시각적 이해: ○과 | 방법
\(n\)개 중에서 중복을 허용하여 \(r\)개를 선택하는 것은
\(r\)개의 ○(공)과 \((n-1)\)개의 |(칸막이)를 배열하는 것과 같습니다.
예제: 3가지 종류(A, B, C)에서 중복을 허용하여 5개 선택
A 2개, B 2개, C 1개를 선택한다면:
○ ○ | ○ ○ | ○
─A─ ─B─ ─C─
A 5개를 선택한다면:
○ ○ ○ ○ ○ | |
────A──── B C
C 5개를 선택한다면:
| | ○ ○ ○ ○ ○
A B ────C────
핵심 원리:
• ○ 5개 (선택할 개수)
• | 2개 (3가지를 구분하는 칸막이 = 3-1개)
• 총 7개를 배열하는 방법의 수
• 같은 것이 있는 순열: \(\frac{7!}{5! \times 2!} = C(7, 5) = C(7, 2) = 21\)
3. 정수해 문제로 배우는 중복조합
3.1 예제 1: \(x + y + z = 7\) (음이 아닌 정수)
문제: \(x + y + z = 7\)을 만족하는 음이 아닌 정수해 \((x, y, z)\)의 개수를 구하시오.
(단, \(x, y, z \geq 0\))
풀이:
방법 1: 중복조합 공식 사용
3개의 변수(\(x, y, z\))에 7을 배분하는 문제
= 3가지 종류에서 중복을 허용하여 7개를 선택
$$H(3, 7) = C(3+7-1, 7) = C(9, 7) = C(9, 2)$$
$$= \frac{9 \times 8}{2 \times 1} = 36$$
방법 2: ○과 | 방법
7개의 ○(공)과 2개의 |(칸막이)를 배열
예: \(x=2, y=3, z=2\)인 경우
○ ○ | ○ ○ ○ | ○ ○
─x─ ──y── ─z─
총 9개 위치에서 ○ 7개를 배치하거나 | 2개를 배치:
$$\frac{9!}{7! \times 2!} = C(9, 2) = 36$$
답: 36가지
일부 해의 예시:
(0,0,7), (0,1,6), (0,2,5), ..., (1,1,5), (1,2,4), ..., (2,2,3), ..., (7,0,0)
3.2 예제 2: \(x + y + z = 7\) (양의 정수)
문제: \(x + y + z = 7\)을 만족하는 양의 정수해 \((x, y, z)\)의 개수를 구하시오.
(단, \(x, y, z \geq 1\))
풀이:
각 변수가 최소 1 이상이어야 하므로, 먼저 각각 1씩 배분합니다.
\(x = x' + 1\), \(y = y' + 1\), \(z = z' + 1\)로 치환하면:
$$(x'+1) + (y'+1) + (z'+1) = 7$$
$$x' + y' + z' = 4$$
여기서 \(x', y', z' \geq 0\) (음이 아닌 정수)
이제 예제 1과 동일한 문제가 됩니다:
$$H(3, 4) = C(3+4-1, 4) = C(6, 4) = C(6, 2)$$
$$= \frac{6 \times 5}{2 \times 1} = 15$$
방법 2: ○과 | 방법
4개의 ○과 2개의 |를 배열:
$$C(6, 2) = 15$$
답: 15가지
모든 해의 목록:
(1,1,5), (1,2,4), (1,3,3), (1,4,2), (1,5,1),
(2,1,4), (2,2,3), (2,3,2), (2,4,1),
(3,1,3), (3,2,2), (3,3,1),
(4,1,2), (4,2,1),
(5,1,1)
총 15가지
4. 두 경우의 비교
| 구분 |
음이 아닌 정수 (≥0) |
양의 정수 (≥1) |
| 조건 |
\(x, y, z \geq 0\) |
\(x, y, z \geq 1\) |
| 변환 |
변환 불필요 |
\(x=x'+1, y=y'+1, z=z'+1\) |
| 방정식 |
\(x + y + z = 7\) |
\(x' + y' + z' = 4\) |
| 중복조합 |
\(H(3, 7)\) |
\(H(3, 4)\) |
| 계산 |
\(C(9, 7) = C(9, 2)\) |
\(C(6, 4) = C(6, 2)\) |
| 답 |
36가지 |
15가지 |
| 0 포함 여부 |
(0,0,7), (0,7,0) 등 포함 |
모든 변수 ≥ 1 |
5. 일반 공식 정리
\(x_1 + x_2 + \cdots + x_n = r\)의 정수해 개수:
경우 1: \(x_i \geq 0\) (음이 아닌 정수)
$$H(n, r) = C(n+r-1, r) = C(n+r-1, n-1)$$
경우 2: \(x_i \geq 1\) (양의 정수)
먼저 각 변수에 1씩 배분 → \(x_i' = x_i - 1\)로 치환
$$H(n, r-n) = C(n+(r-n)-1, r-n) = C(r-1, r-n) = C(r-1, n-1)$$
6. 연습문제
문제 1. \(a + b + c + d = 10\)을 만족하는 음이 아닌 정수해의 개수를 구하시오.
풀이 1.
4개의 변수에 10을 배분:
$$H(4, 10) = C(4+10-1, 10) = C(13, 10) = C(13, 3)$$
$$= \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = \frac{1716}{6} = 286$$
답: 286가지
문제 2. \(a + b + c + d = 10\)을 만족하는 양의 정수해의 개수를 구하시오.
풀이 2.
각 변수에 먼저 1씩 배분 (총 4 사용):
남은 6을 4개 변수에 배분 (\(a', b', c', d' \geq 0\)):
$$H(4, 6) = C(4+6-1, 6) = C(9, 6) = C(9, 3)$$
$$= \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = \frac{504}{6} = 84$$
또는 직접 공식 사용:
$$C(r-1, n-1) = C(10-1, 4-1) = C(9, 3) = 84$$
답: 84가지
문제 3. 5가지 종류의 과일(사과, 배, 포도, 바나나, 오렌지)에서 중복을 허용하여 8개를 선택하는 경우의 수를 구하시오.
풀이 3.
5가지 종류에서 중복을 허용하여 8개 선택:
$$H(5, 8) = C(5+8-1, 8) = C(12, 8) = C(12, 4)$$
$$= \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \frac{11880}{24} = 495$$
답: 495가지
7. 마무리
중복조합 마스터 체크리스트:
✅ 중복조합 = 같은 것을 여러 번 선택 가능
✅ 공식: \(H(n,r) = C(n+r-1, r)\)
✅ ○과 | 방법으로 시각화 가능
✅ 같은 것이 있는 순열로 이해
✅ 정수해 문제: 음이 아닌 정수 vs 양의 정수 구분
✅ 양의 정수 조건: 먼저 1씩 배분 후 나머지 분배
중복조합은 처음에는 어렵게 느껴질 수 있지만, ○과 | 방법으로 시각화하면
직관적으로 이해할 수 있습니다. 정수해 문제는 다양한 응용이 가능하므로
충분히 연습하여 익숙해지는 것이 중요합니다.