伯努利数
伯努利数
是一个与数论有密切关联的有理数序列。前几项被发现的伯努利数分别为:

等幂求和
伯努利数是由雅各布·伯努利的名字命名的,他在研究
次幂和的公式时发现了奇妙的关系。我们记

伯努利观察了如下一列公式,勾画出一种模式:

可以发现,在
中
的系数总是
,
的系数总是
,
的系数总是
,
的系数是
,
的系数总是零等。
而
的系数总是某个常数乘以
,
表示下降阶乘幂,即
。
递推公式

伯努利数由隐含的递推关系定义:

例如,
,前几个值显然是
证明
利用归纳法证明
这个证明方法来自 Concrete Mathematics 6.5 BERNOULLI NUMBER。
运用二项式系数的恒等变换和归纳法进行证明:

令
,我们希望证明
,假设对
,有
。
将原式中两边都减去
后可以得到:

尝试在式子的右边加上
再进行化简,可以得到:

不妨设
,并且将
展开,那么有

将第二个
中的求和顺序改为逆向,再将组合数的写法恒等变换可以得到:

对两个求和符号进行交换,可以得到:

对
进行恒等变换:
=
那么式子就变成了:

将所有的
用
代替,那么就可以得到:

考虑我们前面提到过的递归关系
![\begin{aligned}
\sum_{j=0}^{m}\binom{m+1}{j}B_j&=0,(m>0)\\
B_0&=1\\
\sum_{j=0}^{m}\binom{m+1}{j}B_j&=[m = 0]
\end{aligned}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
代入后可以得到:
![\begin{aligned}
n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}[m - k = 0]+(m+1)\Delta\\
&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}+(m+1)\Delta\\
&=\frac{n^{m+1}}{m+1}\binom{m+1}{m}+(m+1)\Delta\\
&=n^{m+1}+(m+1)\Delta
\end{aligned}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
于是
,且有
。
利用指数生成函数证明
对递推式 ![\sum_{j=0}^{m}\binom{m+1}{j}B_j=[m=0]](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
两边都加上
,即得到:
![\begin{aligned}
\sum_{j=0}^{m+1}\binom{m+1}{j}B_j&=[m=0]+B_{m+1}\\
\sum_{j=0}^{m}\binom{m}{j}B_j&=[m=1]+B_{m}\\
\sum_{j=0}^{m}\dfrac{B_j}{j!}\cdot\dfrac{1}{(m-j)!}&=[m=1]+\dfrac{B_{m}}{m!}
\end{aligned}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
设
,注意到左边为卷积形式,故:

设
,则:

调换求和顺序:

代入
:

由于
,即
:
![\begin{aligned}
S \times m(n)&=m![z^m]F_n(z)\\
&= m!\sum_{i=0}^{m}\dfrac{B \times i}{i!}\cdot\dfrac{n^{m-i+1}}{(m-i+1)!}\\
&=\dfrac{1}{m+1}\sum_{i=0}^{m}\binom{m+1}{i}B_in^{m-i+1}
\end{aligned}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
故得证。
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | using ll = long long;
constexpr int MAXN = 10000;
constexpr int mod = 1e9 + 7;
ll B[MAXN]; // 伯努利数
ll C[MAXN][MAXN]; // 组合数
ll inv[MAXN]; // 逆元(计算伯努利数)
void init() {
// 预处理组合数
for (int i = 0; i < MAXN; i++) {
C[i][0] = C[i][i] = 1;
for (int k = 1; k < i; k++) {
C[i][k] = (C[i - 1][k] % mod + C[i - 1][k - 1] % mod) % mod;
}
}
// 预处理逆元
inv[1] = 1;
for (int i = 2; i < MAXN; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
// 预处理伯努利数
B[0] = 1;
for (int i = 1; i < MAXN; i++) {
ll ans = 0;
if (i == MAXN - 1) break;
for (int k = 0; k < i; k++) {
ans += C[i + 1][k] * B[k];
ans %= mod;
}
ans = (ans * (-inv[i + 1]) % mod + mod) % mod;
B[i] = ans;
}
}
|
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:StudyingFather, Aquistcev, Enter-tainer, Great-designer, Ir1d, kenlig, OkazakiYumemi, ShaoChenHeng, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用