伯努利數
伯努利數 \(B_n\) 是一個與數論有密切關聯的有理數序列。前幾項被發現的伯努利數分別為：
\(B_0=1,B_1=-\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=-\frac{1}{30},\dots\)
等冪求和
伯努利數是由雅各布·伯努利的名字命名的，他在研究 \(m\) 次冪和的公式時發現了奇妙的關係。我們記
\[
S_{m}(n)=\sum_{k=0}^{n-1}k^m=0^m+1^m+\dots+(n-1)^m
\]
伯努利觀察瞭如下一列公式，勾畫出一種模式：
\[
\begin{aligned}
S_0(n)&=n\\
S_1(n)&=\frac{1}{2}n^2-\frac{1}{2}n\\
S_2(n)&=\frac{1}{3}n^3-\frac{1}{2}n^2+\frac{1}{6}n\\
S_3(n)&=\frac{1}{4}n^4-\frac{1}{2}n^3+\frac{1}{4}n^2\\
S_4(n)&=\frac{1}{5}n^5-\frac{1}{2}n^4+\frac{1}{3}n^3-\frac{1}{30}n
\end{aligned}
\]
可以發現，在 \(S_m(n)\) 中 \(n^{m+1}\) 的係數總是 \(\frac{1}{m+1}\)，\(n^m\) 的係數總是 \(-\frac{1}{2}\)，\(n^{m-1}\) 的係數總是 \(\frac{m}{12}\)，\(n^{m-3}\) 的係數是 \(-\frac{m(m-1)(m-2)}{720}\)，\(n^{m-4}\) 的係數總是零等。
而 \(n^{m-k}\) 的係數總是某個常數乘以 \(m^{\underline{k}}\)，\(m^{\underline{k}}\) 表示下降階乘冪，即 \(\frac{m!}{(m-k)!}\)。
遞推公式
\[
\begin{aligned}
S_m{(n)}&=\frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1 n^m+\dots+\binom{m+1}{m}B_m n) \\
&=\frac{1}{m+1}\sum_{k=0}^{m}\binom{m+1}{k}B_kn^{m+1-k}
\end{aligned}
\]
伯努利數由隱含的遞推關係定義：
\[
\begin{aligned}
\sum_{j=0}^{m}\binom{m+1}{j}B_j&=0,(m>0)\\
B_0&=1
\end{aligned}
\]
例如，\(\binom{2}{0}B_0+\binom{2}{1}B_1=0\)，前幾個值顯然是
| \(n\) |
\(0\) |
\(1\) |
\(2\) |
\(3\) |
\(4\) |
\(5\) |
\(6\) |
\(7\) |
\(8\) |
\(\dots\) |
| \(B_n\) |
\(1\) |
\(-\frac{1}{2}\) |
\(\frac{1}{6}\) |
\(0\) |
\(-\frac{1}{30}\) |
\(0\) |
\(\frac{1}{42}\) |
\(0\) |
\(-\frac{1}{30}\) |
\(\dots\) |
證明
利用歸納法證明
這個證明方法來自 Concrete Mathematics 6.5 BERNOULLI NUMBER。
運用二項式係數的恆等變換和歸納法進行證明：
\[
\begin{aligned}
S_{m+1}(n)+n^{m+1}&= \sum_{k=0}^{n-1}(k+1)^{m+1}\\
&=\sum_{k=0}^{n-1}\sum_{j=0}^{m+1}\binom{m+1}{j}k^j\\
&=\sum_{j=0}^{m+1}\binom{m+1}{j}S_j(n)
\end{aligned}
\]
令 \(\hat{S}_{m}(n)=\frac{1}{m+1} \sum_{k=0}^{m} \binom{m+1}{k}B_kn^{m+1-k}\)，我們希望證明 \(S_m(n)=\hat{S}_m(n)\)，假設對 \(j\in[0,m)\)，有 \(S_j(n)=\hat{S}_j(n)\)。
將原式中兩邊都減去 \(S_{m+1}(n)\) 後可以得到：
\[
\begin{aligned}
S_{m+1}(n)+n^{m+1}&=\sum_{j=0}^{m+1}\binom{m+1}{j}S_j(n)\\
n^{m+1}&=\sum_{j=0}^{m}\binom{m+1}{j}S_j(n)\\
&=\sum_{j=0}^{m-1}\binom{m+1}{j}\hat{S}_j(n)+\binom{m+1}{m}S_m(n)
\end{aligned}
\]
嘗試在式子的右邊加上 \(\binom{m+1}{m}\hat{S}_m(n)-\binom{m+1}{m}\hat{S}_m(n)\) 再進行化簡，可以得到：
\[
n^{m+1}=\sum_{j=0}^{m}\binom{m+1}{j}\hat{S}_j(n)+(m+1)(S_m(n)-\hat{S}_m(n))
\]
不妨設 \(\Delta = S_m(n)-\hat{S}_m(n)\)，並且將 \(\hat{S}_j(n)\) 展開，那麼有
\[
\begin{aligned}
n^{m+1}&=\sum_{j=0}^{m}\binom{m+1}{j}\hat{S}_j(n)+(m+1)\Delta\\
&=\sum_{j=0}^{m}\binom{m+1}{j}\frac{1}{j+1}\sum_{k=0}^{j}\binom{j+1}{k}B_kn^{j+1-k}+(m+1)\Delta\\
\end{aligned}
\]
將第二個 \(\sum\) 中的求和順序改為逆向，再將組合數的寫法恆等變換可以得到：
\[
\begin{aligned}
n^{m+1}&=\sum_{j=0}^{m}\binom{m+1}{j}\frac{1}{j+1}\sum_{k=0}^{j}\binom{j+1}{j-k}B_{j-k}n^{k+1}+(m+1)\Delta\\
&=\sum_{j=0}^{m}\binom{m+1}{j}\frac{1}{j+1}\sum_{k=0}^{j}\binom{j+1}{k+1}B_{j-k}n^{k+1}+(m+1)\Delta\\
&=\sum_{j=0}^{m}\binom{m+1}{j}\frac{1}{j+1}\sum_{k=0}^{j}\frac{j+1}{k+1}\binom{j}{k}B_{j-k}n^{k+1}+(m+1)\Delta\\
&=\sum_{j=0}^{m}\binom{m+1}{j}\sum_{k=0}^{j}\binom{j}{k}\frac{B_{j-k}}{k+1}n^{k+1}+(m+1)\Delta
\end{aligned}
\]
對兩個求和符號進行交換，可以得到：
\[
n^{m+1}=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\sum_{j=k}^{m}\binom{m+1}{j}\binom{j}{k}B_{j-k}+(m+1)\Delta
\]
對 \(\binom{m+1}{j}\binom{j}{k}\) 進行恆等變換：
\[
\binom{m+1}{j}\binom{j}{k}＝\binom{m+1}{k}\binom{m-k+1}{j-k}
\]
那麼式子就變成了：
\[
\begin{aligned}
n^{m+1}&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\sum_{j=k}^{m}\binom{m+1}{k}\binom{m-k+1}{j-k}B_{j-k}+(m+1)\Delta\\
&=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=k}^{m}\binom{m-k+1}{j-k}B_{j-k}+(m+1)\Delta\\
\end{aligned}
\]
將所有的 \(j-k\) 用 \(j\) 代替，那麼就可以得到：
\[
n^{m+1}=\sum_{k=0}^{m}\frac{n^{k+1}}{k+1}\binom{m+1}{k}\sum_{j=0}^{m-k}\binom{m-k+1}{j}B_{j}+(m+1)\Delta
\]
考慮我們前面提到過的遞歸關係
\[
\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}
\]
代入後可以得到：
\[
\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}
\]
於是 \(\Delta=0\)，且有 \(S_m(n)=\hat{S}_m(n)\)。
利用指數生成函數證明
對遞推式 \(\sum_{j=0}^{m}\binom{m+1}{j}B_j=[m=0]\)
兩邊都加上 \(B_{m + 1}\)，即得到：
\[
\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}
\]
設 \(B(z) = \sum\limits_{i\ge 0}\dfrac{B_i}{i!}z^i\)，注意到左邊為卷積形式，故：
\[
\begin{aligned}
B(z)\mathrm{e}^z &= z+B(z)\\
B(z)&=\dfrac{z}{\mathrm{e}^z - 1}
\end{aligned}
\]
設 \(F_n(z) = \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m\)，則：
\[
\begin{aligned}
F_n(z) &= \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m\\
&= \sum_{m\ge 0}\sum_{i=0}^{n-1}\dfrac{i^mz^m}{m!}\\
\end{aligned}
\]
調換求和順序：
\[
\begin{aligned}
F_n(z) &=\sum_{i=0}^{n-1}\sum_{m\ge 0}\dfrac{i^mz^m}{m!}\\
&=\sum_{i=0}^{n-1}\mathrm{e}^{iz}\\
&=\dfrac{\mathrm{e}^{nz} - 1}{\mathrm{e}^z - 1}\\
&=\dfrac{z}{\mathrm{e}^z - 1}\cdot\dfrac{\mathrm{e}^{nz} - 1}{z}
\end{aligned}
\]
代入 \(B(z)=\dfrac{z}{\mathrm{e}^z - 1}\)：
\[
\begin{aligned}
F_n(z) &= B(z)\cdot\dfrac{\mathrm{e}^{nz} - 1}{z}\\
&= \left(\sum_{i\ge 0}\dfrac{B_i}{i!} \right)\left(\sum_{i\ge 1}\dfrac{n^i z^{i - 1}}{i!}\right)\\
&= \left(\sum_{i\ge 0}\dfrac{B_i}{i!} \right)\left(\sum_{i\ge 0}\dfrac{n^{i+1} z^{i}}{(i+1)!}\right)
\end{aligned}
\]
由於 \(F_n(z) = \sum_{m\ge 0}\dfrac{S_m(n)}{m!}z^m\)，即 \(S_m(n)=m![z^m]F_n(z)\)：
\[
\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}
\]
故得證。
參考實現
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 | typedef 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;
}
}
|
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用