重複のある組み合わせ

これまで見てきた単純な組み合わせ問題では、異なるモノの組み合わせを考えていました。例えば「メンバーが 10人。その中から 3 人選ぶときの 3 人の組み合わせは何通りあるか？」というような問題です。

しかし今回は、同じモノが複数混ざる場合がある組み合わせを考えます。

例えば下の例のように「3 種類のヤキトリから 5 本注文する」というような場合です。そのときには同じヤキトリが数本入っている場合もあります。

さっそく練習問題で考えてみましょう。

\(3\) 種類のヤキトリ \(A\)、\(B\)、\(C\) を適当に組み合わせて \(5\) 本注文する。

組み合わせは何個あるか？

この問題は \(A\) だけ 5 本注文する場合や、\(A\) を 3 本、\(B\) を 1 本、\(C\) を 1 本のように混ぜこぜの場合があって、なかなかややこしいです。

この手の問題を解くときには、「区切り板」を使うといいです。

ヤキトリを \(\Box\)、区切り板を \(\blacklozenge\) として、次のように考えることにします。

\[ \begin{aligned} &\underbrace{\Box \Box \Box}_{A \text{が3本}} \blacklozenge \underbrace{\Box}_{B \text{が1本}} \blacklozenge \underbrace{\Box}_{C \text{が1本}}\\ &\underbrace{\Box \Box \Box}_{A \text{が3本}} \blacklozenge \underbrace{\Box \Box}_{B \text{が2本}} \blacklozenge\\ &\underbrace{\Box \Box \Box}_{A \text{が3本}} \blacklozenge \blacklozenge \underbrace{\Box \Box}_{C \text{が2本}} \\ &\cdots \end{aligned} \]

左側の区切りの左側の \(\Box\) の数を \(A\) の数、区切りにはさまれている \(\Box\) の数を \(B\) の数、右側の区切りの右側の \(\Box\) の数を \(C\) の数とします。

すると、この問題は \(5\) 個の \(\Box\) と \(2\) 個の \(\blacklozenge\) の順列の総数を求める問題として考えることができます。

「同じモノが含まれるときの順列」でみたように、同種のモノを区別して考えることにより、順列の \(1\) 個のパターンに対して \(5! \cdot 2!\) の組み合わせがあることがわかります。

パターンが \(N\) 個あるとすると、それぞれのモノを区別した順列は \(5! \cdot 2! \cdot N\) 個。

一方 \(7\) 個の異なるモノの順列は \(7!\) 個。

これらが等しいとして、\(N\) が以下のように計算できます。

\[ \begin{aligned} 5! \cdot 2! \cdot N &= 7!\\ \therefore \quad N &= \frac{7!}{5! 2!} &= \frac{7 \cdot 6}{2 \cdot 1}\\ &= 21 \end{aligned} \]

よって、\(5\) 本の焼き鳥の組み合わせは \(21\) 個あることがわかります。