伯努利数 |
您所在的位置:网站首页 › 等幂和问题怎么解 › 伯努利数 |
伯努利数 伯努利数 是一个与数论有密切关联的有理数序列。前几项被发现的伯努利数分别为: 等幂求和伯努利数是由雅各布·伯努利的名字命名的,他在研究 次幂和的公式时发现了奇妙的关系。我们记 伯努利观察了如下一列公式,勾画出一种模式: 可以发现,在 中 的系数总是 , 的系数总是 , 的系数总是 , 的系数是 , 的系数总是零等。 而 的系数总是某个常数乘以 , 表示下降阶乘幂,即 。 递推公式伯努利数由隐含的递推关系定义: 例如,,前几个值显然是 证明利用归纳法证明这个证明方法来自 Concrete Mathematics 6.5 BERNOULLI NUMBER。 运用二项式系数的恒等变换和归纳法进行证明: 令 ,我们希望证明 ,假设对 ,有 。 将原式中两边都减去 后可以得到: 尝试在式子的右边加上 再进行化简,可以得到: 不妨设 ,并且将 展开,那么有 将第二个 中的求和顺序改为逆向,再将组合数的写法恒等变换可以得到: 对两个求和符号进行交换,可以得到: 对 进行恒等变换: =那么式子就变成了: 将所有的 用 代替,那么就可以得到: 考虑我们前面提到过的递归关系 代入后可以得到: 于是 ,且有 。 利用指数生成函数证明对递推式 两边都加上 ,即得到: 设 ,注意到左边为卷积形式,故: 设 ,则: 调换求和顺序: 代入 : 由于 ,即 : 故得证。 参考实现 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 33typedef long long ll; const int maxn = 10000; const 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; } } 本页面最近更新:2023/5/18 20:10:22,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:StudyingFather, Enter-tainer, Great-designer, Ir1d, kenlig, OkazakiYumemi, ShaoChenHeng, Tiphereth-A, Yuuko10032本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |