组合数学8-2003

1、组合数学(Combinatorics),哈尔滨工业大学(威海)计算机科学与技术学院 孟凡超 Email: Tele主要内容,概述 鸽巢原理 排列与组合 生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数 特殊计数序列 Polya计数法,特殊计数序列,Catalan数 Catalan序列：C0,C1,Cn,，其中，,为第n个Catalan数。,具有n+1条边的凸多边形的三角形区域划分方法数,特殊计数序列,C0表示具有2条边的凸多边形的三角形区域划分方法数。 C1表示具有3条边的凸多边形的三角形区域划分方法数。 C2表示具有4条边的凸多边形的三角形区域划分方法

2、数。 Cn表示具有n+2条边的凸多边形的三角形区域划分方法数。,特殊计数序列,4多边形三角形区域划分,5多边形三角形区域划分,3多边形三角形区域划分,C1=1,C2=2,C3=3,C0=1,特殊计数序列,定理：n个+1和n个-1构成的2n项 a1,a2,a2n 其部分和满足 a1+a2+ak0 (k=1,2,2n) 的数列的个数等于第n个Catalan数,(1),(2),特殊计数序列,n=1时，1个+1和1个-1，C1=1 序列：+1,-1 n=2时，2个+1和2个-1，C2=2 序列：+1,+1,-1,-1; +1,-1,+1,-1 n=3时，3个+1和3个-1，C3=5 序列：+1,+1,

3、+1,-1,-1,-1； +1,+1,-1,+1,-1,-1; +1,+1,-1,-1,+1,-1; +1,-1,+1,+1,-1,-1; +1,-1,+1,-1,+1,-1.,特殊计数序列,证明： 不/可接受序列：如果n个+1和n个-1的序列(1)满足(2)，则称其为可接受的序列，否则称其为不可接受序列。令An表示可接受序列的个数，Un表示不可接受序列的个数。 序列个数：由n个+1和n个-1构成的序列的个数等于多重集 n+1, n-1的排列数，该数等于：,因此，,我们首先计算Un，然后再从 中减去Un而算出An。,特殊计数序列,考虑不可接受序列。因为序列是不可接受的，所以存在一个最小的k使得

4、部分和a1+a2+ak是负的。因为k是最小的，所以在ak前面存在相等个数的+1和-1，并且我们有 a1+a2+ak-1=0和ak=-1。特别地，k是一个奇整数。,现在把k项中的每一项的符号都反过来，即对i=1,2,k用 -ai代替ai并保持剩下的项不变。 结果序列a1,a2,a2n有(n+1)个+1和(n-1)个-1的序列。,符号倒转,特殊计数序列,上述过程是可逆的：给定(n+1)个+1和(n-1)个-1的序列，则存在当+1的个数超过-1的个数的时候的第一个实例。把+1和-1符号倒过来，结果就得到n个+1和n个-1的不可接受的序列。这样，有多少个(n+1)个+1和(n-1)个-1的序列就有多少

5、个不可接受序列。 具有(n+1)个+1和(n-1)个-1的序列的个数是多重集 (n+1)+1,(n-1)-1的排列数，该数等于,例如，序列：-1,+1,+1,+1,+1,-1 +1,-1,-1,+1,+1,-1,符号倒转,特殊计数序列,因此，,特殊计数序列,例：有2n个人排成一行进入剧场。入场券50美分。2n个人中的n个人有50分一个的分币，n个人有一美元的纸币。剧院售票处相当草率地用一个空的现金收录机开始售票。有多少种列队方法使得只要有1美元的人买票，售票处就有50分币找零？ 例：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)

6、从家到办公室的对角线，那么，有多少条可能的道路？,家,办公室,特殊计数序列,Catalan序列递推关系,因此，Catalan序列由下面递推关系和初始条件确定：,特殊计数序列,拟-Catalan数,因此，拟-Catalan序列由下面递推关系和初始条件确定：,特殊计数序列,例：令a1,a2,an为n个数。我们说这些数的乘法格式是指进行a1,a2,an的乘法的方案，一个乘法格式需要两数间的n-1次乘法，这两个数中的每一个或者是a1,a2,an之一，或者是它们的部分乘积。求n个数的乘法格式的数目。,特殊计数序列,令hn表示n个数的乘法格式的数目。 h1=1 h2=2 (a1a2)和(a2a1) h3=

