《二项式系数sect54.ppt》由会员分享,可在线阅读,更多相关《二项式系数sect54.ppt(34页珍藏版)》请在三一文库上搜索。
1、二項式係數(5.4),在n個元素的集合中選出r-組合的方法數為 。 這個數也稱作二項式係數(binomial coefficient),因為這些數將出現在二項展開式,如(a + b)n的係數中。,1,二項式定理(The Binomial Theorem),令x和y為變數,而n為非負整數,則 證明:將使用組合證明方式。當j = 0, 1, 2, , n,xnjyj項的係數可以由相乘的n項(x + y)中,選取(nj)項的x和j項的y來相乘而得,所以其係數應可 視為在n元素集合中(nj)-組合的個數,即 ,得證。,2,例:求出(x + y)4的展開式。 解:,3,例:求出(x + y)25展開式中
2、x12y13的係數。 解:,4,例:求出(2x 3y)25展開式中x12y13的係數。 解:,5,系理:令n為非負整數。則 證明:,6,系理:令n為正整數。則 證明: 注意:此系理可推導出,7,系理:令n為非負整數。則 證明:,8,帕斯卡等式與三角形,帕斯卡等式(Pascals Identity) 令n k為正整數,則 證明:假設T為包含n+1個元素的集合,而aT,S = Ta。我們注意到T有 個包含k個元素的不同子集合。這類的子集合能分成兩類:一種是包含元素a與k1個S中的元素;另一種是不包含a,而包含k個S中的元素。由於包含k 1個S中的元素之子集合個數為 ,而包含k個S中的元素之子集合個
3、數為 。所以,我們有,9,帕斯卡三角形(Pascals triangle),10,二項式係數的等式,凡德蒙德等式(Vandermondes Identity) 令m、n和r為非負整數,而且r不能大於m與n。則 證明:假定在一個集合中有m個元素,而第二個集合中有n個元素。從這兩個集合中取出r個元素的方法有 個。另外一種算法,假設這r個元素中,有k個取自第一個集合,而r k個來自第二個集合,其中0 k r。則利用乘法法則這樣選取的方法有 。所以從兩集合中取出r個元素的方 法有 。,11,系理:若n為非負整數。則 證明:,12,定理:令n和r為非負整數,而且r n。則 證明:根據5.3節中的範例,我
4、們知道左式等於長度為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的字串? 解: 允許重複使用之n個
5、元素的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
6、個橘子;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個,一
7、種有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,例: 假設某餅乾店中有四種不同口味的餅乾。若不計挑選時的順序,選取六個餅乾有幾種方法? 解:,18,例:方程式x1 + x2 + x3 = 11有多少組解?其中x1,x2和x3為非負整數。 解:,19,不可區分物件的排列,例 將單字SUCCESS之字母重新排列,將形成多少不同的字串? 解:,20,定理:若n個物件中,第種相同的物件有n1個;第2種相同的物件有n2個;第k種相同的物件有nk個。則此n個物件的排列方
8、式共有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(nn1, n2)C(nn1nk1, nk) = n!/n1!n2!nk!,21,將物件分配至箱子中,可區分物件與可區分的箱子 例:將一副標準的52張撲克牌,分給四個人,一人五張,會有多少種不同的情形? 解:
9、,22,定理:將n個不同物件分配到k個不同的箱子,使得第i個箱子中有ni個物件,其中i = 1,2,k,的方法數為,23,不可區分物件與可區分之箱子 例:將10個相同的球放進八個不同的箱子中,有幾種可能的情況? 解:,24,不同的物件和相同的箱子,例: 有幾種方法能將四個員工分配到三個相同的辦公室?其中辦公室裡的人數可以是任何非負整數。 解:我們將以列舉方法求出這個問題的解。將各個情況表列如下: 四個人都放在同一個辦公室,以A, B, C, D表示。三人在同一個辦公室,一個人在另一個辦公室的情況有A, B, C, D,A, B, D, C,A, C, D, B和B, C, D, A。兩個人在一
10、個辦公室,另外兩人在另一個辦公室的情況有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,相同的物件和相同的箱子,例:將同一本書的六份拷貝分配到四個完全相同的包裹中,有幾種不同的分法?
11、其中每個包裹中可以有任何種數目的書本數。 解:,26,觀察將n個相同物件分配至k個相同箱子中,其實就是將n分成j個小於k的正整數,a1, a2, , aj,其中a1 a2 aj使得a1 + a2 + + aj = n。目前並沒有明顯的公式來計算這種題目的答案。,27,產生排列與組合(5.6),有時排列與組合的形態必須被製造出來,而不只是計數。 考慮下面三個問題。第一個,假設有個推銷員必須訪問六個城市。哪種行程的安排能花最少的時間?有種最好的方式,是將6! = 720種可能的行程所需時間一一加總出來,然後在選出最短的時間。 第二個問題,假定給一個包含六個正整數的集合,如果可能,找出其中相加等於1
12、00的一組正整數。一種找出這組集合的方式,是將所有26種子集合全都列出來,然後一一加總找出所有元素和為100的子集合。 最後一個問題,假設一個實驗室中有95個成員。若想組成一個12人小組來執行一個特別的計畫。這個小組的人員必須擁有25項技能。(每位成員可能擁有項或多項技能。)有種找出這個小組的方式,就是列出所有12個人員的子集合,一一檢驗是否滿足所需要的技能。上述範例說明了,有時求解問題時,必須將排列或組合製造出來。,28,產生排列,我們將介紹一種根據字典排列(lexicographic (or dictionary) ordering)方式而產生的排列。在這種排列中稱排列a1a2an大於排列
13、b1b2bn(或b1b2bn排在a1a2an之前),如果對某個k,1 k n, a1 = b1,a2 = b2,ak1 = bk1但是ak bk。換句話說,在兩種排列中,若第一次出現不相同數字的位置上,數字較大的排列大於數字較小的排列。 例:在集合1, 2, 3, 4, 5的排列中,排列23415排在23514之前。因為第一次出現不相同數字的第三個位置4小於5。相同的道理,41532排在52143之前。,29,例: 依字典順序方式362541的下一個較大排列是什麼?(只使用1, 2, 3, 4, 5, 6六個數字) 解:,30,產生組合,對一個有限的集合,該如何產生出所有的組合方式?因為組合只
14、不過是個子集合,我們能用a1, a2, , an之子集合與長度為n之位元字串間的對應關係來說明。 回顧此對應關係,當對應之位元字串的第k個位置等於1時,表示元素ak在此組合中;而位元字串的第k個位置等於0時,表示元素ak不在此組合中。同時,我們也知道一個長度為n的位元字串對應於一個介於0到2n 1的整數之二進位表示法。 為產生所有n位二進位數字,由n個0的表示法0000開始,持續找出下一個二進位表示法,直至得到n個1的表示法11111為止。產生下一個二進位表示法的過程如下:在每個步驟中,從最右邊找出第一個不是1的位置,將這個位置的位元換成1,然後將其右邊的所有位元全部換成0,就能得到下一個較大
15、的二進位表示法。,31,例:找出10 0010 0111的下一個位元字串。 解:,32,產生r-組合的演算法,給定一個產生集合1, 2, 3, , n之r-組合的演算法。每一個r-組合都對應一個長度為r之遞增數列。 a1a2ar依字典順序之下一個較大數列可依下面程序而得: 首先找出最後一個ai的位置,其中 ai n r + i。然後,以ai + 1替換ai,當j = i + 1, i + 2, , r時,以ai + j i + 1替換aj。如此一來便能得到下一個較大之r-組合。,33,例:在集合1, 2, 3, 4, 5, 6中,找出1, 2, 5, 6的下一個4-組合。 解:已知n = 6,r = 4,a1 = 1,a2 = 2,a3 = 5和 a4 = 6。 最後一個ai,其中ai n r + i,是a2 = 2。以3替換a2 = 2,而 a3 = 2 +3 2 +1 = 4, a4 = 2 + 4 2 +1 = 5。 得到下一個較大的4-組合為1, 3, 4, 5。,34,
链接地址:https://www.31doc.com/p-2572022.html