離散数学・組合せ論の問題

方針　各種類のお菓子を何個選べるかを、$x$ のべき級数（母関数）で表します。それらの積の $x^8$ の係数が、求める選び方の数です。

各種類の母関数

チョコレート・クッキー・キャンディは、それぞれ 0 個以上何個でも選べます。$k$ 個選ぶことを $x^k$ で表すと、1 種類あたりの母関数は
$$1+x+x^2+\cdots =\frac{1}{1-x}$$
です。ゼリーは 0 個か 1 個しか選べないので、母関数は $1+x$ です。

積をとる

4 種類の個数の合計が 8 になる選び方の数は、母関数の積
$$F(x)=\frac{1}{(1-x{)}^3}(1+x)$$
の $x^8$ の係数 $[x^8]F(x)$ に等しくなります。展開したとき、各因子から選んだ項の指数の和が 8 になる組合せが、ちょうど 1 つの選び方に対応するからです。

係数を取り出す

公式
$$[x^n]\frac{1}{(1-x{)}^k}=\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$$
を $k=3$ で使うと、$[x^n]\frac{1}{(1-x{)}^3}=\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)$ です。

$F(x)=\frac{1}{(1-x{)}^3}+x\cdot \frac{1}{(1-x{)}^3}$ と分けて考えます。

• 第 1 項から得られる $x^8$ の係数は $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$ です。
• 第 2 項は $x$ が掛かっているので、$\frac{1}{(1-x{)}^3}$ の $x^7$ の係数を見ればよく、$\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$ です。

よって
$$[x^8]F(x)=45+36=81$$

確認

ゼリーを 0 個選ぶ場合、残り 3 種類で 8 個を選ぶので ${}_3{\mathrm{H}}_8=\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$ 通りです。ゼリーを 1 個選ぶ場合、残り 3 種類で 7 個を選ぶので ${}_3{\mathrm{H}}_7=\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$ 通りです。合計は $81$ 通りで、母関数による計算と一致します。

答え：$81$ 通り

ゼリーの個数は 0 個か 1 個のどちらかである。

(i) ゼリーを 0 個選ぶ場合：チョコレート・クッキー・キャンディから合計 8 個を選ぶ。これは $x+y+z=8$ の 0 以上の整数解の個数に等しく、$\left(\genfrac{}{}{0ex}{}{8+2}{2}\right)=\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$ 通り。

(ii) ゼリーを 1 個選ぶ場合：残り 3 種類から合計 7 個を選ぶ。$x+y+z=7$ の 0 以上の整数解の個数は $\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$ 通り。

合計は $45+36=81$ 通り。

検算：ゼリーの個数に上限がない場合の総数は $\left(\genfrac{}{}{0ex}{}{11}{3}\right)=165$ 通り。ゼリーを $k$ 個選ぶ場合の数は $\left(\genfrac{}{}{0ex}{}{8-k+2}{2}\right)$ で、$k=0,\dots ,8$ に対して $45+36+28+21+15+10+6+3+1=165$ となり一致する。ゼリーが 2 個以上の場合は $165-81=84$ 通りで、$28+21+15+10+6+3+1=84$ と合う。したがって答えは 81 通り。