《经典ppt课件：基本的组合计数公式.ppt》由会员分享，可在线阅读，更多相关《经典ppt课件：基本的组合计数公式.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离 散 数 学第12章基本的组合计数公式13 13 一月一月 2023 202383-83-2 2前言前言 组组合合数数学学是是一一个个古古老老而而又又年年轻轻的的数数学学分支。分支。据据传传说说，大大禹禹在在40004000多多年年前前就就观观察察到神龟背上的幻方到神龟背上的幻方.83-83-3 3前言前言幻幻方方可可以以看看作作是是一一个个3 3阶阶方方阵阵，其其元元素素是是1 1到到9 9的的正正整整数数，每每行行、每每列列以以及及两两条条对对角角线线的的和都是和都是1515。51937248683-83-4 4前言前言 贾宪 北北宋宋数数学学家家（约约1111世世纪纪）著著有有黄黄帝帝
2、九九章章细细草草、算算法法斅斅古古集集斅斅 音音“笑笑（“古古算算法法导导引引”）都都已已失失传传。杨杨辉辉著著详详解解九九章章算算法法（12611261年年）中中曾曾引引贾贾宪宪的的“开开方方作作法法本本源源”图图（即即指指数数为为正正整整数数的的二二项项式式展展开开系系数数表表，现现称称“杨杨辉辉三三角角形形”）和和“增增乘乘开开方方法法”（求求高高次次幂幂的的正正根根法法）。前前者者比比帕帕斯斯卡卡三三角角形形早早600600年年，后后 者者 比比 霍霍 纳纳（William William Geoge Geoge HornerHorner，1786178618371837）的方法（的方
3、法（18191819年）早年）早770770年。年。83-83-5 5前言前言 16661666年年莱莱布布尼尼兹兹所所著著组组合合学学论论文文一一书书问问世世，这这是是组组合合数数学学的的第第一一部部专专著著。书书中中首首次次使使用用了组合论（了组合论（CombinatoricsCombinatorics）一词。一词。83-83-6 6前言前言 组组合合数数学学的的蓬蓬勃勃发发展展则则是是在在计计算算机机问问世世和和普普遍遍应应用用之之后后。由由于于组组合合数数学学涉涉及及面面广广，内内容容庞庞杂杂，并并且且仍仍在在很很快快地地发发展展着着，因因而而还还没没有有一一个个统统一而有效的理论体系
4、。这与数学分析形成了对照。一而有效的理论体系。这与数学分析形成了对照。83-83-7 7前言前言 组组合合数数学学经经常常使使用用的的方方法法并并不不高高深深复复杂杂。最最主主要要的的方方法法是是计数时的合理分类和和组合模型的转换。但但是是，要要学学好好组组合合数数学学并并非非易易事事，既既需需要要一定的数学修养，也要进行相当的训练。一定的数学修养，也要进行相当的训练。83-83-8 8计数问题计数问题 计计数数问问题题是是组组合合数数学学研研究究的的主主要要问问题题之之一一。西西班班牙牙数数学学家家Abraham Abraham ben ben Meir Meir ibn ibn Ezra(
5、1092Ezra(10921167)1167)和和法法国国数数学学家家、哲哲学学家家、天天文文学学家家Levi Levi ben ben Gerson(1288Gerson(12881344)1344)是是排排列列与与组组合合领领域域的的两两位位早早期期研研究究者者。另另外外，法法国国数数学学家家Blaise Blaise PascalPascal还还发发明明了了一一种种机机械械计计算算器器，这这种种计计算算器器非非常常类类似似于于2020世世纪纪4040年年代代在在数数字字电电子子计计算算机机发发明明之之前前使使用用的的一一种种机机械械计计算算器器。同同时时，计计数数技技术术在在数数学学和和
6、计计算算机机科科学学中中是是很很重重要要的的，特特别别是是在在数数据据结结构构、算算法法分分析析与与设计等后续课程中有非常重要的应用。设计等后续课程中有非常重要的应用。83-83-9 9 内容提要内容提要二项式定理与组合恒等式二项式定理与组合恒等式3多项式定理多项式定理4加法法则与乘法法则加法法则与乘法法则1排列与组合排列与组合283-83-1010 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1加法法则和原加法法则和原理法则理法则2 2排列组合的计排列组合的计算算 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 2二项式定理与组
7、二项式定理与组合恒等式计算合恒等式计算 83-83-1111组合问题的处理技巧组合问题的处理技巧n一一对应一一对应n数学归纳法数学归纳法n上下界逼近上下界逼近83-83-1212一一对应与上下界逼近一一对应与上下界逼近例例1 1 在允许移动被切割的物体的情况下，在允许移动被切割的物体的情况下，最少用多少次切割可以将最少用多少次切割可以将 3 3 3 的立的立方体切成方体切成 27个单位边长的立方体？个单位边长的立方体？中间的小立方体的中间的小立方体的6个面都是切割产生的面，每次切割个面都是切割产生的面，每次切割至多产生一个面，至少需要至多产生一个面，至少需要6次切割。存在一种切割方次切割。存在
8、一种切割方法恰好用法恰好用 6 次切割。次切割。例例2 100个选手淘汰赛，为产生冠军至少需要多少轮比赛？个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法方法1：50+25+12+6+3+2+1=99 方法方法2：比赛次数与淘汰人数之间存在一一对应，总计淘：比赛次数与淘汰人数之间存在一一对应，总计淘汰汰99人，因此至少需要人，因此至少需要99场比赛场比赛.83-83-131312.112.1加法法则与乘法法则加法法则与乘法法则开胃食品开胃食品主食主食饮料饮料种类种类价格价格(元元)种类种类价格价格种类种类价格价格玉米片玉米片(Co)2.15汉堡汉堡(H)3.25茶水茶水(T)0.70色拉色拉(
9、Sa)1.90三明治三明治(S)3.65牛奶牛奶(M)0.85鱼排鱼排(F)3.15可乐可乐(C)0.75啤酒啤酒(B)0.75表表1 183-83-1414 乘法法则乘法法则 如如果果一一些些工工作作需需要要t t步步完完成成，第第一一步步有有n n1 1种种不不同同的的选选择择，第第二二步步有有n n2 2种种不不同同的的选选择择，第第t t步步有有n nt t种种不不同同的的选选择择，那那么么完完成成这这项项工工作作所所有可能的选择种数为：有可能的选择种数为：83-83-1515例例1 Melissa1 Melissa病毒病毒19901990年年，一一种种名名叫叫MelissaMelis
10、sa的的病病毒毒利利用用侵侵吞吞系系统统资资源源的的方方法法来来破破坏坏计计算算机机系系统统，通通过过以以含含恶恶意意宏宏的的字字处处理理文文档档为为附附件件的的电电子子邮邮件件传传播播。当当字字处处理理文文档档被被打打开开时时，宏宏从从用用户户的的地地址址本本中中找找出出前前5050个个地地址址，并并将将病病毒毒转转发发给给他他们们。用用户户接接收收到到这这些些被被转转发发的的附附件件并并将将字字处处理理文文档档打打开开后后，病病毒毒会会自自动动继继续续转转发发，不不断断往往复复扩扩散散。病病毒毒非非常常快快速速地地转转发发邮邮件件，将将被被转转发发的的邮邮件件临临时时存存储储在在某某个个磁
11、磁盘盘上上，当当磁磁盘盘占占满满后后，系系统统将将会会死死锁锁甚甚至至崩崩溃溃。问经过四次转发，共有多少个接收者？问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050+505050+5050+50+150505050+505050+5050+50+1=6377551=6377551个接收者。个接收者。83-83-1616例例2 2在在一一幅幅数数字字图图像像中中，若若每每个个像像素素点点用用8 8位位进进行行编编码码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分分析析 用用
12、8 8位位进进行行编编码码可可分分为为8 8个个步步骤骤：选选择择第第一一位位，选选择择第第二二位位，选选择择第第八八位位。每每一一个个位位有有两两种种选选 择择，故故 根根 据据 乘乘 法法 原原 理理，8 8位位 编编 码码 共共 有有22222222=222222222=28 8=256=256种取值。种取值。解解 每个点有每个点有256(=2256(=28 8)种不同的取值。种不同的取值。83-83-1717 加法法则加法法则 假假定定X X1 1,X X2 2,X Xt t均均为为集集合合，第第i i个个集集合合X Xi i有有n ni i个个元元素素。如如XX1 1,X X2 2,
13、X Xt t 为为两两两两不不相相交交的的集集合合，则可以从则可以从X X1 1,X,X2 2,X,Xt t中选出的元素总数为：中选出的元素总数为：n n1 1+n+n2 2+n+nt t。即集合即集合即集合即集合X X X X1 1 1 1XXXX2 2 2 2XXXXt t t t含有含有含有含有n n n n1 1 1 1+n+n+n+n2 2 2 2+n+n+n+nt t t t个元素。个元素。个元素。个元素。83-83-1818例例3 3由由 AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFranci
14、sco六六个个人人组组成成的的委委员员会会，要要选选出出一一个个主主席席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若若主主席席必必须须从从AliceAlice和和BenBen种种选选出出，共共有有多多少少种选法？种选法？（3 3）若）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少种选法？（4 4）若若DolphDolph和和FranciscoFrancisco都都有有职职位位，共共有有多多少少种种选法？选法？83-83-1919例例3 3 解解（1 1）根根据据乘乘法法法法则则，可可能能的的选选法法种种数数为
15、为654=654=120120；（2 2）法法一一 根根据据题题意意，确确定定职职位位可可分分为为3 3个个步步骤骤：确确定定主主席席有有2 2种种选选择择；主主席席选选定定后后，秘秘书书有有5 5个个人人选选；主主席席和和秘秘书书都都选选定定后后，出出纳纳有有4 4个个人人选选。根根据据乘乘法法法则法则，可能的选法种数为，可能的选法种数为254=40254=40；法法二二 若若AliceAlice被被选选为为主主席席，共共有有54 54=2020种种方方法法确确定定其其他他职职位位；若若BenBen为为主主席席，同同样样有有2020种种方方法法确确定定其其他他职职位位。由由于于两两种种选选法
16、法得得到到的的集集合合不不相相交交，所所以根据以根据加法法则加法法则，共有，共有202020=4020=40种选法；种选法；83-83-2020例例3 3 解解(续续)(3)(3)法法一一 将将确确定定职职位位分分为为3 3步步：确确定定EgbertEgbert的的职职位位,有有3 3种种方方法法；确确定定余余下下的的较较高高职职位位人人选选,有有5 5个个人人选选；确确定定最最后后一一个个职职位位的的人人选选,有有4 4个个人人选选。根根据据乘法法则乘法法则，共有，共有354=60354=60种选法；种选法；法法二二 根根据据(1)(1)的的结结论论，如如果果EgbertEgbert为为主主
17、席席，有有2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为秘秘书书，有有2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为出出纳纳员员，也也有有2020种种方方法法确确定定余余下下的的职职位位。由由于于三三种种选选法法得得到到的的集集合合不相交，根据不相交，根据加法法则加法法则，共有，共有2020202020=6020=60种选法；种选法；83-83-2121例例3 3 解解(续续)（4 4）将将给给DolphDolph、FranciscoFrancisco和和另另一一个个人人指指定定职职位位分为分为3 3步：步：给给Dolph
18、Dolph指定职位，指定职位，有有3 3个职位可选；个职位可选；给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选；确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。根据根据乘法法则乘法法则，共有，共有324=24324=24种选法。种选法。83-83-222212.2 12.2 排列与组合排列与组合 ZekeZeke、YungYung、XenoXeno和和WilmaWilma四四个个候候选选人人竞竞选选同同一一职职位位。为为了了使使选选票票上上人人名名的的次次序序不不对对投投票票者者产产生生影影响响，有有必必要要将将每每一一种
19、种可可能能的的人人名名次次序序打打印印在在选选票票上上。会有多少种不同的选票呢？会有多少种不同的选票呢？从从某某个个集集合合中中有有序序的的选选取取若若干干个个元元素素的的问问题题，称称为为排列问题排列问题。83-83-2323排列问题排列问题定义定义12.112.1 （1 1）从从含含n n个个不不同同元元素素的的集集合合S S中中有有序序选选取取的的r r个个元元素素叫叫做做S S的的一一个个r r r r-排排排排列列列列，不不同同的的排排列列总总数数记记为为P(n,P(n,r)r)。如如果果r r=n n，则则称称这这个个排排列列为为S S的的一一个个全全全全排列排列排列排列，简称为，
20、简称为S S的排列。的排列。显然显然，当当当当rnrnrnrn时，时，时，时，P(n,r)=0P(n,r)=0P(n,r)=0P(n,r)=0。83-83-2424例例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。83-83-
21、2525定理定理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)83-83-2626注意：注意：n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 83-83-2727例例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相连的有多少种？相连的有
22、多少种？解解 (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的的全全排排列列，
23、有有4 4！种种排排列列。又根据乘法原理，满足条件的排列总数有又根据乘法原理，满足条件的排列总数有3 3！44！=144=144。83-83-2828例例3 36 6个个人人围围坐坐在在圆圆桌桌上上，有有多多少少种种不不同同的的坐坐法法？通通过过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。A AE EF FB BD DC Cn n n n个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)(n-1)(n-1)！种不同的坐法，我们称！种不同的坐法，我
24、们称！种不同的坐法，我们称！种不同的坐法，我们称这种排列为这种排列为这种排列为这种排列为环排列环排列环排列环排列，从，从，从，从n n n n个人中选出个人中选出个人中选出个人中选出r r r r个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐称为称为称为称为环形环形环形环形r-r-r-r-排列排列排列排列。83-83-2929推论推论1 1含含n n个不同元素的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r)(n,r)是是83-83-3030例例4 4求满足下列条件的排列数。求满足下列条件的排列数。(1)10(1)10个男孩和个男孩和5 5个女孩个女孩站成一
25、排站成一排，无两个女孩相邻无两个女孩相邻。(2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无两个女孩相邻无两个女孩相邻.解解 (1)(1)根根据据定定理理，1010个个男男孩孩的的全全排排列列为为10!10!，5 5个个女女孩孩插插入入到到1010个个男男孩孩形形成成的的1111个个空空格格中中的的插插入入方方法法数数为为P(11,P(11,5)5)。根根据据乘乘法法法法则则，1010个个男男孩孩和和5 5个个女女孩孩站站成成一排，没有两个女孩相邻的排列数为：一排，没有两个女孩相邻的排列数为：10!P(11,5)=10!P(11,5)=（10!11!)/6!10!1
26、1!)/6!。83-83-3131例例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!P(10,5)=（9!10!)/5!9!10!)/5!9!10!)/5!9!10!
27、)/5!。83-83-3232 组合问题组合问题定义定义12.112.1（2 2）从从含含有有n n个个不不同同元元素素的的集集合合S S中中无无序序选选取取的的r r个个元元素素叫叫做做S S的的一一个个r r-组组合合，不不同同的的组组合合总总数数记记为为C(n,r)C(n,r)。当当当当nr=0nr=0nr=0nr=0时，规定时，规定时，规定时，规定C(n,r)=1C(n,r)=1C(n,r)=1C(n,r)=1。显然，当显然，当显然，当显然，当rnrnrnrn时，时，时，时，C(n,r)=0C(n,r)=0C(n,r)=0C(n,r)=0。83-83-3333定理定理12.112.1（
28、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？83-83-4444基本计数公式的应用基本计数公式的应用(续续)例例3 3 设设A A为为 n n 元集，问元集，问(1)(1)A A上的自反关系有多少个？上的自反关系有多少个？(2)(2)A A上的反自
29、反关系有多少个？上的反自反关系有多少个？(3)(3)A A上的对称关系有多少个？上的对称关系有多少个？(4)(4)A A上的反对称关系有多少个？上的反对称关系有多少个？(5)(5)A A上既不对称也不是反对称上既不对称也不是反对称 的关系有多少个？的关系有多少个？83-83-4545多重集的排列多重集的排列定理定理12.2 多重集多重集S=n1 a1,n2 a2,nk ak，0 ni +(1)全排列全排列 r=n,n1+n2+nk=n 证明：分步选取证明：分步选取.先放先放a1,有有C(n,n1)种方法；再放种方法；再放a2,有有C(n n1,n2)种方法种方法,.,放放ak,有有C(n n1
30、 n2 nk 1,nk)种方法种方法 (2)若若r ni 时，每个位置都有时，每个位置都有 k 种选法，得种选法，得 kr.83-83-4646多重集的组合多重集的组合定理定理12.3 多重集多重集 S=n1 a1,n2 a2,nk ak，0smax_index)/(sismax_index)/比比较较得得到到较较大大的的元元素素，并并更更新新最最大元素大元素9.max_index=i 10./9.max_index=i 10./将最大的元素移至序列尾将最大的元素移至序列尾11.swap(sn,smax_index)11.swap(sn,smax_index)12.selection_sort
31、(s,n-1)12.selection_sort(s,n-1)13.13.83-83-8282例例4 4 解解设设计计算算n n个个数数排排序序的的比比较较执执行行次次数数为为b bn n，则则该该算算法法中的比较语句的执行次数的中的比较语句的执行次数的递归关系递归关系为：为：b bn n=b=bn-1 n-1+n 1+n 1，其其初始条件初始条件为：为：b b1 1=0=0。83-83-8383例例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。个人观点供参考，欢迎讨论个人观点供参考，欢迎讨论