Bell number 素数幂

hbghlyj

$$e^{e^x-1}=\sum_{n=0}^\infty \frac{B_n}{n!} x^n$$
求证$$B_{p^m}\equiv m+1 \pmod p$$

Czhang271828

Backward Touchard congruence and Some congruences concerning the Bell numbers might be helpful. The solution is almost there.

hbghlyj

指数型生成函数
Definition
指数型生成函数（exponential generating function，简称EGF），其定义为
$$
F(x)=\sum_nf_n\frac{x^n}{n!}
$$
其意义体现在其乘法操作上：
$$
F(x)G(x)=\sum_n\left(\sum_{i=0}^n\binom nif_ig_{n-i}\right)x^i
$$
多出来的$\binom ni$告诉我们它适用于排列的计算（相对于OGF的普通卷积对应组合）。
只需要注意到$<f_n>$的EGF实际上就是$<\frac{f_n}{n!}>$的OGF，就能找到不少例子。

Example
贝尔数$\omega_n$是把大小为$n$的子集分割成若干非空不相交子集的方案数。
通过枚举第一个元素所在的子集大小$i$，我们可以得到
$$\omega_n=[n=0]+\sum_{i=1}^n\binom{n-1}{i-1}\omega_{n-i}$$
于是其EGF满足
$$F(x)=1+\int_0^xe^tF(t)\mathrm{d}t$$
两边求导
$$
\begin{aligned}
F^\prime(x)&=e^xF(x)\\
\frac{\mathrm{d}F}{\mathrm{d}x}&=e^xF(x)\\
\frac{\mathrm{d}F}F&=e^x\mathrm{d}x\\
\int\frac{\mathrm{d}F}F&=\int e^x\mathrm{d}x\\
\ln F&=e^x+C\\
F&=e^{e^x+C}\\
\end{aligned}
$$
把$F(0)=\omega_0=1$代入即得$F(x)=e^{e^x-1}$。这个多项式的系数可以利用$e^g=\sum_n\frac{g^n}{n!}$计算。
$F(x)=e^{e^x-1}$也可以这样理解：$g(x)=e^x-1$的$n$次项系数是“n个数组成一个非空集合”的方案数（显然），而$g^c(x)$的$n$次项系数（由于EGF对应排列）就是“n个数划分成c个非空集合”的方案数。而由于这$c$个集合是不可区分的，所以要乘上$\frac1{c!}$。于是我们得到$F(x)=\sum_n\frac{g^n(x)}{n!}=e^{g(x)}=e^{e^x-1}$