ヨーキョクデイ

いろいろ雑食

(1+x^k) の乗積を展開したときの係数・その 2

乗積
$$\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}$$
という漸化式を導ける。めでたし。
さて、この数列が オンライン整数列大辞典 で発見されたわけだが。

うむ、リンク先の解説記事みたいになってしまっているなぁ。
もうちっとだけ続くんじゃ?