代数的組合せ論の問題

分割数を $p(n)$（$p(0)=1$）とし、$P(x)={\sum }_{n\ge 0}p(n)x^n={\prod }_{k\ge 1}\frac{1}{1-x^k}$ とする。

ステップ 1（2 変数母関数） 部分 $k$ を少なくとも 1 回使うごとに $t$ を 1 つ掛けると、
$$F(x,t)=\sum _{n\ge 0}\sum _{\lambda ⊢n}{t}^{d(\lambda )}{x}^n=\prod _{k\ge 1}(1+t\frac{x^k}{1-x^k})$$
となる（因子 $k$ の $1$ は部分 $k$ を使わない場合、$t(x^k+x^{2k}+\cdots )$ は 1 回以上使う場合）。

ステップ 2（$t$ で微分して $t=1$ を代入） $t=1$ で各因子は $1+\frac{x^k}{1-x^k}=\frac{1}{1-x^k}$ となり、因子 $k$ の $t$ による微分は $\frac{x^k}{1-x^k}$ なので、積の微分法より
$${\frac{\partial F}{\partial t}|}_{t=1}=\sum _{k\ge 1}\frac{x^k}{1-x^k}\cdot (1-x^k)\prod _{j\ge 1}\frac{1}{1-x^j}=P(x)\sum _{k\ge 1}{x}^k=\frac{x}{1-x}P(x).$$
左辺の $x^n$ の係数は ${\sum }_{\lambda ⊢n}d(\lambda )$ である。

ステップ 3（係数の比較） $\frac{x}{1-x}P(x)={\sum }_n({\sum }_{j=0}^{n-1}p(j))x^n$ なので
$$\sum _{\lambda ⊢10}d(\lambda )=p(0)+p(1)+\cdots +p(9).$$
（組合せ論的には、部分 $k$ を含む $n$ の分割は、$k$ を 1 つ取り除くことで $n-k$ の分割と 1 対 1 に対応するので、その個数は $p(n-k)$ であり、${\sum }_{\lambda }d(\lambda )={\sum }_{k=1}^{n}p(n-k)$ となる、と言い換えることもできる。）

ステップ 4（計算） $p(0),\dots ,p(9)$ は $1,1,2,3,5,7,11,15,22,30$ なので
$$1+1+2+3+5+7+11+15+22+30=97.$$

（小さい場合の検算：$n=3$ では $(3),(2,1),(1,1,1)$ の $d$ は $1,2,1$ で和 $4$、$p(0)+p(1)+p(2)=4$ と一致する。）

$d(\lambda )={\sum }_{k=1}^{10}1[\lambda \text{ は部分 }k\text{ を含む}]$ なので、${\sum }_{\lambda ⊢10}d(\lambda )={\sum }_{k=1}^{10}\#\{\lambda ⊢10:k\text{ を部分にもつ}\}$。

部分 $k$ を少なくとも 1 つもつ分割は、$k$ を 1 つ取り除くことで $10-k$ の任意の分割と 1 対 1 に対応する（逆に $10-k$ の分割に $k$ を 1 つ加えれば $k$ を含む $10$ の分割）。よって個数は $p(10-k)$。

求める和は ${\sum }_{k=1}^{10}p(10-k)=p(0)+p(1)+\cdots +p(9)$。

$p(0),\dots ,p(9)=1,1,2,3,5,7,11,15,22,30$ なので和は $1+1+2+3+5+7+11+15+22+30=97$。

検算：小さい $n$ で確認する。$n=4$ の分割 $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$ の $d$ は $1,2,1,2,1$ で和 $7$。公式 $p(0)+p(1)+p(2)+p(3)=1+1+2+3=7$ で一致。