7、12,三个数的每一个乘法格式都需要两次乘法，每次乘法又对应一套圆括号。,特殊计数序列,对于a1,a2,an的每一种格式均可以从对a1,a2,an-1的格式以恰好下列方法之一得到： 取a1,a2,an-1的一种乘法格式(它有n-2次乘法和n-2组括号)，将an插入到n-2个乘法之一的两个因子中的任一个因子两侧中的任一侧。于是，n-1个数的每一种格式都用这种方法给出n个数的22(n-2)=4(n-2)种格式。 取a1,a2,an-1的一种乘法格式并用an乘它的左边或右边。于是，n-1个数的每一种格式均以这种方式给出n个数的两种格式。,特殊计数序列,推广上述分析得到，n-1个数的hn-1种乘法格式中

8、的每一种格式均给出n个数的4(n-2)+2=4n-6种格式。于是，得到递推关系：hn=(4n-6)hn-1 (n2)。(该数为拟-Catanlan数),特殊计数序列,例如，n=6，并考虑a1,a2,a3,a4,a5的乘法格式 (a1a2)(a3a4)a5) 在该格式中有4次乘法。我们任取其一，例如(a3a4)和a5的乘法，并将a6插入到这两个因子的每一个的任一侧，得到： (a1a2)(a6(a3a4)a5) (a1a2)(a3a4)a6)a5) (a1a2)(a3a4)(a6a5) (a1a2)(a3a4)(a5a6),特殊计数序列,除了这些格式外，还有两种格式， (a6(a1a2)(a3a4

9、)a5) (a1a2)(a3a4)a5)a6),特殊计数序列,例：如果只以顺序a1,a2,an列成的n个数的乘法格式进行计数，那么该数目为多少？,令gn表示带有这种附加限制的乘法格式数。于是hn=n!gn， 因此，,特殊计数序列,在a1,a2,an的每个格式中，存在着最后的乘法(对应外层的圆括号) (a1,a2,ak的格式)(ak+1,an的格式) 关于a1,a2,ak的乘法格式可以有gk种方式选择，而ak+1,an的乘法格式有gn-k种方式选择。由于k可以是数1,2,n-1中的任一个，因此有 gn=g1gn-1+g2gn-2+gn-1g1 (n2),特殊计数序列,这个递推关系和初始条件g1=

10、1一起唯一确定计数序列 g1,g2,g3,gn, 这样，满足初始条件g1=1的递推关系的解就是,特殊计数序列,具有n+1条边的凸多边形区域通过插入在区域内部不相交的对角线而分成三角形区域的方法数与给定顺序的n个数的乘法格式数相同！,a1,a2,a3,a4,a5,(a1a2),(a1a2)a3),(a1a2)a3)a4),(a1a2)a3)a4)a5),a1,a2,a3,a4,a5,(a1a2),(a3a4),(a1a2)(a3a4),(a1a2)(a3a4)a5),特殊计数序列,差分序列 令h0,h1,h2,hn, (1) 为一数列。定义新的序列 h0, h1, h2, hn, (2) 叫做式

11、(1)的由hn=hn+1-hn定义的(一阶)差分序列。,特殊计数序列,二阶差分序列：2h0, 2h1, 2h2, 2hn,特殊计数序列,p-阶差分序列：ph0, ph1, ph2, phn, (p1),p阶差分序列是(p-1)阶差分序列的一阶差分序列。 一个序列的0阶差分序列就是它自己。,特殊计数序列,差分表：通过将每个p=0,1,2,阶差分序列列成一行而得到三角形阵列。,特殊计数序列,例：令序列 h0,h1,h2,hn,由hn=2n2+3n+1 (n0)确定。该序列的差分表为：,特殊计数序列,定理：令序列的一般项是n的p次多项式，即,则对所的n0，p+1hn=0。,证明：用归纳法证明。如果p

