遞迴數列

Transcription

1 - 排列與組合 目標 首先能理解 排列 的意涵, 並能應用 乘法原理 處理 從 個不同元素的集合取出 個 ( ) 來排列的總排列數, 進而能推算 不盡相異物 的排列數, 以及可重複的排列問題 再者, 能了解 組合 的意涵, 並能處理不可重複與可重複的組合問題, 以及不定方程式 x+ x + L + x = 的非負整數解的問題 定義. 階乘 :! 讀作 的階乘, 其意義為! = ( ) ( ) L. 排列數 ( 完全相異物的直線排列 ): 從 個相異物中, 取出 個排成一列 ( ), 稱為 中取 的排列, 其方! 法數為 P = = ( ) L ( + ) ( )! 註 : 要從 個元素的集合 { a, a, L, a} 中取出 個 ( ) 排成一列, 由乘法原理可知其方法數為從 開始 個連續遞減整數的乘積 ( ) L [ ( ) ], 而當 < 時,, 故 ( ) L ( + ) ( ) L! ( ) L [ ( )] = = ( ) L ( )! 當 = 時, 表示將集合 { a, a, L, a} 的 個元素全部取出排成一列, 其方法數為 ( ) L =! 為了方便, 我們規定 0! = ( 即想成取 個或 0 個 物品的方法數為 種, 也就是全取或不取的那一種方法 ), 則!!! = = 故從 個相異物中取出 個排成一列, 時的方法數 0! ( )!! 恆為 ( )!, 此數記為 P () 想法一 : 想成將位置固定, 把物品放置到位置上 () 想法二 : 想成將物品固定, 將位置編號給物品 3. 不完全相異物的直線排列數 ( 排列有先後順序之分, 但相同物之間則不分順序 ): 設有 個物件, 全部取出排成一列 若物件完全相異, 則排列數為! ; 若不盡相異, 且可分成 類, 每類的個數依序為,, L,, + + L+ =,! 則排列數為!! L!, 直排數即 重複數註 : 想成原來的方法當中, 每幾種變成一種的意思 8

2 4. 環狀排列 :! () 由 個相異物品圍成圓圈的排列數為 = ( )! () 由 個相異物品中取出 個排成一個圓圈, 只考慮相鄰關係, 稱環狀排 P ( ) L ( + ) 直排數列, 其排列數為 =, 即環排數 = 旋轉數 5. 項圈排列 : 由 個相異物品中取出 P 個串成一條項鍊, 其排列數為種 直排數註 : 即項排數 = 旋轉數 翻轉數. 正 邊形桌之排列數 : 由 個人中取出 P 個人坐入正 邊形桌, 其方法數有 長方形桌之排列數 : 由 個人中取出 P 個人坐入長方形桌, 其方法數有 7. 重複排列 : 從 個相異物中, 每次選取一個, 得重複選取, 選取 次並排成一列, 稱為 中取 的重複排列, 其方法數為 註 : 從 個元素的集合 A= { a, a, L, a } 中, 每次選取一個元素, 得重複選取, 並依次排成一列, 則選取 次的方法數,由乘法原理可知共有 A = A = () 想法一 : 將 個不同物件分給 個人 ( 每個人所得不限 ) 有 種分法 () 想法二 : 從 類不同物件 ( 每類物件至少 個 ) 中取 個排列 ( 可重複 選 ), 總排列數為 註 : 在判別題目時, 想成一對多的概念, 即多 的類型 8. 組合數 : 由 個相異物中, 取出 個為一組 ( 0 ), 稱為 中取 的組合, 其方法! 數為 = ( )!! 註 : () 設 個元素的集合 S = { a, a, L, a }, 我們將 S 中含 個元素之部分集 合的個數記為, 可知! = P 故 P! = =, = 0,,, L,! ( )!! () 可以想成 P =!, 也就是將排列想成先選出來之後再排列!! (3) 由 = = =, 可得 =, 其意義為 [ ( )]!( )! ( )!! 從 個相異物中,取出 個作一組時, 不取的 個也成一組, 所以 中 取 的組合數 與 中取 的組合數相同 9

3 9. 重複組合數 : 從 種相異物中, 選取 次, 可重複且不論次序, 稱為 中取 的重複組合, + 其方法數為 註 : 一般情形, 若有 種口味的冰淇淋, 要從其中選取 球 ( 口味可重複 ), 則可以 個冰淇淋, 個隔板排成一列, 每一個排列法代表一個選擇法, 故總 ( + )! ( + )! + + 共的選擇數有 = = =!( )!!( )! 0. 非負整數解 : () 個相同的東西分給 + + 個人, 任意分的方法數為 = + () 方程式 x + x + L+ x = 的非負整數解有 H = 組. 正整數解 : () 個相同的東西分給 個人, 每人至少一件的方法數為, 其中 () 方程式 x + x + L+ x = 的正整數解有 組. 重複組合數 : () 從 類相異物中, 可重複 ( 每類至少 個 ) 且不論次序, 稱為 中取 的 + 重複組合, 方法數為種, 其中 H = H + () 個相同的東西分給 個人, 任意分的方法數為 0

