《二项式系数教学教材》由会员分享，可在线阅读，更多相关《二项式系数教学教材（34页珍藏版）》请在金锄头文库上搜索。
1、二項式係數(5.4),在n個元素的集合中選出r-組合的方法數為。這個數也稱作二項式係數(binomialcoefficient)，因為這些數將出現在二項展開式，如(a+b)n的係數中。,1,二項式定理(TheBinomialTheorem),令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的係數。解:,4,系理:令n為非負整
2、數。則證明:,6,系理:令n為正整數。則證明:注意:此系理可推導出,7,系理:令n為非負整數。則證明:,8,帕斯卡等式與三角形,帕斯卡等式(PascalsIdentity)令nk為正整數，則證明:假設T為包含n+1個元素的集合，而aT，S=Ta。我們注意到T有個包含k個元素的不同子集合。這類的子集合能分成兩類：一種是包含元素a與k1個S中的元素；另一種是不包含a，而包含k個S中的元素。由於包含k1個S中的元素之子集合個數為，而包含k個S中的元素之子集合個數為。所以，我們有,9,帕斯卡三角形(Pascalstriangle),10,二項式係數的等式,凡德蒙德等式(VandermondesIden
3、tity)令m、n和r為非負整數，而且r不能大於m與n。則證明:假定在一個集合中有m個元素，而第二個集合中有n個元素。從這兩個集合中取出r個元素的方法有個。另外一種算法，假設這r個元素中，有k個取自第一個集合，而rk個來自第二個集合，其中0kr。則利用乘法法則這樣選取的方法有。所以從兩集合中取出r個元素的方法有。,11,系理:若n為非負整數。則證明:,12,定理:令n和r為非負整數，而且rn。則證明:根據5.3節中的範例，我們知道左式等於長度為n+1位元字串恰巧包含r+1個1的字串數目。在長度為n+1恰巧包含r+1個1的位元字串中，最後一個1一定落在第r+1、r+2、或n+1的位置上。若最後一
4、個1在第j+1個位置時，這樣的字串數等於長度為j，恰巧有r個1的位元字串數，其中rjn。所以，等式成立。,13,較複雜的排列與組合(5.5),重複排列重複組合不可區分物件的排列將物件分配至箱子中可區分物件與可區分的箱子不可區分物件與可區分之箱子不同的物件和相同的箱子相同的物件和相同的箱子,14,重複排列,例：利用英文字母能形成多少長度為r的字串？解：允許重複使用之n個元素的r-排列可能方法數如下面定理所示。定理：有n個元素之集合中，允許重複的r-排列共有nr種。證明：在r-排列中，每個位置都有n個選擇，根據乘法法則允許重複的r-排列共有nr種。,15,重複組合,例：從一個包含蘋果、橘子和梨的碗
5、中，挑選四個水果有幾種可能性？若不計挑選時的順序，而且每種水果在碗中的數目皆大於四。解：解決這個問題的一個方法是，列出所有的可能性如下：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+r1,r)=C(n+r1,n1)。證明：每個在包含n個元素的集合中允許重複之r-組合，都能以n1個隔板和r個記號的排列來表示。第
6、i個隔板和第i+1個隔板間的記號個數，代表某元素選取的個數。譬如，在4個元素的集合中，挑選6個。當隔板與記號的排列方式為表示第一個元素取兩個；第二個元素取一個；第三個元素不取，而第四個元素取三個。如此一來，要解決的問題變為在(n1)+r個物件的排列中，只有兩種不同物件，一種有n1個，一種有r個。故，一共有C(n+r1,r)種方式。由於，(n+r1)r=n1，根據5.3節系理，C(n+r1,r)=C(n+r1,n1)。,17,例：假設某餅乾店中有四種不同口味的餅乾。若不計挑選時的順序，選取六個餅乾有幾種方法？解：,18,例：方程式x1+x2+x3=11有多少組解？其中x1，x2和x3為非負整數。
7、解：,19,不可區分物件的排列,例將單字SUCCESS之字母重新排列，將形成多少不同的字串？解：,20,定理：若n個物件中，第種相同的物件有n1個；第2種相同的物件有n2個；第k種相同的物件有nk個。則此n個物件的排列方式共有n!/n1!n2!nk!。證明：將此n個物件排成一列（共有n個位置）。首先挑選出n1個位置來放第1種物件，其方法數為C(n,n1)。這個時候，只剩下nn1個位置可以放置新的物件。接下來，選出n2個位置來放第2種物件，有C(nn1,n2)種方法。這個時候，只剩下nn1n2個位置可以放置新的物件。繼續這樣的步驟，再根據乘法法則，再經過約分，總排列方法數有C(n,n1)C(nn
8、1,n2)C(nn1nk1,nk)=n!/n1!n2!nk!,21,將物件分配至箱子中,可區分物件與可區分的箱子例：將一副標準的52張撲克牌，分給四個人，一人五張，會有多少種不同的情形？解：,22,定理：將n個不同物件分配到k個不同的箱子，使得第i個箱子中有ni個物件，其中i=1,2,k，的方法數為,23,不可區分物件與可區分之箱子例：將10個相同的球放進八個不同的箱子中，有幾種可能的情況？解：,24,不同的物件和相同的箱子,例：有幾種方法能將四個員工分配到三個相同的辦公室？其中辦公室裡的人數可以是任何非負整數。解：我們將以列舉方法求出這個問題的解。將各個情況表列如下：四個人都放在同一個辦公室
9、，以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,相同
10、的物件和相同的箱子,例：將同一本書的六份拷貝分配到四個完全相同的包裹中，有幾種不同的分法？其中每個包裹中可以有任何種數目的書本數。解：,26,觀察將n個相同物件分配至k個相同箱子中，其實就是將n分成j個小於k的正整數，a1,a2,aj，其中a1a2aj使得a1+a2+aj=n。目前並沒有明顯的公式來計算這種題目的答案。,27,產生排列與組合(5.6),有時排列與組合的形態必須被製造出來，而不只是計數。考慮下面三個問題。第一個，假設有個推銷員必須訪問六個城市。哪種行程的安排能花最少的時間？有種最好的方式，是將6!=720種可能的行程所需時間一一加總出來，然後在選出最短的時間。第二個問題，假定給一
11、個包含六個正整數的集合，如果可能，找出其中相加等於100的一組正整數。一種找出這組集合的方式，是將所有26種子集合全都列出來，然後一一加總找出所有元素和為100的子集合。最後一個問題，假設一個實驗室中有95個成員。若想組成一個12人小組來執行一個特別的計畫。這個小組的人員必須擁有25項技能。（每位成員可能擁有項或多項技能。）有種找出這個小組的方式，就是列出所有12個人員的子集合，一一檢驗是否滿足所需要的技能。上述範例說明了，有時求解問題時，必須將排列或組合製造出來。,28,產生排列,我們將介紹一種根據字典排列(lexicographic(ordictionary)ordering)方式而產生的
12、排列。在這種排列中稱排列a1a2an大於排列b1b2bn（或b1b2bn排在a1a2an之前），如果對某個k，1kn，a1=b1，a2=b2，ak1=bk1但是akbk。換句話說，在兩種排列中，若第一次出現不相同數字的位置上，數字較大的排列大於數字較小的排列。例：在集合1,2,3,4,5的排列中，排列23415排在23514之前。因為第一次出現不相同數字的第三個位置4小於5。相同的道理，41532排在52143之前。,29,例：依字典順序方式362541的下一個較大排列是什麼？（只使用1,2,3,4,5,6六個數字）解：,30,產生組合,對一個有限的集合，該如何產生出所有的組合方式？因為組合只
13、不過是個子集合，我們能用a1,a2,an之子集合與長度為n之位元字串間的對應關係來說明。回顧此對應關係，當對應之位元字串的第k個位置等於1時，表示元素ak在此組合中；而位元字串的第k個位置等於0時，表示元素ak不在此組合中。同時，我們也知道一個長度為n的位元字串對應於一個介於0到2n1的整數之二進位表示法。為產生所有n位二進位數字，由n個0的表示法0000開始，持續找出下一個二進位表示法，直至得到n個1的表示法11111為止。產生下一個二進位表示法的過程如下：在每個步驟中，從最右邊找出第一個不是1的位置，將這個位置的位元換成1，然後將其右邊的所有位元全部換成0，就能得到下一個較大的二進位表示法
14、。,31,例：找出1000100111的下一個位元字串。解：,32,產生r-組合的演算法,給定一個產生集合1,2,3,n之r-組合的演算法。每一個r-組合都對應一個長度為r之遞增數列。a1a2ar依字典順序之下一個較大數列可依下面程序而得：首先找出最後一個ai的位置，其中ainr+i。然後，以ai+1替換ai，當j=i+1,i+2,r時，以ai+ji+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，其中ainr+i，是a2=2。以3替換a2=2，而a3=2+32+1=4，a4=2+42+1=5。得到下一個較大的4-組合為1,3,4,5。,34,
