前回の続きとして、$$\begin{cases} q_0(0)=1 \\ q_n(r)=0 & \qty(r < 0, r > \frac{n(n+1)}{2}) \\ 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 に定めた場合と同じ結果が生じるという話だ。
続く。