二项式系数sect54课件

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展開式中x12y13的係數。

2、解:4系理:令n為非負整數。則證明:6系理:令n為正整數。則證明:注意:此系理可推導出7帕斯卡等式與三角形 帕斯卡等式(Pascals Identity) 令n k為正整數，則 證明:假設T為包含n+1個元素的集合，而aT，S = Ta。我們注意到T有 個包含k個元素的不同子集合。這類的子集合能分成兩類：一種是包含元素a與k1個S中的元素；另一種是不包含a，而包含k個S中的元素。由於包含k 1個S中的元素之子集合個數為 ，而包含k個S中的元素之子集合個數為 。所以，我們有 9帕斯卡三角形(Pascals triangle) 10二項式係數的等式 凡德蒙德等式(Vandermondes Iden

3、tity) 令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節中的範例，我們知道左式等於長度為n + 1位元字串恰巧包含r + 1個1的字串數目。在長度為n + 1恰巧包含r + 1個1的位元字串中，最後一個1一定落在第r + 1、

4、r + 2、或n + 1的位置上。若最後一個1在第j + 1個位置時，這樣的字串數等於長度為j，恰巧有r個1的位元字串數 ，其中 r j n。所以，等式成立。 13較複雜的排列與組合(5.5)重複排列重複組合不可區分物件的排列將物件分配至箱子中可區分物件與可區分的箱子不可區分物件與可區分之箱子不同的物件和相同的箱子相同的物件和相同的箱子14重複組合 例： 從一個包含蘋果、橘子和梨的碗中，挑選四個水果有幾種可能性？若不計挑選時的順序，而且每種水果在碗中的數目皆大於四。解：解決這個問題的一個方法是，列出所有的可能性如下：4個蘋果4個橘子4個梨3個蘋果；個橘子3個蘋果；1個梨3個橘子；1個蘋果3個橘

5、子；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個。當隔板與記號的排列方式為表示第一個元素取兩個；第二個元素取一個；第三個元素不取，而第四個元

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例：方程式x1 + x2 + x3 = 11有多少組解？其中x1，x2和x3為非負整數。解：19不可區分物件的排列 例 將單字SUCCESS之字母重新排列，將形成多少不同的字串？解：20定理：若n個物件中，第種相同的物件有n1個；第2種相同的物件有n2個；第k種相同的物件有nk個。則此n個物件的排列方式共

7、有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張撲克牌，分給四個人，一人五張，會有多少種不同的情形？解：22定理：將n

8、個不同物件分配到k個不同的箱子，使得第i個箱子中有ni個物件，其中i = 1,2,k，的方法數為 23不可區分物件與可區分之箱子 例：將10個相同的球放進八個不同的箱子中，有幾種可能的情況？解：24相同的物件和相同的箱子 例：將同一本書的六份拷貝分配到四個完全相同的包裹中，有幾種不同的分法？其中每個包裹中可以有任何種數目的書本數。解：26觀察將n個相同物件分配至k個相同箱子中，其實就是將n分成j個小於k的正整數，a1, a2, , aj，其中a1 a2 aj使得a1 + a2 + + aj = n。目前並沒有明顯的公式來計算這種題目的答案。 27產生排列 我們將介紹一種根據字典排列(lexic

9、ographic (or dictionary) ordering)方式而產生的排列。在這種排列中稱排列a1a2an大於排列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

10、, 2, 3, 4, 5, 6六個數字）解：30產生組合 對一個有限的集合，該如何產生出所有的組合方式？因為組合只不過是個子集合，我們能用a1, a2, , an之子集合與長度為n之位元字串間的對應關係來說明。回顧此對應關係，當對應之位元字串的第k個位置等於1時，表示元素ak在此組合中；而位元字串的第k個位置等於0時，表示元素ak不在此組合中。同時，我們也知道一個長度為n的位元字串對應於一個介於0到2n 1的整數之二進位表示法。為產生所有n位二進位數字，由n個0的表示法0000開始，持續找出下一個二進位表示法，直至得到n個1的表示法11111為止。產生下一個二進位表示法的過程如下：在每個步驟中

11、，從最右邊找出第一個不是1的位置，將這個位置的位元換成1，然後將其右邊的所有位元全部換成0，就能得到下一個較大的二進位表示法。 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