중복조합

주문 순서보다 종류별 개수

세 종류의 빵에서 4개를 고를 때 “팥·팥·크림·소보로”와 “소보로·팥·크림·팥”은 같은 주문입니다. 종류별 개수 (2,1,1)만 정하면 됩니다. 각 종류의 재고는 충분하다고 가정합니다.

별 r개와 막대 n−1개

빵 4개를 별 4개로, 세 종류의 경계를 막대 2개로 나타냅니다. ★★|★|★는 (2,1,1)입니다. 전체 r+n−1개 위치 중 막대 n−1개의 위치를 고르면 됩니다. 막대가 붙거나 양끝에 있어도 되며 그 종류는 0개입니다.

최소 개수와 최대 개수

x+y+z=8에서 모두 1 이상이면 먼저 1개씩 배정하고 x′+y′+z′=5로 바꿉니다. x≤3 같은 상한이 있으면 전체에서 x≥4인 경우를 빼면 편합니다.

직접 해 보기

별과 막대로 보는 중복조합

r개의 별과 n−1개의 막대가 분배 문제를 어떻게 표현하는지 살펴봅니다.

원본 학습서에서 크게 열기 →

해 볼 것 · 막대가 양 끝에 있거나 두 막대가 붙어 있으면, 각각 어느 상자에 0개가 들어간다는 뜻일까요?

풀이 예제

같이 풀어 보기 1세 종류의 빵

재고가 충분한 빵 3종류 중 4개를 고르는 방법은?

▸ 풀이 보기

1. 종류별 개수를 x,y,z라 하면 x+y+z=4이고 x,y,z≥0입니다.
2. 별 4개와 막대 2개를 배열합니다.
3. C(6,2)=15입니다.

답: 15가지

같이 풀어 보기 2양의 정수해

x+y+z=9를 만족하는 양의 정수해의 수는?

▸ 풀이 보기

1. x′=x−1, y′=y−1, z′=z−1로 놓습니다.
2. x′+y′+z′=6이며 모두 0 이상입니다.
3. C(8,2)=28입니다.

답: 28개

같이 풀어 보기 3한 종류의 상한

x+y+z=6, x,y,z≥0인 정수해 중 x≤2인 해는?

▸ 풀이 보기

1. 전체는 C(8,2)=28입니다.
2. x≥3이면 x′=x−3으로 바꾸어 x′+y+z=3입니다.
3. 위반하는 해 C(5,2)=10을 빼서 28−10=18입니다.

답: 18개

같이 풀어 보기 4최소 한 개씩

서로 같은 사탕 10개를 구별되는 학생 4명에게 한 개 이상씩 나누는 방법은?

▸ 풀이 보기

1. 먼저 학생마다 1개씩 주어 4개를 사용합니다.
2. 남은 6개를 제한 없이 나누는 수는 H(4,6)입니다.
3. C(9,3)=84입니다.

답: 84가지

한 장 요약

1. 중복조합 — H(n,r) = C(n+r−1,r)
2. 음이 아닌 정수해 — x₁+⋯+xₙ=r → C(r+n−1,n−1)
3. 양의 정수해 — x₁+⋯+xₙ=r → C(r−1,n−1), r≥n