《CM》2.4 Multiple Sums

2.4 Multiple Sums 多重和

和的项不仅只被一个索引指定,也可以被多个索引指定,同样的,用∑符号表示法来表示。比如,一般的,两个索引的和为:

\sum_{P(j,k)}a_{j,k}=\sum_{j,k}a_{j,k}\left[P(j,k)\<br />
ight].

这个式子代表所有的满足P性质的项的和,其中P性质是关于两个参数,也就是索引j,k的一个布尔函数。等式右边为相应的Iverson的写法。

根据associative law,我们可以把这个和分组,然后组之间再相加。比如我们对j索引分组,对索引j的每个不同值,j_i,相应的组为\sum_{k}a_{j_i,k}\left[P(j_i,k)\<br />
ight],再把所有组相加,这实际上又是一个和,即为:

\sum_{j}\left(\sum_{k}a_{j,k}\left[P(j,k)\<br />
ight]\<br />
ight),

通常把圆括号去掉,简写成

\sum_{j}\sum_{k}a_{j,k}\left[P(j,k)\<br />
ight]

同样,我们也可以对k分组,然后导出类似的结果。这说明,一个和如果依赖于多个索引,那么我们可以先对其中任意一个索引求和!这个性质叫做interchanging the order of summation,也可以看成是associative law的扩展:

\sum_j\sum_ka_{j,k}\left[P(j,k)\<br />
ight]=\sum_{P(j,k)}a_{j,k}=\sum_k\sum_ja_{j,k}\left[P(j,k)\<br />
ight].

在求一个和时,对其中一个索引先求和会更容易,这时就可以利用这条规则来变换求和顺序,以此来求出和。

根据这条性质以及和的distributive law,可以导出更一般的general distributive law,不难证明:

\sum_{\substack{j \in J \\ k \in K}}a_jb_k=\left(\sum_{j \in J}a_j\<br />
ight)\left(\sum_{k \in K}b_k\<br />
ight),

其中J和K是索引集合。

interchaning the order of summation性质有一些变形,其中一种版本为

\sum_{j \in J}\sum_{k \in K}a_{j,k}=\sum_{\substack{j \in J \\ k \in K}}a_{j,k}=\sum_{k \in K}\sum_{j \in J}a_{j,k}.

这种形式相比上面只是换了一种写法,这种写法仅在j和k相互独立的情况下才能应用。而当j,k相互不独立,即存在依赖关系时,有另一种版本的变形:

\sum_{j \in J}\sum_{k \in K(j)}a_{j,k}=\sum_{k \in K'}\sum_{j \in J'(k)}a_{j,k}.

其中,上述集合必须满足如下关系:

[j \in J][k \in K(j)]=[k \in K'][j \in J'(k)].

特殊情况下,我们知道以下等式

[1 \leq j \leq n][j \leq k \leq n]=[1 \leq j \leq k \leq n]=[1 \leq k \leq n][1 \leq j \leq k].

因此,可以得到一个非常常用的公式

\sum_{j=1}^n\sum_{k=j}^na_{j,k}=\sum_{1 \leq j \leq k \leq n}a_{j,k}=\sum_{k=1}^n\sum_{j=1}^ka_{j,k}.

现在运用已经掌握的处理和方面的知识,考虑如下和

S=\sum_{1 \leq j \lt k \leq n}(a_k-a_j)(b_k-b_j).

由commutative law知,可以把j,k互换,即把k写作j,j写作k,可得

S=\sum_{1 \leq k \lt j \leq n}(a_j-a_k)(b_j-b_k)=\sum_{1 \leq k \lt j \leq n}(a_k-a_j)(b_k-b_j).

两者相加,可得

\begin{array}{l}2S & =\sum_{1 \leq j \lt k \leq n}(a_k-a_j)(b_k-b_j)+\sum_{1 \leq k \lt j \leq n}(a_k-a_j)(b_k-b_j) \\ & =\sum_{1 \leq j,k \leq n}(a_j-a_k)(b_j-b_k)-\sum_{1 \leq j=k \leq n}(a_j-a_k)(b_j-b_k) \\ & =2\sum_{1 \leq j,k \leq n}a_kb_k-2\sum_{1 \leq j,k \leq n}a_jb_k \\ & =2n\sum_{1 \leq k \leq n}a_kb_k-2\left(\sum_{k=1}^na_k\<br />
ight)\left(\sum_{k=1}^nb_k\<br />
ight).\end{array}

变换一下,得到

\left(\sum_{k=1}^na_k\<br />
ight)\left(\sum_{k=1}^nb_k\<br />
ight)=n\sum_{k=1}^na_kb_k-\sum_{1 \leq j \lt k \leq n}(a_k-a_j)(b_k-b_j).