4 問題. 含 個元素的集合有多少個部分集合? 解答 : 設集合 A= { a, a, L, a}, 要作成 A 的一個部分集合, 可以就 A 中的每個元素選擇 取 不取, 由 a, a, L, a 依序選擇, 這是 中取 的重複排列, 故有 個方法, 即 個元素的集合有 個部分集合. 集合 S = {,,3,4,5} 中含 3 個元素的部分集合有幾個呢? 解答 : 5 我們知道從 S 中取出 3 個元素排成一列的方法數為 P 3, 另一方面設 S 中含 3 個元素的部分集合有 x 個, 而每個部分集合中的 3 個元素全部取出排成一列的方法數為 3!, 5 由乘法原理知 x 3! = P3, 5! 5 P3 (5 3)! 5! 5! 故 x = = = = = 0 3! 3! (5 3)!3!!3! P 3 即 5 個元素的集合 {,,3,4,5} 中含 3 個元素的部分集合有 =0 個 3! 3. 方程式 x + y + z + u = 0 之解, 滿足下列條件者各有多少組? () 正整數解 () 非負偶數解 (3) 非負整數且 x, y 3 解答 : () 原式化為 ( x ' + ) + ( y' + ) + ( z' + ) + ( u' + ) = 0, 其中 x', y', z', u' 為非負整數解即可, 此時 x ' + y' + z' + u' =, 其解有 = = 3 = 84 組 () 原式化為 x ' + y' + z' + u' = 0, 其中 x', y', z', u' 為非負整數解即可, 此時 x ' + y' + z' + u' = 5, 其解有 5 = 5 = 3 = 5 組解 (3) 原式化為 ( x ' + ) + ( y' + 3) + z + u = 0, 其中 x ', y', z, u 為非負整數解即可, 此時 x ' + y' + z + u = 5, 其解有 = = 5 組解 = 4. 試求以下各題各有幾組解? () 試求 x + y + z 0 的非負整數解共有幾組? () 若要求 x, y, z 3時, 則有幾組解? (3) 若要求 x, y 都為偶數時, 則有幾組解? (4) 若要求 x, y 都為奇數時, 則有幾組解? (5) 若要求 x, y, z 都為偶數時, 則有幾組解? 5. 將正整數 分拆成 個分部, 且各分部量都是正偶數的有序分拆有幾個? 解答 : 5

5 . 將 9 本不同的書籍, 就下列之情形去分, 有幾種分法? () 分給甲 4 本, 乙 3 本, 丙 本 () 等分給甲乙丙三人 (3) 分給 3 人, 其中二人各得 本, 另一人 5 本 (4) 分成 4,3, 三堆 (5) 分成,,5 三堆 () 等分成三堆 7. 將 5 支筆分給 8 個人, 依下列情形, 方法各有幾種? () 筆不同, 每人所得的筆無限制數量 ( 可能沒拿到 ) () 筆不同, 每人至多得一支 (3) 筆相同, 每人至多一支 (4) 筆相同, 每人所得的筆無限制數量 ( 可能沒拿到 ) (5) 筆相同, 每人至多一支 () 筆不同, 每人至多得一支 8. 個相同的玩具分給四個兒童, () 若每人均可兼得, 有多少種不同的給法 () 若每人至少得一件, 有多少種不同的給法 (3) 若為相異的玩具, 每人均可兼得, 有多少種不同的給法 (4) 若為相異的玩具且每人至少得一件, 有多少種不同的給法 9. 5 種不同的酒, 注入 3 個空杯子, 酒不可混合, 不得有空杯子, 求下列各注入法有幾種? () 杯子不同, 且各杯的酒亦不同 () 杯子不同, 且各杯的酒可相同 (3) 杯子相同, 且各杯的酒亦不同 (4) 杯子相同, 且各杯的酒可相同 0. () 試求滿足條件 x < y < z < u 0 的整數解個數? () 試求滿足條件 x y z u 0的整數解個數? (3) 試求滿足條件 x, y, z, u 0 的整數解個數? (4) 試求滿足條件 x < y z < u 0的整數解個數? (5) 試求滿足條件 x y < z u 0的整數解個數? () 試求滿足條件 x < y z u 0的整數解個數?. 把編號 ~ 7 的 7 個球放入甲 乙 丙三個籃子裡, 每個籃子至少放一個球, 有多少種方法? 解答 : 令 U 表 7 個球任意放入 3 個籃子的所有方法所成集合, 又 A, B, 依序表甲 乙 丙籃子中沒有球的方法, 則所求為 A B, 由笛摩根定律知 A B = ( A B ), 又由取捨原理知 A B = A + B + A B B A + A B (3 ) (3 ) 3(3 3) = + = = 38 7 故 A B = ( A B ) = U A B = 3 38 = = 80

