营业日志 2020.6.22 贝尔数的同余线性递推性质

今天粉兔同学问了一个问题:如何证明贝尔数的 Touchard’s Congruence 性质:
Bn+pBn+1+Bn(modp) B_{n+p} \equiv B_{n+1} + B_n \pmod p Bn+p​≡Bn+1​+Bn​(modp)
其中 ppp 是质数,BnB_nBn​ 是贝尔数。

为了证明这个问题,我们首先证明一个引理:
引理 1k{pk}xkx+xp(modp)\sum_k {p\brace k} x^k \equiv x + x^p \pmod p∑k​{kp​}xk≡x+xp(modp)。
证明:我们考虑多项式 xp=k{pk}xkx^p = \sum_k {p\brace k} x^{\underline k}xp=∑k​{kp​}xk​,这是由下降幂转化得到的。而 xpx(modp)x^p \equiv x \pmod pxp≡x(modp),xp0(modp)x^{\underline p} \equiv 0 \pmod pxp​≡0(modp),因此我们可以知道对于 k<p{pk}xkx(modp)\sum_{k<p} {p\brace k} x^{\underline k} \equiv x \pmod p∑k<p​{kp​}xk​≡x(modp),等式两边都是小于 ppp 次的多项式,必然是对应相等的,而 {pp}=1{p \brace p} = 1{pp​}=1 显然。故 k{pk}xkx+xp(modp)\sum_k {p\brace k} x^k \equiv x + x^p \pmod p∑k​{kp​}xk≡x+xp(modp) 得证。

接下来考虑这样一件事,记贝尔数的 EGF 是 B(x)=exp(ex1)B(x) = \exp (\mathrm e^x - 1)B(x)=exp(ex−1),那么 B(x)=B(x)exB'(x) = B(x)\mathrm e^xB′(x)=B(x)ex,我们考虑对 B(x)B(x)B(x) 连续求导 nnn 次,我们知道求导完必然是一个 B(n)(x)=B(x)kan,kekxB^{(n)}(x) = B(x)\sum_k a_{n,k} \mathrm e^{kx}B(n)(x)=B(x)∑k​an,k​ekx 的形式,归纳则有

B(n+1)(x)=(B(n)(x))B(x)kan+1,kekx=(B(x)kan,kekx)=kan,k(B(x)ekx)=kan,k(kB(x)ekx+B(x)e(k+1)x)kan+1,kekx=kan,k(kekx+e(k+1)x)an+1,k=kan,k+an,k1 \begin{aligned} B^{(n+1)}(x) & = \left(B^{(n)}(x)\right)'\\ B(x)\sum_k a_{n+1,k} \mathrm e^{kx} &= \left(B(x)\sum_k a_{n,k} \mathrm e^{kx}\right)'\\ &= \sum_k a_{n,k} \left(B(x)\mathrm e^{kx}\right)'\\ &= \sum_k a_{n,k} \left(kB(x)\mathrm e^{kx} + B(x)\mathrm e^{(k+1)x}\right)\\ \sum_k a_{n+1,k} \mathrm e^{kx} &= \sum_k a_{n,k} \left(k\mathrm e^{kx} + \mathrm e^{(k+1)x}\right)\\ a_{n+1,k} &= ka_{n,k} + a_{n,k-1} \end{aligned} B(n+1)(x)B(x)k∑​an+1,k​ekxk∑​an+1,k​ekxan+1,k​​=(B(n)(x))′=(B(x)k∑​an,k​ekx)′=k∑​an,k​(B(x)ekx)′=k∑​an,k​(kB(x)ekx+B(x)e(k+1)x)=k∑​an,k​(kekx+e(k+1)x)=kan,k​+an,k−1​​

带入初值,我们容易得到
B(n)(x)=B(x)k{nk}ekx B^{(n)}(x) = B(x) \sum_k {n\brace k} \mathrm e^{kx} B(n)(x)=B(x)k∑​{kn​}ekx

n=pn=pn=p,有
B(p)(x)=B(x)k{pk}ekxB(x)(ex+epx)B(x)(ex+1)B(x)+B(x)Bn+pBn+1+Bn \begin{aligned} B^{(p)}(x) &= B(x) \sum_k {p\brace k} \mathrm e^{kx}\\ & \equiv B(x) (\mathrm e^x + \mathrm e^{px})\\ & \equiv B(x) (\mathrm e^x + 1)\\ & \equiv B'(x) + B(x)\\ B_{n+p} &\equiv B_{n+1} + B_n \end{aligned} B(p)(x)Bn+p​​=B(x)k∑​{kp​}ekx≡B(x)(ex+epx)≡B(x)(ex+1)≡B′(x)+B(x)≡Bn+1​+Bn​​

故原问题得证。


后面还提到了 Bn+pmmBn+1+Bn(modp)B_{n+p^m} \equiv mB_{n+1} + B_n \pmod pBn+pm​≡mBn+1​+Bn​(modp),这个其实就不是很有新东西了,不过一个很爽的事情是我们可以用 Umbral Calculus 来快速得到:现在挪用上指标,我们有

Bp=1+B B^p = 1 + B Bp=1+B

因此 Bpm=(1+B)pm1=1+Bpm1=2+Bpm2==m+BB^{p^m} = (1+B)^{p^{m-1}} = 1 + B^{p^{m-1}} = 2 + B^{p^{m-2}} = \cdots = m + BBpm=(1+B)pm−1=1+Bpm−1=2+Bpm−2=⋯=m+B

得证。

上一篇:深度学习算子优化-FFT


下一篇:『图论杂题题解』