별과 막대 계산기 (중복조합)

별과 막대는 똑같은 물건 n개를 서로 다른 k개의 그룹에 나누어 주는 방법의 수를 셉니다. 아이들에게 사탕을 나누거나, 후보들에게 표를 나누거나, x₁ + x₂ + … + xₖ = n의 음이 아닌 정수해를 구하는 문제가 그 예입니다. 물건을 한 줄로 늘어선 별로 보고, 막대 k − 1개를 놓아 그룹으로 나눈다고 생각하세요. 이 계산기는 빈 그룹, 그룹당 최소 개수, 그룹당 최대 개수를 모두 다루며, 경우의 수가 적으면 모든 배열을 나열합니다.

사용 방법

1. 똑같은 물건의 수 n을 입력합니다.
2. 서로 다른 그룹의 수 k를 입력합니다.
3. 그룹당 최소 개수를 정합니다. 빈 그룹을 허용하면 0, 모두 최소 하나씩 받아야 하면 1입니다.
4. 필요하면 그룹당 최대 개수를 입력합니다.
5. 경우의 수와 사용한 식, 그리고 작은 경우에는 모든 배열을 확인합니다.

계산식

경우의 수 = C(n + k − 1, k − 1), 그룹마다 최소 하나이면 C(n − 1, k − 1)

별 n개와 막대 k − 1개가 늘어선 줄에는 n + k − 1개의 자리가 있고, 그중 어느 k − 1개가 막대인지 정하면 배열이 정해집니다. 그룹당 최소 m개이면 먼저 k·m개를 나누어 주고, 남은 n − k·m개를 자유롭게 나눕니다. 최소가 m일 때 N = n − km, c = 최대 − m이라 하면, 포함-배제 원리에서 Σ (−1)ʲ C(k, j) C(N − j(c + 1) + k − 1, k − 1)을 얻습니다.

예시

똑같은 사탕 10개를 아이 3명에게 나누되 못 받는 아이가 있어도 된다고 합시다. 별 10개와 막대 2개가 12자리에 놓이므로 C(12, 2) = 12 × 11 / 2 = 66가지입니다. 모든 아이가 최소 하나씩 받아야 한다면 먼저 하나씩 나눠 주고 남은 7개를 나누므로 C(9, 2) = 36가지입니다.