説明

第2種スターリング数 $\{ {n \atop k} \}$ を求める。

区別できる $n$ 個のボールを区別できない $k$ 個の箱に分割する方法の数を与える。

計算方法は包除原理の考え方に基づく。$k$ 個の箱のうち空箱があったら違反。違反する個数で包除する。具体的には $k$ 個の箱から $k-i$ 個選んだとして、それらの箱にボールを入れない方法の数 $({k \atop i})i^{n}$ を足し引きする。

$\{ {n \atop k} \} = { \frac {1}{k!} } \sum_{i=0}^{k} {(-1)^{k-i} ({k \atop i})i^{n} }$

計算量

  • $O(K \log N)$

実装例

依存ライブラリ Mod-Int Combination

  • stirling_number_second($n$):= $\{ \textstyle {n \atop k} \}$ を返す
template< typename T >
T stirling_number_second(int n, int k) {
  Combination< T > table(k);
  T ret = 0;
  for(int i = 0; i <= k; i++) {
    auto add = T(i).pow(n) * table.C(k, i);
    if((k - i) & 1) ret -= add;
    else ret += add;
  }
  return ret * table.rfact(k);
}

検証

AOJ DPL_5_I ボールと箱 9

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_5_I"

#include "../../template/template.cpp"

#include "../mod-int.cpp"
#include "../combination.cpp"

#include "../stirling-number-second.cpp"

int main() {
  int N, K;
  cin >> N >> K;
  cout << stirling_number_second< modint >(N, K) << endl;
}