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

加法原理和乘法原理总体结构•1加法原理•2乘法原理•3集合的排列•4集合的组合•5多重集的排列•6多重集的组合加法原理加法原理（additionprinciple）•把集合S划分为S1,S2,…,Sn这n块，则S的个数可以通过找到它的每一个部分的元素的个数来确定，我们把这些数相加，得到：︱S︱＝︱S1︱＋︱S2︱＋…＋︱Sn︱注意，运用加法原则，把要计数的集合S划分成不太多的易于处理的块S1,S2,…,Sn加法原理应用•例：一名学生想选修一门数学课程或者一门生物课程。现有4门数学课程和3门生物课程作为该生的选课范围，那么该生的选择有几种？•解：应用加法法则:4+3=7(种)乘法原理乘法原理（multiplicationprinciple）•令S是元素的序偶（a,b）的集合，其中第一个元素来自大小为p的一个集合，而对于a的每个选择，元素b存在着q种选择。于是S的大小为p×q；|S|=p×q•如果某事件能分成连续n步完成，第一步有r1种方式完成，且不管第一步以何种方式完成，第二步都始终有r2种方式完成，而且无论前两步以何种方式完成，第三步都始终有r3种方式完成，以此类推，那么完成这件事共有r1×r2×…×rn种方式•注意，运用乘法原则，后步结果可随前步结果而变化，但每一步完成方式的数量却是固定不变，不依赖任何一步。乘法原理应用•例：粉笔有3种不同的长度，8种不同的颜色，4种不同的直径。粉笔有多少个不同的种类？•解：3个属性之间没有限制条件，应用乘法原理：3×8×4=96种集合的排列•令r为正整数。我们把n个元素的集合S的一个r-排列理解为n个元素中的r个元素的有序排列•我们用P(n，r)表示n个元素的r-排列的个数。如果rn，则P(n，r)=0•对于正整数n和r，r≤n，有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个辅音字母的排序问题，辅音字母的排列方式有21！种。因为元音字母不能相连，所以只能将元音字母放在辅音字母中间的“空隙”里，22个空间放5个元音字母，其排列数为P(22,5).所以排序的方法数为:!17!22!21集合的循环排列•如果不将集合S中的元素排列成线性而是排列成环形，称为循环排列。如下图所示的循环排列所对应的线性排列有：•»123456234561345612456123561234612345»共6个»循环排列的一般公式为：r)r,n(P集合的组合•令r为非负整数。我们把n个元素的集合S的r-组合理解为从S的n个元素中对r个元素的无序选择。换句话说，S的一个r-组合是S的一个子集，该子集由S得n个元素中的r个组成，即S的元素一个r-子集。•如果rn,则=0•如果r≤n，)!rn(!r!nCrnrnC集合组合的应用•例：平面上给出25个点，没有3个点共线。这些点确定多少条直线？确定多少个三角形？•解：因为没有3个点处于同一条直线上，每一对点就确定一条直线。因此，所确定的直线的数目等于25-个元素集的2-组合数，所取代的直线个数为:•与之类似，每3个点确定一个三角形，因此，所确定的三角形的个数为:300!23!2!25C225!22!3!25C325多重集的排列•多重集指的是集合S中有多个无区分的重复出现的元素。如：S{2·a，1·b，3·c}指的是集合S中含有2个a，1个b，3个c，同名元素没有区别。•多重集的表示S={n1·a1,n2·a2,…,nk·ak}•如果S是1个多重集，那么S的一个r-排列是S的r个元素的一个有序排放。如果S的元素总数是n（包括计算重复元素），那么S的n-排列也成为称为S的排列。•令S是一个多重集，有k个不同类型的元素，每个元素的重数为，设S的大小为•排列数为C(n，)×C(n，)×……C(n，)=•令S是一个多重集，有k个不同的元素，每个元素都有无限重复次数，则S的r-排列数：krk21nnn，，k21nnnS！！！！k21nnnn1n2nkn多重集排列应用•单词MISSISSIPPI的字母排列数为：•解：相当于多重集{1·M,4·I,4·S,2·P}的排列数即：34650244111！！！！！多重集组合•如果S是1个多重集，那么S的r-组合数S中的r个元素的一个无序选择。因此，S的一个r-组合本身就是一个多重集——S的一个含r个元素的子多重集。•令S为具有k种类型元素的一个多重集，每种元素均具有无限的重复数。则S的r-组合的个数等于也就是•证：S={∞·，∞·，……∞·}•S的任意一个r-组合均呈{x1·a1,x2·,…,xk·ak}，其中x1+x2+...+xk=r，xi为非负整数。满足x1+x2+...+xk=r的一组序列x1，x2，……xk对应S的一个r-组合。S的r-组合的个数等于x1+x2+...+xk=r的解的个数r1krC1a2aka2a多重集组合•我们可以这样理解，用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-k1krCr1krC多重集组合应用•例：一家面包房生产8种面包圈。如果1盒含有12个面包圈，能够买到多少种不同的盒装面包？•解：相当于8种类型的12-组合，可知组合数为•令S是具有4个元素a，b，c，d的多重集{10·a，10·b，10·c，10·d}S的使得4种元素每一种都至少出现1次的10-组合的数目是多少？•解：至少出现1次，忽略这个重复度，可知为4种类型的6-组合其组合数为=84121-812C6146C