排列组合公式ppt课件.ppt
《排列组合公式ppt课件.ppt》由会员分享,可在线阅读,更多相关《排列组合公式ppt课件.ppt(129页珍藏版)》请在三一办公上搜索。
1、排列组合公式,排列组合公式非降路径问题组合恒等式,排列与组合,从五个候选人中选出两个代表把5本不同的书安排在书架上从五个候选人中选出两个代表时,有10种可能的结果。把5本不同的书安排在书架上有120种方法选出-组合;安排-排列,一、排列组合公式,排列问题:从某个集合中有序地选取若干个元素的问题组合问题:从某个集合中无序地选取若干个元素的问题注意:可以重复 不能重复,排列,无重排列可重排列从1,2,9中选取数字构成四位数,使得每位数字都不同,有多少个?从1,2,9中选取数字构成四位数,使得不同数位上的数字可以相同,有多少个?,1、 无重排列,n个元素的r-无重排列数:排列的长度r计算(一般情形)
2、:乘法原理r=n时,n个元素的全排列r=0时rn时,2、可重排列,n个元素的r-可重排列数计算(乘法原理),例题,在1和10,000,000,000之间的一百亿个数中,有多少个数含有数码1?又有多少个数不含数码1?不含1:910含1:1010-910+1,例题,一个二元序列是由一些0和1所组成的序列。n码二元序列指该序列中数码的个数为n。试问,含有偶数个0的n码二元序列的个数是多少?2n-1考虑n码四元序列,即以0,1,2和3为其数码的序列。则含0和1的总个数为偶数的序列有多少个?4n/2,例题,求n码四元序列中含有偶数个0的个数?,放球问题,设nr,把r个不同的球放入n个不同的盒子,这里每一
3、盒最多只能装一物,允许空盒。放球的方法数为多少?第一个球有n种选法,第二个球有n-1种,等等,乘法原理P(n,r),放球问题,把r个不同的球放入n个不同的盒子,一个盒中可以放多个球,也允许空盒。放球的方法数为多少?第一个球有n种选法,第二个球有n种,等等,乘法原理nr这里n和r的大小没有限制,例子,将3封信向2个信箱投寄,有多少种投寄方法?23=8无序占位模型:不考虑盒子中的排列次序,放球问题,把r个不同的球放入n个不同的盒子,一个盒中可以放多个球,也允许空盒。考虑每个盒子中球的次序。放球的方法数为多少?有序占位模型有n种方法放第一个球,第一个球放入一个盒后,可以把这个球当成是一个添加的隔板,
4、它把该盒分成两个盒,因此放第二个球有n+1种方法。等等n(n+1)(n+2) (n+r-1)=nrF(n,r)r!,例子,某车站有6个进站口,今有9人进站,有多少种不同的进站方法?69=6714七部汽车通过五间收费亭的方式数?今欲在五根旗杆上悬挂七面不同的旗子,全部旗都得展示出来,但并非所有的旗杆都得使用,问有多少种安排的方法?,放球问题,另解:把这样一个方法设想为r个不同的球和n-1个相同的盒间板的一个有序安排。,组合,无重组合可重组合从a,b,c中选取2个不同元素,选法数是多少?从a,b,c中选取5个元素,元素可以相同,选法数是多少?,3、无重组合(Combination),n个元素的r-
5、无重组合数无重组合数与无重排列数的关系计算r=0时r=n时rn时,组合数的推广,几个记号,下阶乘函数,上阶乘函数,计算,例题,如果一个凸十边形无三条对角线在这个十边形的内部交于一点,问这些对角线被它们的交点分成多少条线段?,多边形,例题,对角线的条数为C(10,2)-10=45-10=35任选两条对角线,可能相交在多边形内部,可能交点为多边形的顶点,可能无交点(交点在多边形外)任选四个顶点,对应一个交点,每个对角线分成两段每个对角线是一段35+C(10,4) 2=455,例题,C(5,2)-5+C(5,4) 2=15,C(10,2)-10+C(10,4) 2=455,C(4,2)-4+C(4,
6、4) 2=4,4、可重组合,n个元素的r-可重组合例子计算一一对应的思想,推论,方程x1+x2+xn=r 的非负整数解的个数。nr时,此方程的正整数解的个数n元集合的r-可重组合数,要求每个元素至少出现一次。正整数r的n-长有序分拆的个数求x1+x2+x3+x4=20的整数解的数目,其中x1 3, x2 1,x3 0,x4 5。,例题,从为数众多的一分币、二分币、一角币和二角币中,可以有多少种方法选出六枚来?F(4,6)=C(4+6-1,6)=C(9,6)=84,例题,某糕点厂将8种糕点装盒,若每盒有一打糕点,求市场上能买到多少种该厂出品的盒装糕点?某糕点厂将8种糕点装盒,若每盒有一打糕点,且
7、要求每种糕点至少放一块。求市场上能买到多少种该厂出品的盒装糕点?,例题,摇三个不同的骰子的时候,可能的结果的个数是多少?63=216。如果这三个骰子是没有区别的,则可能结果的个数是多少?从1,2,3,4,5,6这六个数中允许重复地选出三个数。F(6,3)=C(6+3-1,3)=56将r个骰子掷一次,总共可以掷出多少种不同结果?F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5),有约束条件的排列:引例,用两面红旗、三面黄旗依次悬挂在一根旗杆上,问可以组成多少种不同的标志?,5、有约束条件的排列,设有k个元素a1,a2,ak,由它们组成一个n-长的排列,其中对1ik,ai出现的
8、次数为ni,n1+n2 + +nk=n,求排列的总数。求解方法1求解方法2,例题,五条短划和八个点可以安排成多少种不同的方式?如果只用这十三个短划和点中的七个,则有多少种不同的方式?,例题,证明对任意正整数k,(k!)!能被(k!)(k-1)!整除。提示:k!个物体,其中k个物体属于第一类,k个物体属于第二类, ,k个物体属于第(k-1)!类。,推论,多项式(x1+x2+xn)r的展开式中有 项,其中项 的系数为 。,例题,数1400有多少个正因数?1400=23 52 7(3+1)(2+1)(1+1)=24,放球问题,设nr,把r个相同的球放入n个不同的盒子使得每盒至多装一个球,方法数?选盒
9、子即可C(n,r),放球问题,把r个相同的球放入n个不同的盒子,每盒可以装任意多个球,方法数?放这r个球,等价于从n个盒中选出r个来装这r个球而允许诸盒重复选取。F(n,r)=C(n+r-1,r),放球问题,把r个相同的球放入n个不同的盒子,每盒可以装任意多个球,方法数?另解:把分配这r个球入n个盒子设想为这r个球和n-1个隔板的一个排列。球是相同的,隔板也是相同的。C(n+r-1,r),放球问题,设r n,把r个相同的球放入n个不同的盒子中,盒子中可以放入任意多个球,但不允许空盒,方法数?现在每个盒中放入一个球,再放剩下的r-n个球C(r-n)+n-1,r-n)=C(r-1,r-n)=C(r
10、-1,n-1),放球问题,设r n,把r个相同的球放入n个不同的盒子中,要求每一盒至少包含q个球,方法数?现在每个盒中放入q个球,再放剩下的r-qn个球C(r-qn)+n-1,r-qn)=C(n-nq+r-1,r-nq)= C(n-nq+r-1,n-1),放球问题:例题,今有五封不同的信要经由一个讯道传送。又有总共15个空白要插在这些信之间而使得每两封信之间至少有三个空白。有多少种方法安排这些信和空白?信的安排5!对一种信的安排,有4个信件位置,安排15个空白,要求每个信件位置至少有三个空白。5!C(4-4 3+15-1,4-1)=5!C(6,3),放球问题,有n个球,其中第一种颜色n1个,第
11、二种颜色n2个, ,第k种颜色nk个。将这n个球放入n个不同的盒中,每一个盒装一个球。问分配方案数?等价于这n个球的排列数。另解:选盒子装每种颜色的球。,放球问题,有r个球,其中第一种颜色n1个,第二种颜色n2个, ,第k种颜色nk个。将这r个球放入n个不同的盒中,每一个盒装一个球(rn)。问分配方案数?方法一:先选盒子,再分配球。方法二:针对每种颜色的球选盒子。,多重集合,通常的“集合”具有无重性。在多重集中,同一个元素可以出现多次。1,2,3是一个集合,而1,1,1,2,2,3不是一个集合,而是一个多重集,简记为31,22,13。计算多重集的势时,出现多次的元素则需要按出现的次数计算。上面
12、多重集的势为6。可重组合与可重排列可以看作是多重集的组合与排列问题。,可重排列与可重组合,n个元素a1,a2, ,an的r-无重组合(排列)可以看做多重集1a1, 1 a2, , 1 an的r-组合(排列) 。n个元素a1,a2, ,an的r-可重组合(排列)可以看做多重集a1, a2, , an的r-组合(排列) 。有限制的排列问题可以看做多重集n1a1, n2 a2, ,nk ak的全排列。,分组与分堆,区分:固定分组,将12本(不同的)书平均分给A,B,C,D四个学生,每人三本,有多少种分法?将12本书分给四个学生,使得A,B各得四本,C,D各得2本,有多少种分法?将12本书分给四个学生
13、,A得5本,B得4本,C得2本, D得1本,有多少种分法?,区分:分堆,将12本书平均分成四堆有多少种分法?将12本书分成四堆,有两堆各4本,另外两堆各2本,有多少种分法?将12本书分成四堆,其本数分别为5,4,2,1,有多少种分法?,区分:不固定分组,将12本书平均分给A,B,C,D四个学生,使得每人各得三本,有多少种分法?将12本书分给A,B,C,D四个学生,使得有两个学生各得4本,有两个学生各得2本,有多少种分法?将12本书分给A,B,C,D四个学生,使得有1人得5本,有一人得4本,有1人得两本,有1人得1本,有多少种分法?,分组与分堆,固定分组:无序分组:分堆不定分组固定分组与分堆的区
14、别是讲不讲组间的次序,只在各组元素个数相等时有区别固定分组与不定分组的区别是每个组的元素个数是不是确定,只在各组元素个数不等时才有区别。,区分(一),将12本书分给四个学生,使得A,B各得四本,C,D各得2本,有多少种分法?将12本书分成四堆,有两堆各4本,另外两堆各2本,有多少种分法?将12本书分给A,B,C,D四个学生,使得有两个学生各得4本,有两个学生各得2本,有多少种分法?,区分(二),将12本书分给四个学生,A得5本,B得4本,C得2本, D得1本,有多少种分法?将12本书分成四堆,其本数分别为5,4,2,1,有多少种分法?将12本书分给A,B,C,D四个学生,使得有1人得5本,有一
15、人得4本,有1人得两本,有1人得1本,有多少种分法?,区分(三),将12本书平均分给A,B,C,D四个学生,每人三本,有多少种分法?将12本书平均分成四堆有多少种分法?将12本书平均分给A,B,C,D四个学生,使得每人各得三本,有多少种分法?,限距组合:引例,书架上有1-24共24卷百科全书,从其中选5卷使得任何两卷都不相继,这样的选法有多少种?,6、限距组合,设A=1,2,n,它的任一r-无重组合均可以依自然顺序排出a1,a2, ,ar,其中a1a2 ar 。设k是非负整数,用f(k,n,r)表示A的一切满足条件ai+1-aik+1(1ir-1)的r-无重组合数,求f(k,n,r)。求解思想
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排列组合 公式 ppt 课件
链接地址:https://www.31ppt.com/p-1758390.html