《具体数学》 2.4 多重和式
一、基本法则
本章节其实非常简单，特别是对于 OIer 来说。
下面就是一个简单的多重和式 \[ \sum_{i=1}^n\sum_{j=1}^mF(i,j) \] 对于多重和式，有一个被称为交换求和次序的基本法则，它推广了我们在 2.3 中定义的结合律。 \[ \sum_{P(i,j)}a_{i,j} = \sum_{i}\sum_{j}a_{i,j}[P(i,j)] = \sum_{j}\sum_{i}a_{i,j}[P(i,j)] \] 如何理解呢？其实就是下面的代码
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) if(P(i,j)) ans += a[i][j];
for(int j = 1; j <= n; j++)
for(int i = 1; i <= n; i++) if(P(i,j)) ans += a[i][j];于是可以进一步推导出和式的一般分配律 \[
\sum_{i\in A,~j \in B}a_ib_j = \left(\sum_{i\in A}
a_i\right)\left(\sum_{j \in B} b_j\right)
\] （我觉得这个式子有点...怪怪的）
实际上，交换求和次序有一个非常重要的变形 \[
\sum_{i \in A}\sum_{j\in B(i)}a_{i,j} = \sum_{j \in B^{\prime}}\sum_{i
\in A^{\prime}(j)} a_{i,j}
\] 其中，集合 \(A,\,B(i),\,B^{\prime},\,A^{\prime}(j)\)
必须以下面的方式关联 \[
[i\in A][j\in B(i)] = [j \in B^{\prime}][i\in A^{\prime}(j)]
\]
举个例子，比如 \[ [1 \le i \le n][i \le j \le n] = [1\le i \le j \le n] = [1\le i \le n][1\le i \le j] \] 于是 \[ \sum_{i=1}^n\sum_{j=i}^{n} a_{i,j} = \sum_{i=1}^n\sum_{j=1}^i a_{i,j} \] 当然更重要的一个例子 \[ [1 \le i \le n][k \mid i] = \left[1\le i \le \left\lfloor\frac{n}{k}\right\rfloor\right][k\mid (i\cdot k)] \] 于是 \[ \sum_{i=1}^n[k\mid i] = \sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}1 = \left\lfloor\frac{n}{k}\right\rfloor \] 这是数论分块中非常重要的一个结论，你可以在 洛谷P2522 [HAOI2011]Problem b 中看到它的用处。
二、“具体”数学
小心！本书的作者似乎把 \(i,j,k,n\) 视作“实际的数”。
例如下面这个例子 \[ S_n=\sum_{1\le j < k \le n}\frac{1}{k-j} \] （作者好像很喜欢 \(j,k\) ）
首先书上给出了一种做法 \[ \begin{aligned} S_n & =\sum_{1 \le k \le n} \sum_{1 \le j<k} \frac{1}{k-j} \\[6pt]& =\sum_{1 \le k \le n} \sum_{1 \le k-j<k} \frac{1}{j} && \texttt{用}\ k - j\ \texttt{替换}\ j \\[6pt]& =\sum_{1 \le k \le n} \sum_{0<j \le k-1} \frac{1}{j} \\[6pt]& =\sum_{1 \le k \le n} H_{k-1} \\[6pt]& =\sum_{1 \le k+1 \le n} H_k&& \texttt{用}\ k + 1\ \texttt{替换}\ k \\[6pt]& =\sum_{0 \le k<n} H_k \end{aligned} \] 其中 \(H_n=\sum_{k=1}^n\frac{1}{k}\) 称为调和数。
这并不是一个封闭形式，而我们目前还不会将调和数的和转化为封闭形式
而实际上我们还可以这么做 \[ \begin{aligned} S_n & =\sum_{1 \le j<k \le n} \frac{1}{k-j} \\[6pt]& =\sum_{1 \le j<k+j \le n} \frac{1}{k}&& \texttt{用}\ k + j\ \texttt{替换}\ k \\[6pt]& =\sum_{1 \le k \le n} \sum_{1 \le j \le n-k} \frac{1}{k} && \texttt{首先对}\ j \ \texttt{求和} \\[6pt]& =\sum_{1 \le k \le n} \frac{n-k}{k} \\[6pt]& =\sum_{1 \le k \le n} \frac{n}{k}-\sum_{1 \le k \le n} 1 \\[6pt]& =n\left(\sum_{1 \le k \le n} \frac{1}{k}\right)-n \\[6pt]& =n H_n-n \end{aligned} \] 于是我们求出了 \(S_n\) ，还顺便得到了 \(\sum_{0 \le k<n} H_k = nH_n-n\) 。
实际上这种情况很常见，例如 note[16] 中本人用了两种方式推导结果，而其中一种方式却比较复杂。
