スターリング数・ベル数（写像12相） の詳細バージョン

第一種スターリング数

定義

次の式を満たすように定義された $S_2(N, k)$ を第二種スターリング数という

$x^N = \sum_{k=0}^N S_2(N,k) x^{\underline{k}}$

• 下方階乗冪

組合せ論的な意味

区別できる $N$ 個のものを $K$ 個のグループに分ける（各グループには1つ以上入れる）分け方が $S_2(N, K)$ 通り

参考: スターリング数・ベル数（写像12相）

計算方法

• $N, K$ を1つ固定したときの $S_2(N, K)$ を $O(K \log N)$ で計算する方法
• $N$ を1つ固定したとき、$(S_2(N,k))_{k\in [0, N]}$ を $O( N \log N)$ で計算する方法（畳み込みを使う）
• $N, K$ を1つ固定したとき、$(S_2(n, k))_{n \in [0, N], k \in [0, K]}$を $O(NK)$ で計算する方法（漸化式）

応用例

N 乗和

$\displaystyle \sum_{x=0}^{X-1} x^{N} = \sum_{k=0}^N S_2(N,k) \frac{1}{k+1} X^{\underline{k+1}}$

• 証明
• ソースコード