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

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

2、yx122101210jnjnn2p例例:求出求出(x + y)4的展開(kāi)式。的展開(kāi)式。p解解:3p例例:求出求出(x + y)25展開(kāi)式中展開(kāi)式中x12y13的係數(shù)。的係數(shù)。p解解:4p例例:求出求出(2x 3y)25展開(kāi)式中展開(kāi)式中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個(gè)元素的集合，而個(gè)元素的集合，而aT，S = Ta。我們留意到。我們留意到T有有 個(gè)包含個(gè)包含k個(gè)元素的個(gè)元素的不同子集合。這類(lèi)的子集合能分成兩類(lèi)：一種是不同子集合。這類(lèi)的子集合能分成兩類(lèi)：一種是包含元素包含元素a與與k1個(gè)個(gè)S中的元素；另一種是不包含中的元素；另一種是不包含a，而包含，而包含k個(gè)個(gè)S中的元素。由於包含中的元素。由於包含k 1個(gè)個(gè)S中中的元素之子集合個(gè)數(shù)為的元素之子集合個(gè)數(shù)為 ，而包含，而包含k個(gè)個(gè)S中的元中的元素之子集合個(gè)數(shù)為素之子集合個(gè)數(shù)為 。所以，我們

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

5、外一種算法，假設(shè)這個(gè)。另外一種算法，假設(shè)這r個(gè)元素中，個(gè)元素中，有有k個(gè)取自第一個(gè)集合，而個(gè)取自第一個(gè)集合，而r k個(gè)來(lái)自第二個(gè)集個(gè)來(lái)自第二個(gè)集合，其中合，其中0 k r。則利用乘法法則這樣選取的。則利用乘法法則這樣選取的方法有方法有 。所以從兩集合中取出。所以從兩集合中取出r個(gè)元素的方個(gè)元素的方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)例，我們知道左式等於長(zhǎng)節(jié)中的

6、範(fàn)例，我們知道左式等於長(zhǎng)度為度為n + 1位元字串恰巧包含位元字串恰巧包含r + 1個(gè)個(gè)1的字串?dāng)?shù)目。的字串?dāng)?shù)目。在長(zhǎng)度為在長(zhǎng)度為n + 1恰巧包含恰巧包含r + 1個(gè)個(gè)1的位元字串中，的位元字串中，最後一個(gè)最後一個(gè)1一定落在第一定落在第r + 1、r + 2、或或n + 1的的位置上。假設(shè)最後一個(gè)位置上。假設(shè)最後一個(gè)1在第在第j + 1個(gè)位置時(shí)，這樣個(gè)位置時(shí)，這樣的字串?dāng)?shù)等於長(zhǎng)度為的字串?dāng)?shù)等於長(zhǎng)度為j，恰巧有，恰巧有r個(gè)個(gè)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)成多少長(zhǎng)度為例：利用英文字母能構(gòu)成多少長(zhǎng)度為r的字串？的字串？p解：解：p允許重複運(yùn)用之允許重複運(yùn)用之n個(gè)元素的個(gè)元素的r-陳列能夠方法數(shù)如下面定理陳列能夠方法數(shù)如下面定理所示。所示。p定理：有定理：有n個(gè)元素之集合中，允許重複的個(gè)元素之集合中，允許重複的r-陳列共有陳列共有nr種。種。p證明：在證明：在r-陳列中，每個(gè)位置都有陳列中，每個(gè)位置都有n個(gè)選擇，根據(jù)乘法法個(gè)選擇，根據(jù)乘法法則允許重複的則允

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

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

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

11、 1個(gè)，一種有個(gè)，一種有r個(gè)。個(gè)。故，一共有故，一共有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è)不計(jì)挑選時(shí)的順序，選取六個(gè)餅乾有幾種方法？設(shè)不計(jì)挑選時(shí)的順序，選取六個(gè)餅乾有幾種方法？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個(gè)物件中，第種一樣的物件有個(gè)物件中，第種一樣的物件有n1個(gè)；第個(gè)；第2種種一樣的物件有一樣的物件有n2個(gè)；個(gè)；第；第k種一樣的物件有種一樣的物件有nk個(gè)。則此個(gè)。則此n個(gè)物件的陳列方式共有個(gè)物件的陳列方式共有n!/n1!n2!nk!。p證明：將此證明：將此n個(gè)物件排成一列共有個(gè)物件排成一列共有n個(gè)位置。首先挑選個(gè)位置。首先挑選出出n1個(gè)位置來(lái)放第個(gè)位置來(lái)放第1種物件，其方法數(shù)為種物件，其方法數(shù)為C(n, n1)。這個(gè)時(shí)。這個(gè)時(shí)候，

13、只剩下候，只剩下n n1個(gè)位置可以放置新的物件。接下來(lái)，個(gè)位置可以放置新的物件。接下來(lái)，選出選出n2個(gè)位置來(lái)放第個(gè)位置來(lái)放第2種物件，有種物件，有C(n n1, n2)種方法。種方法。這個(gè)時(shí)候，只剩下這個(gè)時(shí)候，只剩下n n1 n2個(gè)位置可以放置新的物件。個(gè)位置可以放置新的物件。繼續(xù)這樣的步驟，再根據(jù)乘法法則，再經(jīng)過(guò)約分，總陳列繼續(xù)這樣的步驟，再根據(jù)乘法法則，再經(jīng)過(guò)約分，總陳列方法數(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張撲克牌，分給四個(gè)人，一張撲克牌，分給四個(gè)人，一人五張，會(huì)有多少種不同的情形？人五張，會(huì)有多少種不同的情形？p解：解：22p定理：將定理：將n個(gè)不同物件分配到個(gè)不同物件分配到k個(gè)不同的箱子，使個(gè)不同的箱子，使得第得第i個(gè)箱子中有個(gè)箱子中有ni個(gè)物件，其中個(gè)物件，其中i = 1,2,k，的，的方法數(shù)為方法數(shù)為 !21knnnn23p不可區(qū)分物件與可區(qū)分之箱子不可區(qū)分物件與可區(qū)分之箱子 p例：將例：將10個(gè)一樣的球放進(jìn)八個(gè)不同的箱子中，有個(gè)一樣的球放進(jìn)八個(gè)不同的箱子中，有幾種能夠的情況？幾種能夠的情況？p解：解：24不同的物件和一樣的箱子不同的物件和一樣的箱子 p例：例： 有

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

16、兩個(gè)人在一個(gè)辦公室，另外兩人在另一個(gè)辦公室的情況有公室的情況有A, B, C, D，A, C, B, D和和A, D, B, C。兩個(gè)人在同一個(gè)辦公室，另外兩人一人一間辦公。兩個(gè)人在同一個(gè)辦公室，另外兩人一人一間辦公室有室有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由上面的表列中也能看出，將四個(gè)員工安排在三個(gè)一由上面的表列中也能看出，將四個(gè)員工安排在三個(gè)一樣的辦公室，而且沒(méi)有空辦公室的方法有六種。將四個(gè)員樣的辦公室，而且沒(méi)有空辦公室的方法有六種。將四個(gè)員工安排在兩個(gè)一樣的

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

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

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

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