组合数学4PPT课件

《组合数学4PPT课件》由会员分享，可在线阅读，更多相关《组合数学4PPT课件（41页珍藏版）》请在装配图网上搜索。

1、2021/6/71 P13练习题练习题9 一间屋子内有一间屋子内有10个人，他们中没有人年龄超个人，他们中没有人年龄超过过60岁，但又至少不低于岁，但又至少不低于1岁。证明，总能找到岁。证明，总能找到两组人（两组不含相同的人），各组人的年龄两组人（两组不含相同的人），各组人的年龄和是相同。题中的数和是相同。题中的数10能换成更小的吗？能换成更小的吗？解：从解：从10个人中任意选个人中任意选0到到10人为一组，则共有：人为一组，则共有：1021010.2101100102021/6/72种选择方法，由于必须分成两组，去掉其中的：种选择方法，由于必须分成两组，去掉其中的：共有：共有：1022种，又

2、因为每个人种，又因为每个人的年龄可以是的年龄可以是1到到60中的任意一个，中的任意一个，年龄和年龄和可可能的分布共：能的分布共：6010=600种，因此，相当于种，因此，相当于1022个物体放在个物体放在600个盒子，由鸽巢原理，至个盒子，由鸽巢原理，至少有两组分配在同一盒子中，在同一个盒子中少有两组分配在同一盒子中，在同一个盒子中的两组的年龄和必然相等；的两组的年龄和必然相等；若将人数降为若将人数降为9人，共有人，共有29-2=510种，分配种，分配给给609=540个盒子，不能得到题意的要求。个盒子，不能得到题意的要求。210100102021/6/73第三章第三章 排列与组合排列与组合

3、3.2 集合的排列集合的排列定义定义:设设n元集元集S=a1,a2,an，从，从S中取出中取出r个不个不同元素按次序排列，称为同元素按次序排列，称为S的一个的一个r-排列排列，其个，其个数称为数称为r-排列数排列数，记作，记作P(n,r)或或 。当。当n=r时，时，S的的r-排列又称排列又称S的的全排列全排列，其个数，其个数P(n,n)又称又称全全排列数排列数。r-排列就是将排列就是将r个元素有序摆放。个元素有序摆放。rnp2021/6/74例：如果集合例：如果集合 S=a,b,c，则，则S的的3个个1-排列是排列是 a,b,c P(3,1)=3 S的的6个个2-排列是排列是:ab,ac,ba

