ねねじゃっじ　0014 - ベル数

解説を読んだ。

{1,2,3,...,N-1,N}を分割する方法の数をベル数という。B_Nで表す。

ベル数は

$B_N$

$=\sum_{i=1}^N 1/{k!} \sum_{k=1}^i (-1)^{i-k} k^N \binom{i}{k}$

$=\sum_{i=1}^N \sum_{k=1}^i \frac{(-1)^{i-k}}{(i-k)!} \frac{k^N}{k!}$ 　

i組のグループに分けるときの分け方についてそれぞれ包除原理を用いて求めている。

ここで、和を取る順序を変更する。k^N/k!についてまとめると、

$B_N=\sum_{k=1}^N \frac{k^N}{k!}\sum_{i=1}^{N-k} \frac{(-1)^{i}}{i!}$ 　

$\sum_{i=1}^{N-k} \frac{(-1)^{i}}{i!}$ については前計算しておくことができるので、O(N)でB_Nが求まる。