별과 막대¶
별과 막대는 특정 조합론 문제를 풀기 위한 수학적 기법입니다. 이 기법은 서로 구별되지 않는 물체들을 묶는 방법의 수를 세고자 할 때마다 등장합니다.
정리¶
서로 구별되지 않는 물체 $n$개를 이름표가 붙은 상자 $k$개에 넣는 방법의 수는 다음과 같습니다.
증명에서는 물체를 별로 바꾸고 상자들을 막대로 구분합니다(이름이 여기서 유래했습니다). 예를 들어, 첫 번째 상자에 물체가 하나, 두 번째 상자에 물체가 두 개 있고, 세 번째 상자는 비어 있으며, 마지막 상자에 물체가 두 개 있는 상황을 $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$로 나타낼 수 있습니다. 이것은 물체 5개를 상자 4개에 나누는 방법 중 하나입니다.
모든 분할은 별 $n$개와 막대 $k - 1$개로 나타낼 수 있고, 별 $n$개와 막대 $k - 1$개로 이루어진 모든 별과 막대 순열은 각각 하나의 분할을 나타낸다는 것은 꽤 자명합니다. 따라서 서로 구별되지 않는 물체 $n$개를 이름표가 붙은 상자 $k$개에 나누는 방법의 수는 별 $n$개와 막대 $k - 1$개의 순열의 수와 같습니다. 이항 계수로부터 원하는 공식을 얻을 수 있습니다.
음이 아닌 정수 합의 개수¶
이 문제는 위 정리를 직접 적용한 것입니다.
다음 방정식의 해의 개수를 세고자 합니다.
단, $x_i \ge 0$입니다.
이번에도 해를 별과 막대로 나타낼 수 있습니다. 예를 들어, $n = 4$, $k = 3$일 때 해 $1 + 3 + 0 = 4$는 $\bigstar | \bigstar \bigstar \bigstar |$로 나타낼 수 있습니다.
이것이 정확히 별과 막대 정리라는 것은 쉽게 알 수 있습니다. 따라서 답은 $\binom{n + k - 1}{n}$입니다.
양의 정수 합의 개수¶
두 번째 정리는 양의 정수에 대해 좋은 해석을 제공합니다. 다음 방정식의 해를 생각해 봅시다.
단, $x_i \ge 1$입니다.
별 $n$개를 생각할 수 있지만, 이번에는 별 사이에 최대 막대 하나만 놓을 수 있습니다. 별 사이에 막대가 두 개 있으면 $x_i=0$, 즉 빈 상자를 나타내기 때문입니다. 막대 $k-1$개를 놓을 수 있는 별 사이의 틈은 $n-1$개이므로, 답은 $\binom{n-1}{k-1}$입니다.
하한이 있는 정수 합의 개수¶
이는 서로 다른 하한이 있는 정수 합으로 쉽게 확장할 수 있습니다. 즉, 다음 방정식의 해의 개수를 세고자 합니다.
단, $x_i \ge a_i$입니다.
$x_i' := x_i - a_i$로 치환하면 다음과 같은 변형된 방정식을 얻습니다.
단, $x_i' \ge 0$입니다. 이렇게 문제를 $x_i' \ge 0$인 더 간단한 경우로 환원했으므로, 다시 별과 막대 정리를 적용할 수 있습니다.
상한이 있는 정수 합의 개수¶
포함-배제 원리를 활용하면 정수에 상한을 두어 제한할 수도 있습니다. 해당 문서의 상한이 있는 정수 합의 개수 절을 참고하십시오.