组合数学幻灯片35..ppt

§3.5 一般有限制的排列 §3.3节中的错排问题是一种有限制的排列，即i不排在第i位的排列。更一般地若i不排在某些位的1，2，…,n的全排列，其排列个数又如何计算呢?此类问题的解法之一是利用所谓“棋子多项式”。 设n是一个正整数，一个n×n棋盘是指一个正方形被均分为n×n个小方格所成的“图形”。一个n×n棋盘去掉某些格后剩下部分也称它为一个棋盘。在给定棋盘C中放入k个无区别的棋子，要求每个棋子只能放一格，且各子不同行不同列，记不同的放法数为rk(C)，问rk(C)=?此问题称为棋子问题。 例如图3.3是四个棋子放入5×5棋盘的一种放法。 例1 设C1= , C2= , C3= 有 r1(C1) =r1( )=1,r2( )=0 r1(C2) =r1( )=2,r2( )=0 r1(C3) =r1( )=2,r2( )=1  定义3.1 给定棋盘C，令r0(C)=1,n为C的格子数，称 R(C)= 为棋盘C的棋子多项式。 例如由例1求得的结果，易知 R( )=1+x, R( )=1+2x, R( )=1+2x+x2 定理3.6 给定棋盘C，指定C中某格A。令Ci为C中删去A所在行与列所剩的棋盘，Ce为C中删去格A所剩的棋盘，则 R(C)=xR(Ci)+R(Ce) (3.11) 证明：将k个棋子放入棋盘C，其所有放法可按格A有棋子与没有棋子分为 两类。格A有棋子相当于在格A放一个棋子后，再将余下k-1个棋子放入Ci，故放法总数为rk-1(Ci)。格A没有棋子的放法数为rk(Ce)。由加法规则 rk(C)=rk-1(Ci)+rk(Ce) （此后略）。 ［例2］计算R( )与R( )。 解：R( )=xR( )+R( ） =xR( )+［xR( )+R( )］ =x(1+2x)+x(1+x)+(1+2x) =1+4x+3x2 R( )=xR( )+R( )  =xR( )+［xR( )+R( )］  =x(1+2x)+x(1+x)+(1+4x+3x2)  =1+6x+6x2 定义3.2 设C1和C2是两个棋盘，若C1的所有格都不与C2的所有格同行同列，则称两个棋盘是独立的。  例如， 中无阴影的棋盘与有阴影的棋盘是独立的。 中无阴影的棋盘与有阴影的棋盘不独立 定理3.7 若棋盘C可分解为两个独立的棋盘C1和C2，则 R(C)=R(C1)R(C2) (3.12) 考虑集合｛1,2,…,n｝的一个全排列且满足i(i=1,2,…,n)不排在某些已知位，求不同的排列方式数。此问题称为n元有禁位的排列问题，可通过棋子多项式求解。首先建立一个n×n棋盘C，再对每一个元i，若i不排在第j位，则将C中第i行第j列的小格画上阴影。对i的所有禁位都做如此处理。处理完毕后，称C中阴影部分为禁区棋盘。最后求出禁区棋盘的棋子多项式，再将相应数据代入下面定理3.7中的公式，即可求得排列数。 例如｛1,2,3,4｝的全排列，要求1不排在第二位；2不排在第三、四位；3不排在第一位；4不排在第二、三位。此问题对应的禁区棋盘如图3.4中阴影部分所示。 定理3.7 n元有禁位的排列数为 n!-r1(n-1)!+r2(n-2)!-…＋(-1)ｎrn 其中ri为将i个棋子放入禁区棋盘的方式数，i=1,2,…,n。 ［例4］ 四位小朋友x1,x2,x3,x4排成一行，但x1不愿排在第二位；x2不愿排在第三、四位；x3不愿排在第一位；x4不愿排在第二、三位，求不同的排法数。 解：该问题是一个4元有禁位的排列问题。该问题所对应的棋盘即为图3.4。设C为图3.4的禁区棋盘，利用式(3.11)可求得 R(C)=1+6x+11x2+7x3+x4 即r1=6,r2=11,r3=7,r4=1。由定理3.7， 可得排列数为 N=4!-r1·(4-1)!+r2·(4-2)!-r3(4-3)!+r4 =4!-6·3!+11·2!-7·1!+1=4. ［例5] 试解错排问题。 解：错排问题对应的棋盘如图3.5所示。 ［例6］四对夫妇前来参加宴会，围圆桌而坐，男女相间，夫妇不相邻，问有多少种入座方式数? 解：设女士x1,x2,x3,x4，其