12、=0，则有hn=a0， hn=hn+1-hn=a0-a0=0 假设p1，当一般项为n的至多p-1次多项式时定理成立。有,特殊计数序列,从上式可知，n的p次幂在hn中消去了，并且， hn是n的至多p-1次多项式。根据归纳假设p(hn)=0 (n0)。 由于p+1hn=p(hn)，所以， p+1hn= 0。 因此，根据归纳法定理成立。,特殊计数序列,差分的线性性：设hn=fn+gn，则hn= fn+ gn。 例：令gn=n2+n+1，并令fn=n2-n-2(n0)。求hn=2gn+3fn的差分表。 hn=2(n2+n+1)+3(n2-n-2)=5n2-n-4,特殊计数序列,gn的差分表,fn的差分

13、表,hn的差分表,差分表由第0行元素确定,差分表由第0条对角线元素确定,特殊计数序列,定理：其差分表的第0条对角线等于c0,c1,c2,cp,0,0,0, 其中cp0的序列的一般项是满足,的n的p次多项式。,特殊计数序列,第0条对角线元素为0,0,0,0,1,0,0,的差分表,h0=0,h1=0,h2=0,h3=0,h4=1。,特殊计数序列,由于差分表第5行全是0，那么寻找一个其第n项hn是n的4次多项式的序列。如果hn是一个4次多项式，它有根0,1,2,3，所以，hn=cn(n-1)(n-2)(n-3)。 因为h4=1，所以，1=c4321，即c=1/4!。因此,特殊计数序列,根据上述推导可

14、以得出结论,0, 0,0,1,0,0,是n的p次多项式，其差分表的第0条对角线等于,p个,特殊计数序列,1,0,0,差分表 一般项为常数,0,1,0,差分表 一般项为n的1次多项式,0,0,1,差分表 一般项为n的2次多项式,特殊计数序列,1,0,0,差分表,0,2,0,差分表,0,0,2,差分表,1,2,2,差分表,特殊计数序列,定理：其差分表的第0条对角线等于c0,c1,c2,cp,0,0,0, 其中cp0的部分和等于,的n的p次多项式。,特殊计数序列,特殊计数序列,恒等式：,证明：根据Pascal公式,有,对第一项展开,对第一项展开,对第一项展开,特殊计数序列,令hn=np，hn的差分表

15、的第0条对角线有形式 c(p,0),c(p,1),c(p,2),c(p,p),0,0, 且,令,与P(n,k)相同,所以,从而得到,特殊计数序列,第二类Stirling数,特殊计数序列,0,1,16,81,256,1,15,65,175,14,50,110,36,60,24,hn=n4的差分表,c(4,0),c(4,1),c(4,2),c(4,3),c(4,4),S(4,0)=0,S(4,1)=1/1!=1,S(4,2)=14/2!=7,S(4,3)=36/3!=6,S(4,4)=24/4!=1,特殊计数序列,第二类Stirling数：,特殊计数序列,定理：如果1kp-1，则 S(p,k)=k

16、S(p-1,k)+S(p-1,k-1)。,特殊计数序列,对于满足1kp-1的每一个k，比较两个公式中np表达式nk的系数,特殊计数序列,S(p,k)三角形,3=21+1,65=410+25,性质1：S(p,1)=1 (p1) 性质2：S(p,2)=2p-1-1 (p2) 性质3：S(p,p-1)= (p1),特殊计数序列,性质1：S(p,1)=1 (p1)。,证明：,特殊计数序列,性质2：S(p,2)=2p-1-1 (p2),证明：,特殊计数序列,性质3：,证明：,特殊计数序列,定理：第二类Stirling数S(p,k)是将p个元素的集合划分成k个不可辨别的空盒的划分的个数。,1,2,3,划分

17、1,划分2,划分3,S(3,2)=3,特殊计数序列,证明：令S*(p,k)是将p个元素的集合划分成k个不可辨别的非空盒的划分的个数。 S*(p,p)=1 (p0)。如果盒子的个数与元素的个数相同，那么每一个盒子恰好有一个元素。 S*(p,0)=0 (p1)。如果至少有一个元素没有盒子，那么就不可能存在划分。 S*(p,1)=1 (p1)。如果只有一个盒子，那么所有的元素都被装入该盒子中。 因此，S*(p,k)与第二类Striling数满足相同的初始条件。,特殊计数序列,如果能够证明S*(p,k)满足第二类Stirling数所满足的相同的递推关系，也就是说，如果能够能够证明 S*(p,k)=kS

