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

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

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

4、輔音字母的排序問題，輔音字母的排列方式有21！種。因為元音字母不能相連，所以只能將元音字母放在輔音字母中間的“空隙”里，22個空間放5個元音字母，其排列數為P(22,5).所以排序的方法數為:!17!22!21集合的循環排列如果不將集合S中的元素排列成線性而是排列成環形，稱為循環排列。如下圖所示的循環排列所對應的線性排列有： 123456 234561 345612 456123 561234 612345 共6個 循環排列的一般公式為：r) r , n(P集合的組合令r為非負整數。我們把n個元素的集合S的r-組合理解為從S的n個元素中對r個元素的無序選擇。換句話說，S的一個r-組合是S的一個

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

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

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