6 討論. 分組組合 : 將 個人分成 組方法數之討論, 又有指定數字與不指定數字兩種情形 註 : () 連續的 相乘表示為有序的, 也就是有指定給誰的含意 () 本身為表示無序的 (3) P 可以表成為一連串的 相乘. 分堆組合 : 將 個人分成 堆方法數之討論 也就是看分組組合後, 再除以重複數 例如 : 利用組合及乘法原理討論下列方法數 將 8 個相異物品分給 4 個人, 不同個數及分法, 其方法數如下表 : 類別個數 (,,,) (5,,,) (3,,,) (3,3,,) 分組且不指定數字, 給甲乙丙丁四人 8 4 4! 4! 8 3 4! 5! 3! ! 3!!! 8 5 4! 33!! 分組且依序指定數字給甲乙丙丁四人 分堆不指定, 只分堆 8 4 4! ! ! !! 3

7 3. 重複組合 ( 任意選取 ): ( 想法一 ) 由 類相異物品中 ( 每類至少有 個 ), 取出 個為一組, 每類可重複選取, + + 方法數有 H = = 種 ( 想法二 ) 方程式的非負整數解 ( 有序分拆 ): 第 類物品取出 x 個, 每一類可以任取 ( 即 0 x, =,, L, ), 則滿足 元一次方程式 x + x + L+ x = + + 之非負整數解 ( x, x, L, 0 ) 個數, 有 H = = 種 x ( 想法三 ) 分球問題 : 個相同的球分給 個人, 任意分, 因為分給 個人需要 個隔板, 故先加入 個球, 則現在有 + 個球, 此時將隔板放置於球上, 共有 + 個位置可以選取, 要選取 個位置來放置隔板, 以便將球分成 個區域 ( 隔版間可以 0 個 ), + 有種方法 Ο Ο Ο Ο Ο 4. 重複組合 ( 每類至少一個 ): ( 想法一 ) 由 類相異物品中 ( 每類至少有 個 ), 取出 個為一組, 每類可重複選取且每類至少各取出 個, 方法數有 H 種 = ( 想法二 ) 方程式的正整數解 ( 有序分拆 ): 第 類物品取出 x 個, 每一類至少取一個 ( 即 x, =,, L, ), 則滿足 元一次方程式 x + x + L+ x =, x, L, x 之正整數解 ( x ) 個數, 有 H 種 註 : 可以先丟給每人一個, 就轉換成為非負整數解的問題 ( 想法三 ) 分球問題 : 個相同的球分給 個人, 每人至少一個, 因為分給 個人需要 個隔板, 此時共有 個空格可以放置隔版, 要選取 個位置, 以便將球分成 個區域 ( 隔版間至少 個 ), 有種方法 = Ο Ο Ο Ο Ο 4

8 定義. 旋轉數 : 假設底面不變時, 幾種視為同一種之意 ; 底面不變時, 原本直排時當不同的, 現在卻當相同之情形. 翻轉數 : 假設底面變化時, 幾種視為同一種之意 ; 底面翻了以後, 原本直排時當不同 的, 現在卻當相同之情形 註 : 可以歸類到旋轉的情形就不能歸類到翻轉的情形, 否則會重複計算 討論. 平面塗色問題 : 需分類討論某些區塊是否同色, 再依序討論相鄰區塊塗色法, 再把各類情形相加, 且相鄰較多區域的先塗. 立體塗色問題 : 直排數立體塗色方法數 = 旋轉數 翻轉數 P5 () 塗直四角錐方法數有種 ( 旋轉數 4, 翻轉數 ) 4 P5 () 塗角錐台方法數有種 ( 旋轉數 4, 翻轉數 ) 4 P3 (3) 塗圓柱方法數有種 ( 旋轉數, 翻轉數 ) P (4) 塗長方體方法數有種 ( 旋轉數 4, 翻轉數 ) 4 P4 (5) 塗正四面體方法數有種 ( 旋轉數 3, 翻轉數 4 ) 3 4 P () 塗正立方體方法數有種 ( 旋轉數 4, 翻轉數 ) 4 5

9 類型 排列組合的問題有幾種重要的類型 :. 數字排列問題 : 數字和問題 倍數問題. 數列排序問題 : 大於 小於 大於等於 小於等於 3. 函數對應問題 : 函數對應 一對一函數 映成函數 一對一且映成函數 遞增函數 4. 整數解問題 : 非負整數解 正整數解 有限制範圍的整數解 5. 子集合問題 : 二項式定理的應用. 道路問題 : 走捷徑 不回頭 有陷阱 每條道路恰走一次 每個頂點恰走一次 7. 幾何問題 : 交點數 平面分割數 直線數 三角形個數 正方形數 矩形數 8. 塗色問題 9. 一筆劃問題 總結. 基本上排列組合的問題, 依照物品及箱子的相同或相異性, 可以分成以下幾 類重要型態, 現在先假設有 件物品, 個箱子 : 類型 條件 方法數 排列 重複排列 組合 相異排成一列 相異物, 取出 個, 可重複取, 排成一列 且每箱至多放一件物品 重複組合 ( 非負整數解 ) 相同分給人, 可重複分 重複組合 ( 正整數解 ) P + H = H = = 相同分給人, 可重複分, 每人至少一件物品