18、*(p-1,k)+S*(p-1,k-1) (1kp-1) 那么就可以断言对满足0kp的所有k和p，S*(p,k)=S(p,k)。,集合1,2,p被划分成k个非空、不可辨别盒子的划分有两种类型： (1)那些使得p自己单独在一个盒子的划分； (2)那些使得p不单独在一个盒子的划分，这样，包含p的盒子就至少还有多于一个的其它元素。,特殊计数序列,在第(1)种情况中，如果我们从含有p的盒子中拿走p，那么我们就得到将1,2,p-1划分成k-1个非空、不可辨别盒子的划分。因此，存在S*(p-1,k-1)种对1,2,p的第(1)种划分方法。 在第(2)种情况，首先将1,2,p-1划分成k个非空、不可辨别的盒

19、子的划分，共有S*(p-1,k)种方法，然后，对于1,2,p-1的每个k划分，将p加到该划分的某个盒子中，从得到1,2,p的第(2)种划分。由乘法原理，此类划分共共有kS*(p-1,k)种方法。,特殊计数序列,综合上述分析，由加法原理，有 S*(p,k)=kS*(p-1,k)+S*(p-1,k-1)。 所以，S*(p,k)=S(p,k)。,特殊计数序列,例：由1,2,3的2划分，构造1,2,3,4的2划分。,1,2,3共有3个2划分：1,23，1,32，2,31。 构造1,2,3,4的2划分方法： (1) 4是一个划分，则只有唯一的2划分，即 1,2,34;,特殊计数序列,(2) 4不是单独一

20、个划分，则4可以加入到1,2,3的每一个2划分的两个部分的任一部分，从而构成了1,2,3,4的6个不同的2划分，即 1,2,43， 1,23,4； 1,3,42， 1,32,4； 2,3,41， 2,31,4。,特殊计数序列,令S#(p,k)表示将p个元素的集合划分成k个可辨别的非空盒子的划分的个数，则，S#(p,k)=k!S(p,k)。,1,2,3,划分1,划分4,划分6,S#(3,2)=2!3=6,划分2,划分3,划分5,特殊计数序列,定理：对每一个满足0kp的整数k，都有,从而,例如,特殊计数序列,证明：令U是将1,2,p分成k个可辨别盒子B1,B2,Bk的所有划分的集合，则|U|=kp

21、。 我们定义k个性质：P1,P2,Pk，其中，Pi为第i个盒子Bi是空盒的性质。令Ai为U的子集，表示由盒Bi是空盒的那些划分组成。,因此,特殊计数序列,A1A2 At (1t k)表示盒子B1,B2,Bt是空的而剩下的盒子Bt+1,Bk可以是也可以不是空的。因此， |A1A2At|是对1,2,p的划分到k-t个可辨别的盒子的划分数的计数，即等于(k-t)p。 无论假设哪t个盒子是空的，相同的结论都成立。即，对于1,2,k的每一个t-组合i1,i2,it,根据容斥原理，我们有,特殊计数序列,Bell数：Bell数Bp是将p个元素的集合分成非空、不可辨别盒子的划分数。Bp=S(p,0)+S(p,

22、1)+S(p,p)。,B0=1,B1=0+1=1,B2=0+1+1=2,B3=0+1+3+1=5,B4=0+1+7+6+1=15,B5=0+1+15+25+10+1=52,B6=0+1+31+90+65+15+1=203,B7=0+1+63+301+350+140+21+1=877,特殊计数序列,定理：如果p1，则,证明：将集合1,2,p划分成一些非空、不可辨别的盒子。含有p的盒子还包含1,2,p-1的子集X。X有t个元素，其 中，0tp-1。我们可以有 种方式选择大小为t的集 合X，并以Bp-1-t种方式将1,2,p-1中不属于X的p-1-t个元素划分成一些非空、不可辨别的盒子。因此,特殊计

