《组合数学学习.pptx》由会员分享，可在线阅读，更多相关《组合数学学习.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1种选择方法，由于必须分成两组，去掉其中的：共有：1022种，又因为每个人的年龄可以是1到60中的任意一个，年龄和年龄和可能的分布共：6010=600种，因此，相当于1022个物体放在600个盒子，由鸽巢原理，至少有两组分配在同一盒子中，在同一个盒子中的两组的年龄和必然相等；若将人数降为9人，共有29-2=510种，分配给609=540个盒子，不能得到题意的要求。第1页/共40页2第三章第三章 排列与组合排列与组合 3.2 集合的排列定义:设n元集S=a1,a2,an，从S中取出r个不同元素按次序排列，称为S的一个r-排列，其个数称为r-排列数，记作P(n,r)或 。当n=r时，S的r-排列又
2、称S的全排列，其个数P(n,n)又称全排列数。r-排列就是将r个元素有序摆放。第2页/共40页3例：如果集合 S=a,b,c，则S的3个1-排列是 a,b,c P(3,1)=3 S的6个2-排列是:ab,ac,ba,bc,ca,cb P(3,2)=6 S的6个3-排列是:abc,acb,bac,bca,cab,cba P(3,3)=6 S没有4-排列及其以上的排列,因为S中最多只有3个元素。排列的特征在于排出的字符串一定有顺序之分字符串一定有顺序之分。第3页/共40页4 定理3.2.1 对于正整数n和r，若 r n，则 P(n,r)n(n1)(nr1)即:我们定义n!（读作n的阶乘阶乘）为：n
3、!=n(n1)2 1 并约定0!=1第4页/共40页5 例例1字字母母ABCDEFABCDEF的的排排列列中中有有多多少少个个包包含含子子串串 DEF?DEF?解：为了保证解：为了保证DEFDEF出现在子串中，这三个字母必须出现在子串中，这三个字母必须连在一起且保持这个顺序连在一起且保持这个顺序,可以将可以将DEF DEF 看成一个字看成一个字符。剩余的字母符。剩余的字母A,BA,B和和C C可以放置在任意的位置。可以放置在任意的位置。可以把构造包含子串可以把构造包含子串DEFDEF的的ABCDEFABCDEF的排列看作四个的排列看作四个标号标号DEF,A,B,CDEF,A,B,C的排列的排列
4、.由全排列定义，由全排列定义，第5页/共40页6四个对象有4 4！个排列。于是包含子串DEFDEF的ABCDEFABCDEF的排列数为4 4！=24=24。DEF A B C例2:ABCDEF的包含字母DEF不间隔任意顺序任意顺序 的排列有多少个？第6页/共40页7 我们可以通过两步来解决这个问题：选择字母DEF为一个子字符串，构造DEF的一个任意顺序的排列。由全排列定义，第一步有3！=6种方法，根据例1，第二步可以有24种方法。根据乘法原理，ABCDEF的包含字母DEF的任意顺序的排列数为：624=144第7页/共40页8 例3:七个男人和五个女人坐一排开会，如果不允许两个女人坐在一起(可能
5、是因为她们开会喜欢说话)，有多少种方法？解:我们可以用两步将男人和女人排列起来：先排列男人，再排列女人。男人有7！=5040种排法，一旦我们已经排好男人，因为不能有两个女人站在一起，女人有八个可能的位置可以站：第8页/共40页9 _M1_M2_M3_M4_M5_M6_M7_ （这样就保证了女人不相邻）因此女人有P(8,5)=87654=6720种排列方法。根据乘法原理，七个男人和五个女人坐一排开会，如果不能有两个女人站在一起，共有：50406270=33868800种方法。第9页/共40页10例4 有多少取自1,2,9的各位互异的7位数 使得5和6不以任何顺序相继出现？解法一 1,2,9的7-
6、排列中满足要求的可被分成4类：1）5，6均不出现。即1,2,3,4,7,8,9的7-排序P(7,7)第10页/共40页11 2）5出现6不出现。即5有7个位置，其余是1,2,3,4,7,8,9的6-排列 7P(7,6)3）5不出现6出现。即5有7个位置，其余是1,2,3,4,7,8,9的6-排列 7P(7,6)第11页/共40页124）5与6同时出现，但是 a）第1位等于5。此时6有5个位置，其余是1,2,3,4,7,8,9的5-排列:5P(7，5)b）第7位等于5。此时6有5个位置，其余是1,2,3,4,7,8,9的5-排列:5P(7，5)c）5出现在首尾之外的位置上。第12页/共40页13
7、此时，5有5个位置可选。对于每种5的选择，6仅 有4个位置可选。其余5位是1,2,3,4,7,8,9的5-排列。于是 54P(7，5)综上所述，结论为 P(7,7)7P(7,6)25P(7,5)2 54P(7,5)151200第13页/共40页14解法二 令T是1,2,.,9的所有7-排序的集合。现对T构造划分S和 ,其中S是满足要求的7位数的集合，而 T=S T =S +所以 S=T 而 T P(9,7);26P(7,5)故 S P(9,7)26P(7,5)151200 5,6作为相连子串有:56或65之分,共有6个位置放。第14页/共40页15 以上我们讨论的是线性排列线性排列。例如1，2
8、，3，4，5，6 的两个6-排列：5 6 1 2 3 4 与 2 3 4 5 6 1 是两个不同的排列。但是，如果我们把每个排列各自的首尾相接起来，所形成的两个“环”就没有什么不同。此时，1我们称它们属于同 2 6一个循环排列循环排列。3 5他们是右图：4第15页/共40页16 上述循环排列可以从下列线性排列得到：123456 234561 345612 456123 561234 612345 其中的每一个通过将第一元素看成接在最后一个元素后面的元素产生。这样，要想求得循环排列的数目，我们只要用6 6去除线性排列去除线性排列的数目即可。故上述元素的循环排列数为：6!/6=5!=120第16页
9、/共40页17定理3.3.2 n个元素的集合的循环r-排列的个数是 特别地，n个元素的循环排列的个数是(n-1)!例5：10个人要围坐一圆桌，其中有两人不愿意彼此挨着座。共有多少种循环座位按排方法？解法一 将这两个人挨着座，看成一个元素，共9个元素的循环排列有：9!/9=8!种；这两个人挨着座又有左右之分，总共应该有:28!种;题意的安排为：10!/10 28!=78!第17页/共40页18 解法二 我们把不愿意彼此挨着座的两人设为：A,B 。假设A固定位置不动，B就不能排在A的左右，A的左边只能余下的8个人，同时 A的右边只能再余下的7个人,其他7个位置的安排可以 是：7!种满足题意的排法共
10、：877!=78!A.。DC非B.非B第18页/共40页19例6 将12个不同的记号记在旋转的圆鼓上的方法 有：12!/12 =11!种例7 用20个不同的珠子穿成一条项链，能够做成多少不同的项链？解：20个珠子共有20！种不同的排列。由于是做成项链，属于循环排列，项链数目最多为：20！/20=19！；又由于项链可以翻转而珠子的排列未改动，因此项链的总数是：19！/2第19页/共40页20 生成生成n!个全排列的错位置排法个全排列的错位置排法 当n=1，排列方式只有一种，就是1。当n=2时，先将唯一的1-排列1写出两次，并错位置以2，即得两个2排列如下：1 2 2 1 当n=3时,先将两个2-
11、排列分别写出3次,共6次第20页/共40页21并错位置以3，即得3!=6个3排列如下：1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3 当n=4 时,先将6个3排列分别写出4次,并错位置以4,即得4!=24个4排列.(请仿上法自己写出)第21页/共40页22与彩票选号一样,从1-1-33中第22页/共40页23 集合的组合集合的组合 定义:设n元集S=a1,a2,an，从S中无序选择取出r个不同元素作为S 的一个子集，称为S的一个r-组合组合，其个数称为r-组合数组合数，记作C(n,r)或 =例：S=a,b,c,d,那么S的3-组合是：a,b,c,a,b,d,a,c,d,
12、b,c,d;组合数第23页/共40页24 组合数中显然有下列结论：1.当rn时 2.当r0时 3.几个特殊的组合数第24页/共40页25 定理3.3.1 对于0 r n 有 从而 证明：由定义r-组合与r-排列的区别在于前者不计较元素的先后顺序，因此由每个r组合可以作出r！个不同的r-排列。即先完成组合再排列第25页/共40页26 于是若有C(n,r)种r组合，则有C(n,r)r!种排 列,因此C(n,r)r!=P(n,r)。例 8 在平面上给出25个点，没有三点共线，问这些点能够成多少直线？能确定多少三角形？解：由于没有三点共线，25个点中任意2个点就能连成一条线，有：第26页/共40页27
13、 同理，25个点中任意3个点就能连成一三角形，有：例 9 从五个女生和六个男生中选出一个由两个女生和三个男生组成的委员会有多少种方法?解：两个女生可以有C(5,2)=10种选法,而三个男生可以有C(6,3)=20种选法。委员会可以有两步顺序构成:选择女生,选择男生。根据乘法原理,委员会总共可以有1020=200种选法。第27页/共40页28例:从133这33个连续的自然数中任意选出7个数为彩票号码,共有C(33,7),大约四百多万组号码。这里面肯定包含了所有的奖项，包括5000000圆的大奖，但是我们不能花八百多万去夺取这个大奖；彩迷们都希望将大奖的范围尽可能缩的更小，这就给研究随机问题的数学
14、家提出挑战。第28页/共40页29例10 用26个英文字母能构成多少个含有3个、4 个或5个元音的长为8位的单词？其中，每个字母出现在单词中的次数不限。解 对于含有3个元音8位单词,单词中任三位都可是元音，先调出元音位置共有C(8,3)个,26个英文字母共有5个元音字母，每个位置有5种可能共53种放置法，其余5位都是辅音有215种可能，从而具有3个元音的单词数为:第29页/共40页30同理，含有4个元音的单词数为 含有 5 个元音的单词数为 从而，满足题设的单词共有:第30页/共40页31例11 恰好包含四个1的八位二进制串有多少个?解：在8个位置中给1任找4个位置，不关0,1的顺序共有例12
15、 一副52张的普通纸牌由梅花,方片,红心,黑桃四个花色的13种面额为A,2-10,J,Q,K的牌组成。第31页/共40页32 (a)从52张普通牌中选五张牌(无序)有多少种选法?(b)五张牌为同一花色的有多少种选法?(c)五张牌中的三张为一个面额而另外两张为另一个面额的选法有多少种?解(a)答案是C(52,5)=2598960 (b)要有同一花色的五张牌可以经过两步:选择花色,再从这种花色中选择五张牌。第一步有4种第32页/共40页33方法而第二步有C(13,5)种方法。根据乘法原理，答案为4C(13,5)=5148(c)要有3张为一个面额而另外两张为另一个面额的五张牌，可以经过四步来选取：选
16、择第一种面额，再选择第二种面额，选择第一种面额的三张牌，选择第二种面额的两张牌。第一种面额有13种选法，选了第一种面额之后，第二种面额有12种选法。从第一种面额中选择不同花色的三张牌有第33页/共40页34C(4,3)种方法，而从第二种面额中选择不同花 色的二张牌有C(4,2)种方法。根据乘法原理，答案为：1312C(4,3)C(4,2)=3744推论：对于0 r n 有:证明很简单，请同学们自己完成第34页/共40页35定理3.3.2 n个元素的集合的所有组合的总数是 即 证明:因为S的r-组合的个数是:r0,1,2,n 所以 S的所有组合的总数是:第35页/共40页36另一方面，若Sx1,
17、x2,xn，则S的一个组合 是由S中的若干元素构成，要么xi在其中，要么xi不在其中，i=1,2,n。每个xi都有两种不同的选择，n个元素中选取1,2,n个元素的不同组合数的总数是：22 2 =2n 综上所述，我们有:本结论在以后也可以 由二项式定理证第36页/共40页37总总 结结 本次课我们介绍了从n个元素的集合中选出r元素的排列和组合方法以及排列数和组合数的求法，它们最大的区别在于，排列于元素顺序有关，而组合于顺序无关。求排列数和组合数的有固定的方法。第37页/共40页38本次授课到此结束作作业如下如下:P47 7,8,147.六男六女围坐一个圆桌。如果男女交替围坐，可有多少围坐方式？8.15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方法？如果B只拒绝坐在A的右侧，又有多少种围坐方法？第38页/共40页39 14.在一次聚会上有在一次聚会上有15位男士和位男士和20位女士。位女士。1）有多少种方式形成）有多少种方式形成15对男女？对男女？2）有多少种方式形成）有多少种方式形成10对男女？对男女？下次上下次上课内容：内容：3.4 多重集的排列多重集的排列 3.5 多重集的多重集的组合合第39页/共40页40感谢您的观看！第40页/共40页