二项式系数(54).ppt

二項式係數 5 4 在n個元素的集合中選出r 組合的方法數為 這個數也稱作二項式係數 binomialcoefficient 因為這些數將出現在二項展開式 如 a b n的係數中 1 二項式定理 TheBinomialTheorem 令x和y為變數 而n為非負整數 則證明 將使用組合證明方式 當j 0 1 2 n xn jyj項的係數可以由相乘的n項 x y 中 選取 n j 項的x和j項的y來相乘而得 所以其係數應可視為在n元素集合中 n j 組合的個數 即 得證 2 例 求出 x y 4的展開式 解 根據二項式定理 3 例 求出 x y 25展開式中x12y13的係數 解 根據二項式定理 係數為 4 例 求出 2x 3y 25展開式中x12y13的係數 解 由於 2x 3y 25相當於 2x 3y 25 根據二項式定理所以 x12y13的係數是當j 13時 5 系理 令n為非負整數 則證明 利用二項式定理當x 1 y 1時 得證 6 系理 令n為正整數 則證明 利用二項式定理當x 1 y 1時 注意 此系理可推導出 7 系理 令n為非負整數 則證明 利用二項式定理當x 1 y 2時 8 帕斯卡等式與三角形 帕斯卡等式 Pascal sIdentity 令n k為正整數 則證明 假設T為包含n 1個元素的集合 而a T S T a 我們注意到T有個包含k個元素的不同子集合 這類的子集合能分成兩類 一種是包含元素a與k 1個S中的元素 另一種是不包含a 而包含k個S中的元素 由於包含k 1個S中的元素之子集合個數為 而包含k個S中的元素之子集合個數為 所以 我們有 9 帕斯卡三角形 Pascal striangle 此三角形之第n列包含二項式係數C n k 帕斯卡等式 10 二項式係數的等式 凡德蒙德等式 Vandermonde sIdentity 令m n和r為非負整數 而且r不能大於m與n 則證明 假定在一個集合中有m個元素 而第二個集合中有n個元素 從這兩個集合中取出r個元素的方法有個 另外一種算法 假設這r個元素中 有k個取自第一個集合 而r k個來自第二個集合 其中0 k r 則利用乘法法則這樣選取的方法有 所以從兩集合中取出r個元素的方法有 11 系理 若n為非負整數 則證明 令m r n 代入凡德蒙德等式 得到最後的等式來自 12 定理 令n和r為非負整數 而且r n 則證明 根據前面章節中的範例 我們知道左式等於長度為n 1位元字串恰巧包含r 1個1的字串數目 在長度為n 1恰巧包含r 1個1的位元字串中 最後一個1一定落在第r 1 r 2 或n 1的位置上 若最後一個1在第j 1個位置時 這樣的字串數等於長度為j 恰巧有r個1的位元字串數 其中r j n 所以 等式成立 13 較複雜的排列與組合 5 5 重複排列重複組合不可區分物件的排列將物件分配至箱子中可區分物件與可區分的箱子不可區分物件與可區分之箱子不同的物件和相同的箱子相同的物件和相同的箱子 14 重複排列 例 利用英文字母能形成多少長度為r的字串 解 根據乘法法則 因為英文字母有26個 又因為可以重複使用 所以長度為r的字串共有26r 允許重複使用之n個元素的r 排列可能方法數如下面定理所示 定理 有n個元素之集合中 允許重複的r 排列共有nr種 證明 在r 排列中 每個位置都有n個選擇 根據乘法法則允許重複的r 排列共有nr種 15 重複組合 例 從一個包含蘋果 橘子和梨的碗中 挑選四個水果有幾種可能性 若不計挑選時的順序 而且每種水果在碗中的數目皆大於四 解 解決這個問題的一個方法是 列出所有的可能性如下 4個蘋果4個橘子4個梨3個蘋果 個橘子3個蘋果 1個梨3個橘子 1個蘋果3個橘子 1個梨3個梨 1個蘋果3個梨 1個橘子2個蘋果 2個橘子2個蘋果 2個梨2個橘子 2個梨2個蘋果 1個橘子 1個梨2個橘子 1個蘋果 1個梨2個梨 1個蘋果 1個橘子一共有15中可能性 16 定理 包含n個元素的集合中允許重複之r 組合的個數為C n r 1 r C n r 1 n 1 證明 每個在包含n個元素的集合中允許重複之r 組合 都能以n 1個隔板和r個記號的排列來表示 第i個隔板和第i 1個隔板間的記號個數 代表某元素選取的個數 譬如 在4個元素的集合中 挑選6個 當隔板與記號的排列方式為 表示第一個元素取兩個 第二個元素取一個 第三個元素不取 而第四個元素取三個 如此一來 要解決的問題變為在 n 1 r個物件的排列中 只有兩種不同物件 一種有n 1個 一種有r個 故 一共有C n r 1 r 種方式 由於 n r 1 r n 1 根據5 3節系理 C n r 1 r C n r 1 n 1 17 例 假設某餅乾店中有四種不同口味的餅乾 若不計挑選時的順序 選取六個餅乾有幾種方法 解 此問題等同於求出在4個元素所成集合中 允許重複的6 組合方式之個數 根據前定理 共有種不同的方式來挑選餅乾 18 例 方程式x1 x2 x3 11有多少組解 其中x1 x2和x3為非負整數 解 此問題等同於由3個元素 x1 x2 x3 的集合中 允許重複的選出11個元素出來組合 根據定理 共有組解 19 不可區分物件的排列 例 將單字SUCCESS之字母重新排列 將形成多少不同的字串 解 由於字串中有相同的字母 所以排列方式不會等於將七個元素排列 字串中有3個S 2個C 1個U和1個E 在考慮重排後的字串時 首先將三個位置分配給S共有C 7 3 種方法 從剩下的五個位置中 分配2個給C 有C 5 2 中方法 剩下兩個位置一個給U 有C 2 1 種方式 最後的位置留給E 有C 1 1 種方式 利用乘法法則 共有種 20 定理 若n個物件中 第 種相同的物件有n1個 第2種相同的物件有n2個 第k種相同的物件有nk個 則此n個物件的排列方式共有n n1 n2 nk 證明 將此n個物件排成一列 共有n個位置 首先挑選出n1個位置來放第1種物件 其方法數為C n n1 這個時候 只剩下n n1個位置可以放置新的物件 接下來 選出n2個位置來放第2種物件 有C n n1 n2 種方法 這個時候 只剩下n n1 n2個位置可以放置新的物件 繼續這樣的步驟 再根據乘法法則 再經過約分 總排列方法數有C n n1 C n n1 n2 C n n1 nk 1 nk n n1 n2 nk 21 將物件分配至箱子中 可區分物件與可區分的箱子例 將一副標準的52張撲克牌 分給四個人 一人五張 會有多少種不同的情形 解 我們將使用乘法法則來解決這個問題 首先 將5張牌分給第一個人的方法有C 52 5 種方法 將5張牌分給第二個人的方法有C 52 5 5 C 47 5 種方法 5張牌分給第三個人的方法有C 42 5 種方法 分給第四個人的方法有C 37 5 因此 總共的方法有 22 定理 將n個不同物件分配到k個不同的箱子 使得第i個箱子中有ni個物件 其中i 1 2 k 的方法數為 23 不可區分物件與可區分之箱子例 將10個相同的球放進八個不同的箱子中 有幾種可能的情況 解 此問題等同於自八個元素的集合中找出10 組合的方式 故 可能方式有C 8 10 1 10 C 17 10 17 10 7 19 448種 24 不同的物件和相同的箱子 例 有幾種方法能將四個員工分配到三個相同的辦公室 其中辦公室裡的人數可以是任何非負整數 解 我們將以列舉方法求出這個問題的解 將各個情況表列如下 四個人都放在同一個辦公室 以 A B C D 表示 三人在同一個辦公室 一個人在另一個辦公室的情況有 A B C D A B D C A C D B 和 B C D A 兩個人在一個辦公室 另外兩人在另一個辦公室的情況有 A B C D A C B D 和 A D B C 兩個人在同一個辦公室 另外兩人一人一間辦公室有 A B C D A C B D A D B C B C A D B D A C 和 C D A B 共有14中方法 由上面的表列中也能看出 將四個員工安排在三個相同的辦公室 而且沒有空辦公室的方法有六種 將四個員工安排在兩個相同的辦公室 而且沒有空辦公室的方法有七種 而將四個員工安排在一個的辦公室方法只有一種 25 相同的物件和相同的箱子 例 將同一本書的六份拷貝分配到四個完全相同的包裹中 有幾種不同的分法 其中每個包裹中可以有任何種數目的書本數 解 我們將列舉出所有的可能情況 包裹中可能有的書本數目為 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1其中4 1 1表示一個包裹中有4份拷貝 另兩份包裹中各有一份 而有個包裹是空的 根據上面表列的方式 我們得知將同一本書的六份拷貝分配到四個完全相同的包裹中 若每個包裹中可以有任何種數目的書本數 總共有九種方法 26 觀察將n個相同物件分配至k個相同箱子中 其實就是將n分成j個小於k的正整數 a1 a2 aj 其中a1 a2 aj使得a1 a2 aj n 目前並沒有明顯的公式來計算這種題目的答案 27 產生排列與組合 5 6 有時排列與組合的形態必須被製造出來 而不只是計數 考慮下面三個問題 第一個 假設有個推銷員必須訪問六個城市 哪種行程的安排能花最少的時間 有種最好的方式 是將6 720種可能的行程所需時間一一加總出來 然後在選出最短的時間 第二個問題 假定給一個包含六個正整數的集合 如果可能 找出其中相加等於100的一組正整數 一種找出這組集合的方式 是將所有26個子集合全都列出來 然後一一加總找出所有元素和為100的子集合 最後一個問題 假設一個實驗室中有95個成員 若想組成一個12人小組來執行一個特別的計畫 這個小組的人員必須擁有25項技能 每位成員可能擁有 項或多項技能 有種找出這個小組的方式 就是列出所有12個人員的子集合 一一檢驗是否滿足所需要的技能 上述範例說明了 有時求解問題時 必須將排列或組合製造出來 28 產生排列 我們將介紹一種根據字典排列 lexicographic ordictionary ordering 方式而產生的排列 在這種排列中稱排列a1a2 an大於排列b1b2 bn 或b1b2 bn排在a1a2 an之前 如果對某個k 1 k n a1 b1 a2 b2 ak 1 bk 1但是ak bk 換句話說 在兩種排列中 若第一次出現不相同數字的位置上 數字較大的排列大於數字較小的排列 例 在集合 1 2 3 4 5 的排列中 排列23415排在23514之前 因為第一次出現不相同數字的第三個位置4小於5 相同的道理 41532排在52143之前 29 例 依字典順序方式362541的下一個較大排列是什麼 只使用1 2 3 4 5 6六個數字 解 最後一對整數aj和aj 1滿足ajaj 2 an的是a3 2和a4 5 將5 4 1中大於2的最大整數 即4放到第3個位置 然後將2 5 按遞增方式排列得到125 最後得到排列364125即為所求 30 產生組合 對一個有限的集合 該如何產生出所有的組合方式 由於組合可視為一個子集合 我們能用 a1 a2 an 之子集合與長度為n之位元字串間的對應關係來說明 回顧此對應關係 當對應之位元字串的第k個位置等於1時 表示元素ak在此組合中 而位元字串的第k個位置等於0時 表示元素ak不在此組合中 同時 我們也知道一個長度為n的位元字串對應於一個介於0到2n 1的整數之二進位表示法 為產生所有n位二進位數字 由n個0的表示法00 00開始 持續找出下一個二進位表示法 直至得到n個1的表示法111 11為止 產生下一個二進位表示法的過程如下 在每個步驟中 從最右邊找出第一個不是1的位置 將這個位置的位元換成1 然後將其右邊的所有位元全部換成0 就能得到下一個較大的二進位表示法 31 例 在 a1 a2 a6 中 對應於子集合 a2 a5 a6 的位元字串為010011 例 找出1000100111的下一個位元字串 解 從右邊數來第一個不為1的位元在第4位 將其換為1 將其右邊的所有位元全部換成0 就能得到下一個較大的二進位表示法1000101000 32 產生r 組合的方法 給定一個產生集合 1 2 3 n 之r 組合的演算法 每一個r 組合都對應一個長度為r之遞增數列 a1a2 ar依字典順序之下一個較大數列可依下面程序而得 首先找出最後一個ai的位置 其中ai n r i 然後