代数的組合せ論の問題

母関数. 相異なる部分からなる分割 $\alpha$ は、各 $k\ge 1$ について「$k$ を部分に使うか使わないか」で決まる。使うとき $q^k$ と符号 $-1$ がつくので
$$\sum _{\alpha }(-1{)}^{\ell (\alpha )}{q}^{|\alpha |}=\prod _{k\ge 1}(1-q^k).$$
3 つ組についてはこれの 3 乗だから
$$\sum _{n\ge 0}{c}_n{q}^n=\prod _{k\ge 1}(1-q^k{)}^3.$$

ヤコビの恒等式. ヤコビの三重積公式
$$\prod _{k\ge 1}(1-x^{2k})(1+x^{2k-1}z)(1+x^{2k-1}{z}^{-1})=\sum _{m\in \mathbb{Z}}{x}^{m^2}{z}^m$$
で $x=q^{1/2}$、$z=-q^{-1/2}w$ とおく。$1+x^{2k-1}z=1-q^{k-1}w$、$1+x^{2k-1}{z}^{-1}=1-q^k{w}^{-1}$ だから、左辺は
$$\prod _{k\ge 1}(1-q^k)(1-q^{k-1}w)(1-q^k{w}^{-1})=(1-w)\prod _{k\ge 1}(1-q^k)(1-q^{k}w)(1-q^k{w}^{-1})$$
となる（$k=1$ の因子 $1-q^{0}w=1-w$ をくくり出した）。右辺は $x^{m^2}{z}^m=(-1{)}^m{q}^{m^2/2}{q}^{-m/2}{w}^m=(-1{)}^m{q}^{m(m-1)/2}{w}^m$ より
$$\sum _{m\in \mathbb{Z}}(-1{)}^m{q}^{m(m-1)/2}{w}^m.$$
ここで $m$ と $1-m$ の項を組にする。$(1-m)(-m)/2=m(m-1)/2$ で指数が等しく、符号は $(-1{)}^{1-m}=-(-1{)}^m$ なので、$m\ge 1$ について組の和は
$$(-1{)}^m{q}^{m(m-1)/2}\left(w^m-w^{1-m}\right)=(-1{)}^{m+1}{q}^{m(m-1)/2}{w}^{1-m}\left(1-w^{2m-1}\right).$$
両辺を $1-w$ で割ると、$\frac{1-w^{2m-1}}{1-w}=1+w+\cdots +w^{2m-2}$ なので
$$\prod _{k\ge 1}(1-q^k)(1-q^{k}w)(1-q^k{w}^{-1})=\sum _{m\ge 1}(-1{)}^{m+1}{q}^{m(m-1)/2}{w}^{1-m}\left(1+w+\cdots +w^{2m-2}\right).$$
両辺は $q$ の形式的べき級数で、各係数は $w$ のローラン多項式だから、$w=1$ を代入してよい。$1+w+\cdots +w^{2m-2}$ は $w=1$ で $2m-1$ になるので
$$\prod _{k\ge 1}(1-q^k{)}^3=\sum _{m\ge 1}(-1{)}^{m+1}(2m-1)q^{m(m-1)/2}.$$
$m=j+1$ と書き直すと、ヤコビの恒等式
$$\prod _{k\ge 1}(1-q^k{)}^3=\sum _{j\ge 0}(-1{)}^j(2j+1)q^{j(j+1)/2}$$
が得られる。したがって
$$c_n=\{\begin{array}{ll}(-1{)}^m(2m+1)& (n=\frac{m(m+1)}{2},m\ge 0)\\ 0& (n\text{ が三角数でない})\end{array}$$
である。（確認: $\prod (1-q^k{)}^3=1-3q+0\cdot q^2+5q^3+\cdots$ を直接展開しても一致する。たとえば $q^3$ の係数は $(1-q{)}^3$ の $-1$、$(-3q)(-3q^2)$ の $9$、$(1-q^3{)}^3$ の $-3$ の和で $5$。）

和の計算. $\frac{m(m+1)}{2}\le 1000$ となる $m$ の範囲を調べる。$\frac{44\cdot 45}{2}=990\le 1000<1035=\frac{45\cdot 46}{2}$ なので $0\le m\le 44$ である。よって
$$\sum _{n=0}^{1000}{c}_n=\sum _{m=0}^{44}(-1{)}^m(2m+1).$$
$m=2j,2j+1$ を組にすると $(4j+1)-(4j+3)=-2$ で、$j=0,1,\dots ,21$ の $22$ 組（$m=0,\dots ,43$）の和は $-44$。残る $m=44$ の項は $+89$。したがって
$$\sum _{n=0}^{1000}{c}_n=-44+89=45.$$

相異なる部分からなる分割の母関数は、符号 $(-1{)}^{\ell }$ をつけると ${\prod }_{k\ge 1}(1-q^k)$（各 $k$ を使えば $-q^k$、使わなければ $1$）。順序つき 3 つ組なので
$$\sum _{n\ge 0}{c}_n{q}^n=\prod _{k\ge 1}(1-q^k{)}^3.$$
ヤコビの 3 乗恒等式より
$$\prod _{k\ge 1}(1-q^k{)}^3=\sum _{m\ge 0}(-1{)}^m(2m+1)q^{m(m+1)/2}.$$
したがって $c_n$ は $n=m(m+1)/2$（三角数）のとき $(-1{)}^m(2m+1)$、それ以外は $0$。

$\frac{m(m+1)}{2}\le 1000$ をみたす最大の $m$ は $m=44$（$\frac{44\cdot 45}{2}=990$）で、$m=45$ では $1035>1000$。よって
$$\sum _{n=0}^{1000}{c}_n=\sum _{m=0}^{44}(-1{)}^m(2m+1).$$
$m=0,\dots ,43$ を 2 つずつ組にすると、$(2m+1)-(2m+3)=-2$ が 22 組で $-44$。残る $m=44$ の項は $+89$。合計 $-44+89=45$。

検算: 小さい範囲で、$m=\mathrm{0..2}$ の和は $1-3+5=3$、一般に ${\sum }_{m=0}^M(-1{)}^m(2m+1)=(-1{)}^M(M+1)$ で、$M=44$ なら $45$。一致する。また $c_1=-3$（$n=1$: $\alpha ,\beta ,\gamma$ のいずれかが $(1)$ で $3$ 通り、符号 $-1$）で、公式の $m=1$: $-3$ とも合う。