《12基本的组合计数公式.ppt》由会员分享，可在线阅读，更多相关《12基本的组合计数公式.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离 散 数 学第12章基本的组合计数公式132-132-2 2 内容提要内容提要二项式定理与组合恒等式二项式定理与组合恒等式3多项式定理多项式定理4加法法则与乘法法则加法法则与乘法法则1排列与组合排列与组合2132-132-3 3 加法法则加法法则事事件件 X X1 1有有 n n1 1种种产产生生方方式式，事事件件 X X2 2有有 n n2 2 种种产产生生方方式式，,事事件件 X Xt t 有有 n nt t 种种产产生生的的方方式式，,X,X1 1,X X2 2,X Xt t 两两两两不不相相交交，则则可可以以从从事事件件X X1 1或或 X X2 2或或 X Xt t中选出的元素总数
2、为：中选出的元素总数为：n n1 1+n+n2 2+n nt t。使用条件：事件使用条件：事件 X Xi i与与 X Xj j产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取132-132-4 4 乘法法则乘法法则 如如果果一一些些工工作作需需要要t t步步完完成成，第第一一步步有有n n1 1种种不不同同的的选选择择，第第二二步步有有n n2 2种种不不同同的的选选择择，第第t t步步有有n nt t种种不不同同的的选选择择，那那么么完完成成这这项项工工作作所所有可能的选择种数为：有可能的选择种数为：使用条件：事件使用条件：事件 A A 与与 B B 产生方式彼此独立产生方式
3、彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1A1有有 p1p1种产生方式，事件种产生方式，事件 A2A2有有 p2 p2 种产生方式，种产生方式，,事件事件 AkAk 有有 pkpk 种产生的方式，种产生的方式，则则 “事件事件A1A1与与 A2A2与与 AkAk”有有 p1 p2 p1 p2 pk pk 种种产生的方式产生的方式.132-132-5 5设设A A为为 n n 元集，问元集，问(1)(1)A A上的自反关系有多少个？上的自反关系有多少个？(2)(2)A A上的反自反关系有多少个？上的反自反关系有多少个？(3)(3)A A上的对称关系有多少个？上的对称关
4、系有多少个？(4)(4)A A上的反对称关系有多少个？上的反对称关系有多少个？(5)(5)A A上既不对称也不是反对称上既不对称也不是反对称 的关系有多少个？的关系有多少个？(6)(6)A A上的函数有多少个？其中双上的函数有多少个？其中双 射函数有多少个？射函数有多少个？例例1 1 n n 元集元集上关系和函数的计数问题上关系和函数的计数问题 有有 n nn n 个函数个函数有有n n！个双射函数个双射函数132-132-6 6例例2 2 Melissa Melissa病毒病毒19901990年年，一一种种名名叫叫MelissaMelissa的的病病毒毒利利用用侵侵吞吞系系统统资资源源的的方
5、方法法来来破破坏坏计计算算机机系系统统，通通过过以以含含恶恶意意宏宏的的字字处处理理文文档档为为附附件件的的电电子子邮邮件件传传播播。当当字字处处理理文文档档被被打打开开时时，宏宏从从用用户户的的地地址址本本中中找找出出前前5050个个地地址址，并并将将病病毒毒转转发发给给他他们们。用用户户接接收收到到这这些些被被转转发发的的附附件件并并将将字字处处理理文文档档打打开开后后，病病毒毒会会自自动动继继续续转转发发，不不断断往往复复扩扩散散。病病毒毒非非常常快快速速地地转转发发邮邮件件，将将被被转转发发的的邮邮件件临临时时存存储储在在某某个个磁磁盘盘上上，当当磁磁盘盘占占满满后后，系系统统将将会会
6、死死锁锁甚甚至至崩崩溃溃。问经过四次转发，共有多少个接收者？问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050505050+5050+50505050+5050+5050+50+150+50+1=6377551=6377551个接收者。个接收者。132-132-7 7例例3 3 像素点取值问题像素点取值问题在在一一幅幅数数字字图图像像中中，若若每每个个像像素素点点用用8 8位位进进行行编编码码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分分析析 用用8 8位位进进行行编编
7、码码可可分分为为8 8个个步步骤骤：选选择择第第一一位位，选选择择第第二二位位，选选择择第第八八位位。每每一一个个位位有有两两种种选选 择择，故故 根根 据据 乘乘 法法 原原 理理，8 8位位 编编 码码 共共 有有22222222=222222222=28 8=256=256种取值。种取值。解解 每个点有每个点有256(=2256(=28 8)种不同的取值。种不同的取值。132-132-8 8例例4 4 职位分配问题职位分配问题由由 AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六六个个人
8、人组组成成的的委委员员会会，要要选选出出一一个个主主席席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若若主主席席必必须须从从AliceAlice和和BenBen种种选选出出，共共有有多多少少种选法？种选法？（3 3）若）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少种选法？（4 4）若若DolphDolph和和FranciscoFrancisco都都有有职职位位，共共有有多多少少种种选法？选法？132-132-9 9例例4 4 解解（1 1）根根据据乘乘法法法法则则，可可能能的的选选法法种种数数为为654=65
9、4=120120；（2 2）法法一一 根根据据题题意意，确确定定职职位位可可分分为为3 3个个步步骤骤：确确定定主主席席有有2 2种种选选择择；主主席席选选定定后后，秘秘书书有有5 5个个人人选选；主主席席和和秘秘书书都都选选定定后后，出出纳纳有有4 4个个人人选选。根根据据乘乘法法法则法则，可能的选法种数为，可能的选法种数为254=40254=40；法法二二 若若AliceAlice被被选选为为主主席席，共共有有54 54=2020种种方方法法确确定定其其他他职职位位；若若BenBen为为主主席席，同同样样有有2020种种方方法法确确定定其其他他职职位位。由由于于两两种种选选法法得得到到的的
10、集集合合不不相相交交，所所以根据以根据加法法则加法法则，共有，共有202020=4020=40种选法；种选法；132-132-1010例例4 4 解解(续续)(3)(3)法法一一 将将确确定定职职位位分分为为3 3步步：确确定定EgbertEgbert的的职职位位,有有3 3种种方方法法；确确定定余余下下的的较较高高职职位位人人选选,有有5 5个个人人选选；确确定定最最后后一一个个职职位位的的人人选选,有有4 4个个人人选选。根根据据乘法法则乘法法则，共有，共有354=60354=60种选法；种选法；法法二二 根根据据(1)(1)的的结结论论，如如果果EgbertEgbert为为主主席席，有有
11、2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为秘秘书书，有有2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为出出纳纳员员，也也有有2020种种方方法法确确定定余余下下的的职职位位。由由于于三三种种选选法法得得到到的的集集合合不相交，根据不相交，根据加法法则加法法则，共有，共有2020202020=6020=60种选法；种选法；132-132-1111例例4 4 解解(续续)（4 4）将将给给DolphDolph、FranciscoFrancisco和和另另一一个个人人指指定定职职位位分为分为3 3步：步：给给DolphDol
12、ph指定职位，指定职位，有有3 3个职位可选；个职位可选；给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选；确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。根据根据乘法法则乘法法则，共有，共有324=24324=24种选法。种选法。132-132-121212.2 12.2 排列与组合排列与组合 ZekeZeke、YungYung、XenoXeno和和WilmaWilma四四个个候候选选人人竞竞选选同同一一职职位位。为为了了使使选选票票上上人人名名的的次次序序不不对对投投票票者者产产生生影影响响，有有必必要要将将每每一一种种
13、可可能能的的人人名名次次序序打打印印在在选选票票上上。会有多少种不同的选票呢？会有多少种不同的选票呢？从从某某个个集集合合中中有有序序的的选选取取若若干干个个元元素素的的问问题题，称称为为排列问题排列问题。132-132-1313排列问题排列问题定义定义12.112.1 （1 1）从从含含n n个个不不同同元元素素的的集集合合S S中中有有序序选选取取的的r r个个元元素素叫叫做做S S的的一一个个r r r r-排排排排列列列列，不不同同的的排排列列总总数数记记为为P(nP(n,r)r)。如如果果r r=n n，则则称称这这个个排排列列为为S S的的一一个个全全全全排列排列排列排列，简称为，
14、简称为S S的排列。的排列。显然显然，当当当当rnrnrnrn时，时，时，时，P(nP(nP(nP(n,r)=0,r)=0,r)=0,r)=0。132-132-1414例例1 1从从含含3 3个个不不同同元元素素的的集集合合S S中中有有序序选选取取2 2个个元元素素的的排排列总数。列总数。解解 从从含含3 3个个元元素素的的不不同同集集合合S S中中有有序序选选取取2 2个个元元素素的排列总数为的排列总数为6 6种。种。如果将这如果将这3 3个元素记为个元素记为A A、B B和和C C，则，则6 6个排列为个排列为AB,AC,BA,BC,CB,CAAB,AC,BA,BC,CB,CA。132-
15、132-1515定理定理12.112.1对满足对满足rnrn的正整数的正整数n n和和r r有有第第r r位位第第r-1r-1位位第第3 3位位第第2 2位位第第1 1位位n nn-1n-1n-2n-2 n-(r-2)n-(r-2)n-(r-1)n-(r-1)132-132-1616注意：注意：n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 132-132-1717例例2 2 A,B,C,D,E,F A,B,C,D,E,F组成的排列中，组成的排列中，（1 1）有多少含有）有多少含有DEFDEF的子串？的子串？（2 2）三个字母）三个字母D D、E E和和F F相连的有
16、多少种？相连的有多少种？解解 (1)(1)将将DEFDEF看看成成一一个个对对象象，根根据据定定理理，满满足足条条件件的的排排列为列为A,B,C,DEFA,B,C,DEF的全排列，共有的全排列，共有4 4！=24=24种；种；（2 2）根根据据题题意意，满满足足该该条条件件的的排排列列分分为为两两步步：第第一一步步确确定定D,D,E E和和F F三三个个字字母母的的全全排排列列，有有3 3！种种排排列列，第第二二步步将将已已排排序序的的D,D,E E和和F F看看成成一一个个整整体体，与与A,A,B B和和C C共共4 4个个元元素素构构造造出出A,A,B,B,C,C,D,D,E,E,F F的
17、的全全排排列列，有有4 4！种种排排列列。又根据乘法原理，满足条件的排列总数有又根据乘法原理，满足条件的排列总数有3 3！44！=144=144。132-132-1818例例3 36 6个个人人围围坐坐在在圆圆桌桌上上，有有多多少少种种不不同同的的坐坐法法？通通过过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。A AE EF FB BD DC Cn n n n个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)(n-1)(n-1)！种不同的坐法，我们
18、称！种不同的坐法，我们称！种不同的坐法，我们称！种不同的坐法，我们称这种排列为这种排列为这种排列为这种排列为环排列环排列环排列环排列，从，从，从，从n n n n个人中选出个人中选出个人中选出个人中选出r r r r个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐称为称为称为称为环形环形环形环形r-r-r-r-排列排列排列排列。132-132-1919推论推论1 1含含n n个不同元素的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r(n,r)是是环排列数环排列数是是线排列数的线排列数的1 1/r r132-132-2020例例4 4求满足下列条件的排列数。求满
19、足下列条件的排列数。(1)101)10个男孩和个男孩和5 5个女孩个女孩站成一排站成一排，无两个女孩相邻无两个女孩相邻。(2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无两个女孩相邻无两个女孩相邻.解解 (1)(1)根根据据定定理理，1010个个男男孩孩的的全全排排列列为为10!10!，5 5个个女女孩孩插插入入到到1010个个男男孩孩形形成成的的1111个个空空格格中中的的插插入入方方法法数数为为P(11,P(11,5)5)。根根据据乘乘法法法法则则，1010个个男男孩孩和和5 5个个女女孩孩站站成成一排，没有两个女孩相邻的排列数为：一排，没有两个女孩相邻的排列数
20、为：10!P(11,5)=10!P(11,5)=（10!11!)/6!10!11!)/6!。132-132-2121例例4 4 解（续）解（续）（2 2）根根据据定定理理，1010个个男男孩孩站站成成一一个个圆圆圈圈的的环环排排列列数数为为9 9！，5 5个个女女孩孩插插入入到到1010男男孩孩形形成成的的1010个个空空中中的的插插入入方方法法数数为为P(10,P(10,5)5)。根根据据乘乘法法原原理理，1010个个男男孩孩和和5 5个个女女孩孩站站成成一一个个圆圆圈圈，没没有有两两个个女女孩孩相相邻邻的的排排列法为：列法为：9!P(10,5)=9!P(10,5)=9!P(10,5)=9!
21、P(10,5)=（9!10!)/5!9!10!)/5!9!10!)/5!9!10!)/5!。132-132-2222 组合问题组合问题定义定义12.112.1（2 2）从从含含有有n n个个不不同同元元素素的的集集合合S S中中无无序序选选取取的的r r个个元元素素叫叫做做S S的的一一个个r r-组组合合，不不同同的的组组合合总总数数记记为为C(nC(n,r),r)。当当当当nrnrnrnr=0=0=0=0时，规定时，规定时，规定时，规定C(nC(nC(nC(n,r)=1,r)=1,r)=1,r)=1。显然，当显然，当显然，当显然，当rnrnrnrn时，时，时，时，C(nC(nC(nC(n,
22、r)=0,r)=0,r)=0,r)=0。132-132-2323定理定理12.112.1（2 2）对满足对满足0 r n0 500;200个是个是 5 的倍数，的倍数，40个是个是 25 的倍数（多加的倍数（多加 40 个个 5），），8个是个是 125 的倍数（再多加的倍数（再多加 8 个个 5），），1个是个是 625 的倍数（再多加的倍数（再多加 1 个个 5）i=200+40+8+1=249.min(i,j)=249.例例2 求求1000！的末尾有多少个！的末尾有多少个0？132-132-3434多重集的排列多重集的排列定理定理12.2 多重集多重集S=n1 a1,n2 a2,nk a
23、k，0 ni +(1)全排列全排列 r=n,n1+n2+nk=n 证明：分步选取证明：分步选取.先放先放a1,有有C(n,n1)种方法；再放种方法；再放a2,有有C(n n1,n2)种方法种方法,.,放放ak,有有C(n n1 n2 nk 1,nk)种方法种方法 (2)若若r ni 时，每个位置都有时，每个位置都有 k 种选法，得种选法，得 kr.132-132-3535多重集的组合多重集的组合定理定理12.3 多重集多重集 S=n1 a1,n2 a2,nk ak，0 smax_indexsmax_index)/)/比比较较得得到到较较大大的的元元素素，并并更更新新最最大元素大元素9.9.ma
24、x_indexmax_index=i 10./=i 10./将最大的元素移至序列尾将最大的元素移至序列尾11.11.swap(snswap(sn,smax_indexsmax_index)12.12.selection_sort(sselection_sort(s,n-1),n-1)13.13.132-132-6767例例4 4 解解设设计计算算n n个个数数排排序序的的比比较较执执行行次次数数为为b bn n，则则该该算算法法中的比较语句的执行次数的中的比较语句的执行次数的递归关系递归关系为：为：b bn n=b=bn-1 n-1+n 1+n 1，其其初始条件初始条件为：为：b b1 1=0=0。132-132-6868例例4 4 解（续）解（续）用用迭代法迭代法求解该递归关系：求解该递归关系：b bn n=b=bn-1n-1+n1+n1 =b =bn-2n-2+n2+n-1+n2+n-1 =b =bn-3n-3+n3+n2+n1+n3+n2+n1 =b =b1 1+1+2+n3+n2+n1+1+2+n3+n2+n1 =0+1+2+=0+1+2+n 3+n2+n1+n 3+n2+n1 =n(n-1)/2 =n(n-1)/2。132-132-6969作业作业1,5,71,5,7，1414，2222（2 2），），2424（3 3）