二項式系數(shù)ppt課件

1、二項式係數(shù)二項式係數(shù)(5.4) p在n個元素的集合中選出r-組合的方法數(shù)為 。p這個數(shù)也稱作二項式係數(shù)(binomial coefficient)，因為這些數(shù)將出現(xiàn)在二項展開式，如(a + b)n的係數(shù)中。 rn1二項式定理二項式定理(The Binomial Theorem)p令x和y為變數(shù)，而n為非負(fù)整數(shù)，則p證明：將運用組合證明方式。當(dāng)j = 0, 1, 2, , n，xnjyj項的係數(shù)可以由相乘的n項(x + y)中，選取(nj)項的x和j項的y來相乘而得，所以其係數(shù)應(yīng)可p視為在n元素集合中(nj)-組合的個數(shù)，即p，得證。 nnnnnnjjjnnynnxynnyxnyxnxnyxjn

2、yx122101210jnjnn2p例例:求出求出(x + y)4的展開式。的展開式。p解解:3p例例:求出求出(x + y)25展開式中展開式中x12y13的係數(shù)。的係數(shù)。p解解:4p例例:求出求出(2x 3y)25展開式中展開式中x12y13的係數(shù)。的係數(shù)。p解解:5p系理系理:令令n為非負(fù)整數(shù)。則為非負(fù)整數(shù)。則ppp證明證明:nnkkn206p系理系理:令令n為正整數(shù)。則為正整數(shù)。則p證明證明:p留意留意:此系理可推導(dǎo)出此系理可推導(dǎo)出0) 1(0nkkkn7p系理系理:令令n為非負(fù)整數(shù)。則為非負(fù)整數(shù)。則 p證明證明:nnkkkn3208帕斯卡等式與三角形帕斯卡等式與三角形 p帕斯卡等式帕

3、斯卡等式(Pascals Identity) 令令n k為正整數(shù)，為正整數(shù)，則則 p證明證明:假設(shè)假設(shè)T為包含為包含n+1個元素的集合，而個元素的集合，而aT，S = Ta。我們留意到。我們留意到T有有 個包含個包含k個元素的個元素的不同子集合。這類的子集合能分成兩類：一種是不同子集合。這類的子集合能分成兩類：一種是包含元素包含元素a與與k1個個S中的元素；另一種是不包含中的元素；另一種是不包含a，而包含，而包含k個個S中的元素。由於包含中的元素。由於包含k 1個個S中中的元素之子集合個數(shù)為的元素之子集合個數(shù)為 ，而包含，而包含k個個S中的元中的元素之子集合個數(shù)為素之子集合個數(shù)為 。所以，我們

4、有。所以，我們有 knknkn11kn11knknknknkn119帕斯卡三角形帕斯卡三角形(Pascals triangle) 00110122120233231303443424140455453525150510二項式係數(shù)的等式二項式係數(shù)的等式 p凡德蒙德等式凡德蒙德等式(Vandermondes Identity) 令令m、n和和r為非負(fù)整數(shù)，而且為非負(fù)整數(shù)，而且r不能大於不能大於m與與n。則。則 p證明證明:假定在一個集合中有假定在一個集合中有m個元素，而第二個集個元素，而第二個集合中有合中有n個元素。從這兩個集合中取出個元素。從這兩個集合中取出r個元素的個元素的方法有方法有 個。另

5、外一種算法，假設(shè)這個。另外一種算法，假設(shè)這r個元素中，個元素中，有有k個取自第一個集合，而個取自第一個集合，而r k個來自第二個集個來自第二個集合，其中合，其中0 k r。則利用乘法法則這樣選取的。則利用乘法法則這樣選取的方法有方法有 。所以從兩集合中取出。所以從兩集合中取出r個元素的方個元素的方p法有法有 。 knkrmrnmrk 0rnmkrnkmknkrmrnmrk 011p系理系理:假設(shè)假設(shè)n為非負(fù)整數(shù)。則為非負(fù)整數(shù)。則 p證明證明:202knnnnk12p定理定理:令令n和和r為非負(fù)整數(shù)，而且為非負(fù)整數(shù)，而且r n。則。則p證明證明:根據(jù)根據(jù)5.3節(jié)中的範(fàn)例，我們知道左式等於長節(jié)中的

6、範(fàn)例，我們知道左式等於長度為度為n + 1位元字串恰巧包含位元字串恰巧包含r + 1個個1的字串?dāng)?shù)目。的字串?dāng)?shù)目。在長度為在長度為n + 1恰巧包含恰巧包含r + 1個個1的位元字串中，的位元字串中，最後一個最後一個1一定落在第一定落在第r + 1、r + 2、或或n + 1的的位置上。假設(shè)最後一個位置上。假設(shè)最後一個1在第在第j + 1個位置時，這樣個位置時，這樣的字串?dāng)?shù)等於長度為的字串?dāng)?shù)等於長度為j，恰巧有，恰巧有r個個1的位元字串的位元字串?dāng)?shù)數(shù) ，其中，其中 r j n。所以，等式成立。所以，等式成立。 nrjrjrn11rk113較複雜的陳列與組合較複雜的陳列與組合(5.5)p重複陳列

