Bell数

$[n]$ の分割 $\pi$ のブロックを、最小元の小さい順に $T_1,T_2,\dots$ と番号づけ、$i\in T_{a_i}$ で $a_i$ を定める。$1\in T_1$ なので $a_1=1$ である。$i+1$ が新しいブロックの最小元なら、そのブロックの番号はそれまでに使った番号の最大値に $1$ を足したものなので、条件を満たす。逆に条件を満たす列から、$T_j:=\{i\mid a_i=j\}$ とおく。条件により、列の中で新しい番号は $1,2,3,\dots$ の順に 1 つずつ初めて現れるので、使われる番号は $1,2,\dots,\max a_i$ のすべてで、$T_j$ の最小元（$j$ が初めて現れる位置）は $j$ とともに増える。よって $T_1,T_2,\dots$ は最小元の小さい順に番号づけた分割で、この列に対応する分割が戻る。2 つの対応は互いに逆である。$\square$

$[n+1]$ の分割を、$n+1$ を含むブロック $T$ で分類する。$T$ に入らない $[n]$ の元の集合を $R:=[n+1]\setminus T$ とし、$i:=|R|$ とする。$R\subset[n]$ の選び方は $\binom ni$ 通りで、$T=[n+1]\setminus R$ はそれで決まる。残りのブロックは $R$ の分割で、$B_i$ 通りある。逆に $R$ と $R$ の分割を決めれば、それに $T$ を加えた $[n+1]$ の分割がただ 1 つ定まる。$i=0,\dots,n$ について足せばよい。$\square$

左辺を $F(x)$ とおく。$F'(x)=\sum_{n\ge0}B_{n+1}x^n/n!$ である。一方、指数型母関数の積の規則（母関数 の記事の命題「指数型母関数の積」）により
$$ e^xF(x)=\sum_{n\ge0}\Bigl(\sum_{i=0}^{n}\binom ni\cdot1\cdot B_i\Bigr)\frac{x^n}{n!} $$
なので、thm-bell-recurrence は $F'=e^xF$ と同値である。
$G:=\exp(e^x-1)$ とおき、$A:=e^x-1$ とする。$A^k$ の微分は積の微分の規則により $kA^{k-1}A'$ であり、各係数が有限和なので項ごとに微分してよいから、
$$ G'=\sum_{k\ge1}\frac{kA^{k-1}A'}{k!}=A'\sum_{k\ge1}\frac{A^{k-1}}{(k-1)!}=e^xG $$
である（$A'=e^x$）。$G$ の定数項は $1=B_0$ である。
$H=\sum_nh_nx^n/n!$ が $H'=e^xH$ を満たせば、係数を比べて $h_{n+1}=\sum_i\binom nih_i$ となり、$h_0$ からすべての係数が順に決まる。$F$ と $G$ はともにこれを満たし、$h_0=1$ が等しいので $F=G$ である。$\square$

右辺を $b_{n,k}$ とおき、$a_{n,k}=b_{n,k}$ を $n$ についての帰納法で示す。$n=0$ では $a_{0,0}=1=B_0=b_{0,0}$ である。$n\ge1$ とし、第 $n-1$ 行で成り立つとする。
$k=0$：thm-bell-recurrence により $a_{n,0}=a_{n-1,n-1}=b_{n-1,n-1}=\sum_{i=0}^{n-1}\binom{n-1}iB_i=B_n=b_{n,0}$ である。
$1\le k\le n$：$k-1$ まで $a_{n,k-1}=b_{n,k-1}$ が成り立つとすると、帰納法の仮定と Pascal の規則 $\binom{k-1}{i-1}+\binom{k-1}i=\binom ki$ により
$$ a_{n,k}=b_{n,k-1}+b_{n-1,k-1}=\sum_{i}\binom{k-1}iB_{n-k+1+i}+\sum_i\binom{k-1}iB_{n-k+i}=\sum_{i}\Bigl(\binom{k-1}{i-1}+\binom{k-1}{i}\Bigr)B_{n-k+i}=b_{n,k} $$
である（第 1 の和の添字を $i\mapsto i-1$ とずらした）。$k=n$ では thm-bell-recurrence により $b_{n,n}=\sum_i\binom niB_i=B_{n+1}$ である。$\square$

