组合数学第三章 2

1、n个元素依次给以标号1，2，n。 N个元素的全排列中，求每个元素都不 在自己原来位置上的排列数。 设 为数 在第 位上的全体排列， =1，2，n。因数字 不能动， 因而有：,3.4 错排问题,3.4 错排问题,每个元素都不在原来位置的排列数为,3.4 错排问题,例1。数1，2，9的全排列中，求 偶数在原来位置上，其余都不在原来位 置的错排数目。 解：实际上是1，3，5，7，9五个数 的错排问题，总数为：,3.4 错排问题,例2. 在8个字母A,B,C,D,E,F,G,H的全 排列中,求使A,C,E,G四个字母不在原来 上的错排数目。,8个字母的全排列中，令 分别表A,C,E,G在原来位置上的排

2、列，则错排数为：,3.4 错排问题,3.4 错排问题,1. 有限制排列,3.5 棋盘多项式和有限制排列,例4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 解设出现xxxx的排列的集合记为A1， |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105；,6!,1!3!2!,4!2!,7!,3.5 棋盘多项式和有限制排列,设出现zz的排列的集合记为A3， | A3|= =280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的个数为： =1260； 所以： |A1A2A3

3、|=1260(60+105+280) +(12+20+30)6 =871,4!3!,8!,4!,2!,5!,3!,6!,4!,9!,2!3!4!,3.5 棋盘多项式和有限制排列,2棋子多项式,n个不同元素的一个全排列可看做n个相 同的棋子在nn的棋盘上的一个布局。布 局满足同一行（列）中有且仅有一个棋子,x,x,x,x,x,如图所示的布局对应 于排列41352。,3.5 棋盘多项式和有限制排列,可以把棋盘的形状推广到任意形状：,布子规定称为无对攻规则，棋子相当于 象棋中的车。 令r k（C）表示k个棋子布到棋盘C上的 方案数。如：,3.5 棋盘多项式和有限制排列,r1( )=1，,r1( )=

4、2，,r1( )=2，,r2( )=0，,r2( )=1。,为了形象化起见，（ ）中的图象便是棋盘 的形状。,3.5 棋盘多项式和有限制排列,定义设C为一棋盘，称R(C)= rk(C) xk 为C的棋盘多项式。 规定 r0(C)=1，包括C=时。 设Ci是棋盘C的某一指定格子所在的行与 列都去掉后所得的棋盘；Ce是仅去掉该 格子后的棋盘。 在上面定义下，显然有 rk(C)=rk1(Ci)rk(Ce)，,k=0,3.5 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 rk1(Ci)； 要么不布子，方案数为 rk(Ce)。,设C有n个格子，则 r1(C)n r1(C)r0(

5、Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的,3.5 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 rk1(Ci)； 要么不布子，方案数为 rk(Ce)。 从而 R(C)= rk(C) xk rk1(Ci)+ rk(Ce)xk = x rk(Ci)xk + rk(Ce)xk xR(Ci) + R(C e) (3),k=0,k=0,k=0,k=0,3.5 棋盘多项式和有限制排列,例如：,R( )=1+ x；,R( )= xR( )+ R( )= x+ (1+ x)=1+2x；,R( )= x R( ) + R( ) = x(1

6、+ x )+1 + x =1+ 2x +x2,3.5 棋盘多项式和有限制排列,有禁区的排列,例设对于排列P=P1 P2 P3 P4，规定P1， P、， P2、， P42。,1 2 3 4,P1,P2,P3,P4,1,2,4 3,1 4 3,2,2 3,4,3,1 2,1 4,这样的排列对应于有 禁区的布子。如右图 有影线的格子表示禁 区。,3.5 棋盘多项式和有限制排列,定理设 ri 为 I个棋子布入禁区的方案数， i =1,2,3,n。有禁区的布子方案数（即禁 区内不布子的方案数）为,r0 n! r1(n1)! r2(n2)!(1)nrn (1)k rk ( nk)!,k=0,n,证设Ai

7、为第i个棋子布入禁区，其他棋子 任意布的方案集，i =1 , 2 , 3, ,n。,3.5 棋盘多项式和有限制排列,则所有棋子都不布入禁区的方案数为 A1A2An n！ (1)kAi,I(n , k),n,iI,k=0,而 Ai正是k个棋子布入禁区，其 他n - k个棋子任意布的方案数。由假设可知 等于rk(nk)！(注意：布入禁区的棋子也要 遵守无对攻规则）.所以 A1A2An=n!+ (1)k rk ( nk)!,I(n , k),iI,k=0,n,3.5 棋盘多项式和有限制排列,上例方案数为 4!6(41)!11(42)!7(43)! 1(4)!4,例，四位工人，A，B， C，D四项任务

8、。条件如下： 不干B；不干B、C； 不干C、D；不干D。 问有多少种可行方案？,3.5 棋盘多项式和有限制排列,解由题意，可得如下棋盘：,其中有影线的格子表示 禁区。,A B C D,1 2 3 4,R( )=1+6x+10 x2+4x3,方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4,.7鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有 一个巢内有至少有两个鸽子。”,例367人中至少有人的生日相同。 例10双手套中任取11只，其中至少有 两只是完整配对的。 例参加一会议的人中至少有人认识 的别的参

9、加者的人数相等。,.7鸽巢原理之一,例从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是 另一个的倍数。,证设n+1个数是 a1 , a2 , , an+1。每个数去 掉一切2的因子，直至剩下一个奇数为止。 组成序列 r1 , r2, , , rn+1。这n+1个数仍在 1 , 2n中，且都是奇数。而1 , 2n中只有n个 奇数 . 故必有 ri = rj = r , 则 ai = 2i r, aj = 2j r 若ij ，则 ai 是 aj 的倍数。,.7鸽巢原理之一,例5设 a1 , a2 , a3为任意个整数，b1b2b3 为a1 , a2 , a3的任一排列，

10、则 a1b1 , a2b2 , a3b3中至少有一个是偶数,证由鸽巢原理， a1 , a2 , a3必有两个同奇 偶设这个数被除的余数为 xxy，于 是b1 , b2 , b3中被除的余数有个x，一个 y这样a1b1 , a2b2 , a3b3被除的余 数必有一个为,.8鸽巢原理之二,鸽巢原理二m1 , m2 , , mn都是正整数， 并有m1 + m2 + +mnn + 1个鸽子住进n个 鸽巢，则至少对某个 i 有第 i 个巢中至少有 mi个鸽子，i = 1 , 2 , , n,上一小节的鸽巢原理一是这一原理的特殊 情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的 鸽子数mi1则,.8鸽巢原理之二,鸽子总数 m1 + m2 + +mnn ， 与假设相矛盾,推论m只鸽子进n个巢，至少有