加法原理和乘法原理及多重集的排列組合

1、加法原理和乘法原理總體結(jié)構(gòu) 1加法原理 2乘法原理 3集合的排列 4集合的組合 5多重集的排列 6多重集的組合加法原理加法原理（加法原理（addition principleaddition principle）把集合S劃分為S1,S2,Sn這n塊，則S的個(gè)數(shù)可以通過(guò)找到它的每一個(gè)部分的元素的個(gè)數(shù)來(lái)確定，我們把這些數(shù)相加，得到： SS1S2Sn注意，運(yùn)用加法原則，把要計(jì)數(shù)的集合S劃分成不太多的易于處理的塊S1, S2, Sn加法原理應(yīng)用例：一名學(xué)生想選修一門(mén)數(shù)學(xué)課程或者一門(mén)生物課程?，F(xiàn)有4門(mén)數(shù)學(xué)課程和3門(mén)生物課程作為該生的選課范圍，那么該生的選擇有幾種？解：應(yīng)用加法法則:4+3=7(種)乘法原

2、理乘法原理（乘法原理（multiplication principlemultiplication principle） 令S是元素的序偶（a,b）的集合，其中第一個(gè)元素來(lái)自大小為p的一個(gè)集合，而對(duì)于a的每個(gè)選擇，元素b存在著q種選擇。于是S的大小為pq；|S|=pq如果某事件能分成連續(xù)n步完成，第一步有r1種方式完成，且不管第一步以何種方式完成，第二步都始終有r2種方式完成，而且無(wú)論前兩步以何種方式完成，第三步都始終有r3種方式完成，以此類推，那么完成這件事共有r1r2rn種方式注意，運(yùn)用乘法原則，后步結(jié)果可隨前步結(jié)果而變化，但每一步完成方式的數(shù)量卻是固定不變，不依賴任何一步。 乘法原理應(yīng)用

3、例：粉筆有3種不同的長(zhǎng)度，8種不同的顏色，4種不同的直徑。粉筆有多少個(gè)不同的種類？解：3個(gè)屬性之間沒(méi)有限制條件，應(yīng)用乘法原理：384=96種集合的排列令r為正整數(shù)。我們把n個(gè)元素的集合S的一個(gè)r-排列理解為n個(gè)元素中的r個(gè)元素的有序排列我們用P(n，r)表示n個(gè)元素 的r-排列的個(gè)數(shù)。如果rn，則P(n，r)=0對(duì)于正整數(shù)n和r，rn，有P（n，r）=n（n-1）（n-2）（n-3）（n-r+1）P（n，r）也可以表示為r）?。?！r-nnPrn集合排列的應(yīng)用例：將字母表中26個(gè)英文字母排序，使得元音字母a,e,i,o,u中任意兩個(gè)都不能相繼出現(xiàn)，這種排序的方法的總數(shù)是多少？解：首先要確定21個(gè)

4、輔音字母的排序問(wèn)題，輔音字母的排列方式有21！種。因?yàn)樵糇帜覆荒芟噙B，所以只能將元音字母放在輔音字母中間的“空隙”里，22個(gè)空間放5個(gè)元音字母，其排列數(shù)為P(22,5).所以排序的方法數(shù)為:!17!22!21集合的循環(huán)排列如果不將集合S中的元素排列成線性而是排列成環(huán)形，稱為循環(huán)排列。如下圖所示的循環(huán)排列所對(duì)應(yīng)的線性排列有： 123456 234561 345612 456123 561234 612345 共6個(gè) 循環(huán)排列的一般公式為：r) r , n(P集合的組合令r為非負(fù)整數(shù)。我們把n個(gè)元素的集合S的r-組合理解為從S的n個(gè)元素中對(duì)r個(gè)元素的無(wú)序選擇。換句話說(shuō)，S的一個(gè)r-組合是S的一個(gè)

5、子集，該子集由S得n個(gè)元素中的r個(gè)組成，即S的元素一個(gè)r-子集。如果rn,則 =0如果rn，)!rn( ! r!nCrnrnC集合組合的應(yīng)用例：平面上給出25個(gè)點(diǎn)，沒(méi)有3個(gè)點(diǎn)共線。這些點(diǎn)確定多少條直線？確定多少個(gè)三角形？解：因?yàn)闆](méi)有3個(gè)點(diǎn)處于同一條直線上，每一對(duì)點(diǎn)就確定一條直線。因此，所確定的直線的數(shù)目等于25-個(gè)元素集的2-組合數(shù)，所取代的直線個(gè)數(shù)為:與之類似，每3個(gè)點(diǎn)確定一個(gè)三角形，因此，所確定的三角形的個(gè)數(shù)為:300!23! 2!25C225!22! 3!25C325多重集的排列多重集指的是集合S中有多個(gè)無(wú)區(qū)分的重復(fù)出現(xiàn)的元素。如：S2a，1b，3c指的是集合S中含有2個(gè)a，1個(gè)b，3個(gè)

