似乎是一篇又水又没啥用的博客。
首先给出伯努利数 B n B_n Bn?的生成函数定义：
x e x ? 1 = ∑ n = 0 ∞ B n x n n ! \frac{x}{e^x-1}=\sum_{n=0}^{\infty}\frac{B_nx^n}{n!} ex?1x?=n=0∑∞?n!Bn?xn?
伯努利数可以用来等幂求和。
定义
S
m
(
n
)
=
∑
i
=
0
n
?
1
i
m
S_m(n)=\sum_{i=0}^{n-1}i^m
Sm?(n)=i=0∑n?1?im
众所周知这是一个 m + 1 m+1 m+1次多项式，事实上：
S m ( n ) = 1 m + 1 ∑ k = 0 m ( m + 1 k ) B k n m + 1 ? k S_m(n)=\frac{1}{m+1}\sum_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k} Sm?(n)=m+11?k=0∑m?(km+1?)Bk?nm+1?k
事实上可以观察发现每一行的各项系数和为 0 0 0，因此我们可以得到伯努利数的递推关系：
∑ j = 0 m ( m + 1 j ) B j = 0 , ( m > 0 ) B 0 = 1 \sum_{j=0}^m\binom{m+1}{j}B_j=0,(m>0)\\B_0=1 j=0∑m?(jm+1?)Bj?=0,(m>0)B0?=1
因此理论上伯努利数也可以半在线卷积求，但是 我不会高科技 直接多项式求逆显然更方便一些。
这下我们终于知道为什么任意
m
m
m次多项式的前缀和是
m
+
1
m+1
m+1次多项式了。这不是显然吗。当然在大多数题目中还会做一些类似于平移、伸缩的变换。
众所周知自然数幂与第二类斯特林数有一定的关系，因此我们猜测伯努利数和第二类斯特林数也有一定的关系。
小小的trick：
x e x ? 1 = ln ? ( 1 ? ( 1 ? e x ) ) e x ? 1 = ∑ k ≥ 0 ( 1 ? e x ) k k + 1 = ∑ k ≥ 0 ( ? 1 ) k k + 1 ∑ i ≥ k { i k } k ! i ! x i = ∑ i ≥ 0 x i i ! ∑ 0 ≤ k ≤ i ( ? 1 ) k k ! k + 1 { i k } \begin{aligned} \frac{x}{e^x-1}&=\frac{\ln(1-(1-e^x))}{e^x-1}\\&=\sum_{k\ge 0}\frac{(1-e^x)^k}{k+1}\\&=\sum_{k\ge 0}\frac{(-1)^k}{k+1}\sum_{i\ge k}\begin{Bmatrix}i\\k\end{Bmatrix}\frac{k!}{i!}x^i\\&=\sum_{i\ge 0}\frac{x^i}{i!}\sum_{0\le k\le i}\frac{(-1)^kk!}{k+1}\begin{Bmatrix}i\\k\end{Bmatrix} \end{aligned} ex?1x??=ex?1ln(1?(1?ex))?=k≥0∑?k+1(1?ex)k?=k≥0∑?k+1(?1)k?i≥k∑?{ik?}i!k!?xi=i≥0∑?i!xi?0≤k≤i∑?k+1(?1)kk!?{ik?}?
对这部分推导不熟悉的可以看一下 这篇博客 。则我们得到了直接计算伯努利数的公式：
B n = ∑ k = 1 n ( ? 1 ) k k ! k + 1 { i k } B_n=\sum_{k=1}^n\frac{(-1)^kk!}{k+1}\begin{Bmatrix}i\\k\end{Bmatrix} Bn?=k=1∑n?k+1(?1)kk!?{ik?}
评价是没什么用处。
例题：仓鼠的数学题