ヨーキョクデイ

いろいろ雑食

(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 と定義した無限列として扱うことにすると、

\displaystyle 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}

という漸化式を導ける。めでたし。

さて、この数列が オンライン整数列大辞典 で発見されたわけだが。

うむ、リンク先の解説記事みたいになってしまっているなぁ。

もうちっとだけ続くんじゃ?