$X:=[n]\sqcup P$、$P:=\{c_0,c_1,\dots,c_{p-1}\}$ とし（$|X|=n+p$）、$X$ の置換 $\sigma$ を $\sigma(c_i):=c_{i+1}$（添字は $p$ を法とする）、$\sigma(x):=x$（$x\in[n]$）で定める。$\sigma$ は位数 $p$ で、$\sigma$ が生成する巡回群 $\langle\sigma\rangle$ は、分割 $\pi$ を $\sigma(\pi):=\{\sigma(T)\mid T\in\pi\}$ に写すことで $X$ の分割全体の集合 $\Pi(X)$ に作用する（群作用）。
軌道の大きさ．群作用 の記事の定理「軌道・安定化群定理」により、各軌道の大きさは $|\langle\sigma\rangle|=p$ を割るので $1$ か $p$ である。大きさ $1$ の軌道は $\sigma(\pi)=\pi$ となる $\pi$（固定された分割）である。よって
$$ B_{n+p}=|\Pi(X)|\equiv(\text{固定された分割の個数})\pmod p $$
である。
固定された分割．$\sigma(\pi)=\pi$ とし、$c_0$ を含むブロックを $T$ とする。$\sigma(T)$ は $\pi$ のブロックで $c_1$ を含む。
(i) $\sigma(T)=T$ の場合：$c_i=\sigma^i(c_0)\in\sigma^i(T)=T$ なので $P\subset T$ である。逆に、$P$ が 1 つのブロックに含まれる分割は固定される（$\sigma$ はそのブロックを保ち、ほかのブロックは $[n]$ に含まれるので動かさない）。このような分割は、$P$ を 1 つの点 $\ast$ につぶすことで $[n]\sqcup\{\ast\}$ の分割と一対一に対応するので、$B_{n+1}$ 個ある。
(ii) $\sigma(T)\ne T$ の場合：$T\cap[n]=\emptyset$ である。実際 $x\in T\cap[n]$ なら $x=\sigma(x)\in\sigma(T)$ となり、ブロック $T$ と $\sigma(T)$ が交わるので等しくなる。また $T\cap P=\{c_0\}$ である。実際 $c_j\in T$（$0< j< p$）なら、$c_j=\sigma^j(c_0)\in\sigma^j(T)$ なので $\sigma^j(T)=T$ であり、$p$ は素数なので $uj\equiv1\pmod p$ となる整数 $u\ge1$ があって $\sigma(T)=(\sigma^j)^u(T)=T$ となり、仮定に反する。よって $T=\{c_0\}$ で、$\sigma^i(T)=\{c_i\}$ もすべてブロックであり、残りのブロックは $[n]$ の分割をなす。逆に、$P$ の各元が単独のブロックをなす分割は固定される。このような分割は $[n]$ の分割と一対一に対応するので、$B_n$ 個ある。
$p\ge2$ なので (i) と (ii) は重ならない。固定された分割は $B_{n+1}+B_n$ 個であり、主張を得る。$\square$

thm-bell-touchard で $n=0$ とすると $B_p\equiv B_0+B_1=2$ である。$\square$

要点：$p$ を法とする列のずらしの作用素 $E$ について Touchard の合同式は $E^p=E+1$ と読め、標数 $p$ では $p$ 乗が和を保つので $E^{p^p}=E$ となる。

$[n]$ の置換 $\sigma$ に、その巡回（互いに素な巡回置換への分解の各因子。不動点も長さ $1$ の巡回とする）の台が作る $[n]$ の分割を対応させる（置換 の記事の定理「互いに素な巡回置換の積への分解」）。どの分割 $\pi$ も、各ブロックの元を 1 つの巡回に並べた置換の像なので、この対応は全射であり、$B_n\le n!$ である。$n\ge3$ では、ブロック $[n]$ だけの分割に、$[n]$ 全体を 1 つの巡回とする $(n-1)!\ge2$ 個の置換が対応するので、全射は単射でなく $B_n< n!$ である。$n\le2$ では $B_n=n!$ を直接確かめられる。$\square$