4、,bc,ca,cb P(3,2)=6 S的的6个个3-排列是排列是:abc,acb,bac,bca,cab,cba P(3,3)=6 S没有没有4-排列及其以上的排列排列及其以上的排列,因为因为S中最多中最多只有只有3个元素。个元素。排列的特征在于排出的排列的特征在于排出的字符串一定有顺序之分字符串一定有顺序之分。2021/6/75 定理定理3.2.1 对于正整数对于正整数n和和r，若，若 r n，则，则 P(n,r)n(n1)(nr1)即即:我们定义我们定义n!（读作（读作n的的阶乘阶乘）为：）为：n!=n(n1)2 1 并约定并约定0!=1)!(!),(rnnrnp)1()(110knkn

5、rkrk2021/6/76 例例1字母字母ABCDEFABCDEF的排列中有多少个包含子串的排列中有多少个包含子串 DEF?DEF?解：为了保证解：为了保证DEFDEF出现在子串中，这三个字母必须出现在子串中，这三个字母必须连在一起且保持这个顺序连在一起且保持这个顺序,可以将可以将DEF DEF 看成一个字看成一个字符。剩余的字母符。剩余的字母A,BA,B和和C C可以放置在任意的位置。可以放置在任意的位置。可以把构造包含子串可以把构造包含子串DEFDEF的的ABCDEFABCDEF的排列看作四个的排列看作四个标号标号DEF,A,B,CDEF,A,B,C的排列的排列.由全排列定义，由全排列定义

6、，2021/6/77四个对象有四个对象有4 4！个排列。于是包含子串！个排列。于是包含子串DEFDEF的的ABCDEFABCDEF的排列数为的排列数为4 4！=24=24。DEF A B C例例2:ABCDEF的包含字母的包含字母DEF不间隔任意顺序不间隔任意顺序 的排列有多少个？的排列有多少个？2021/6/78 我们可以通过两步来解决这个问题：选择字我们可以通过两步来解决这个问题：选择字母母DEF为一个子字符串，构造为一个子字符串，构造DEF的一个任意的一个任意顺序的排列。由全排列定义，第一步有顺序的排列。由全排列定义，第一步有3！=6种方法，根据例种方法，根据例1，第二步可以有，第二步可

7、以有24种方法。根种方法。根据乘法原理，据乘法原理，ABCDEF的包含字母的包含字母DEF的任意的任意顺序的排列数为：顺序的排列数为：624=1442021/6/79 例例3:七个男人和五个女人坐一排开会，如果不七个男人和五个女人坐一排开会，如果不允许两个女人坐在一起允许两个女人坐在一起(可能是因为她们开会喜可能是因为她们开会喜欢说话欢说话)，有多少种方法？，有多少种方法？解解:我们可以用两步将男人和女人排列起来：先我们可以用两步将男人和女人排列起来：先排列男人，再排列女人。男人有排列男人，再排列女人。男人有7！=5040种排法，种排法，一旦我们已经排好男人，因为不能有两个女人站一旦我们已经排

8、好男人，因为不能有两个女人站在一起，女人有八个可能的位置可以站：在一起，女人有八个可能的位置可以站：2021/6/710 _M1_M2_M3_M4_M5_M6_M7_ （这样就保证了女人不相邻）（这样就保证了女人不相邻）因此女人有因此女人有P(8,5)=87654=6720种种排列方法。根据乘法原理，七个男人和五个女排列方法。根据乘法原理，七个男人和五个女人坐一排开会，如果不能有两个女人站在一起，人坐一排开会，如果不能有两个女人站在一起，共有：共有：50406270=33868800种方法。种方法。2021/6/711例例4 有多少取自有多少取自1,2,9的各位互异的的各位互异的7位数位数 使

9、得使得5和和6不以任何顺序不以任何顺序相继相继出现？出现？解法一解法一 1,2,9的的7-排列中满足要求的可被排列中满足要求的可被分成分成4类：类：1）5，6均不出现。均不出现。即即1,2,3,4,7,8,9的的7-排序排序P(7,7)2021/6/712 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)2021/6/7134）5与与6同时出现，但是同时出现，但是 a）第）第1位等于位

10、等于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出现在首尾之外的位置上。出现在首尾之外的位置上。2021/6/714此时，此时，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

11、54P(7,5)1512002021/6/715解法二解法二 令令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个位置放。个位置放。SSSSS2021/6/716 以上我们讨论的是以上我们讨论的是线性排列线性排列。例如例如1，2，3，4，5，6 的两个的两个6-排列：排列：5 6 1

12、2 3 4 与与 2 3 4 5 6 1 是两个不同的排列。但是，如果我们把每是两个不同的排列。但是，如果我们把每个排列各自的首尾相接起来，所形成的两个个排列各自的首尾相接起来，所形成的两个“环环”就没有什么不同。此时，就没有什么不同。此时，1我们称它们属于同我们称它们属于同 2 6一个一个循环排列循环排列。3 5他们是右图：他们是右图：42021/6/717 上述循环排列可以从下列线性排列得到：上述循环排列可以从下列线性排列得到：123456 234561 345612 456123 561234 612345 其中的每一个通过将第一元素看成接在最后一其中的每一个通过将第一元素看成接在最后一

13、个元素后面的元素产生。这样，要想求得循环个元素后面的元素产生。这样，要想求得循环排列的数目，我们只要用排列的数目，我们只要用6 6去除线性排列去除线性排列的数目的数目即可。故上述元素的循环排列数为：即可。故上述元素的循环排列数为：6!/6=5!=1202021/6/718定理定理3.3.2 n个元素的集合的循环个元素的集合的循环r-排列的个数是排列的个数是 特别地，特别地，n个元素的循环排列的个数是个元素的循环排列的个数是(n-1)!例例5：10个人要围坐一圆桌，其中有两人不愿意个人要围坐一圆桌，其中有两人不愿意彼此挨着座。共有多少种循环座位按排方法？彼此挨着座。共有多少种循环座位按排方法？解