23、数序列,当t取值0,1,p-1时，(p-1)-t也取这些值，因此得到,第二类Stirling数利用n0,n1,np写出np,特殊计数序列,第一类Stirling数：,np展开后得到含有n的幂：np,np-1,n1,n0的多项式，其系数的符号正负相间。,特殊计数序列,第一类Stirling数：s(p,k) (0kp) s(p,0)=0 (p1) s(p,p)=1 (p0),特殊计数序列,定理：如果1kp-1，则 s(p,k)=(p-1)s(p-1,k)+s(p-1,k-1),证明：,比较nk的系数,特殊计数序列,定理：第一类Stirling数s(p,k)是将p个元素排成k个非空的循环排列的方法数

24、。,例：1,2,3,4的排成2个非空循环排列的两种方法。,1,2,4,3,1,3,4,2,划分1,划分2,特殊计数序列,证明：令s#(p,k)表示把p个元素排成k个非空圆圈的方法数。,s#(p,p)=1 (p0)：如果k个元素k个圆圈，那么每个圆圈就只含有一个人； s#(p,0)=0 (p1)：如果至少有一个元素，那么任何安排都至少包含一个圆圈。 因此，s#(p,k)与第一类Stirling数满足相同的初始条件，下面，我们证明它们具有相同的递推关系： s#(p,k)=(p-1)s#(p-1,k)+s#(p-1,k-1),特殊计数序列,设这n个元素分别为1,2,p。将1,2,p排成k个圆圈有两种

25、类型： (1)将p自己排成一个圆圈，其它p-1个元素排成k-1个圆圈，这种排法共有s#(p-1,k-1)个。 (2)P至少和一个别人在一个圆圈中。这些排法可以通过把1,2,p-1排成k个圆圈，并把p放在1,2,p-1任何一个元素的左边得到。因此，这种排法共有s#(p-1,k)种。 于是，将p个元素排成k个圆圈的安排方法数为： s#(p,k)=(p-1)s#(p-1,k)+s#(p-1,k-1) 所以，s#(p,k)=s(p,k)。,特殊计数序列,正整数分拆 定义：正整数n的一个k分拆是把n表示成k个正整数的和 n=n1+n2+nk (k1) (*) 的一种表示法，其中ni0(1i k)叫做该分

26、拆的分部量。 无序分拆：如果表达式(*)是无序的，即对诸ni任意换位后的表示法都只视为一种表示法，这样的分拆叫做无序分拆；,特殊计数序列,有序分拆：如果表达式(*)是有序的，即表达式右边的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆叫做有序分拆。这时，ni叫做第i个分部量。 分拆数：n的k分拆的个数称为n的k分拆数。n的所有分拆(k取遍所有可能的值)的个数称为n的分拆数。,特殊计数序列,例如，4=2+1+1 =1+2+1 =1+1+2 是4的所有3个有序3分拆。 而4=2+1+1是4的唯一一个无序3分拆。,特殊计数序列,有序分拆 定理：正整数n的有序k

27、分拆的个数为,证明：正整数n的有序k分拆可以表示为 n=n1+n2+nk，其分拆的个数等价于方程 x1+x2+xk=n的正整数解的个数。 所以，正整数n的有序k分拆数等于,特殊计数序列,性质1：正整数n的有序k分拆，要求第i个分部量大于等于pi，其个数为,特殊计数序列,性质2：正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为,证明：设正整数2n的有序k分拆为： 2n=x1+x2+xk (xi为偶数，1i k) 令yi=xi/2，则有n=y1+y2+yk。即y1,y2,yk是n的一个有序k分拆。,特殊计数序列,反之，设y1,y2,yk是n的一个有序k分拆，令xi=2yi，则x1,x2

