伯努利数学习笔记

最没用的数学知识。

定义伯努利数$\{b_n\}$:

$$b_n=[n==0]-\sum_{k=0}^{n-1}\binom{n}{k}\frac{b_k}{n-k+1}$$

根据这个东西，可以推出伯努利数的指数生成函数$B(x)$:

$$\sum_{k=0}^{n}\binom{n}{k}\frac{b_k}{n-k+1}=[n==0]$$ $$\sum_{k=0}^{n}\frac{b_k}{k!}\cdot\frac{1}{(n-k+1)!}=\frac{[n==0]}{n!}$$ $$B(x)\frac{e^x-1}{x}=1$$ $$B(x)=\frac{x}{e^x-1}$$

这就允许了在$O(nlogn)$的时间内求出$B(x)$。

有关伯努利数最重要的定理就是对自然数幂的转化关系式：

$$S(n,k)=\sum_{i=0}^{n-1}i^k=\frac{1}{k+1}\sum_{i=0}^{k}\binom{k+1}{i}b_in^{k+1-i}$$

下面是证明，定义$\{S(n,k)\}$的指数生成函数：

$$F(n,k)=\sum_{p=0}^{\infty}\frac{S(n,p)}{p!}x^p$$ $$\ \ \ \ \ \qquad=\sum_{p=0}^{\infty}\sum_{k=1}^{n}\frac{(kx)^p}{p!}$$ $$\ =\sum_{k=1}^{n}e^{kx}$$ $$\qquad\ \ \ =\frac{e^{(n+1)x}-e^x}{e^x-1}$$ $$\ \ \ \ =\frac{1-e^{nx}}{e^{-x}-1}$$ $$\qquad\qquad\ \ \ \ \ =\frac{x}{1-e^{-x}}\cdot\frac{1-e^{nx}}{x}$$

可以看出来这个前一项就是$B(-x)$，那么原式就等于：

$$=(\sum_{i=0}^{\infty}b_i\frac{(-x)^{i-1}}{i!})\cdot(-\sum_{i=1}^{\infty}\frac{(nx)^i}{i!})$$ $$=(\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}b_ix^i)(\sum_{i=1}^{\infty}\frac{n^i}{i!}x^i)\qquad$$ $$=\sum_{p=0}^{\infty}(\sum_{j=0}^{p}\frac{(-1)^ib_in^{p-i+1}}{i!(p-i+1)!})x^p\qquad\ \$$ $$\qquad\qquad=\sum_{p=0}^{\infty}x^p\frac{1}{(p+1)!}\sum_{i=0}^{p}(-1)^i\binom{p+1}{i}b_in^{p-i+1}$$

那么在等式左右两边同时放上一个$[x^p]$：

$$\frac{1}{p!}\sum_{k=1}^{n}k^p=\frac{1}{(p+1)!}\sum_{i=0}^{p}(-1)^i\binom{p+1}{i}b_in^{p-i+1}$$ $$\sum_{k=1}^{n}k^p=\frac{1}{p+1}\sum_{i=0}^{p}(-1)^i\binom{p+1}{i}b_in^{p-i+1}$$

应用：

P3711

给一个数列$\{a_n\}$，求一个多项式

$$ANS(x)=\sum_{k=0}^{n}(S(x,k)+x^k)a^k$$