【学习笔记】母函数Part3

大概就是整理一下「伯努利数」吧…

其实还有一块关于切比雪夫不等式的内容,但是我觉得不是很有意思,决定不整理了.jpg

伯努利数

定义

考虑用母函数的方式定义。此处直接定义伯努利数的指数型母函数是:

那么考虑如何展开。记伯努利数为 $\{B_n\}$。发现移一下项

如果记右边卷出来的结果是 $\{a_n\}$,那么发现

此处上界为 $n-1$ 的原因是 $\left(e(x)-1\right)_0=0$ ,其余项均为 $1$ 。

比较同次项系数可知

考虑用这个方程去递推每一项。大致思路是左右两边同时加上 $B_n$ 。

然后就可以发现,比如拿 $n=2$ 举例:

就可以消掉 $B_2$ 求出 $B_1$。以此类推,每次用 $n$ 可以消出 $B_{n-1}$ 。

一个小性质

考虑 $B_n$ 的性质,发现推出来的大概长这样:

发现似乎,除了 $B_1$ 之外,其余 $n$ 为奇数的时候均为 $0$ 。证明考虑:

那么如果令

那么

可知 $f(x)$ 是偶函数,那么也就是

是偶函数。考虑他是偶函数的条件,当且仅当所有奇次幂系数都为 $0$ 的时候,才会是偶函数。所以可以证明上面的结论。

伯努利多项式

考虑观察下列两个EGF的卷积:

其中 $t$ 是任意常数。考虑记卷积结果为 $\beta(t)$ 。那么显然

记这样的多项式为伯努利多项式。这个多项式有个很有用的性质:

考虑直接做差法证明。首先设出两个式子:

$(2)-(1)$ 得到

比较系数可知

变一下形就可以得到:

用伯努利多项式求自然数的 $k$ 次方和

考虑决定自然数 $k$ 次方的要素在于下标 $n$ 。于是考虑所有自然数的 $k$ 次方和就是这样:

展开之后

也就是

其中 $r=0$ 时减掉了 $\beta_{k+1}(1)$ 这一项。

发现本质上可以 $k\log k$ 用 $\exp$ 来预处理伯努利数,然后就可以 $O(k)$ 算不限制 $n$ 时的 $k$ 次方和了。

emmm似乎预处理也不用 $\rm exp$ ,$e(x)-1$ 直接写出来,然后直接多项式求逆就可以了?

但显然这个方法被线性插值给爆锤了。