乗積$$\begin{align} Q_n(x) &= (1+x)(1+x^2)(1+x^3) \cdots (1+x^n) \\ &= \prod_{k=1}^{n}(1 + x^k) \end{align}$$に対して、多項式$$\begin{align} Q_n(x) &= q_n(0) + q_n(1)\,x + q_n(2)\,x^2 + \cdots + q_n \left(\frac{n(n+1)}{2} \right)\,x^\frac{n(n+1)}{2} \\ &= \sum_{r=0}^{\frac{n(n+1)}{2}}q_n(r)\,x^r \end{align}$$を考える続き。
とりあえず、$q_n(r)$ を書き出してみる試み。
| n\r | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | |||||||||||||||
| 1 | 1 | 1 | ||||||||||||||
| 2 | 1 | 1 | 1 | 1 | ||||||||||||
| 3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | |||||||||
| 4 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | |||||
| 5 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 1 | 1 | 1 |
この数の並びから何が読み取れるか。
ところで、乗積形より明らかに、$$\begin{align} Q_{n+1}(x) &= Q_n(x) \cdot (1+x^{n+1}) \\ &= Q_n(x) + x^{n+1}\,Q_n(x) \end{align}$$である。
さらに、一般に母関数の性質として、$x^n \cdot F(x)$ は $F(x)$ の係数列を $n$ だけ「右シフト」する操作である（推移則っていうの？）。また、線型性から、母関数同士の和は母関数の係数同士を加える操作である。たとえば、$q_5(6) = q_4(6)+q_4(1)$ であることが上表からも見えるわけだが、便宜上 $r$ を整数全体に拡張して、上表における右側の空白、すなわち $r > \frac{n(n+1)}{2}$ の領域と左側、すなわち $r < 0$ において、$q_n(r) = 0$ と定義した無限列として扱うことにすると、$$Q_n(x) = \sum_{r=0}^\infty q_n(r)\,x^r$$なる母関数で表せる $q_n(r)$ であることになる。さらに先程の母関数の関係も踏まえて、$$\begin{cases} q_0(0)=1 \\ q_n(r)=0 & \left(r < 0, r > \frac{n(n+1)}{2}\right) \\ q_n(r) = q_{n-1}(r)+q_{n-1}(r-n) \end{cases}$$という漸化式を導ける。めでたし。
さて、この数列が オンライン整数列大辞典 で発見されたわけだが。
うむ、リンク先の解説記事みたいになってしまっているなぁ。
もうちっとだけ続くんじゃ？
