スターリング数・ベル数

集合の分割

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

$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$ と求まる
よくあるミス

$B(12,12)\approx 4\times 10^6$