Skip to content

《组合数学》缩写(二)

第4章

本章讲了生成各种排列与组合的算法,最后提了一下偏序和等价关系的相关概念。

书中生成n个元素的所有全排列的算法并不好,原因是不按照字典序生成。其实我们需要的只是生成字典序意义下的“下一个”全排列的算法。设原序列为s[0..n-1],算法是这样的:找到最大的i使s[i]<s[i+1](若i不存在则不存在下一个全排列);再找到最大的j使i<j、s[i]<s[j],交换s[i]与s[j];将s[i+1..n-1]的元素逆序。

排列的逆序列就是排列中每个元素逆序数构成的数列,一个元素的逆序数就是在排列中先于它且大于它的元素的个数。当排列中元素的取值一定时,根据逆序列可以构造出原来的排列。

生成集合所有子集(等价于0和1的n元组)的方法是类似于二进制进位的,也就是从01序列的一边开始不断把1改成0直到遇到一个0并把它改成1。还有一种方法是按照n阶反射Gray码的顺序生成这些n元组,不过似乎没什么用。

按照字典序生成前n个正整数的r-组合的算法看上去还是挺有用的,当然只需要研究如何生成“下一个”r-组合即可。舌原序列为s[0..r-1],算法是:确定最大的k,使得s[k]+1<=n且s[k]+1未在s[0..k-1]中出现;将s[k..n-1]顺次设为s[k]+1、s[k]+1、…、s[k]+r-k+1。

(按照字典序生成r-排列的方法是什么呢?有待研究……)

定义一些关系R的性质:自反(对于所有x,满足xRx)、反自反(对于所有x,不满足xRx)、对称(对于所有x、y,若xRy,则yRx)、反对称( 对于所有不相同的x、y,若xRy,则yRx不成立;或者说xRy且yRx仅当x=y)、传递(对于所有x、y、z,若xRy且yRz,则xRz)。

满足自反、反对称、传递的关系是偏序;将上面的自反改成反自反就成了严格偏序。对于偏序R,若任意x、y都有xRy或yRx,则R是全序。元素见存在偏序/全序关系的集合以及该关系称为偏序集/全序集。

有序偏序集的线性扩展(即所有元素的一个排列s[0..n-1],若s[i]≤s[j],则i<=j)跟拓扑排序是一样的。

满足自反、对称、传递的关系是等价关系。利用元素间的等价关系可以将集合划分成若干等价类;或者说,集合上的等价关系与集合的划分是对应的。

第5章

组合数C(n,k)出现在二项式定理中,所以它们也叫二项式系数。二项式系数有好多重要的性质。

Pascal公式:C(n,k) = C(n-1,k) + C(n-1,k-1)。当需要系统地求出一定范围内所有C(n,k)的值时,这是比较好的递推方法。证明方法是:从n个元素中选k个元素,可以选择元素1,这时只需从剩下n-1个元素中选择k-1个,方法数是C(n-1,k-1),也可以不选元素1,这时的方法数是C(n-1,k),根据加法原理可得结论。Pascal三角形是一个很有意思的图形,它的另一种解释是:从顶部开始,只能向下或下右走,到达点(n,k)的路径条数。

二项式定理:(x+y)n = C(n,0) xny0 + C(n,1) xn-1y1 + … + C(n,k)xn-kyk + … + C(n,n)x0yn。它的证明可以通过归纳法(代数方法)也可以通过二项展开式的组合意义得出。

二项式系数还存在另外一些恒等式:k C(n,k) = n C(n-1,k-1);C(n,0) + C(n,2) + … = C(n,1) + C(n,3) + …;ΣkC(n,k) = n*2n-1(1<=k<=n);Σ C(n,k)^2 =C(2n,n)(0<=k<=n);ΣC(r+i,i) = C(r+k+1,k)(0<=i<=k);ΣC(i,k) = C(n+1,k+1)(0<=i<=n)……

k递增的二项式系数序列是单峰的,最大值为C(n,n/2)(如果n是奇数,那就有两个,分别是n/2取上整和下整)。证明可以由C(n,k) = C(n,k-1) * (n-k+1) / k的恒等式得出,这个恒等式可以用来求n一定的二项式系数序列,也可以用来求某个C(n,k)并最大限度减少溢出的可能性。

可以扩展组合数,定义C( n, (n_1,n_2,…,n_t))=n! / (n_1! n_2! … n_t!),其中Σn_i = n。我们原来的C(n,r)在这种定义下表示为C(n, (r,n-r))。它表示把n个东西划分成t个集合,使第i个集合有n_i个物品的方法数。这也可以认为是所谓的多项式系数,有相应的Pascal公式、多项式定理,都很容易可以推广出来。

牛顿二项式定理是对前述二项式定理的推广。首先要推广组合数:定义C(a,k)=a(a-1)…(a-k+1)/k!(其中a是实数)。这定理就是:(x+y)a=ΣC(a,k)xkya-k(k=0..∞,也就是说,这是一个无穷级数)。在后面的生成函数部分这定理很有用,可以用来将很长的和式变成一个分式、根式或者相反。

偏序集的链与反链的性质很有用。链就是一个偏序集的一个子集,每两个元素都可比较,也就是说拓扑序唯一。反链就是偏序集每两个元素都不可比较的子集,或者说拓扑序任意。三个重要定理:偏序集中任一反链与任一链的公共元素不超过一个(这是明显的);偏序集中反链的最大长度等于它能划分成链的最少个数;偏序集中链的最大长度等于它能划分成反链的最少个数(这两个优美的定理是对偶的,证明略繁,略过)。有了这些定理,就可以轻松地证明最小的上升子序列覆盖为何等于最长的不上升子序列长度了(若将偏序关系定义成i<j且s[i]<s[j],那么LIS就是链)。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*