《组合数学之反演理论》由会员分享，可在线阅读，更多相关《组合数学之反演理论（47页珍藏版）》请在金锄头文库上搜索。
1、1,组合数学,第七讲,反演理论,2,第七讲*: 内容提要,II. 二项式反演公式,III. Mbius 反演公式,IV. 反演原理介绍,I. 反演方法引言,3,I. 反演方法引言,在代数及分析问题中, 为了定出某个未知元, 我们常从问题的要求出发,列出未知元所满足的一类方程, 然后从中解出未知元本身. 对于未知数列, 我们前面所学习的递归关系法, 也是这个思想, 它给出序列所满足的线性常系数递归关系, 然后求解出数列本身.,4,当然并不是每个序列都有这样的递归关系, 在有递归关系的情况下, 也可能这个关系不是齐次关系, 或者不是常系数, 求解起来就比较难. 反演方法是另外一种求解序列的方法,
2、不同的是这种方法是把一个序列用另外一个序列表示出来. 粗略来说, 就是根据两个序列f(n)和g(n)所满足的特殊关系, 给出他们的相互表示方法.,5,具体来说, 为得到某个组合计数问题的解, 我们首先设法求出相应序列f(n)所满足的(累计)关系式,其中g(n)是已知序列, 然后从中解出,(1)与(2)两式互为反演公式.,6,互逆公式：若由公式A可推出公式B，由公 式B也能推出公式A，则称公式A、B互逆。,反演公式：如果公式A、B互逆，则称命题“ 公式A成立当且仅当公式B成立”是反演公式.,反演技巧：为了求an=|An|, 引进bn=|Bn|, 其中 bn是易求的或者已知的。先建立bn由ak的
3、表达公式A，然后应用反演公式，得到公式 B，此公式B是用bk表示an的公式，从而求 出an.,7,第一反演公式,定理：设n是一个自然数，多项式序列pn, qn(其中pn, qn均为n次多项式)有下列关系,且ii0,ii 0则,8,证明：令,将已知条件以矩阵形式表示为,9,于是 p=Aq=ABp,由于pn|n=0,1,2,是线性空间Rx的一组基,所以AB=I，于是A-1=B,所以,10,II.二项式反演公式,例1(错排问题) 在n个数字1,2,n形成的n!个排列a1a2an中, 满足ai i 的排列有多少个？我们已两次用到这个例子. 第一次: 建立递归关系, 利用指数型母函 数方法求解; 第二次
4、: 利用容斥原理, 得到通项公式. 下面先简单回顾一下, 再引入反演公式.,11,第一次：建立了递归关系,并由递归关系求得其指数型母函数：,由此得到:,12,第二次: 令Aj表示排列12n中使j位置上元素就是j的排列的集合, j=1,n. 则排列12n的所有错位排列组成集合,根据容斥原理, 即可得到:,13,第三次: 容易看出恰好有r个ai=i的排列a1a2an之个数正好为C(n,r)Dn-r, 既然全部排列个数为n!, 自然有,根据后面将要学习的二项式反演公式, 可以直接得到:,14,定理A (二项式反演公式) 设有两个序列 an,bn, 则,证明:,15,注: 上述公式的证明也可以利用指数
5、型母母函数方法. 设an与bn的指数型母函数分别为A(x)及B(x), 则有,16,第一反演公式,定理：设n是一个自然数，多项式序列pn, qn (其中pn, qn均为n次多项式)有下列关系,则,17,用第一反演公式证明,由,及,由第一反演公式即得。,18,II. Mbius反演公式,定理B (Mbius反演公式) 设f(n)和g(n)是 定义在正整数集合上的两个函数.,成立当且仅当下式成立,其中(m)为Mbius函数(定义见后面), 称f(n)与g(n)互为Mbius逆变换. (M1), (M2)称为Mbius反演公式.,19,Mbius函数(m)的定义如下：,例如: 30=235, 121
6、=112. (30)=(-1)3=-1,(121)=0. 要证明本定理需要先证明一个关于Mbius函数(m)的一个性质作为引理.,20,引理C 序列(d)满足下面公式：,证 n=1, 命题成立. 如果n1, 设 n=p11p22pkk , n1= p1p2pk 用(k,j)表示1,2,k中的j元子集所组 成的集合, 则有,21,设d1|n, 引理C中(5)等价于下列等式:,22,Mbius反演公式证明： 设(M1)成立, d|n, 则有,因d1|(n/d), 所以存在m, 使得dd1m=n 从而d|(n/d1). 将上式代入(M2)的右端, 有,23,反之, 设(M2)成立, 对d|n, 有,
7、24,以此代入(M1)的右端, 得,25,Mbius反演公式的上述证明只要熟悉连和号的性质和Mbius函数的特殊性质,证明起来并不困难. 但是它们是如何被推导出来的, 或者说是如何发现的? 这个问题更有启发性. 1968年Berlekam在他的一本Algebraic Coding Thoery书中给出了由(M1)逐次解出g(n)的过程, 从求解中自然地引出了Mbius函数, 这种启发性的推理值得有兴趣的同学参考.,26,V. Mbius反演公式的应用,Mbius反演公式在组合计数、数论、信息论、遗传密码等问题中有应用. 作为例子, 我们考察圆排列问题, 也就是著名的环状字问题. 设有m个字母组
8、成的字母表T, 从中取出n个字母(允许重复)按顺时针方向可以组成一个圆排列: W=a1a2a3an.,27,由于一个圆排列可以选取其中一个字 母ai开始, a1a2an, a2ana1, ,anan-1a1 都看作是同一圆排列. 例3: 当m=2, n=4,T=a,b时, 共有6个不 同的圆排列: aaaa, bbbb, abab, aabb, aaab, bbba. 这里圆排列aabb也可写成abba或bbaa.,28,问题: 求圆排列总数Cm(n)=? 首先我们注意到由m种字母共可作出mn个可重复的线排列a1a2an, 它与圆排列唯一区别在于首尾不相接. n个线状排列 a1a2an, a2
9、an, , ana1an-1 一旦首尾相接均对应同一个圆排列 a1a2an. 由此似乎有Cm(n)=mn/n? 但例子m=2,n=4指出C2(4)=64=24/4.,29,原因何在? 原来一个圆排列所产生的n个线排列并不总是互异的. 例如圆排列abab只能产生出两个不同线排列abab与baba. 导致这种现象的原因在于这一字有“最小周期”2：ai=ai+2. 周期的严格定义如下: 如果由k个元素线排列L在圆周上重复若干次而得到园排列W，则称k是园排列W的周期，其中最小者，称为最小周期。,30,定理：设p是n园排列的最小周期，则p|n。,证明：否则，存在非负整数m，使得,把n园排列从任一处断开，
10、并依顺时针方向 依次排列，而且无限重复下去，得到序列,有xn+i=xi,于是xpm+l+i=xi,因为p是周期，所以有xl+i=xi,说明l也是周期，与p是最小周期矛盾。,31,如果圆排列W的最小周期为p, 则p|n, 由W只能产生出p个不同线排列而不是n个. 注意到每个圆排列总有周期. 这样可以把圆排列按照最小周期来分类. 如果用M(p)=Mm(p)来表示最小周期为p的圆排列的个数, 由于每个最小周期为p的圆排列恰好对应p个线排列,而且不同的最小周期的圆排列产生不同的线排列. 由最小周期为p的圆排列共可产生出pM(p) 个不同的线排列.,32,这样全体线排列总数为,应用Mbius反演公式即得
11、,33,例4.,证. 仅须证n1情形, n1为n不同素因子积.,34,利用这个例题的结果, 可以把圆排列计 数公式利用欧拉函数改进成单重求和形式:,这个公式还可以利用下章将要学习的 Polya计数理论得到. 反演方法是组合数学中比较难的部分, 大家了解一下就行了.,35,例 从红、蓝、绿三种珠子中，共取10个排成一个 圆周，其最小周期为10，求排列方法数。,解：即求M3(10),36,例 从4种颜色的珠子中，共取12个排成一个 圆周，有多少种排法？,解：即求C4(12),37,V. 反演原理介绍,在引言中我们指出反演公式的一般形 式为由下列两个公式互相解出:,可以把这两个式子用矩阵形式表示出
12、来, 更容易理解反演公式的基本原理.,38,39,如果令,显然只要C或者D可逆, 则就可以得到 一个反演公式, D=C-1或者C=D-1. 反演公式无非是给出在已知其中之一 的时候, 求另外一个的公式而已.,40,下面用这个公式来考察一下我们所学习的两个反演公式： 二项式反演公式：,41,C是一个主对角线元素全为1的下三角矩阵, 自然是可逆的. 可以利用待定法求逆矩阵D, 设,由CD=I可解出D, 注意到D的结构, 可以先从第一行决定起, 逐渐递归求出D的全部元素, 结果正如反演公式.,42,Mbius反演公式: 这个公式的矩阵表示没有上面那么方便.,43,可见C是一个主对角线元素均为1的(0
13、,1)矩阵. 利用待定法可以得到C的逆矩阵D=(dij)的元素刚好是Mbius函数:,要知详细的推理细节参考下列文献: E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill (1968).,44,如果要想寻找新的反演公式, 可以按照下列思想进行. 由刚才的分析我们知道, 一般反演公式的寻求相当于求下三角矩阵C=(cij)的逆矩阵D=(dij). 从理论上来讲, 只要C的主对角线元素cii0, 则其逆矩阵总可以用下面的递推方式求出: 由CD=I得到,45,其中ij为Kronecker函数:,但是ik的时候才cik=0; 对kj, dkj=0, 故上式子可简化为,46,尤其当i=j的时候, 得到ciidii=1, 由此 dii-1= cii (7),而对ji, 由(i,j)=0及其(6)可以得到,(7), (8)两个式子给出了依次计算诸dij 的递推算法.,47,VI. 课后学习任务,预习: 鸽巢原理, Ramsey问题 练习题(不需要提交): (1) 用m(m2)种颜色去涂1n棋盘，每格涂一种颜色. 以h(m,n)表示使得相邻格子异色且每种颜色都用上的涂色方法,求h(n,m)的计数公式. (2) 计算出从字母表T=a,b,c中取出3个字母(允许重复)按顺时针方向组成圆排列的总数C3(3)并列出全部不同的圆排列.,
