Microsoft Word - 第二章 排列 組合.doc

排列 組合 排列 (permutatio) 是集合中一群個體的有序選擇 ; 組合 (combiatio) 是集合中一群個體的無序選擇 在排列與組合中個體的選擇可允許重覆或不允許重覆 例加,a b c 三個字母中選出兩字母, 有 9 種字母可重複的排列 : aa, ab, ac, ba, bb, bc, ca, cb, cc 有 6 種字母不可重覆的排列 : ab, ac, ba, bc, ca, cb 有 6 種字母可重覆的組合 : aa, bb, cc, ab, ac, bc 有 3 種字母不可重覆的組合 : ab, ac, bc 個不同個體中選取 r 個元素不重覆的排列. 簡稱 r- 排列, 共有 P(, 種, 而 P(, = (-1) (-r+1) 因第一個位置的選擇有 種, 第二個位置的選擇有 -1 種,, 第 r 個位置的選擇有 -r+1 種, 根據乘法原理可得上式 又 P(, ) =.(-1) 3..1, 以! 表.(-1) 3..1, 定義 0!=1,! 讀做 階乘 ( factorial), 故! P(, =,P(, ) =! (! 個不同個體中選取 r 個且不可重覆的組合, 簡稱 r- 組合共有 C(, 種, 而 C(, = P(, P( r, =! r! (! 因 個不同個體中選取 r 個且不可重覆的排列有 P(, 種, 我們可先選 r 個不可重覆的組合, 有 C(, 種, 再將它們做排列, 有 r! 種, 故 一 加法律與乘法律 : P(, = C(, P(r, (1) 加法律 :#(A B C) = #(A) + #(B) + #(C), 當 A, B, C 互斥 () 乘法律 :#(A B C) = #(A) #(B) #(C) 1

例 1: 從 5 本 BASIC,4 本 FORTRAN,7 本 Pascal 中選一本書的方法數有多少種? 由於只選一本書, 所以選到一種書後便不會選到另一種書即不會同時發生, 利用加法原理知有 5 + 4 + 7 = 16 種 例 : 從 5 本 BASIC,4 本 FORTRAN,7 本 Pascal 中選二本不同語言的書方法數有多少種? (1) 若選到的二本, 一本是 BASIC, 一本是 FORTRAN, 利用乘法原理知選法有 5 4=0 種 () 若選到的二本, 一本是 BASIC, 一本是 Pascal 的選法有 5 7=35 種 (3) 若選到的二本, 一本是 FORTRAN, 一本是 Pascal 的選法有 4 7=8 種這三個事件不會同時發生, 利用加法原理總共的選法有 0+35+8=83 種 二 排列 : 方式說明公式 排列 在不可重複選取的情況下, 從 相異物中 取 r 件做排列的方法數 P (, =! ( -! 全相異物直線排列 相異物在 不同位置的直線排列數! 不全相異物直線排 列 重覆排列 共有 k 種之 件不全相異物, 第 i 種有 q i 個, 在 不同位置的直線排列數在可重複選取的情況下, 從 相異物中取 r 件做排列的方法數! q! q!...q 1 r k! 環狀排列 相異物在 不同位置的環狀排列數 (-1)! 珠串排列環狀排列 + 可翻轉 (-1)!/.1 全相異物直線排列 例 3: 試求 4 位數中, 每位數字都相異的有多少? 這問題等於將 10 個數字 0, 1,,..., 9 中的 4 個加以排列, 排列數共有 P(10, 4) = 5040 在這 5040 個 4 位數中, 有一些第一位數字是 0 的, 不能算在我們的答案內, 這種 13

情況有 9 8 7 = 504 因此, 我們的答案應該是 5040 504 = 4536 [ 另解 ] 第一位數字不能是 0, 故有 9 種選法, 第二位數字可從第一位數字以外的 9 個中任選一個, 方法有 9 個, 第三位數字有 8 種, 第四位數字有 7 種選法, 因此每一位數字都相異的 4 位數共有 9 9 8 7 = 4536 個 例 4: 4 個相異的英文字母後面再排 3 個相異的數字, 排法共有多少種? P(6, 4) P(10, 3) = 58,336,000. 不全相異物直線排列 例 5: 排列字母 TALLAHASSEE 的排列數有多少種? 11! Sol: = 831600 3!!!!1!1! 例 6: 證明 (k!) (k-1) 整除 (k!)!, 其中 k N [ 證明 ] 設有 k! 件物品, 其中共有 (k-1) 種, 每種各有 k 件, 則這 k! 件物品的排列數為 ( k! )! ( k! )! = 種 ( k 1 ) k! k! Lk! ( k! ) 由於總排列數必為整數, 所以 (k!) (k-1) 必整除 (k!)!.3 重覆排列 例 7: 在 5 天中, 排 3 門課的考試時間, 如果每天所考的科目不限制多少科, 那麼考試時間表的排法共有 5 3 = 15 例 8: 設 A 為一有限集, 基數為 r, 求 A 的子集的個數? 考慮將 A 中的 r 個元素放在兩個箱子中, 箱子編號為 1, 對應於每一種放置法, 就可以定義 A 的一個子集, 即放在箱子 1 中的元素屬於這子集, 放在箱子 中的元素不 屬於這子集 因為這種對應是 1 對 1 的對應, 且放置 r 個元素於兩個箱子的方法共有 r 種, 因此 A 的子集共有 r 個 例 9: 二元 r- 序列是指由 個數字所構成的 r 個項的數列 二元 r- 序列共有 r 種 在這 r 14

種二元 r- 序列中, 有多少種序列, 其中含有偶數個 0? ( 所給的 個數字是 0 和 1) 將這些二元 r- 序列配對, 使每一對的兩個序列只是第 r 個數字相異, 其餘都相同 則每一對序列中, 必有一個序列, 所含的 0 的個數為偶數個 因此共有 r-1 個二元 r- 序 列, 含有偶數值 0 例 10: 考慮五元 r- 序列,( 所給的 5 個數字是 0,1,,3,4), 其中包含偶數個 0 的有多少? 五元 r- 序列的個數共有 5 r 個 其中有 3 r 個這種序列, 只包含數字,3 和 4 這 3 r 個 當然都含有偶數個 0 其餘的 5 r -3 r 個序列, 再依照序列中所含的,3 和 4 的情形分類, 3 和 4 出現的位置都一樣的形成一類, 例如所有形如 3xx344xxxxx 的序列都屬於 同一類, 其中的每一 x 都可以是 0 或 1 則每一類中, 有一半的序列, 所含 0 的個數為 偶數 故 5 r r 1 r r 1 r r 個五元 r- 序列中, 含有偶數個 0 的序列有 3 ( 5 3 ) = ( 5 + 3 ).4 環狀排列 + 例 11: 主人夫婦與賓客四對夫婦共 10 人圍一圓桌, 依下述條件, 分別求其坐法 : (1) 任意圍坐 () 男女相間而坐 (3) 每對夫婦均相鄰而坐 (4) 男女相間且夫婦相鄰 (5) 主人夫婦相對而坐 (6) 每對夫婦相對而坐 (1) 10 人圍圓桌而坐, 坐法有 9!( 種 ) () 男女相間而坐,5 位男士先坐, 坐法有 4!; 對其中每一種坐法,5 位太太再坐於 五個間隔, 坐法有 5!, 故共有坐法 4! 5!=880( 種 ) (3) 5 位男士先坐, 坐法有 4!, 然後每一位太太可坐於先生的左鄰或右鄰故共有坐法 4! 5 =768( 種 ) (4) 5 位男士先坐, 坐法有 4!, 對其中每一種坐法 5 位太太的坐法只有 種 ( 太太們要 同時坐先生的右鄰或左鄰 ), 故共有坐法 4! =480( 種 ) 15

(5) 主人夫婦先坐有 1( 種 ), 其他 8 人再人坐有 8!( 相當於人坐到有編號之 8 個坐位 ), 故共有 8! 種 (6) 主人夫婦先坐有 1( 種 ), 再讓 4 對夫妻人坐有 4!, 而此 4 對夫婦可對調有 4 ( 種 ), 故共有 4! 4 ( 種 ).5 珠串排列 例 1: 珠串排列 (1) 紅 黃 綠 藍 黑 紫 白等 7 顆不同寶石串成一項圈有幾種串法? () 承上題其中紅 黃 藍三顆寶石必相鄰之串法有幾種? 將左邊之項圈沿虛線上下翻轉, 可得右邊之結果, 故雖然是 種不同之環狀排列, 其實表示同一項圈 例 13: 一顆紅寶石 二顆藍寶石 四顆黃寶石串成一項圈, 其串法有幾種? 3! (1) 對稱型 : 將藍 黃 黃填入 3 空格有 = 3種! () 不對稱型 : ( 7-1 )! 1 6 種 - 3 =! 4! 串法有 3+6 = 9 種 16

三 組合 : 方式說明公式 一般組合 1. 在不可重複選取的情況下, 從 相異物中取 r 件做組合的方法數. 個元素的集合 A 的子集合當中, 有幾個內含 r 個元素? 3. ( + x) 1 展開後, x r 項係數是多少? C (,r ) =! (-!r! C(, = C( 1, r 1) + C( 1, 二項式定理 ( 稱為 biomial coefficiet) 4. Pascal 三角形的第 列第 r 個值是多少? 5. 把 個紅色的球, 與 m- 個藍色的球排入 1 到 m 號共 m 個位置, 有多少種不同的排法? ( x + y) = k = 0 C(, k) x k y k C(,0)+C(,1)+C(,)+...+C(,-1)+C(,) = 多項式定理 重覆組合! 1 x x1 x... x!!...! ( 1 + x +... + xt ) = 1. 件相同物分到 r 個相異盒子 H(r,) = C(+r-1, ) 1 t t t. 由 r 類相異物, 可重覆選取 件 H(r,) = C(+r-1,) 3. x 1 +x +...+x r =, 非負整數解總數 H(r,) = C(+r-1,) 4. x 1 +x +...+x r =, 正整數解總數 H(r,- = C(-1, r-1) 3.1 一般組合 例 14: 五件不同的工作, 指派給四位員工, 每人都要有工作, 問有多少種指派的方式? 首先將 5 件工作分成 1 1 1, 四個人 A B C D 中, 有一個人做 件, 而其他三人各做 1 件 總方法數 = C(5,) 4! = 40 17

例 15: 設一個凸 10 邊形中, 任意三條對角線都不共點, 試問所有的對角線互相之間, 共分成多少個線段? 首先, 對角線的個數共有 C(10,)-10 = 45-10 = 35 其中 C(10,) 指從 10 個頂點中, 任取 點, 即可連成一線段, 這些線段中去掉 10 個邊, 即為對角線的個數 因為, 從 10 個頂點中, 任取 4 個, 都可產生一個對角線的交點, 如圖所示, 因此, 所有對角線的交點數共有 C(10,4)=10 因為每一對角線上, 如果有 k 個交點在其上, 就會被分成 k+1 個線段, 在 10 個交點中, 每一個交點都恰在兩條對角線上, 因此, 對角線間互相分成的線段共有 35+ 10 = 455 0 1 r = 例 16: 證明 ( C ) + ( C ) + ( C ) + K + ( C ) + K + ( C ) C [ 證 ] 由 件相異物品中選取 件, 可先將此 件相異物品分成各含 件物品的兩堆, 選取 件的方法可以由甲堆中選取 r 件, 再由乙堆中選取 -r 件, 其選法有 i= 0 C i C i = i= 0 ( C ) = C i 18

17: 由 1,,, 300 中選 3 個相異數字, 使其和為 3 的倍數的選法有多少種? 將 1,,...,300 分成三個集合 A 1 ={3k 1 k 100} 表 3 的倍數的集合 A ={3k+1 0 k 99} 表除以 3 餘數為 1 的集合 A 3 ={3k+ 0 k 99} 表除以 3 餘數為 的集合取 3 個數和為 3 的倍數的可能選法有下列 4 種情形 : (1) 3 個數都由 A 1 選出有 C(100, 3) 種 () 3 個數都由 A 選出有 C(100,3) 種 (3) 3 個數都由 A 3 選出有 C(100,3) 種 (4) 3 個數由 A 1, A, A 3 中各選一個有 C(100, 1) C(100, 1) C(100,1) 種利用加法原理知共有 3 C(100, 3)+ 100 100 100 例 18: 證明 C(, = C(-1, r-1) + C(-1, [ 證明 ] 若固定其中某一物品 X 可分成二種來討論 (1) 沒取到 X 時, 相當於在其他 -1 個物品取 r 個有 C(-1, 種 () 取到時, 相當於在其他 -1 個物品取 r-1 個有 C(-1, r-1) 種故由加法定理知 C(, = C(-1, r-1) + C(-1, 3. 二項式與多項式定理例 19: (1) 求 C(, 0) + C(, 1) + C(, ) + + C(, ) =? () 求 C(, 0) - C(, 1) + C(, ) - + (-1) C(, ) =? 例 0: 展開 (x+y+z) 7 後 19

(1) x y z 3 7! 的係數 = = 10 () xyz 5 7! 的係數 = = 4!!3! 1!1! 5! (3) x 3 z 4 7! 的係數 = = 35 3! 4! 3.3 重覆組合 例 1: 以下的問題答案皆為 H(, (1) r 個相同球放入 個相異箱子, 允許有空箱的方法數 () x 1 + x +...+ x = r 之非負整數解個數 (3) r 個 0,-1 個 1 的二元序列個數 [ 證明 ] (1) 個箱子可以用 -1 個欄杆圍起來, 例如 :000 00 0 000 表示 9 個球 5 個箱子, 第 1 到第 5 個箱子的球數分別為 3 1 0 3, 所以相當於 r 個 0,-1 個 的不 全相異排列, 方法數有 ( + r -1)! =C(+r-1, = H(, r! ( 1)! () 相對於 (1) 可視 x i 表示第 i 個箱子的球數,i =1,,, 因為允許有空箱, 所以 x i 0; 總共有 r 個球, 所以 x i + x + + x = r 所以與 (1) 的問題是等價的, 其方法數亦為 C(+r-1, = H(, (3) 將 (1) 中的 視為 1, 則與 (1) 的問題亦是等價的, 其方法數亦為 C(+r-1, = H(, 例 : x 1 + x + x 3 + x 4 = 1 中, 有幾組非負整數解? 有幾組正整數解? 有幾組整數解? 其中 x 1,x,x 3 4,x 4 0 解 : (1) H(4, 1) = C(15, 1) 0

例 3: 試問 r 個相同球放入 個相異箱子不允許有空箱的方法數? 例 4: 有 7 個朋友到速食店點餐, 速食店提供 4 種餐點 A,B,C,D, 問共有幾種點餐方式? 解 : 相當於 4 件相異物允許重複取 7 件組合 (=4,r=7) 若點的情形為 個 A 3 個 B 1 個 C 1 個 D, 則 AABBBCD 可標記為 xx xxx x x 同理, 若點的情形為 AAAACCC 可 標記為 xxxx xxx 每一種點法皆可對應至一種標記法, 反之一種標記法也會對應一種點法, 所以 只要算標記的方法有幾種即可 標記包含 7 個 x 3 個 的不全相異排列, 其方法數有 例 5: ( 7 + 3)! 10 4+ 7 1 + 1 = C 7 = C7 = C r r 7!3! 普通的 8 8 西洋棋盤上, 一個城堡棋子從最南端的角落方格, 走到最北端的角落方格, 每步只能向東或向北前進, 試問這城堡棋子所能走的不同路徑有多少種?( 如下圖所示, 即為其中的一路徑 ) 解 : 如果以 0 代表往東走一步, 以 1 代表往北走一步, 則從最南端的角落走到最北端的角落方格的路徑都是 7 個 1 和 7 個 0 所組成的二元 14- 序列, 亦即 7 個 0 和 7 個 1 的排列, 14! 故路徑數有 = 343 7! 7! 1

例 6: 接上題, 這些路徑中含有 4 次向東前進,3 次向北前進的路徑有多少?( 一次向東前進是指連續若干步的向東走, 一次向北前進的定義相同 ) 解 : 路徑中含有 4 次向東前進的數目等於將 7 個相同的球放進 4 個相異的箱子中, 每一 箱至少裝一個球的放法數, 首先每一箱都先放一個球, 然後再來分配剩下的 3 個球, 因為將 3 個相同的球, 放進 4 個相異的箱子, 每箱裝的球數不限, 放法共有 H(4, 3) = C(4+3-1,3) = 0 因此, 將 7 個相同的球, 放進 4 個相異的箱子, 每箱至少裝 1 個的放法共有 0 種 同樣 的方法, 可以求得路徑中, 含有 3 次向北前進的數目等於 H(3, 4) = C(3+4-1, 4) = 15 因此, 利用乘法律, 路徑中含有 4 次向東前進及 3 次向北前進的, 共有 0 15 = 300 例 7: 將 t+1 個相同的球放進 3 個相異的箱子中, 使任意兩個箱子所裝的球數比另一個 箱子多, 試求放法有多少? 解 : 如果不管問題中的限制條件, 那麼放法就有 H(3, t+1) 第一個箱子中所裝的球數, 比第二個箱子和第三個箱子所裝球數的和多的放 法, 可將 t+1 個球先放在第一個箱子, 剩下的 t 個球再任意放在全部的 3 個箱子, 因此 放置的方法共有 H(3, t) 第二個箱子中所裝的球數多於第一, 第三兩箱所裝的球數和放法亦有 H(3, t), 第 三個箱子中所裝的球數多於第一, 第二兩箱所裝的球數和的放法也有 H(3, t), 因此, 原問題的答案為 H(3, t+1) - 3H(3,t) = C(t+3,t+1)-3C(t+,t) =C(t+3,)-3C(t+,) = ( t + 3)( t + ) ( t + )( t + 1) ( t 1) 1 3 t = + 例 8: 投擲三粒骰子的方法數, 與從 6 個數字 1,, 3, 4, 5, 6 中重複選取 3 個數字等價, 因此投三粒骰子的方法數, 共有 H(6, 3) = C(6+3-1, 3) = C(8, 3) = 56 例 9: for i=1 to do

for j=1 to i do for k=1 to j do write(i+j-k) ed ed ed 問 write 執行多少次? Sol: 由題意知 1 k j i 可在 1 至 中選 3 段放置 i, j, k, 如下圖 1 k j i 每一種放置方式對應 write 執行 1 次本問題相當於 : 由 相異物中重複選取 3 數字 解答為 H 3 = C ( + 1)( = 6 + 3 + ) 四 排容定理 : 1. A U B U C = A + B + C - A I B - B I C - A I C + A I B I C. S = N,N(ai) = 在 S 中具性質 ai 之元素個數 ; N(ai') = 在 S 中不具性質 ai 之元素個數 ; s0=n;s1 =ΣN(ai);s=ΣN(aiaj);... e0= N(a1'a'...ar'); e1= N(a1a'...ar')+N(a1'a...ar')+N(a1'a'...a; ei= 在 S 中滿足 i 個性質之元素個數 e0= s0-s1+s-...(-1)rsr 例 30: 試求五元 r- 序列中, 至少含有 1 個 0,1 個 1 和 1 個 的序列有多少? 解 : 令 A 1 代表五元 r- 序列中, 不含數字 0 的序列集 ;A 代表五元 r- 序列中, 不含數字 1 的序列集 ;A 3 代表五元 r- 序列中, 不含數字 的序列集 則 3

A 1 A A3 因為 代表不含 0,1, 三個數字中一個以上的序列集 五 排容定理之重要題型 : (1) A = m B =, A 至 B 映成函數的個數 (m 異物置入 相異箱中且不允許空箱的方法數 ) = 所有函數的個數 -B 中一元素不在值域 +B 中二元素不在值域 -... k = ( 1) C(,k) ( k) m k = 0 () m 異物置入 相同箱中且不允許空箱的方法數 ( 稱為 Stirlig umber of the d kid): 1 k ( ) C(, k) ( k) m /! k = 0 S(,1)=1, S(,) = 1, S(,k)=kS(-1,k)+S(-1,k-1) (3) m 異物置入 相同箱中且不允許空箱的方法數 : S(m,1)+S(m,)+...+S(m,),m S(m,1)+S(m,)+...+S(m,m),m (4) 亂序公式 : D! [1 1 1 1 1 = + +... + ( ) ] 1!! 3!! (5) Euler's phi 函數 : 任意的自然數 可寫成 pe1pe... pe, 其中 = 1 p1,p,...,pt 為相異質數,e1,e,...,et 為自然數, t 1 φ()= 與 互質且 之自然數個數 = ( 1 ) i = 1 p i t t 4