すると、今度は \(i=N-1\) での呼び出し回数は \(O(Nf(N,K))\) 回となることが示せます。

とありますが、少し非自明に感じたので、証明を記しておきます。

まず、\(i=N-1\) での呼び出しに現れる長さ \(N-1\) の数列の集合を \(\mathcal A\) とします。すなわち、

\[ \mathcal A = \left\{ (A_1,\ldots,A_{N-1}) \ \middle| \ A_j\ge 0,\ \sum_{j=1}^{N-1}jA_j\le K \right\} \]

とします。 \(i=N-1\) での呼び出しは、\(\mathcal A\) の各要素についてちょうど一度ずつ行われるため、その呼び出し回数は \(|\mathcal A|\) です。

今回、列挙したい長さ \(N\) の数列の集合を \(\mathcal B\) とします。すなわち、

\[ \mathcal B = \left\{ (B_1,\ldots,B_N) \ \middle|\ B_j\ge 0,\ \sum_{j=1}^{N}jB_j=K \right\} \]

です。以下では、

\[ |\mathcal A|\le N|\mathcal B| \left(= N f(N, K) \right) \]

を示します。

各 \(A\in\mathcal A\) に対して、ある \(B\in\mathcal B\) を対応させる写像を考えましょう。

\(A=(A_1,\ldots,A_{N-1})\in\mathcal A\) について

\[ K-\sum_{j=1}^{N-1}jA_j=Np+q, \ 0\le q <N \]

を満たすような \(p, q\) を考えます。そして

\[ B = (A_1, A_2, \dots, A_{q-1}, A_q \red{+ 1}, A_{q+1}, A_{N-1}, \red{p}) \]

とします。（\(q = 0\) のときは \(+1\) の加算はしないことにします）このとき \(B\in\mathcal B\) であることは簡単に確認できます。

さて、この写像のある出力 \(B\) に対して、入力として考えられる \(A\) はいくつあるでしょうか？これは、「 \(B\) のはじめ \(N-1\) 項をとりだし、（どこかの項を \(-1\) した or なにもしない）によって得られる \(A\) 」だけです。つまり、ある \(B\) に対してありうる入力は高々 \(N\) 個です。

よって \(|\mathcal A|\le N|\mathcal B|\) が示されました。