7、p重複組合p不可區(qū)分物件的陳列p將物件分配至箱子中p可區(qū)分物件與可區(qū)分的箱子p不可區(qū)分物件與可區(qū)分之箱子p不同的物件和一樣的箱子p一樣的物件和一樣的箱子14重複陳列重複陳列 p例：利用英文字母能構(gòu)成多少長度為例：利用英文字母能構(gòu)成多少長度為r的字串？的字串？p解：解：p允許重複運用之允許重複運用之n個元素的個元素的r-陳列能夠方法數(shù)如下面定理陳列能夠方法數(shù)如下面定理所示。所示。p定理：有定理：有n個元素之集合中，允許重複的個元素之集合中，允許重複的r-陳列共有陳列共有nr種。種。p證明：在證明：在r-陳列中，每個位置都有陳列中，每個位置都有n個選擇，根據(jù)乘法法個選擇，根據(jù)乘法法則允許重複的則允

8、許重複的r-陳列共有陳列共有nr種。種。 15重複組合重複組合 p例：例： 從一個包含蘋果、橘子和梨的碗中，挑選四個水果從一個包含蘋果、橘子和梨的碗中，挑選四個水果有幾種能夠性？假設(shè)不計挑選時的順序，而且每種水果在有幾種能夠性？假設(shè)不計挑選時的順序，而且每種水果在碗中的數(shù)目皆大於四。碗中的數(shù)目皆大於四。p解：解決這個問題的一個方法是，列出一切的能夠性如下：解：解決這個問題的一個方法是，列出一切的能夠性如下：p4個蘋果個蘋果4個橘子個橘子4個個梨梨p3個蘋果；個橘子個蘋果；個橘子3個蘋果；個蘋果；1個梨?zhèn)€梨3個個橘子；橘子；1個蘋果個蘋果p3個橘子；個橘子；1個梨?zhèn)€梨3個梨；個梨；1個蘋果個蘋果

9、3個個梨；梨；1個橘子個橘子p2個蘋果；個蘋果；2個橘子個橘子2個蘋果；個蘋果；2個梨?zhèn)€梨2個個橘子；橘子；2個梨?zhèn)€梨p2個蘋果；個蘋果；1個橘子；個橘子；1個梨?zhèn)€梨p2個橘子；個橘子；1個蘋果；個蘋果；1個梨?zhèn)€梨p2個梨；個梨；1個蘋果；個蘋果；1個橘子個橘子p一共有一共有15中能夠性。中能夠性。 16p定理：包含定理：包含n個元素的集合中允許重複之個元素的集合中允許重複之r-組合的個數(shù)為組合的個數(shù)為C(n + r 1, r) = C(n + r 1, n 1)。p證明：每個在包含證明：每個在包含n個元素的集合中允許重複之個元素的集合中允許重複之r-組合，組合，都能以都能以n 1個隔板和個隔

10、板和r個記號的陳列來表示。第個記號的陳列來表示。第i個隔板個隔板和第和第 i + 1個隔板間的記號個數(shù)，代表某元素選取的個數(shù)。個隔板間的記號個數(shù)，代表某元素選取的個數(shù)。譬如，在譬如，在4個元素的集合中，挑選個元素的集合中，挑選6個。當(dāng)隔板與記號的陳個。當(dāng)隔板與記號的陳列方式為列方式為pp表示第一個元素取兩個；第二個元素取一個；第三個表示第一個元素取兩個；第二個元素取一個；第三個元素不取，而第四個元素取三個。元素不取，而第四個元素取三個。p 如此一來，要解決的問題變?yōu)樵谌绱艘粊恚鉀Q的問題變?yōu)樵?n 1) + r個物件的個物件的陳列中，只需兩種不同物件，一種有陳列中，只需兩種不同物件，一種有n

