这是人人都会的求和符号用法,高一便学过的用于数列求和的表达方法:
i=m∑nai=am+am+1+⋯+an 但有时候这么写并不方便。比如如果我们需要遍历一个无序的集合:
S 为所有小于 100 的质数的集合。求 S 的元素之和。
除了把 S 强行规定成一个数列,还可以用这种方法写求和:
x∈S∑x=x1+x2+⋯+xn,S={x1,x2,…,xn} 集合下标可以是一个判断式(如属于、不等式、等式),只要一个元素符合该判断式,则会被计入求和。
比如求一个多项式所有根的和:
p(x)=0∑x 求 n 所有因数的和:
k∣n∑k 我们也可以用不等式的方法求和。比如经典的 Sigma 用法就可以等价为一个不等式:
i=m∑nf(i)=m≤i≤n∑f(i) 不等式中一般默认循环变量(i, j, k等)为整数,不过也可以特别说明。
用不等式做循环的好处是可以添加多个变量,比如:
1≤i,j≤n∑f(i,j)=f(1,1)+f(1,2)+⋯+f(1,n)+f(2,1)+f(2,2)+⋯+f(2,n)+⋯+f(n,1)+f(n,2)+⋯+f(n,n)=i=1∑nj=1∑nf(i,j) 如果两个变量的遍历规则是互相独立的,则可以把它们拆分成两次求和——比如下面的求和,i, j, k 就是互相依赖的:
0<k<2j>1≤i<j≤n∑f(i,j,k) 它等效于这样的代码:
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = 1; k < 2 * j; k++) {
sum += f(i, j, k);
}
}
}
那么如果想解出一个通项或值,就需要把三个变量分离。这往往借助于对 f(i,j,k) 做一些变形,这是竞赛中常用的手段,因为我们并不擅长在求和时同时循环两个变量。
除此以外,还有特殊的求和方法,比如轮换求和:
cyc∑f(a1,a2,…,an)=f(a1,a2,…,an)+f(a2,a3,…,an,a1)+⋯+f(an,a1,a2,…,an−1) 穷举所有对 a1, a2, ..., an 的轮换(每次把第一个元素放到最后去),然后算出它们对应的 f 的和。一共有 n 个这样的项。
也可以把需要轮换的变量写在下标中:
a1,a2,a3∑f(a1,a2,a3,a4)=f(a1,a2,a3,a4)+f(a2,a3,a1,a4)+f(a3,a1,a2,a4) 对称求和:
sym∑f(a1,a2,…,an) 穷举所有 a1, a2, …, an 的排列,然后算出它们对应的 f 的和。一共会有 n! 个这样的项,因此一般只讨论两个或三个变量的对称和。
用轮换、对称求和可以非常方便地表示出一些轮换式,比如:
(i+j+k)3=i,j,k∑i3+3i,j,ksym∑i2j+6ijk 有时候也会在不引发歧义的情况下把下标 i, j, k 省去。
附上一个花式使用求和符号的对拉格朗日恒等式的证明,也就是柯西不等式的加强形式:
i=1∑nai2i=1∑nbi2−(i=1∑naibi)2=1≤i<j≤n∑(aibj−ajbi)2LHS=1≤i,j≤n∑ai2bj2−i=1∑nai2bi2−1≤i<j≤n∑2aibiajbj=1≤i=j≤n∑ai2bj2−1≤i<j≤n∑2aibiajbj=1≤i<j≤n∑(ai2bj2+aj2bi2−2aibiajbj)=RHS