スターリング数・ベル数の組合せ論的な意味

集合の分割

• スターリング数 $S(n, k):$ $n$ 個の区別できるボールを $k$ 個の区別できない箱で分割する。各箱には $1$ つ以上ボールを入れる
• ベル数 $B(n, k)$: $n$ 個の区別できるボールを $k$ 個の区別できない箱で分割する。ボールが入ってない箱があってもよい。

スターリング数の計算方法

詳しくは 第二種スターリング数 を参照

• スターリング数の漸化式

ベル数の計算方法

• スターリング数から計算する
• $B(n,n)$ について

kが小さいときのスターリング数、ベル数

• $k=1, n\geq 1$ のとき
  • $S(n,1) = 1$
  • $B(n,1) = 1$
• $k=2, n\geq 2$ のとき
  • $S(n,2) = (2^n-2)/2 = 2^{n-1} -1$
  • $B(n,2) = 2^n/2 = 2^{n-1}$
    • 玉が入ってない箱がある場合もない場合も2で割ってOK ($k=2$なら)
    • $S(n,2)$ からすべての玉を同じ箱に入れた場合を加えた場合の数になる。
• $k=3, n\geq 3$ のとき
  • $S(n,3)=(3^n-3\cdot 2^n + 3)/6$
    • 包除原理で全射の数を求めて $3! = 6$ で割る
  • $B(n,3)= (3^n-3)/6 + 1$
    • 基本的には軌道の長さは6だが、空箱が2つある場合は軌道の長さは3になっているので、$3^n/6$ では求まらない
      • 玉の入っている箱は区別できるが、玉が入っていない空箱は区別できない
    • 軌道の長さが $6$ のものは $3^n -3$ 通り、軌道の長さが $3$ のものは $3$ 通りなので、 $B(n,3)=(3^n-3)/6 + 3/3 = (3^n-3)/6 + 1$ と求まる
• よくあるミス

全列挙

• スターリング数: https://github.com/paruma/atcoder_rust/blob/115a0569966be5220811058ff4ff8c479b596b4a/src/example/math/stirling.rs
• ベル数: https://github.com/paruma/atcoder_rust/blob/115a0569966be5220811058ff4ff8c479b596b4a/src/example/math/bell.rs

スターリング数・ベル数のサイズ