11、 1個，一種有個，一種有r個。個。故，一共有故，一共有C(n + r 1, r)種方式。由於，種方式。由於，(n + r 1) r = n 1，根據(jù)，根據(jù)5.3節(jié)系理，節(jié)系理，C(n + r 1, r) = C(n + r 1, n 1)。 17p例：例： 假設(shè)某餅乾店中有四種不同口味的餅乾。假假設(shè)某餅乾店中有四種不同口味的餅乾。假設(shè)不計挑選時的順序，選取六個餅乾有幾種方法？設(shè)不計挑選時的順序，選取六個餅乾有幾種方法？p解：解：18p例：方程式例：方程式x1 + x2 + x3 = 11有多少組解？其中有多少組解？其中x1，x2和和x3為非負(fù)整數(shù)。為非負(fù)整數(shù)。p解：解：19不可區(qū)分物件的陳列不

12、可區(qū)分物件的陳列 p例例 將單字將單字SUCCESS之字母重新陳列，將構(gòu)成之字母重新陳列，將構(gòu)成多少不同的字串？多少不同的字串？p解：解：20p定理：假設(shè)定理：假設(shè)n個物件中，第種一樣的物件有個物件中，第種一樣的物件有n1個；第個；第2種種一樣的物件有一樣的物件有n2個；個；第；第k種一樣的物件有種一樣的物件有nk個。則此個。則此n個物件的陳列方式共有個物件的陳列方式共有n!/n1!n2!nk!。p證明：將此證明：將此n個物件排成一列共有個物件排成一列共有n個位置。首先挑選個位置。首先挑選出出n1個位置來放第個位置來放第1種物件，其方法數(shù)為種物件，其方法數(shù)為C(n, n1)。這個時。這個時候，

13、只剩下候，只剩下n n1個位置可以放置新的物件。接下來，個位置可以放置新的物件。接下來，選出選出n2個位置來放第個位置來放第2種物件，有種物件，有C(n n1, n2)種方法。種方法。這個時候，只剩下這個時候，只剩下n n1 n2個位置可以放置新的物件。個位置可以放置新的物件。繼續(xù)這樣的步驟，再根據(jù)乘法法則，再經(jīng)過約分，總陳列繼續(xù)這樣的步驟，再根據(jù)乘法法則，再經(jīng)過約分，總陳列方法數(shù)有方法數(shù)有pC(n, n1)C(nn1, n2)C(nn1nk1, nk)p = n!/n1!n2!nk!21將物件分配至箱子中將物件分配至箱子中 p可區(qū)分物件與可區(qū)分的箱子可區(qū)分物件與可區(qū)分的箱子 p例：將一副標(biāo)準(zhǔn)

14、的例：將一副標(biāo)準(zhǔn)的52張撲克牌，分給四個人，一張撲克牌，分給四個人，一人五張，會有多少種不同的情形？人五張，會有多少種不同的情形？p解：解：22p定理：將定理：將n個不同物件分配到個不同物件分配到k個不同的箱子，使個不同的箱子，使得第得第i個箱子中有個箱子中有ni個物件，其中個物件，其中i = 1,2,k，的，的方法數(shù)為方法數(shù)為 !21knnnn23p不可區(qū)分物件與可區(qū)分之箱子不可區(qū)分物件與可區(qū)分之箱子 p例：將例：將10個一樣的球放進(jìn)八個不同的箱子中，有個一樣的球放進(jìn)八個不同的箱子中，有幾種能夠的情況？幾種能夠的情況？p解：解：24不同的物件和一樣的箱子不同的物件和一樣的箱子 p例：例： 有

15、幾種方法能將四個員工分配到三個一樣的辦公室？有幾種方法能將四個員工分配到三個一樣的辦公室？其中辦公室裡的人數(shù)可以是任何非負(fù)整數(shù)。其中辦公室裡的人數(shù)可以是任何非負(fù)整數(shù)。p解：我們將以列舉方法求出這個問題的解。將各個情況表解：我們將以列舉方法求出這個問題的解。將各個情況表列如下：列如下：p四個人都放在同一個辦公室，以四個人都放在同一個辦公室，以A, B, C, D表示。表示。三人在同一個辦公室，一個人在另一個辦公室的情況有三人在同一個辦公室，一個人在另一個辦公室的情況有A, B, C, D，A, B, D, C，A, C, D, B和和B, C, D, A。兩個人在一個辦公室，另外兩人在另一個辦。

