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

方針 部分の大きさに制限のある分割の母関数を使う。

部分 $1$ を $a$ 個、部分 $2$ を $b$ 個、部分 $3$ を $c$ 個使う（$a,b,c$ は $0$ 以上の整数）とすると、どの部分も $3$ 以下である $8$ の分割は
$$a+2b+3c=8$$
を満たす $(a,b,c)$ と $1$ 対 $1$ に対応する。

部分 $k$ を使う個数の選び方を $1+x^k+x^{2k}+\cdots =\frac{1}{1-x^k}$ で表すと、求める個数は
$$\frac{1}{1-x}\cdot \frac{1}{1-x^2}\cdot \frac{1}{1-x^3}=\left(\sum _{a\ge 0}{x}^a\right)\left(\sum _{b\ge 0}{x}^{2b}\right)\left(\sum _{c\ge 0}{x}^{3c}\right)$$
の $x^8$ の係数である。

係数の計算 $x^a\cdot x^{2b}\cdot x^{3c}=x^8$ となる組を数える。$b,c$ を決めると $a=8-2b-3c$ が $0$ 以上ならちょうど $1$ つ決まるので、$2b+3c\le 8$ を満たす $(b,c)$ の個数を数えればよい。
- $c=0$ のとき $2b\le 8$ より $b=0,1,2,3,4$ の $5$ 個
- $c=1$ のとき $2b\le 5$ より $b=0,1,2$ の $3$ 個
- $c=2$ のとき $2b\le 2$ より $b=0,1$ の $2$ 個

（$c\ge 3$ は $3c>8$ なので不可。）よって係数は $5+3+2=10$。

確認 実際に書き出すと
$3+3+2,3+3+1+1,3+2+2+1,3+2+1+1+1,3+1+1+1+1+1,2+2+2+2,2+2+2+1+1,2+2+1+1+1+1,2+1+1+1+1+1+1,1+1+1+1+1+1+1+1$
の $10$ 個で一致する。

答え：$10$

$\frac{1}{(1-x)(1-x^2)}$ の $x^k$ の係数は、1 と 2 だけを使う $k$ の分割の個数で、$c_k=\lfloor k/2\rfloor +1$ となる。
$c_0,\dots ,c_8=1,1,2,2,3,3,4,4,5$。

これに $\frac{1}{1-x^3}=1+x^3+x^6+\cdots$ を掛けると、$x^8$ の係数は
$c_8+c_5+c_2=5+3+2=10$。

検算：3 を使う個数で場合分けする。
- 3 が 0 個：8 を 1 と 2 で表す方法は 5 通り。
- 3 が 1 個：残り 5 を 1 と 2 で表す方法は 3 通り。
- 3 が 2 個：残り 2 を 1 と 2 で表す方法は 2 通り。

合計は $5+3+2=10$ で、母関数の計算と一致する。