秋山・谷川アルゴリズム

アルゴリズム

まず、正整数の逆数を並べます。

$\displaystyle 1 \quad \frac{1}{2} \quad \frac{1}{3} \quad \frac{1}{4} \quad \frac{1}{5} \quad \frac{1}{6} \quad \frac{1}{7} \quad \frac{1}{8} \quad \frac{1}{9} \quad \frac{1}{10} \quad \frac{1}{11} \quad \frac{1}{12} \quad \frac{1}{13} \quad \cdots$

その後、ある計算規則に基づいて一行ずつ下に数列を追加していきます。その計算規則は

f:id:integers:20180611024202p:plain:w200

新しい数列の左から数えて $N$ 番目の数が $C$ で、 $C$ の上にある数が $A, B$ のとき、

$C=N(A-B)$

と計算されます。

この計算規則に基づいて得られる数列の一部分を見てみましょう：

例えば、

の部分は

$\displaystyle \frac{5}{84}=6\left(\frac{3}{28}-\frac{7}{72}\right)$

と計算されています。

さて、こうして得られた計算結果の一番左端に注目してみましょう。

なんと、関-Bernoulli数になっています！！

integers.hatenablog.com

これが、秋山・谷川アルゴリズムです。

証明(by 金子先生)

数列 $\{b_{n,k}\}_{n, k\geq 0}$ を $b_{0, k}=\frac{1}{k+1}$ および漸化式

$b_{n+1,k}=(k+1)(b_{n,k}-b_{n,k+1})$

で定義するとき、 $b_{n,0}=B_n$ を示せばよい( $B_n$ は関-Bernoulli数)。 $\displaystyle f_n(t):=\sum_{k=0}^{\infty}b_{n,k}t^k$ と母関数を作ると、漸化式より $n\geq 1$ のとき

$\begin{align}f_n(t) &= \sum_{k=0}^{\infty}(k+1)(b_{n-1,k}-b_{n-1,k+1})t^k\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k}t^{k+1}\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k+1}t^{k+1}\right)\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left(tf_{n-1}(t)\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(f_{n-1}(t)-b_{n-1,0}\right)\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left( (t-1)f_{n-1}(t)\right)\end{align}$

が成り立つので、 $g_n(t):=(t-1)f_n(t)$ とおけば

$\displaystyle g_n(t)=(t-1)\frac{\mathrm{d}}{\mathrm{d}t}(g_{n-1}(t) )$

であり、

$\displaystyle g_n(t)=\left( (t-1)\frac{\mathrm{d}}{\mathrm{d}t}\right)^ng_{0}(t)$

を得る。Bell数の母関数表示と第二種Stirling数 - INTEGERSの補題１の第二種Stirling数に関する

$\displaystyle \left(x\frac{\mathrm{d}}{\mathrm{d}x}\right)^n=\sum_{k=0}^n\left\{ {n \atop k}\right\}x^k\left(\frac{\mathrm{d}}{\mathrm{d}x}\right)^k$

という公式があるので、 $x\mapsto t-1$ と変数変換して利用すれば

$\displaystyle g_n(t) = \sum_{k=0}^n\left\{ {n\atop k}\right\}(t-1)^k\left(\frac{\mathrm{d}}{\mathrm{d}t}\right)^kg_0(t)$

なる等式を得る。右辺の微分を実行して $t=0$ を代入して $-1$ 倍すると、

$\begin{align} b_{n,0}&=-\sum_{k=0}^n\left\{ {n\atop k}\right\}(-1)^kk!(b_{0,k-1}-b_{0,k})\\ &=\sum_{k=0}^n(-1)^kk!\left( (k+1)\left\{ {n \atop k+1}\right\}+\left\{ {n\atop k}\right\}\right)b_{0,k} \\ &=\sum_{k=0}^n(-1)^kk!\left\{ {n+1\atop k}\right\}b_{0,k}\\ &=\sum_{k=0}^n\frac{(-1)^kk!\left\{ {n+1 \atop k+1} \right\}}{k+1}\end{align}$