16、兩個人在一個辦公室，另外兩人在另一個辦公室的情況有公室的情況有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中方法。中方法。p由上面的表列中也能看出，將四個員工安排在三個一由上面的表列中也能看出，將四個員工安排在三個一樣的辦公室，而且沒有空辦公室的方法有六種。將四個員樣的辦公室，而且沒有空辦公室的方法有六種。將四個員工安排在兩個一樣的

17、辦公室，而且沒有空辦公室的方法有工安排在兩個一樣的辦公室，而且沒有空辦公室的方法有七種。而將四個員工安排在一個的辦公室方法只需一種。七種。而將四個員工安排在一個的辦公室方法只需一種。 25一樣的物件和一樣的箱子一樣的物件和一樣的箱子 p例：將同一本書的六份拷貝分配到四個完全一樣的包裹中，例：將同一本書的六份拷貝分配到四個完全一樣的包裹中，有幾種不同的分法？其中每個包裹中可以有任何種數(shù)目的有幾種不同的分法？其中每個包裹中可以有任何種數(shù)目的書本數(shù)。書本數(shù)。p解：解：26p觀察將n個一樣物件分配至k個一樣箱子中，其實就是將n分成j個小於k的正整數(shù)，a1, a2, , aj，其中a1 a2 aj使得a

18、1 + a2 + + aj = n。目前並沒有明顯的公式來計算這種題目的答案。 27產(chǎn)生陳列與組合產(chǎn)生陳列與組合(5.6) p有時陳列與組合的形態(tài)必須被製造出來，而不只是計數(shù)。p考慮下面三個問題。第一個，假設(shè)有個推銷員必須訪問六個城市。哪種行程的安排能花最少的時間？有種最好的方式，是將6! = 720種能夠的行程所需時間一一加總出來，然後在選出最短的時間。p第二個問題，假定給一個包含六個正整數(shù)的集合，假設(shè)能夠，找出其中相加等於100的一組正整數(shù)。一種找出這組集合的方式，是將一切26種子集合全都列出來，然後一一加總找出一切元素和為100的子集合。p最後一個問題，假設(shè)一個實驗室中有95個成員。假想

19、象組成一個12人小組來執(zhí)行一個特別的計畫。這個小組的人員必須擁有25項技藝。每位成員能夠擁有項或多項技藝。有種找出這個小組的方式，就是列出一切12個人員的子集合，一一檢驗?zāi)芊駶M足所需求的技藝。上述範(fàn)例說明了，有時求解問題時，必須將陳列或組合製造出來。 28產(chǎn)生陳列產(chǎn)生陳列 p我們將介紹一種根據(jù)字典陳列(lexicographic (or dictionary) ordering)方式而產(chǎn)生的陳列。在這種陳列中稱陳列a1a2an大於陳列b1b2bn或b1b2bn排在a1a2an之前，假設(shè)對某個k，1 k n， a1 = b1，a2 = b2，ak1 = bk1但是ak bk。換句話說，在兩種陳列

20、中，假設(shè)第一次出現(xiàn)不一樣數(shù)字的位置上，數(shù)字較大的陳列大於數(shù)字較小的陳列。p p例：在集合1, 2, 3, 4, 5的陳列中，陳列23415排在23514之前。因為第一次出現(xiàn)不一樣數(shù)字的第三個位置4小於5。一樣的道理，41532排在52143之前。29p例：例： 依字典順序方式依字典順序方式362541的下一個較大陳列是什麼？的下一個較大陳列是什麼？只運用只運用1, 2, 3, 4, 5, 6六個數(shù)字六個數(shù)字p解：解：30產(chǎn)生組合產(chǎn)生組合 p對一個有限的集合，該如何產(chǎn)生出一切的組合方式？因為組合只不過是個子集合，我們能用a1, a2, , an之子集合與長度為n之位元字串間的對應(yīng)關(guān)係來說明。p回顧此對應(yīng)關(guān)係，當(dāng)對應(yīng)之位元字串的第k個位置等於1時，表示元素ak在此組合中；而位元字串的第k個位置等於0時，表示元素ak不在此組合中。同時，我們也知道一個長度為n的位元