7-错排问题

第六讲错排问题考虑如下问题:某人写了5份信与5个信封,将信随便乱装入信封(每个信封装一封信),问无一匹配的装法是多少?这个问题实质上就是一个错排问题．6.1错排问题当1n时,1的全排列只有一个1,它不是错位.所以.01D当2n时,2,1的全排列有2个2,1和,1,2前者不是错位,后者是错位.所以.12D当3n时,3,2,1的全排列有6个,1,3,2,2,1,3,3,1,2,1,2,3,2,3,1,3,2,1前4个不是错位,后2个是错位.所以.23D6.1错排问题n个元素依次给以标号1，2，…，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设为数在第位上的全体排列，=1，2，…，n。因数字不能动，因而有：iAiiii(1)!，1,2,...,iAnin同理jinjinAAji,,2,1,,!26.1错排问题kjinkjinAAAkji,,2,1,,,!3每个元素都不在原来位置的排列数为1211...!(,1)(1)1!(1!(,2)(2))1!2!!!(,)1!nAAAnCnnCnnnnCnn又记为!11!22!111!nnDnn6.1错排问题例在一次聚会上，７位男士将他们的帽子寄存衣帽间．有多少种方法使得这些帽子被返还时分别满足下列条件？（１）没有男士收到自己的帽子；（２）至少一位男士收到自己的帽子；（３）至少两位男士收到自己的帽子．答：（１）7D（２）7!7D（３）6177!7DCD6.1错排问题例数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。5!(5,1)4!(5,2)3!(5,3)2!(5,4)1!1111(5,5)120()442624120CCCCC解：实际上是1，3，5，7，9五个数的错排问题，总数为：6.1错排问题例在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。解:8个字母的全排列中,令分别表A,C,E,G在原来位置上的排列，则错排数为：1234,,,AAAA12348!(4,1)7!(4,2)6!(4,3)5!(4,4)4!24024AAAACCCC6.1错排问题例求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为1111!(1)1!2!3!4!11124(11)926244故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)·9=6306.1错排问题考虑极限?!limnDnn!11!31!21!111lim!limnnDnnnn1e它表明的是我们随机地选择n,,2,1的一个全排列是一个错排列的概率.6.1错排问题例设有n册书分给n个学生，之后又将书收回重新分给学生．问有多少种方式分配这些书使得没有一个学生两次得到同一本书．解：第一次分有!n种方法．第二次分配，由题义知就是一个错排，所以有nD种方法．所求方式为12!!enDnn6.1错排问题定理211nnnDDnD证明:n,,2,1的错排kaaa21可以分为互不相容的两种类型;(1)对于,,,3,2nk令.1,1kaka由于,11a故选取1a的方法共有1n种.又由于1,1kaka的值已定,故将剩下的进行错排列,2n个数由nkk,,1,1,,3,2故这样的错排列个数为.2nD6.1错排问题由乘法法则知,此类型包含的错排列数为.12nDn(2)对于,,,3,2nk令.1,1kaka由于,11a故选取1a的方法共有1n种.但这时只有的值已定,且ka1,1ka故将剩下的1n个数由nkk,,1,1,1,,3,2作错排,其错排数为.1nD由乘法法则知,此类型包含的错排列数为.11nDn由于这两种类型互不相容,由加法法则即证．6.1错排问题1.有限制排列解设出现xxxx的排列的集合记A1，|A1|==60;设出现yyy的排列的集合记A2，|A2|==105；1!3!2!６!4!·1!·2!7!例4个x，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。6.2有限制排列和棋盘多项式设出现zz的排列的集合记为A3,|A3|==280；4!·3!8!|A1∩A2|==12；|A1∩A3|==20；|A2∩A3|==30；|A1∩A2∩A3|=3!=6；全排列的个数为：=1260；所以：|A1∩A2∩A3|=1260－(60+105+280)+(12+20+30)－6=8714!2!5!3!6!4!9!2!·3!·4!6.2有限制排列和棋盘多项式例在整数n,,2,1的无重全排列naaa21中,要求,1,,2,111nkaakk试求全体排列数.nQ解:问题等价于在排列中,数ii不能排在数1i之前,即不允许出现nn1,,34,23,12中任何一种形式.用S表示所有无重全排列的集合,并设性质iP表示在全排列中具有1ii形式的这一性质,令1,,2,1,,niPxSxxAii具有性质6.2有限制排列和棋盘多项式令1,,2,1,,niPxSxxAii具有性质则,!2,!1nAAnAjii121nnAAAQnnDD1!11!2!1!1112111nnnnnCnCnCnniiniiinin010!11!!11!1nDn16.2有限制排列和棋盘多项式例8个小孩围坐在旋转木马上,问有多少种变换坐位的方法,使得每个小孩前面坐的都不是原来的小孩?S表示所有无重圆排列的集合,则!7S1A{‘12’,3,4,…,8}的圆排列2A{1,‘23’,4,…,8}的圆排列……8A{2,3,4,…,‘81’}的圆排列．,!5,!6jiiAAA解:用821AAA1!078!168!258!348!438!528!618!76.2有限制排列和棋盘多项式2．棋子多项式n个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx如图所示的布局对应于排列41352。行:全排列中第几个数列:全排列中排哪个数6.2有限制排列和棋盘多项式可以把棋盘的形状推广到任意形状：r1()=1，r1()=2，r1()=2，令rk（C）表示k个棋子布到棋盘C上的方案数,要求每行每列只有一个棋子。如：r2()=0，r2()=1。6.2有限制排列和棋盘多项式定义设C为一棋盘，称R(C)=∑rk(C)为C的棋盘多项式。规定r0(C)=1，包括C=Ф时。k=0nkxkxR()x1R()221xxR()231xxR()2241xxR()32441xxx6.2有限制排列和棋盘多项式设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk－1(Ci)＋rk(Ce)，即对任一指定的格子，要么布子，所得的方案数为rk－1(Ci)；要么不布子，方案数为rk(Ce)。设C有n个格子，则r1(C)＝n．r1(C)＝r0(Ci)+r1(Ce)，∵r1(Ce)＝n－1∴r0(Ci)＝1．故规定r0(C)＝1是合理的．6.2有限制排列和棋盘多项式从而R(C)=∑rk(C)xk＝∑[rk－1(Ci)+rk(Ce)]xk=x∑rk-1(Ci)xk-1+∑rk(Ce)xk＝xR(Ci)+R(Ce)(3)nnnk=0k=0k=1nk=06.2有限制排列和棋盘多项式例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x26.2有限制排列和棋盘多项式如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：rk(C)=∑ri(C1)rk－i(C2)i=0k故R(C)=∑(∑ri(C1)rk－i(C2))xk=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)(4)6.2有限制排列和棋盘多项式利用（３）和（４），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例R()=xR()+R()=x(1+x)2+(1+2x)2=1+5x+6x2+x3*R()=xR()+R()=1+6x+10x2+4x3*6.2有限制排列和棋盘多项式３．有禁区的排列例设对于排列P=P1P2P3P4，规定P1≠３，P２≠１、４，P３≠2、４，P4≠2。1234P1P2P3P41243143223431214这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。6.2有限制排列和棋盘多项式定理设ri为i个棋子布入禁区的方案数，i=1,2,3,···,n。有禁区的布子方案数（即禁区内不布子的方案数）为r0n!－r1(n－1)!＋r2(n－2)!－···＋(－1)nrn＝∑(－1)krk(n－k)!k=0n证设Ai为第i个棋子布入禁区，其他棋子任意布的方案集，i=1,2,3,…,n。6.2有限制排列和棋盘多项式则所有棋子都不布入禁区的方案数为｜A1∩A2∩···∩An｜＝n！＋∑(－1)k∑｜∩Ai｜I∈￠(n,k)ni∈Ik=1而∑｜∩Ai｜正是k个棋子布入禁区，其他n-k个棋子任意布的方案数。由假设可知等于rk(n－k)！(注意：布入禁区的棋子也要遵守无对攻规则）.所以｜A1∩A2∩···∩An｜=n!+∑(－1)krk(n－k)!I∈￠(n,k)i∈Ik=1n6.2有限制排列和棋盘多项式上例方案数为4!－6(4－1)!＋11(4－2)!－7(4－3)!＋1(4－４)!＝4例１，２，３，４四位工人，A，B，C，D四项任务。条件如下：１不干B；２不干B、C；３不干C、D；４不干D。问有多少种可行方案？6.2有限制排列和棋盘多项式解由题意，可得如下棋盘：其中有影线的格子表示禁区。ABCD1234R()=1+6x+10x2+4x3方案数=4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=46.2有限制排列和棋盘多项式例错排问题错排问题对应的是n×n的棋盘的主对角线上的格子是禁区的布子问题。C=···R(C)=(1+x)n=∑()xk令rk=()nk=0nknk故R(C)中的xn:n!+∑(－1)k()(n－k)!=n!∑(－1)k－=Dnk=1nnk=0k!1kn6.2有限制排列和棋盘多项式例四对夫妇前来参加宴会,围圆桌而坐,男女相间,夫妇不相邻,问有多少种入坐方法数?解:设女士,,,,4321xxxx其丈夫依次为.,,,4321yyyy先让女士入坐,其方式是6种.女士入坐后再让男士入坐,下面计算男士入坐的方法数.123412344321yyyy43216.2有限制排列和棋盘多项式