ヨーキョクデイ

いろいろ雑食

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

前回の続きとして、
$$\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}$$
という(一般化された)漸化式で表される数列 $q_n(r)$ を調べる。
$q_n(r)$ を書き出してみた表を発展させる。

n\r 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
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
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32

$n \to \infty$ の場合の極限を $q_\infty(r)$ と書くことにして、それも表に入れてみた。この数列 $q_\infty(r)$ は初回に少し触れた "strict partition" の数を示す物であり、例によってオンライン整数列大辞典にある。

上表では少しわかりにくいが、$r$ を固定して縦の変化を見たとき、$q_n(r)$ は $n=r$ のとき以来、値が変化しない。つまり、その時点で極限値たる $q_\infty(r)$ に収束しているわけで、次のような等式が得られる。
$$q_r(r)=q_{r+1}(r)=q_{r+2}(r)= \cdots = q_\infty(r)$$
要するに、$n \geq r$ において、
$$q_n(r)= q_\infty(r)$$
である。表の対角線を含むその下側を見れば "strict partition" が見えるよ、というお話。
これは漸化式からも容易にわかることであり、$n \geq r$ のとき、正の整数 $k$ に対して $n+k > r$ であるから、 $r-n-k < 0$ である。そのとき、$q_{n}(r-n-k) = 0$ であるから、
$$q_{n+k}(r) = q_{n+k -1}(r)+q_n(r-n-k) = q_{n+k -1}(r)$$
という具合である。
自然数の分割という観点からもこれは明らかにわかる。たとえば、6 の分割に 7 以上の整数は登場しえないわけで、分割の成分の上限を 6 より大きな整数と定めたり、上限を撤去したところで、それは上限を 6 に定めた場合と同じ結果が生じるという話だ。
続く。