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

りんご・みかん・ももの個数をそれぞれ $a,b,c$ とすると、求める選び方の数は
$$a+b+c=9,a,b,c\text{ は }0\text{ 以上の整数},c\le 2$$
を満たす組 $(a,b,c)$ の個数である。

母関数を作る. 個数 $k$ を $x^k$ で表す。
- りんご（何個でもよい）: $1+x+x^2+\cdots =\frac{1}{1-x}$
- みかん（何個でもよい）: $\frac{1}{1-x}$
- もも（2 個以下）: $1+x+x^2=\frac{1-x^3}{1-x}$

これらを掛け合わせて展開したとき、$x^9$ の項は $x^a\cdot x^b\cdot x^c$（$a+b+c=9$）の形の積から 1 つずつ現れる。したがって、求める数は
$$[x^9]\frac{1}{1-x}\cdot \frac{1}{1-x}\cdot \frac{1-x^3}{1-x}=[x^9]\frac{1-x^3}{(1-x{)}^3}$$
である。

係数を取り出す. 公式 $[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)$ となる。
$$\frac{1-x^3}{(1-x{)}^3}=\frac{1}{(1-x{)}^3}-x^3\cdot \frac{1}{(1-x{)}^3}$$
と分ける。第 2 項の $x^9$ の係数は、$\frac{1}{(1-x{)}^3}$ の $x^6$ の係数に等しい。よって
$$[x^9]\frac{1-x^3}{(1-x{)}^3}=\left(\genfrac{}{}{0ex}{}{11}{2}\right)-\left(\genfrac{}{}{0ex}{}{8}{2}\right)=55-28=27.$$

（確認: $c=0,1,2$ のとき、$a+b=9,8,7$ の解はそれぞれ $10,9,8$ 個あり、合計 $27$ 個となって一致する。）

答え: $27$ 通り

りんご・みかんの個数をそれぞれ $a,b\ge 0$、ももの個数を $c$ ($0\le c\le 2$) とし、$a+b+c=9$ となる組の数を求める。

母関数は $\frac{1}{(1-x{)}^2}(1+x+x^2)$ で、$x^9$ の係数が答えである。

$\frac{1}{(1-x{)}^2}={\sum }_{n\ge 0}(n+1)x^n$ なので、$x^9$ の係数は $c=0,1,2$ に対応して
- $c=0$: $a+b=9$ より $10$
- $c=1$: $a+b=8$ より $9$
- $c=2$: $a+b=7$ より $8$

合計は $10+9+8=27$。

検算: ももの制限がなければ $\left(\genfrac{}{}{0ex}{}{11}{2}\right)=55$ 通り。$c\ge 3$ は $a+b+c^{\prime }=6$ の解の数 $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$ 通り。$55-28=27$ で一致する。