スターズ・アンド・バーズ（重複組み合わせ）計算

スターズ・アンド・バーズは、同じもの n 個を区別できる k 個のグループに分ける方法の数を数えます。子どもたちにお菓子を分ける、候補者に票を割り振る、x₁ + x₂ + … + xₖ = n の非負整数解を求める、といった問題がその例です。ものを一列に並んだ星と考え、棒を k − 1 本置いてグループに区切ると考えます。この計算ツールは、空のグループ、グループあたりの最小数と最大数に対応し、場合の数が少ないときは、すべての並びを一覧にします。

使い方

1. 同じものの個数 n を入力します。
2. 区別できるグループの数 k を入力します。
3. グループあたりの最小数を決めます。空のグループを許すなら 0、全員が最低1つ受け取るなら 1 です。
4. 必要ならグループあたりの最大数を入力します。
5. 場合の数、使った式、そして小さい場合はすべての並びを確認します。

計算式

場合の数 = C(n + k − 1, k − 1)；各グループ最低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 通りです。どの子も最低1個もらうなら、まず1個ずつ配って残りの7個を分けるので、C(9, 2) = 36 通りです。