《具体数学》 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] 中本人用了两种方式推导结果，而其中一种方式却比较复杂。

---