14、法一解法一 将这两个人挨着座，看成一个元素，共将这两个人挨着座，看成一个元素，共9个元素的循环排列有：个元素的循环排列有：9!/9=8!种；这两个种；这两个人挨着座又有左右之分，总共应该有人挨着座又有左右之分，总共应该有:28!种种;题意的安排为：题意的安排为：10!/10 28!=78!！)(!),(rnrnrrnp 2021/6/719 解法二解法二 我们把不愿意彼此挨着座的两人设为：我们把不愿意彼此挨着座的两人设为：A,B 。假设。假设A固定位置不动，固定位置不动，B就不能排在就不能排在A的左右，的左右，A的左边只能余下的的左边只能余下的8个人，同时个人，同时 A的右边只能再余下的的右边

15、只能再余下的7个人个人,其他其他7个位置的安排可以个位置的安排可以 是：是：7!种满足题意的种满足题意的排法共：排法共：877!=78!A.。DC非非B.非非B2021/6/720例例6 将将12个不同的记号记在旋转的圆鼓上的方法个不同的记号记在旋转的圆鼓上的方法 有：有：12!/12 =11!种种例例7 用用20个不同的珠子穿成一条项链，能够做成个不同的珠子穿成一条项链，能够做成多少不同的项链？多少不同的项链？解：解：20个珠子共有个珠子共有20！种不同的排列。由于是做！种不同的排列。由于是做成项链，属于循环排列，项链数目最多为：成项链，属于循环排列，项链数目最多为：20！/20=19！；又

16、由于项链可以翻转而珠子的排列！；又由于项链可以翻转而珠子的排列未改动，因此项链的总数是：未改动，因此项链的总数是：19！/22021/6/721 生成生成n!个全排列的错位置排法个全排列的错位置排法 当当n=1，排列方式只有一种，就是，排列方式只有一种，就是1。当当n=2时，先将唯一的时，先将唯一的1-排列排列1写出两次，并写出两次，并错位置以错位置以2，即得两个，即得两个2排列如下：排列如下：1 2 2 1 当当n=3时时,先将两个先将两个2-排列分别写出排列分别写出3次次,共共6次次2021/6/722并错位置以并错位置以3，即得即得3!=6个个3排列如下：排列如下：1 2 3 1 3 2

17、 3 1 2 3 2 1 2 3 1 2 1 3 当当n=4 时时,先将先将6个个3排列分别写出排列分别写出4次次,并错位并错位置以置以4,即得即得4!=24个个4排列排列.(请仿上法自己写出请仿上法自己写出)2021/6/723与彩票选号一样与彩票选号一样,从从1-1-33中中2021/6/724 3.2 集合的组合集合的组合 定义定义:设设n元集元集S=a1,a2,an，从，从S中中无序无序选择取出选择取出r个不同元素作为个不同元素作为S 的一个子集，称为的一个子集，称为S的一个的一个r-组合组合，其个数称为，其个数称为r-组合数组合数，记作，记作C(n,r)或或 =例：例：S=a,b,c

18、,d,那么那么S的的3-组合是：组合是：a,b,c,a,b,d,a,c,d,b,c,d;组合数组合数rnCrn4342021/6/725 组合数中显然有下列结论：组合数中显然有下列结论：1.当当rn时时 2.当当r0时时 3.几个特殊的组合数几个特殊的组合数00r0rn1nnnn110n1002021/6/726 定理定理3.3.1 对于对于0 r n 有有 从而从而 证明：由定义证明：由定义r-组合与组合与r-排列的区别在于前者不计排列的区别在于前者不计较元素的先后顺序，因此由每个较元素的先后顺序，因此由每个r组合可以作出组合可以作出r！个不同的个不同的r-排列。即先完成组合再排列排列。即先

19、完成组合再排列rnrrnP!),()!(!),(rnrnrrnPrn2021/6/727 于是若有于是若有C(n,r)种种r组合，则有组合，则有C(n,r)r!种排种排 列列,因此因此C(n,r)r!=P(n,r)。例例 8 在平面上给出在平面上给出25个点，没有三点共线，问个点，没有三点共线，问这些点能够成多少直线？能确定多少三角形？这些点能够成多少直线？能确定多少三角形？解：由于没有三点共线，解：由于没有三点共线，25个点中任意个点中任意2个点就个点就能连成一条线，有：能连成一条线，有：300224*25)!225(!2!252252021/6/728 同理，同理，25个点中任意个点中任意

20、3个点就能连成一三角形，个点就能连成一三角形，有：有：例例 9 从五个女生和六个男生中选出一个由两个从五个女生和六个男生中选出一个由两个女生和三个男生组成的委员会有多少种方法女生和三个男生组成的委员会有多少种方法?解：两个女生可以有解：两个女生可以有C(5,2)=10种选法种选法,而三个男而三个男生可以有生可以有C(6,3)=20种选法。委员会可以有两步种选法。委员会可以有两步顺序构成顺序构成:选择女生选择女生,选择男生。根据乘法原理选择男生。根据乘法原理,委员会总共可以有委员会总共可以有1020=200种选法。种选法。!22!3!25)!325(!3!253252021/6/729例例:从从

21、133这这33个连续的自然数中任意选出个连续的自然数中任意选出7个个数为彩票号码数为彩票号码,共有共有C(33,7),大约四百多万组号大约四百多万组号码。这里面肯定包含了所有的奖项，包括码。这里面肯定包含了所有的奖项，包括5000000圆的大奖，但是我们不能花八百多万圆的大奖，但是我们不能花八百多万去夺取这个大奖；去夺取这个大奖；彩迷们都希望将大奖的范围尽可能缩的更彩迷们都希望将大奖的范围尽可能缩的更小，这就给研究随机问题的数学家提出挑战。小，这就给研究随机问题的数学家提出挑战。2021/6/730例例10 用用26个英文字母能构成多少个含有个英文字母能构成多少个含有3个、个、4 个或个或5个

22、元音的长为个元音的长为8位的单词？其中，每个位的单词？其中，每个字母出现在单词中的次数不限。字母出现在单词中的次数不限。解解 对于含有对于含有3个元音个元音8位单词位单词,单词中任三位都可单词中任三位都可是元音，先调出元音位置共有是元音，先调出元音位置共有C(8,3)个个,26个个英文字母共有英文字母共有5个元音字母，每个位置有个元音字母，每个位置有5种可种可能共能共53种放置法，其余种放置法，其余5位都是辅音有位都是辅音有215种可种可能，从而具有能，从而具有3个元音的单词数为个元音的单词数为:2021/6/731同理，含有同理，含有4个元音的单词数为个元音的单词数为 含有含有 5 个元音的

23、单词数为个元音的单词数为 从而，从而，满足题设的单词共有满足题设的单词共有:5353215)!38(!3!8215384444215)!48(!4!8215483535215)!58(!5!8215582021/6/732例例11 恰好包含四个恰好包含四个1的八位二进制串有多少个的八位二进制串有多少个?解：在解：在8个位置中给个位置中给1任找任找4个位置，不关个位置，不关0,1的顺序的顺序共有共有例例12 一副一副52张的普通纸牌由梅花张的普通纸牌由梅花,方片方片,红心红心,黑桃黑桃四个花色的四个花色的13种面额为种面额为A,2-10,J,Q,K的牌组成。的牌组成。354453215!3!5!

24、8215!4!4!8215!5!3!8个702345678!4!4!8482021/6/733 (a)从从52张普通牌中选五张牌张普通牌中选五张牌(无序无序)有多少种选法有多少种选法?(b)五张牌为同一花色的有多少种选法五张牌为同一花色的有多少种选法?(c)五张牌中的三张为一个面额而另外两张五张牌中的三张为一个面额而另外两张为另一个面额的选法有多少种为另一个面额的选法有多少种?解解(a)答案是答案是C(52,5)=2598960 (b)要有同一花色的五张牌可以经过两步要有同一花色的五张牌可以经过两步:选择选择花色花色,再从这种花色中选择五张牌。第一步有再从这种花色中选择五张牌。第一步有4种种2

25、021/6/734方法而第二步有方法而第二步有C(13,5)种方法。根据乘法原理，种方法。根据乘法原理，答案为答案为4C(13,5)=5148(c)要有要有3张为一个面额而另外两张为另一个面额的张为一个面额而另外两张为另一个面额的五张牌，可以经过四步来选取：选择第一种面额五张牌，可以经过四步来选取：选择第一种面额，再选择第二种面额，选择第一种面额的三张牌，再选择第二种面额，选择第一种面额的三张牌，选择第二种面额的两张牌。第一种面额有，选择第二种面额的两张牌。第一种面额有13种种选法，选了第一种面额之后，第二种面额有选法，选了第一种面额之后，第二种面额有12种种选法。从第一种面额中选择不同花色的

26、三张牌有选法。从第一种面额中选择不同花色的三张牌有2021/6/735rnnrnC(4,3)种方法，而从第二种面额中选择不同花种方法，而从第二种面额中选择不同花 色的二张牌有色的二张牌有C(4,2)种方法。根据乘法原理，种方法。根据乘法原理，答案为答案为：1312C(4,3)C(4,2)=3744推论：推论：对于对于0 r n 有有:证明很简单，请同学们自己完成证明很简单，请同学们自己完成2021/6/736定理定理3.3.2 n个元素的集合的所有组合的总数是个元素的集合的所有组合的总数是 即即 证明证明:因为因为S的的r-组合的个数是组合的个数是:r0,1,2,n 所以所以 S的所有组合的总

27、数是的所有组合的总数是:nnnnnn2.210nnrrn20rnnrrn02021/6/737另一方面，若另一方面，若Sx1,x2,xn，则，则S的一个组合的一个组合 是由是由S中的若干元素构成，要么中的若干元素构成，要么xi在其中，在其中，要么要么xi不在其中，不在其中，i=1,2,n。每个。每个xi都有两都有两种不同的选择，种不同的选择，n个元素中选取个元素中选取1,2,n个元个元素的不同组合数的总数是：素的不同组合数的总数是：22 2 =2n 综上所述，我们有综上所述，我们有:本结论在以后也可以本结论在以后也可以 由二项式定理证由二项式定理证nnrrn202021/6/738总总 结结

28、本次课我们介绍了从本次课我们介绍了从n个元素的集合中个元素的集合中选出选出r元素的排列和组合方法以及排列数和元素的排列和组合方法以及排列数和组合数的求法，它们最大的区别在于，排列组合数的求法，它们最大的区别在于，排列于元素顺序有关，而组合于顺序无关。于元素顺序有关，而组合于顺序无关。求排列数和组合数的有固定的方法。求排列数和组合数的有固定的方法。2021/6/739本次授课到此结束本次授课到此结束作业如下作业如下:P47 7,8,147.六男六女围坐一个圆桌。如果男女交替围坐，六男六女围坐一个圆桌。如果男女交替围坐，可有多少围坐方式？可有多少围坐方式？8.15人围坐一个圆桌。如果人围坐一个圆桌。如果B拒绝挨着拒绝挨着A坐，坐，有多少种围坐方法？如果有多少种围坐方法？如果B只拒绝坐在只拒绝坐在A的右的右侧，又有多少种围坐方法？侧，又有多少种围坐方法？2021/6/740 14.在一次聚会上有在一次聚会上有15位男士和位男士和20位女士。位女士。1）有多少种方式形成）有多少种方式形成15对男女？对男女？2）有多少种方式形成）有多少种方式形成10对男女？对男女？下次上课内容：下次上课内容：3.4 多重集的排列多重集的排列 3.5 多重集的组合多重集的组合部分资料从网络收集整理而来，供大家参考，感谢您的关注！