第2種スターリング数
区別できる$ n個の玉を、区別できないちょうど$ k個の箱に入れる方法を$ S(n,k)と表す。
式
以下の漸化式で表される。
$ S(n, n) = 1
$ S(n, 0) = 0
$ S(0, k) = 0
$ S(n \ge 1, k \ge 1) = S(n - 1, k - 1) + kS(n - 1, k)
一般項は以下のように表される。
$ S(n, k) = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n = \sum_{j=0}^k \frac{(-1)^{k-j}j^n}{j!(k-j)!}
ベル数$ B_{n, k}を使って以下のように表すことができる。
$ S(n, k) = B_{n,k} - B_{n,k-1}
$ nを固定した形は通常型母関数により以下のように表される。（ここで$ T_n(x)はトゥシャール多項式） $ S_{n,*}(x) = \sum_{k = 0}^\infty S(n, k) x^n = T_n(x) = e^{-x} \left( \sum_{k = 0}^\infty \frac{k^n x^k}{k!} \right)
$ kを固定した形は指数型母関数により以下のように表される。
$ S_{*,k}(x) = \sum_{n=0}^\infty S(n, k) \frac{x^n}{n!} = \frac{1}{k!} (e^x - 1)^k
実装方法
DPにより、すべての$ n \in [0, N], k \in [0, K] について$ S(n,k) を$ O(NK)で求めることができる。
code:Rust
use ac_library_rs::modint::ModIntBase;
fn stirling2_table<M: ModIntBase>(n_max: usize, k_max: usize) -> Vec<Vec<M>> {
for n in 1 ..= n_max {
if n <= k_max {
}
for k in 2 ..= (n - 1).min(k_max) {
}
}
table
}
二項係数を前計算し、一般項の式を使うと特定の$ N, Kについて$ S(N, K)を$ O(K \log N)で求めることができる。
code:Rust
use ac_library_rs::modint::ModIntBase;
fn stirling2<M: ModIntBase>(n: usize, k: usize) -> M {
fact_invk = (1 ..= k).fold(M::from(1), |f, k| f * M::from(k) ).inv(); for k in (1 .. k).rev() {
fact_invk = fact_invk + 1 * M::from(k + 1); }
let mut ans = M::from(0);
for j in 0 ..= k {
if (k - j) % 2 == 0 {
ans += M::from(j).pow(n as u64) * fact_invj * fact_invk - j; } else {
ans -= M::from(j).pow(n as u64) * fact_invj * fact_invk - j; }
}
ans
}
通常型母関数を用いて、特定の$ N およびすべての$ k \in [0, N] についての$ S(N, k) を$ O(N\log N) で求めることができる。
code:Rust
use ac_library::{convolution, modint::{Modulus, StaticModInt}};
fn stirling2_fps_fixed_n<Mod: Modulus>(n: usize) -> Vec<StaticModInt<Mod>> {
fact_invn = (1 ..= n).fold(StaticModInt::<Mod>::from(1), |f, k| f * k ).inv(); for k in (1 .. n).rev() {
fact_invk = fact_invk + 1 * (k + 1); }
for i in 0 ..= n {
fi = StaticModInt::<Mod>::from(i).pow(n as u64) * fact_invi; gi = if i % 2 == 0 { fact_invi } else { -fact_invi }; }
let mut h = convolution(&f, &g);
h.truncate(n + 1);
h
}
指数型母関数を用いて、すべての$ n \in [0, N] および特定の$ K について$ S(n, K) を$ O(N \log N + K) で求めることができる。
code:Rust
use ac_library::modint::ModIntBase;
use my_library::FPS;
fn stirling2_fps_fixed_k<M: ModIntBase>(n_max: usize, k: usize) -> Vec<M> {
f = f.exp();
f = f.pow(k as u64); // f = (f.log() * M::from(k)).exp();
f *= (1 ..= k).fold(M::from(1), |f, k| f * M::from(k) ).inv();
for n in 1 ..= n_max {
factn = factn - 1 * M::from(n); }
(0 ..= n_max).map(|n| fn * factn ).collect() }
参考