組合數(shù)學(xué)-棋盤(pán)多項(xiàng)式和有限制條件的排列

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

2、子規(guī)定稱無(wú)對(duì)攻規(guī)則，即同一行（列）有且僅有一個(gè)棋子。 棋盤(pán)C可推廣為任意形狀，令rk(C)表示k個(gè)棋子布列棋盤(pán)C上的方案數(shù)，稱 為棋盤(pán)C的棋盤(pán)多項(xiàng)式，規(guī)定r0(C)=1，包括C=時(shí)。 如r1( )=1，r1( )=2，r1( )=2，r2( )=1 R( )=1+x， R( )=1+2x， R( )=1+2x+x23.4 棋盤(pán)排列加法2.3 棋盤(pán)多項(xiàng)式和有限制條件的排列概 念棋盤(pán)（子）多項(xiàng)式 設(shè)C(i)為C的某一指定格子所在行與列去掉后的所得棋盤(pán)，C(e)為C是僅去掉該格子后的所得棋盤(pán)。如 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 棋盤(pán)排列乘法2.3 棋盤(pán)多項(xiàng)式和有限制條件的排列概 念棋盤(pán)（子）多項(xiàng)式 設(shè)C由相互分離的C1、C2組成，即C1的任一格子所在的行和列中都沒(méi)有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ū)的排列概 念對(duì)于1,2,3,4的一個(gè)排列P=p1p2p3p4，規(guī)定p13，p21,4，p32,4，p42。這樣的排列對(duì)應(yīng)于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。1 2 3 4 p4p1p2p32.3 棋盤(pán)多項(xiàng)式和有限制條件的排列3.4 禁區(qū)排列定理8有禁區(qū)的排列定理 2.5有禁區(qū)的排列數(shù)為n!-r1(n-1)! +r2(n-2)!+(-1)nrn 。其中ri是有i個(gè)棋子布置到禁區(qū)部分的方案數(shù)。 證

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

6、C兩項(xiàng)任務(wù)，W不能做C,D工作，Y不能從事任務(wù)D。若要求每人從事各自力所能及的一項(xiàng)工作，試問(wèn)有多少種不同方案？ A B C DGLWY解：由題意，可得棋盤(pán)如右圖，其中有陰影的格子表示禁區(qū)。由上述可知R( )=1+6x+10 x2+4x3，即r1=6，r2=10，r3=4，故所求方案數(shù)為4!-63!+102!-4=4*2.3 棋盤(pán)多項(xiàng)式和有限制條件的排列3.4 禁區(qū)排列例2 有禁區(qū)的排列例 題例2、設(shè)右圖是nn棋盤(pán)，禁區(qū)都在對(duì)角線上，用n個(gè)棋子在上面布局。求如圖所示的有禁區(qū)的棋盤(pán)的布局方案數(shù)。n格n格解：設(shè)棋盤(pán)中有陰影的格子為禁區(qū)C。顯然這是一個(gè)錯(cuò)排。由上述可知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)，故所求方案數(shù)為Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)!+(-1)nC(n,n)注：這是錯(cuò)排公式的另一種推導(dǎo)方式。2.3 棋盤(pán)多項(xiàng)式和有限制條件的排列3.5 廣義容斥原理概念3.3 廣義容斥原理概 念 若將2.1中的例1所問(wèn)改為“單修一門(mén)數(shù)學(xué)的學(xué)生有多少？” “只修一門(mén)課的學(xué)生有多少？”“只修兩門(mén)課的學(xué)生有多少？”則相應(yīng)的答案表示如下： 設(shè)有與性質(zhì)r1,r2,rn相關(guān)的集合S的子集A1,A2,An，pk表示至少具有k種性質(zhì)的元素的元次，qk為恰有k種性質(zhì)的元素個(gè)數(shù)，有3.5 廣義容斥原理定理93

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

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

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

11、置上。設(shè)ai是坐在第i號(hào)位置上的男人，則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每列中都無(wú)相同元素。滿足這樣的限制的排列a1a2an稱為二重錯(cuò)排。設(shè)二重錯(cuò)排的個(gè)數(shù)為Un，原問(wèn)題所求的方案數(shù)就是Un(n-1)!。設(shè)Ai為ai=i,i-1,2in，A1為a1=n,1的排列a1a2an的集合，則|Ai|=2(n-1)!，因?yàn)锳i表示兩個(gè)位置集合，關(guān)鍵是計(jì)算k個(gè)Ai的交集的排列數(shù)?？紤](n,1)(1,2)(2,3)(n-1,n)這n對(duì)數(shù)的k 對(duì)中各取一數(shù)，且互不相同的取法的計(jì)數(shù)，這相當(dāng)于從n,1,1,2,2,3,3,4,n-1,n-1,n中取k個(gè)互不相鄰數(shù)的組合的計(jì)數(shù)，但首尾的n不能同時(shí)取。根據(jù)前面的不相鄰組合，其計(jì)數(shù)為C(2n-k+1,k)-C(2n-4-(k-2)+1,k-2)= C(2n-k,k)(2n)/(2n-k)，根據(jù)容斥原理，有第3章 小結(jié)本章小結(jié) 本章主要討論了容斥原理及其推廣定理的概念，及其在排列組合計(jì)數(shù)中的各種應(yīng)用，包括：有限元重集的排列、組合、圓排列，錯(cuò)排、多種有禁區(qū)排列等。 合理分類是計(jì)數(shù)的重要方法。在無(wú)法簡(jiǎn)單分類的情況下，要涉及有重復(fù)的