伯努利数

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

等幂求和

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

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

可以发现，在中的系数总是，的系数总是，的系数总是，的系数是，的系数总是零等。

而的系数总是某个常数乘以，表示下降阶乘幂，即。

递推公式

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

例如，，前几个值显然是

证明

利用归纳法证明

这个证明方法来自 Concrete Mathematics 6.5 BERNOULLI NUMBER。

运用二项式系数的恒等变换和归纳法进行证明：

令，我们希望证明，假设对，有。

将原式中两边都减去后可以得到：

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

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

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

对两个求和符号进行交换，可以得到：

对进行恒等变换：

＝

那么式子就变成了：

将所有的用代替，那么就可以得到：

考虑我们前面提到过的递归关系

代入后可以得到：

于是，且有。

利用指数生成函数证明

对递推式

两边都加上，即得到：

设，注意到左边为卷积形式，故：

设，则：

调换求和顺序：

代入：

由于，即：

故得证。

参考实现

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日
创建日期: 2020年7月30日