組合數學-棋盤多項式和有限制條件的排列

1、3.4 禁區(qū)排列概念有禁區(qū)的排列概 念對于1,2,3,4的一個排列P=p1p2p3p4，規(guī)定p13，p21,4，p32,4，p42。這樣的排列對應于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。1 2 3 4 p4p1p2p32.3 棋盤多項式和有限制條件的排列2.3 棋盤多項式和有限制排列1棋盤多項式 n個不同元素的一個全排列可看做n個相同的棋子在nn的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子xxxxx 如圖所示的布局對應于排列41352。3.4 棋盤排列概念2.3 棋盤多項式和有限制條件的排列概 念棋盤（子）多項式 n個元素的排列可看作n個棋子（車）在nn棋盤C上的一種布局，布

2、子規(guī)定稱無對攻規(guī)則，即同一行（列）有且僅有一個棋子。 棋盤C可推廣為任意形狀，令rk(C)表示k個棋子布列棋盤C上的方案數，稱 為棋盤C的棋盤多項式，規(guī)定r0(C)=1，包括C=時。 如r1( )=1，r1( )=2，r1( )=2，r2( )=1 R( )=1+x， R( )=1+2x， R( )=1+2x+x23.4 棋盤排列加法2.3 棋盤多項式和有限制條件的排列概 念棋盤（子）多項式 設C(i)為C的某一指定格子所在行與列去掉后的所得棋盤，C(e)為C是僅去掉該格子后的所得棋盤。如 C： C(i)： C(e)： 顯然有rk(C)=rk-1(C(i)+rk(C(e)，R(C)=xR(C(

3、i)+R(C(e)。 如R( )=1+x， R( )=xR( )+R( )=x+(1+x)=1+2x， R( )= xR( )+R( )=x(1+x)+(1+x)=1+2x+x2 *3.4 棋盤排列乘法2.3 棋盤多項式和有限制條件的排列概 念棋盤（子）多項式 設C由相互分離的C1、C2組成，即C1的任一格子所在的行和列中都沒有C2的格。有：R(C)=R(C1) R(C2)。如R( )=R( )R( )=(1+x)(1+x)=1+2x+x2 R( )=xR()+R( )=x+(1+2x+x2)=1+3x+x2R( )=xR( )+R( )=x(1+2x)+(1+3x+x2)=1+4x+3x2

4、R( )=xR( )+R( )= xR( )+xR( )+R( ) =x(1+4x+3x2)+x(1+3x+x2)+(1+4x+3x2 )=1+6x+10 x2+4x3*3.4 禁區(qū)排列概念有禁區(qū)的排列概 念對于1,2,3,4的一個排列P=p1p2p3p4，規(guī)定p13，p21,4，p32,4，p42。這樣的排列對應于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。1 2 3 4 p4p1p2p32.3 棋盤多項式和有限制條件的排列3.4 禁區(qū)排列定理8有禁區(qū)的排列定理 2.5有禁區(qū)的排列數為n!-r1(n-1)! +r2(n-2)!+(-1)nrn 。其中ri是有i個棋子布置到禁區(qū)部分的方案數。 證

5、明：設S為n個棋子布入nn棋盤的所有排列的集合，Ai為第i個棋子布入禁區(qū)，其他棋子任意布的方案集，i=1,2,3,n。根據題意有|S|=n!。一個棋子落入禁區(qū)的方案數為r1，剩下的n-1棋子任意排列，故至少一個棋子落入禁區(qū)的方案數為r1(n-1)!。同理，兩個棋子落入禁區(qū)的方案數為r2，剩下的n-2棋子任意排列，故至少兩個棋子落入禁區(qū)的方案數為r2(n-2)!，以此類推。 根據容斥原理，無一棋子落入禁區(qū)的方案數為2.3 棋盤多項式和有限制條件的排列3.4 禁區(qū)排列例1 3.5.2 有禁區(qū)的排列例 題例1、有G,L,W,Y四位工作人員，A,B,C,D為四項任務，但G不能從事任務B，L不能從事B,

6、C兩項任務，W不能做C,D工作，Y不能從事任務D。若要求每人從事各自力所能及的一項工作，試問有多少種不同方案？ A B C DGLWY解：由題意，可得棋盤如右圖，其中有陰影的格子表示禁區(qū)。由上述可知R( )=1+6x+10 x2+4x3，即r1=6，r2=10，r3=4，故所求方案數為4!-63!+102!-4=4*2.3 棋盤多項式和有限制條件的排列3.4 禁區(qū)排列例2 有禁區(qū)的排列例 題例2、設右圖是nn棋盤，禁區(qū)都在對角線上，用n個棋子在上面布局。求如圖所示的有禁區(qū)的棋盤的布局方案數。n格n格解：設棋盤中有陰影的格子為禁區(qū)C。顯然這是一個錯排。由上述可知R(C)=R( )n=(1+x)n

7、=1+C(n,1)x+C(n,2)x2+C(n,n)xn，即ri=C(n,i)，故所求方案數為Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)!+(-1)nC(n,n)注：這是錯排公式的另一種推導方式。2.3 棋盤多項式和有限制條件的排列3.5 廣義容斥原理概念3.3 廣義容斥原理概 念 若將2.1中的例1所問改為“單修一門數學的學生有多少？” “只修一門課的學生有多少？”“只修兩門課的學生有多少？”則相應的答案表示如下： 設有與性質r1,r2,rn相關的集合S的子集A1,A2,An，pk表示至少具有k種性質的元素的元次，qk為恰有k種性質的元素個數，有3.5 廣義容斥原理定理93

8、.3 廣義容斥原理定理 3.9注：q0即通用的容斥原理 。證明：可以利用數學歸納法證明?；蛴媒M合分析方法如下：為證明等式成立，只需證明等式右端恰好具有k個性質ri (i=1,2,n)的元素被計算的次數凈值為1，而少于或多于k個性質的元素被計算的次數凈值為0即可?？紤]S中一個恰好具有k個性質的元素x，則其對pk的某一項的貢獻為1，而對pk+1,pk+2,pn的貢獻都是0。若某一元素具有的性質少于k種，則其對pk,pk+1,pn的貢獻都是0。若恰有k+j種性質，則其對pk的貢獻是C(k+j,j)，對pk+i的貢獻是C(k+j,k+i)，其中 (j=1,2,n-k; i=1,2,j) 。而即恰有k+

9、j種性質，對pk, pk+1, pn的貢獻都是0。定理得證。3.5 廣義容斥原理例13.3 廣義容斥原理例 題例1、某學校有12位教師，已知教數學課的教師有8位，教物理的教師有6位，教化學的教師有5位，其中有5位既教數學又教物理，有4位兼教數學和化學，兼教物理和化學的有3位；有3位教師教三門課，試問教數、理、化以外的課的教師有幾位？只教一門課的教師有幾位？正好教兩門課的教師有幾位？解：設全體教師集合為S，令教數學的教師屬于A1，教物理的屬于A2，教化學的屬于A3。則p0=12，p1=|A1|+|A2|+|A3|=8+6+5=19，p2=|A1A2|+|A1A3|+|A2A3|=5+4+3=12

10、，p3=|A1A2A3|=3。故教其他課的老師數為：q0=p0-p1+p2-p3=12-19+12-3=2恰好教一門的教師數為：q1=p1-2p2+3p3=4恰好教兩門的老師數為：q2=p2-3p3=33.5 廣義容斥原理例23.6 廣義容斥原理例 題例2、（n 對夫妻圍坐問題二重錯排）設 n 對夫妻圍圈而坐，男女相間，每個男人都不和他的妻子相鄰，有多少種可能的方案？解：不妨令n個女人先圍成一圈，方案數為(n-1)!。對任一這種給定方案，順時針給每個女人編號1,2,n。設第i號女人順時針與下一個女人之間的位置為第i號位置，第i號女人的丈夫的編號也為第i號，1in。讓n個男人坐到上述編號的n個位

11、置上。設ai是坐在第i號位置上的男人，則aii,i-1,2in，a1n,1。這樣的限制也即要求在下面3行n列的排列中 a1 a2 a3 an-1 an1 2 3 n-1 n n 1 2 n-2 n-1每列中都無相同元素。滿足這樣的限制的排列a1a2an稱為二重錯排。設二重錯排的個數為Un，原問題所求的方案數就是Un(n-1)!。設Ai為ai=i,i-1,2in，A1為a1=n,1的排列a1a2an的集合，則|Ai|=2(n-1)!，因為Ai表示兩個位置集合，關鍵是計算k個Ai的交集的排列數?？紤](n,1)(1,2)(2,3)(n-1,n)這n對數的k 對中各取一數，且互不相同的取法的計數，這相當于從n,1,1,2,2,3,3,4,n-1,n-1,n中取k個互不相鄰數的組合的計數，但首尾的n不能同時取。根據前面的不相鄰組合，其計數為C(2n-k+1,k)-C(2n-4-(k-2)+1,k-2)= C(2n-k,k)(2n)/(2n-k)，根據容斥原理，有第3章 小結本章小結 本章主要討論了容斥原理及其推廣定理的概念，及其在排列組合計數中的各種應用，包括：有限元重集的排列、組合、圓排列，錯排、多種有禁區(qū)排列等。 合理分類是計數的重要方法。在無法簡單分類的情況下，要涉及有重復的