중복조합

음료 가게에서 사과, 포도, 귤 주스 가운데 10잔을 주문하려 한다. 같은 주스를 여러 잔 골라도 되고 어떤 주스는 하나도 안 골라도 된다. 그러면 주문 방법은 방정식 \(x + y + z = 10\)의 음이 아닌 정수해의 개수와 같다. 그런데 사과 주스는 적어도 한 잔, 포도 주스는 적어도 두 잔 넣어야 한다는 조건이 붙으면 몇 가지로 줄어들까? 또 귤 주스를 다섯 잔 넘게 넣을 수 없다면 어떻게 셀까?

1.2.1칸막이로 나누다

서로 다른 \(n\)종류에서 중복을 허락해 \(r\)개를 고르는 방법은, 고른 \(r\)개를 일렬로 놓고 \(n - 1\)개의 칸막이로 종류를 나누는 방법과 하나씩 대응한다. 첫째 칸에 있는 것은 첫째 종류, 둘째 칸은 둘째 종류이다. 그래서 \(r\)개와 칸막이 \(n - 1\)개, 모두 \(n + r - 1\)개의 자리에서 칸막이의 자리를 고르면 된다. 이것을 중복조합이라 하고 \({}_n\mathrm{H}_r\)로 쓴다. 고르는 것들은 서로 구별되지 않고 몇 개씩 골랐는지만 중요하다.

변수에 하한 조건이 있으면 먼저 그만큼을 나누어 주고 남은 것을 제한 없이 나눈다. 사과 주스를 적어도 한 잔 넣어야 하면 \(x = x' + 1\)로 놓아 \(x' \ge 0\)인 문제로 바꾸는 것이다. 양의 정수해는 모든 변수에 1씩 먼저 주는 경우여서 \(r - n\)개를 나누는 문제가 된다. 상한 조건이 있으면 바로 셀 수 없으므로, 조건을 어기는 경우를 세어 전체에서 뺀다. 어기는 경우는 그 변수에 상한보다 하나 많은 만큼을 먼저 주고 남은 것을 나누어 센다.¹

1.2.2중복조합과 다항식의 항

중복조합은 다항식의 항을 셀 때도 나온다. \((a + b + c)^{10}\)을 전개하면 \(a^xb^yc^z\) 꼴의 항이 나오는데, 지수의 합이 늘 10이므로 서로 다른 항의 개수는 \(x + y + z = 10\)의 음이 아닌 정수해의 개수인 \({}_3\mathrm{H}_{10} = 66\)이다. 같은 방법으로 주사위 세 개를 던져 나오는 눈의 조합, 곧 순서를 무시한 결과의 가짓수는 \({}_6\mathrm{H}_3 = 56\)이다.

1.2.3예제 풀이

\(x = x' + 1\), \(y = y' + 2\)로 놓으면 \(x' + y' + z = 7\)이고 세 변수가 모두 0 이상이다. 그래서 주문 방법은 \({}_3\mathrm{H}_7 = {}_9\mathrm{C}_7 = {}_9\mathrm{C}_2 = 36\)가지이다.

이 가운데 귤 주스가 여섯 잔 이상인 경우를 빼야 한다. \(z = z' + 6\)으로 놓으면 \(x' + y' + z' = 1\)이고 그 해는 \({}_3\mathrm{H}_1 = 3\)가지이다. 그래서 조건을 모두 만족하는 주문은 \(36 - 3 = 33\)가지이다. 확인하면 \(z\)가 6 이상인 주문은 \((1, 2, 7)\), \((2, 2, 6)\), \((1, 3, 6)\)의 세 가지뿐이다. 즉 중복을 허락해 고르는 문제는 칸막이를 놓는 자리를 고르는 조합으로 바뀌고, 하한 조건은 먼저 나누어 준 뒤, 상한 조건은 어기는 경우를 빼서 센다.

아래 탐구 카드에서 같은 사탕을 친구들에게 나누는 방법을 칸막이로 세어 보고, 조건이 붙은 방정식의 정수해를 구해 보자.

1. 상한 조건이 여러 변수에 붙으면 어기는 경우들이 서로 겹칠 수 있다. 그때는 다음 절의 포함배제의 원리로, 둘을 동시에 어기는 경우를 다시 더해 주어야 정확한 수가 나온다.