インテジャーズ

INTEGERS

数、特に整数に関する記事。

秋山・谷川アルゴリズム

アルゴリズム

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


\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)

と計算されます。

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

f:id:integers:20180611022918p:plain

例えば、

f:id:integers:20180611170126p:plain

の部分は

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

と計算されています。


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


f:id:integers:20180611025413p:plain


なんと、関-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の補題1の第二種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}

が得られた。これは関-ベルヌーイ数の第二種Stirling数を用いた公式 - INTEGERSの(5)式より関-Bernoulli数に等しい。 Q.E.D.

最近、秋山・谷川アルゴリズムの広範な一般化が川﨑・大野によって得られています。