这样,由这个式子很显然的可以推出切比雪夫单调不等式(Chebyshev's monotonic inequalities)的一种特例:

\begin{array}{l}\left(\sum_{k=1}^na_k\<br />
ight)\left(\sum_{k=1}^nb_k\<br />
ight) \leq n\sum_{k=1}^na_kb_k, & \text{if }a_1 \leq \dots \leq a_n \text{ and }b_1 \leq \dots \leq b_n; \\\left(\sum_{k=1}^na_k\<br />
ight)\left(\sum_{k=1}^nb_k\<br />
ight) \geq n\sum_{k=1}^na_kb_k, & \text{if }a_1 \leq \dots \leq a_n \text{ and }b_1 \geq \dots \geq b_n. \\ \end{array}

对单索引和的求解也经常会先把它变成多重和,再做适当操作后求解。这看似后退,实则进步!比如在单索引和的变换索引操作时,就可以引入多重和。设有函数f为f:J \to K,引入索引k并利用interchanging the order of summation规则,有

\sum_{j \in J}a_{f(j)}=\sum_{j,k}a_k[j \in J][k \in K][f(j)=k]=\sum_{k \in K}a_k\sum_{j \in J}[f(j)=k]=\sum_{k \in K}a_k\#f^-(k).

其中\sum_{j \in J}[f(j)=k]=\#f^-(k),意思是对一个k值,使得f(j)=k的j的个数。特别的,若f是一个双射函数(一一对应)时,这时对所有k都有\#f^-(k)=1,上式就变成commutative law!即

\sum_{j \in J}a_{f(j)}=\sum_{f(j) \in K}a_{f(j)}=\sum_{k \in K}a_k.

最后,来求一个关于两重和的具体例子,求解和

S_n=\sum_{1 \leq j \lt k \leq n}\frac{1}{k-j}.

解多重和通常都需要转化成先对某个索引求和,然后对其它索引求和,一级一级减少索引数,从而求出和。对S_n,尝试先对j求和再对k求和:

\begin{array}{l}S_n & =\sum_{1 \leq k \leq n}\sum_{1 \leq j \lt k}\frac{1}{k-j} & \text{summing first on }j \\ & =\sum_{1 \leq k \leq n}\sum_{1 \leq k-j \lt k}\frac{1}{j} & \text{replacing }j\text{ by }k-j \\ & =\sum_{1 \leq k \leq n}H_{k-1} & \text{simplify and by the definition of }H_{k-1} \\ & =\sum_{0 \leq k \lt n}H_k & \text{replacing }k\text{ by }k+1\text{ and simplify}\end{array}

改变求和顺序,先k后j也只能得到相同的结果。

看样子有点棘手。如果我们在把S_n转化成和的和形式之前,把k替换成k+j,即

\begin{array}{l}S_n & =\sum_{1 \leq j \lt k \leq n}\frac{1}{k-j} & \\ & =\sum_{1 \leq j \lt k+j \leq n}\frac{1}{k} & \text{replacing }k\text{ by }k+j \\ & =\sum_{1 \leq k \leq n}\sum_{1 \leq j \leq n-k}\frac{1}{k} & \text{summing first on }j \\ & =\sum_{1 \leq k \leq n}\frac{n-k}{k} & \\ & =\sum_{1 \leq k \leq n}\frac{n}{k}-\sum_{1 \leq k \leq n}1 & \text{by the associative law} \\ & =nH_n-n. & \text{by definition of }H_n\end{array}

bingo!搞定了!并且,我们还得到一个额外的收获:

\sum_{0 \leq k \lt n}H_k=nH_n-n.

这个例子告诉我们,如果一个两重和的项包含k+f(j)这种形式的式子(这个例子中f(j)=-j),可以尝试先把k替换成k-f(j),然后对j索引先求和。另外还有一种几何意义上的启发,如n=4时:

\begin{matrix}& k=1 & & k=2 & & k=3 & & k=4 \\ j=1 & & & \frac{1}{1} & + & \frac{1}{2} & + & \frac{1}{3} \\ j=2 & & & & & \frac{1}{1} & + & \frac{1}{2} \\ j=3 & & & & & & & \frac{1}{1} \\ j=4 & & & & & & & & \end{matrix}

之前的做法,先j后k导致结果为H_1+H_2+H_3,同样先k后j得到H_3+H_2+H_1。而正解是应该按对角线求和,得到:\frac{3}{1}+\frac{2}{2}+\frac{1}{3}!(加上\frac{1}{1}+\frac{2}{2}+\frac{3}{3}+\frac{4}{4}即得到\frac{4}{1}+\frac{4}{2}+\frac{4}{3}+\frac{4}{4}=4H_4,所以结果为4H_4-4



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*