《二项式系数》ppt课件

《《二项式系数》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二項式係數(§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

2、例:求出(2x3y)25展開式中x12y13的係數。解:5系理:令n為非負整數。則證明:6系理:令n為正整數。則證明:注意:此系理可推導出7系理:令n為非負整數。則證明: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帕斯卡三角形(P

3、ascal’striangle)10二項式係數的等式凡德蒙德等式(Vandermonde’sIdentity)令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+

4、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個元素的r-排列可能方法數如下面定理所示。定理：有n個元素之集合中，允許重複的r-排

5、列共有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個元素的集合

6、中允許重複之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節

7、系理，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個物件的排列方式共有n!/n1!n2!…nk!!。證明：將此n個物件排成一列（共有n個位置）。首先挑選出n1個位置來放第1種物