インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

Bell数に関するHurst-Schultzの定理

B_nをBell数とします。Bell数については

integers.hatenablog.com
integers.hatenablog.com

で記事にしましたが、書こうと思ってその後書き忘れていた部分を書こうと思います(4回分)。

Bell数については次の二つの関係式が重要です:

\displaystyle B_n = \sum_{k=0}^n \left\{ {n \atop k} \right\} ‐①

\displaystyle B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_k ‐②

ここで、\displaystyle \left\{ {n \atop k} \right\}は第二種Stirling数です。第二種Stirling数については漸化式

\displaystyle \left\{ {n+1 \atop k} \right\} =k\left\{ {n \atop k} \right\} +\left\{ {n \atop k-1} \right\}

が重要です。

今回のメインは①、②の両方を含む一般化であるHurst-Schultzの定理の解説です。

Hurst-Schultzの定理 n, jを非負整数とするとき、
\displaystyle B_{n+j}=\sum_{k=0}^n \left( \sum_{r=0}^j\binom{j}{r}B_{j-r}k^r \right) \left\{ {n \atop k} \right\}
が成り立つ。

j=0とすれば①が、n=1とした後にj\mapsto nとすれば②が復元できます。

証明. jに関する帰納法で証明する。j=0のときは容易にチェックできる。n+(j+1)=(n+1)+jなので、jで正しいと仮定すると、

\begin{equation}\begin{split} B_{n+j+1} &= \sum_{k=0}^{n+1} \left( \sum_{r=0}^j\binom{j}{r}B_{j-r}k^r\right) \left\{ {n+1 \atop k} \right\} \\ &= \sum_{k=0}^{n+1}\left( \sum_{r=0}^j\binom{j}{r}B_{j-r}k^r\right) \left( k\left\{ {n \atop k} \right\}+\left\{ {n \atop k-1} \right\}\right) \\ &= \sum_{k=0}^n \left( \sum_{r=0}^j\binom{j}{r}B_{j-r}k^r \right) \left\{ {n \atop k} \right\} + \sum_{k=0}^n\left( \sum_{r=0}^j \binom{j}{r} B_{j-r} (k+1)^r \right) \left\{ {n \atop k} \right\} \\ &= \sum_{k=0}^n\sum_{l=0}^{j+1}\left\{ \sum_{r=l}^j\binom{j}{r}\binom{r}{l}B_{j-r}+\binom{j}{l-1}B_{j-(l-1)}\right\} k^l\left\{ {n \atop k} \right\}\end{split}\end{equation}

と変形できる。最後は二項定理を用いている。

\displaystyle \binom{j}{r}\binom{r}{l} = \binom{j}{l}\binom{j-l}{r-l}

なので、d=j-rとおくことにより、

\begin{equation}\begin{split} \text{中括弧の中身} &= \binom{j}{l} \left\{ \sum_{d=0}^{j-l}\binom{j-l}{d}B_j \right\} +\binom{j}{l-1}B_{j-l+1} \\ &= \binom{j}{l}B_{j-l+1} + \binom{j}{l-1}B_{j-l+1} \\ &= \binom{j+1}{l}B_{j-l+1}\end{split}\end{equation}

を得る(②を用いた)。よって、

\displaystyle B_{n+j+1}=\sum_{k=0}^n\left( \sum_{l=0}^{j+1}\binom{j+1}{l}B_{j-l+1}k^l\right) \left\{ {n \atop k} \right\}

となって、j+1のときも成立することが示された。 Q.E.D.