6、c，同名元素沒(méi)有區(qū)別。多重集的表示S=n n1 1a a1 1,n2,n2a2,na2,nk ka ak k如果S是1個(gè)多重集，那么S的一個(gè)r-排列是S的r個(gè)元素的一個(gè)有序排放。如果S的元素總數(shù)是n（包括計(jì)算重復(fù)元素），那么S的n-排列也成為稱為S S的排列的排列。令S是一個(gè)多重集，有k個(gè)不同類型的元素，每個(gè)元素的重?cái)?shù)為 ，設(shè)S的大小為排列數(shù)為C(n， )C(n， )C(n， )=令S是一個(gè)多重集，有k個(gè)不同的元素，每個(gè)元素都有無(wú)限重復(fù)次數(shù)，則S的r-排列數(shù)：krk21nnn，k21nnnS！k21nnnn1n2nkn多重集排列應(yīng)用單詞MISSISSIPPI的字母排列數(shù)為：解：相當(dāng)于多重集1M

7、,4I,4S,2P的排列數(shù) 即： 34650244111！多重集組合如果S是1個(gè)多重集，那么S的r-組合數(shù)S中的r個(gè)元素的一個(gè)無(wú)序無(wú)序選擇。因此，S的一個(gè)r-組合本身就是一個(gè)多重集S的一個(gè)含r個(gè)元素的子多重集。令S為具有k種類型元素的一個(gè)多重集，每種元素均具有無(wú)限的重復(fù)數(shù)。則S的r-組合的個(gè)數(shù)等于 也就是證：S= ， ， S的任意一個(gè)r-組合均呈x1a1,x2 ,xkak，其中x1 + x2 +.+ xk =r， xi 為非負(fù)整數(shù)。滿足x1 + x2 +.+ xk =r的一組序列 x1，x2，xk 對(duì)應(yīng)S的一個(gè)r-組合。 S的r-組合的個(gè)數(shù)等于x1 + x2 +.+ xk =r的解的個(gè)數(shù) r1krC1a2aka2a多重集組合我們可以這樣理解，用1代表組合中的一個(gè)元素，共有r個(gè)1，用*代表分割符，有（k-1）個(gè)。將*插入r個(gè)1中，形成了1個(gè)新的多重集示例：1111*11*111*1 代表元素總數(shù)為10，分成4種。第一個(gè)*之前為 ，之后依次為 ， ， 其個(gè)數(shù)分別為4個(gè)，2個(gè)，3個(gè)，2個(gè)。S的組合數(shù)可以理解為在（r+k-1）中找到（k-1）個(gè)位置放分隔符即 =1x2x3x4x1 -k1krCr1krC多重集組合應(yīng)用例：一家面包房生產(chǎn)8種面包圈。如果1盒含有12個(gè)面包圈，能夠買(mǎi)到多少種不同的盒裝面包？解：相當(dāng)于8種類型的 12-組合 ，可