第六章容斥原理及應(yīng)用64帶有禁止位置的排列(編輯修改稿)
2025-08-28 13:19 本頁面
【文章內(nèi)容簡介】 F2 3 4 三 四 20 兩個車放置的情況可以都在 F F2中也可以在 F1F2各一個中。如果在都 F1中，不攻擊的位置只有一種，如果在都 F2中；不攻擊的位置有兩種；如果分別在 F F2中 ,不攻擊的位置有 3 4種 所以 r2 = 1 + 2 + 3 4 = 15 F2 3 4 三 四 F1 1 2 一 二 21 三個車放置的情況只能分別在 F F2中，在 F F2同一個中必然會互相攻擊；如果兩個在 F1中，一個在 F2中，有 1 4個不攻擊的位置；如果一個在 F1中，兩個在 F2中，有 3 2個不攻擊的位置。 所以 r3 = 1 4 + 3 2 = 10 四個車只能各放兩個，有 1 2個不攻擊的位置 所以 r4 = 1 2 = 2 22 顯然 r5 = r6 = 0 故將 6個 非攻擊 型車放到 6行 6列棋盤中使得沒有車占據(jù)禁止擺放位置的方法數(shù)等于： 6! － 7 5! + 15 4! － 10 3! + 2 2! =226 通過例題我們看出 ， 運用定理 ri , 比直接將 n個 非攻擊 型車放到禁放位置的 n行n列棋盤上的方法數(shù)更容易 ， 但 ri的求法與禁止位置數(shù)量有關(guān) ， 禁止位置數(shù)太多時求 ri就困難 。 23 例：討論對于排列 P=P1 P2 P3 P4，規(guī)定 P1≠３， P２ ≠１、４， P３ ≠４， P4≠2。 解：這樣的排列對應(yīng)于有禁區(qū)的放車。如下圖 有影線的格子表示禁區(qū)。將棋盤按紅線分成兩份 1 2 3 4 P1 P2 P3 P4 占一個禁放位置時： r1 =6， 占兩個禁放位置時可分為左 占 2個，右占 2個和各占 1個 r2=2+2+3+4=11 24 占三個禁放位置時必須分為左 2個右 1個或者左 1 個右 2個； 2個在同一側(cè)時還要避開互相攻擊（同行或者同列的情況） r3=(1+2)+(2+2)=7 ； 占四個禁放位置時必須分為左 2個右 2個， r4=1 這樣上例題的排列方案數(shù)為： n!－ r1(n－ 1)!+r2(n－ 2)!－ … . +…..+( 1)nrn =4!－ 6(4－ 1)!＋ 11(4－ 2)!－ 7(4－ 3)! ＋ 1(4－４ )! ＝ 4 25 例 :１ ,２ ,３ ,４四位工人 , 還有 A,B, C,D四項任務(wù)。 條件如下： １ 不干 B。 ２不干 B、 C。 ３不干 C、 D。 ４不干 D。 問有多少種可行方案？ 解 由題意，可得如左棋盤： 其中有影線的格子表示 禁區(qū)。 r1 =6， r2=1+1+3 2+1 2=10 A B C D 1 2 3 4 26 r3=(1 2)+(2 1)=4 ； r4= 0 故方案數(shù)為： n!－ r1(n－ 1)!+r2(n－ 2)!－ …..+( 1)nrn =4!－ 6(4－ 1)!+10(4－ 2)!－ 4(4－ 3)! +0(4－ 4)!=4 “錯位排列”和“帶有禁止位置的排列”這兩節(jié)中，我們對絕對禁止位置的排列進行了計算，下面我們將考慮存在某些 相對 禁止位置計數(shù)問題。 27 另外的禁排位置問題 問題引入：某班 8個男生每天跑步，他們排成一豎行，除第一個領(lǐng)跑的男生外，每一個男生前面都有另一個男生，為了不讓他們總看見前面的是同一個人，第二天要交換位置，使得前面的人與前一天的不同。他們有多少交換位置的方法？ 我們對 8個男生進行編號，第一天的序列是： 1 2 3…8 ，其中第一個是 1號，最后一個是 8號。 28 那么確定對集合 {1,2,3,…,8} 的 8排列，使得每個 排列中不要出現(xiàn)： 12, 23, …78 的模式。 例如： 31542876 就是允許出現(xiàn)的一個排列，而84312657則不是，其中的 12還是前面的次序。 對于每個正整數(shù) n，令 Qn表示集合 {1,2,3,…, n}中沒有 12, 23, … ,( n1 )n 模式的排列的個數(shù)。利用容斥原理求的 Qn值。 當 n = 1 時， 1 就是一個允許的排列。 29 當 n = 2 時， 21 就是一個允許的排列。 當 n = 3 時， 213 321 132 就是三個允許的排列。 當 n = 4 時，允許的排列如下：
試題試卷相關(guān)推薦
鄂ICP備17016276號-1