ヨーキョクデイ

いろいろ雑食

(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) に収束しているわけで、次のような等式が得られる。

\displaystyle q_r(r)=q_{r+1}(r)=q_{r+2}(r)= \cdots = q_\infty(r)

要するに、 n \geq r において、

\displaystyle 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 であるから、

\displaystyle q_{n+k}(r) = q_{n+k -1}(r)+q_n(r-n-k) = q_{n+k -1}(r)

という具合である。

自然数の分割という観点からもこれは明らかにわかる。たとえば、6 の分割に 7 以上の整数は登場しえないわけで、分割の成分の上限を 6 より大きな整数と定めたり、上限を撤去したところで、それは上限を 6 に定めた場合と同じ結果が生じるという話だ。

続く。