28、,xk是2n的一个满足题意条件的有序k分拆。 所以，2n满足各分部量为偶数的有序k分拆数等于n 的有序k分拆数，为,特殊计数序列,性质3：正整数n分拆成k个分部，若n与k同为奇数或同为偶数，则n的个分部量都是奇数的有序分拆数为,证明：n的个分部量为奇数的分拆： n=n1+n2+nk 与n-k的各分部量为偶数的分拆 n-k=(n1-1)+(n2-1)+(nk-1) (ni-1为偶数),特殊计数序列,n-k=(n1-1)+(n2-1)+(nk-1) (ni-1为偶数) 显然构成一一对应。由性质2可知，n的各个分部量都为奇数的分拆数为,特殊计数序列,无序分拆 定义：我们用p(n,k)来表示n的k分拆

29、的个数，用p(n)表示n的所有分拆的个数，则有,在n的k分拆中，各分部量的次序无关紧要，一般按照递降顺序排列，若n=n1+n2+nk，则n1n2 nk。如果在n的k分拆中有ai个分部量为i(1in)，那么可以把该分拆表示为： n=an1+an-12+a11或者,特殊计数序列,分拆序列：令pn表示正整数n的无序分拆数，令p0=1，则无序分拆序列为：p0,p1,pn, p1=1。1=1 p2=2。2=2，2=1+1 p3=3。3=3，3=2+1，3=1+1+1 p4=5。4=4，4=3+1，4=2+2，4=2+1+1，4=1+1+1+1 pn等于方程nan+(n-1)an-1+2a2+1a1=n

30、的非负整数解an,an-1,a2,a1的个数。,特殊计数序列,分拆的Ferrers图：设n的一个k分拆为 :n=n1+n2+nk，其中，n1n2n3nk。我们在一条水平直线上画n1个点，在其下面一条直线上画n2个点，且使这两条直线上的第一个点在同一竖线上，其它点依次与上一行的点对齐；依次类推，最后在第k条直线上画nk个点，第一个点与前面各行的第一个点均在同一条竖线上，其它点依次与上面各行点对齐。这样得到的点阵图叫做n的k分拆的Ferrers图。 例如，10的5分拆：10=4+2+2+1+1的Ferrers图,特殊计数序列,共轭Ferrers图：把一个Ferrers图的各行改成列，但其相对位置不

31、变，这样又得到一个Ferrers图，该图叫做原Ferrers图的共轭图。 共轭拆分：共轭Ferrers图所对应的分拆*叫做原分拆的共轭分拆。 例如，图1对于的共轭Ferrers图为图2。 10=4+2+2+1+1所对应的共轭拆分为10=5+3+1+1。,特殊计数序列,图1,图2,分拆的共轭分拆*部分个数等于的最大的部分,特殊计数序列,定理：令是n的分拆n=n1+n2+nk。 的共轭分拆*是n的分拆n=n1*+n2*+nl*(l=n1)，其中，ni*是的至少等于i的部分的个数：ni*=|j:ji| (i=1,2,l, j=1,2,k)。 例如，拆分 :10=4+2+2+1+1所对应的共轭拆分为

32、* : 10=5+3+1+1。 n1*=5。 的至少等于1的部分个数为5。 n2*=3。 的至少等于2的部分个数为3。 n3*=1。 的至少等于3的部分个数为1。 n4*=1。 的至少等于1的部分个数为1。,特殊计数序列,自共轭拆分：令是n的分拆n=n1+n2+nk。 的共轭分拆*也是n的分拆n=n1+n2+nk，即， = *，则称为自共轭拆分。 例如，拆分 :12=4+4+2+2，它的Ferrers图为：,其共轭拆分*也是12=4+4+2+2。因此为共轭拆分。,特殊计数序列,定理：,证明：右边表达式等于乘积,项xn由这个乘积通过从第一个因子选择项,从第二个因子选择项,从第三个因子选择项,等等而得到。其中，1a1+2a2+3a3+=n。因此，n的每一个分拆都使xn的系数增1，而xn的系数等于n的分拆个数pn。,特殊计数序列,超优关系：令:n=n1+n2+nk (n1n2nk)和:n=m1+m2+mk (m1m2mk)为n的两个分拆。如果的部分和至多等于的部分和：n1+n2+nim1+m2+mi (i=1,2,k)，则我们说被优超，或优超。 性质：超优关系是自反的、对称的和传递的。,特殊计数序列,例：考虑9的三个分拆： :9=5+1+1