代数的組合せ論の問題

母関数　$p(n)$ を $n$ の分割数（$p(0)=1$）、$P(q)={\prod }_{k\ge 1}\frac{1}{1-q^k}={\sum }_{n\ge 0}p(n)q^n$ とする。各 $k$ について「$k$ が現れないか、$1$ 回以上現れるか」を $x$ で数えると
$$F(x,q)=\sum _{\lambda }{x}^{d(\lambda )}{q}^{|\lambda |}=\prod _{k\ge 1}\left(1+\frac{x{q}^k}{1-q^k}\right).$$
$\theta =x\frac{\partial }{\partial x}$ とおくと ${\sum }_{\lambda }d(\lambda {)}^2{q}^{|\lambda |}={\theta }^{2}F{|}_{x=1}$。

$b_k(x)=\frac{x{a}_k}{1+x{a}_k}$（$a_k=\frac{q^k}{1-q^k}$）とおくと $\theta \log F={\sum }_k{b}_k$、$\theta b_k=b_k(1-b_k)$ であり、$x=1$ で $b_k=q^k$。よって
$${\theta }^{2}F{|}_{x=1}=P(q)\left[(\sum _k{q}^k{)}^2+\sum _k(q^k-q^{2k})\right]=P(q)\left[\sum _{k\ge 1}{q}^k+\sum _{\begin{array}{c}j,k\ge 1\\ j\ne k\end{array}}{q}^{j+k}\right].$$

（組合せ的には、$d(\lambda {)}^2={\sum }_k[k\in \lambda ]+{\sum }_{j\ne k}[j,k\in \lambda ]$ で、$k$ を含む $n$ の分割は $k$ を $1$ 個取り除くと $n-k$ の分割と一対一に対応する、ということである。）

したがって
$$\sum _{\lambda ⊢n}d(\lambda {)}^2=\sum _{k=1}^{n}p(n-k)+\sum _{s=3}^{n}c(s)p(n-s),$$
ただし $c(s)$ は $j+k=s$ となる相異なる正の整数の順序対 $(j,k)$ の個数で、$c(s)=(s-1)-[s\text{ が偶数}]$。

$n=10$ の計算　$p(0),\dots ,p(9)=1,1,2,3,5,7,11,15,22,30$。

第 1 項：${\sum }_{k=1}^{10}p(10-k)=30+22+15+11+7+5+3+2+1+1=97$。

第 2 項：
- $s=3$: $c=2,p(7)=15$ で $30$
- $s=4$: $c=2,p(6)=11$ で $22$
- $s=5$: $c=4,p(5)=7$ で $28$
- $s=6$: $c=4,p(4)=5$ で $20$
- $s=7$: $c=6,p(3)=3$ で $18$
- $s=8$: $c=6,p(2)=2$ で $12$
- $s=9$: $c=8,p(1)=1$ で $8$
- $s=10$: $c=8,p(0)=1$ で $8$

合計 $146$。

よって ${\sum }_{\lambda ⊢10}d(\lambda {)}^2=97+146=243$。

検算（$n=4$）　分割 $4,31,22,211,1111$ の $d$ は $1,2,1,2,1$ で $d^2$ の和は $11$。公式では $(3+2+1+1)+(2\cdot 1+2\cdot 1)=7+4=11$ で一致する。

$\lambda ⊢10$ に対し、値 $j$ が $\lambda$ に現れるとき $1$、そうでないとき $0$ をとる指示関数を ${\chi }_j(\lambda )$ とすると $d(\lambda )={\sum }_{j=1}^{10}{\chi }_j(\lambda )$。したがって
$$\sum _{\lambda }d(\lambda {)}^2=\sum _j\sum _{\lambda }{\chi }_j+2\sum _{i<j}\sum _{\lambda }{\chi }_i{\chi }_j.$$

値 $j$ を含む $10$ の分割は、$j$ を 1 つ取り除く対応により $10-j$ の分割と一対一なので $p(10-j)$ 個。同様に $i<j$ の両方を含む分割は $p(10-i-j)$ 個。

$p(0),\dots ,p(9)=1,1,2,3,5,7,11,15,22,30$。

第 1 項: ${\sum }_{j=1}^{10}p(10-j)=30+22+15+11+7+5+3+2+1+1=97$。

第 2 項: $i+j=s$ となる $i<j$ の組は $\lfloor (s-1)/2\rfloor$ 個なので
${\sum }_{s=3}^{10}\lfloor (s-1)/2\rfloor p(10-s)=1\cdot 15+1\cdot 11+2\cdot 7+2\cdot 5+3\cdot 3+3\cdot 2+4\cdot 1+4\cdot 1=15+11+14+10+9+6+4+4=73$。

よって総和は $97+2\cdot 73=243$。

検算: 第 1 項 $97$ は相異なる部分の個数の総和（既知の値 97）と一致する。また $p(10)=42$ なので平均 $d$ は約 $2.3$、$d^2$ の平均 $243/42\approx 5.8$ は妥当（$d\le 4$、$d^2$ の最大 16）。