《概率论（第四版）》课件预备知识-排列组合.pptx

1、一、基本原理一、基本原理 例例1 12从甲村到乙村共有两类方式从甲村到乙村共有两类方式:第第1类方式是走旱路类方式是走旱路,有有3条路线条路线;第第2类方式是走水路类方式是走水路,有有2条路线条路线,如图预如图预-1.问从甲村到乙村共有多少种走法问从甲村到乙村共有多少种走法?例例1 13解:完成从甲村到乙村这件事情,走旱路与走水路这两类方式是并列的,沿着它们中的每一条路线都可以到达目的地这样的例子是很多的,概括起来,就得到加法原理加法原理因此从甲村到乙村共有3+2=5种走法加法原理加法原理4加法原理加法原理完成一件事情共有r类方式:第1类方式有m1种方法,第2类方式有m2种方法,第r类方式有m

2、r种方法则完成这件事情共有m1+m2+mr种方法例例2 25从甲村到丙村必须经过乙村从甲村到丙村必须经过乙村,而从甲村到乙村有而从甲村到乙村有5条条路线路线,从乙村到丙村有从乙村到丙村有4条路线条路线,如图如图0-2.问从甲村到问从甲村到丙村共有多少种走法丙村共有多少种走法?例例2 26解:完成从甲村到丙村这件事情,必须依次经过两个步骤:第1个步骤是从甲村到乙村,有5条路线 第2个步骤是从乙村到丙村,有4条路线只有这两个步骤都完成了,才能到达目的地,缺少哪一个步骤都不行例例2 27由于从甲村到乙村的每一条路线都对应从甲村到丙村的4条路线这样的例子是很多的,概括起来,就得到乘法原理乘法原理因此从

3、甲村到丙村共有54=20种走法乘法原理乘法原理8乘法原理乘法原理完成一件事情必须依次经过l个步骤:第1个步骤有n1种方法 第2个步骤有n2种方法 第l个步骤有nl种方法则完成这件事情共有n1n2nl种方法加法加法原理与乘法原理的区别原理与乘法原理的区别9在应用基本原理时,必须注意加法原理与乘法原理的根本区别.若完成一件事情有多类方式,其中每一类方式的任一种方法都可以完成这件事情,则用加法原理加法原理 若完成一件事情必须依次经过多个步骤,缺少其中任一个步骤都不能完成这件事情,则用乘法原理乘法原理例例3 310某班共有某班共有26名同学名同学,分成分成3个组个组,其中第一组有其中第一组有9名同名同

4、学学,第二组有第二组有8名同学名同学,第三组有第三组有9名同学名同学,现在全校举现在全校举行歌咏比赛行歌咏比赛,每名同学都有资格参加每名同学都有资格参加.问问:(1)若从全班选派若从全班选派1名同学参加全校歌咏比赛名同学参加全校歌咏比赛,共有多共有多少种选法少种选法?(2)若从每组各选派若从每组各选派1名同学参加全校歌咏比赛名同学参加全校歌咏比赛,共有共有多少种选法多少种选法?例例3 311解:(1)完成从全班选派1名同学参加全校歌咏比赛这件事情,共有三类方式:第1类方式是从第一组选派1名同学参加全校歌咏比赛,有9种选法 第2类方式是从第二组选派1名同学参加全校歌咏比赛,有8种选法 第3类方式

5、是从第三组选派1名同学参加全校歌咏比赛,有9种选法例例3 312这三类方式是并列的,其中每一类方式的任一种选法都可以完成这件事情根据加法原理,所以从全班选派1名同学参加全校歌咏比赛共有9+8+9=26种选法其实,从全班26名同学中选派1名同学参加全校歌咏比赛,当然有26种选法例例3 313(2)完成从每组各选派1名同学参加全校歌咏比赛这件事情,必须依次经过三个步骤:第1个步骤是从第一组选派1名同学参加全校歌咏比赛,有9种选法 第2个步骤是从第二组选派1名同学参加全校歌咏比赛,有8种选法 第3个步骤是从第三组选派1名同学参加全校歌咏比赛,有9种选法例例3 314这三个步骤是必须依次完成的,缺少其

6、中任一个步骤都不能完成这件事情根据乘法原理,所以从每组各选派1名同学参加全校歌咏比赛共有989=648种选法二、元素不重复的排列二、元素不重复的排列 例例4 415用用3个数字个数字5,7,9可以组成多少个数字不重复的两位可以组成多少个数字不重复的两位数数?解:组成数字不重复的两位数,必须依次经过两个步骤:第1个步骤是确定十位数,这时数字5,7,9都可以放在十位上,有3种方法 第2个步骤是确定个位数,由于要求个位数与十位数不能重复,这时只能从所给3个数字去掉放在十位上的数字后剩余2个数字中取出1个数字放在个位上,有2种方法例例4 416只有这两个步骤都完成了,才能组成数字不重复的两位数,缺少哪

7、一个步骤都不行根据乘法原理,所以组成数字不重复的两位数共有32=6种方法即可以组成6个数字不重复的两位数,它们是57,59,75,79,95,97例例4 417在例4中,数字5,7,9可以称为元素,组成数字不重复的两位数就是从这3个不同元素中每次取出2个不同元素排队,排在前面的是十位数,排在后面的是个位数由于这样的排列与数字不重复的两位数是一一对应的,因此求数字不重复两位数的个数等价于求这样排列的个数排列数排列数18定义定义0 0.1 1如何计算排列数如何计算排列数19从n个不同元素中取出m个不同元素排成一列,必须依次经过m个步骤:第1个步骤是确定排列第1位置上的元素,这时是从n个不同元素中取

8、出1个元素放在这个位置上,有n种方法 第2个步骤是确定排列第2位置上的元素,考虑到排列第1位置上已经占用了1个元素,这时是从剩余的n-1个不同元素中取出1个元素放在这个位置上,有n-1种方法如何计算排列数如何计算排列数20 第m个步骤是确定排列第m位置上的元素,考虑到排列前m-1个位置上已经占用了m-1个元素,这时是从剩余的n-(m-1)=n-m+1个不同元素中取出1个元素放在这个位置上,有n-m+1种方法如何计算排列数如何计算排列数21根据乘法原理,共有n(n-1)(n-m+1)种方法由于一种方法对应一个排列,所以所有这样排列的个数即排列数 若mn,则称排列为选排列例例5 522根据排列数的

9、计算公式,有排列数例例6 623从从10人中选举正副组长各人中选举正副组长各1名名,问共有多少种选举结问共有多少种选举结果果?解:从10人中选举正副组长各1名,意味着从10人中选出2人排队值得注意的是值得注意的是:在甲、在甲、乙都当选的情况下乙都当选的情况下,甲为正组长、乙为副甲为正组长、乙为副组长与乙为正组长、组长与乙为正组长、甲为副组长是两种选甲为副组长是两种选举结果举结果.例例7 7246台不同品牌的洗衣机摆在展厅内排成一列台不同品牌的洗衣机摆在展厅内排成一列,问问:(1)共有多少种排法共有多少种排法?(2)若要求其中某一台洗衣机摆在中间位置若要求其中某一台洗衣机摆在中间位置,有多少有多

10、少种排法种排法?解:(1)6台不同品牌的洗衣机排成一列,相当于从6个不同元素中每次取出6个不同元素的元素不重复全排列例例7 725(2)要求6台不同品牌洗衣机中某一台洗衣机摆在中间位置,必须依次经过两个步骤:第1个步骤是将这台洗衣机摆在中间位置中的一个位置,有2种方法例例7 726根据乘法原理,有种方法,即有240种排法例例8 827小赵、小钱、小孙、小李及小周五位青年坐成一排小赵、小钱、小孙、小李及小周五位青年坐成一排照相照相,问问:(1)若小赵与小钱相邻若小赵与小钱相邻,有多少种排法有多少种排法?(2)若小赵与小钱不相邻且他们之间只安排小李或小若小赵与小钱不相邻且他们之间只安排小李或小周周

11、,有多少种排法有多少种排法?(3)若小赵与小钱不相邻且他们之间只安排小李与小若小赵与小钱不相邻且他们之间只安排小李与小周周,有多少种排法有多少种排法?(4)若小赵、小钱在小孙的同一侧若小赵、小钱在小孙的同一侧,共有多少种排法共有多少种排法?例例8 828解:(1)完成五位青年坐成一排照相且小赵与小钱相邻这件事情,必须依次经过两个步骤:第2个步骤是将相邻的小赵与小钱交换位置,有2种方法例例8 829根据乘法原理,完成五位青年坐成一排照相且小赵与小钱相邻这件事情,有种排法例例8 830(2)完成五位青年坐成一排照相且小赵与小钱不相邻但他们之间只安排小李或小周这件事情,必须依次经过三个步骤 第2个步

12、骤是将不相邻的小赵与小钱交换位置,有2种方法 第3个步骤是将不相邻的小李与小周交换位置,有2种方法例例8 831根据乘法原理,完成五位青年坐成一排照相且小赵与小钱不相邻但他们之间只安排小李或小周这件事情,有种排法例例8 832(3)完成五位青年坐成一排照相且小赵与小钱不相邻但他们之间只安排小李与小周这件事情,必须依次经过三个步骤:第2个步骤是将不相邻的小赵与小钱交换位置,有2种方法 第3个步骤是将相邻的小李与小周交换位置,有2种方法例例8 833根据乘法原理,完成五位青年坐成一排照相且小赵与小钱不相邻但他们之间只安排小李与小周这件事情,有种排法例例8 834(4)完成五位青年坐成一排照相且小赵

13、、小钱在小孙的同一侧这件事情,共有三类方式：例例8 835这三类方式是并列的,其中每一类方式的任一种排法都可以完成这件事情根据加法原理,所以完成五位青年坐成一排照相且小赵、小钱在小孙的同一侧这件事情,共有种排法三、元素可重复的排列三、元素可重复的排列36元素可重复包括元素重复与元素不重复两种情况元素可重复包括元素重复与元素不重复两种情况,元元素可重复的排列是指在排列中允许出现相同元素素可重复的排列是指在排列中允许出现相同元素.例例9北京市电话号码为八位北京市电话号码为八位,问电话局问电话局8461支局共支局共有多少个电话号码有多少个电话号码?解:由于8461支局的电话号码前四位为8461,因此

14、只需确定后四位的数字,就组成8461支局电话号码.显然,在电话号码中允许出现相同数字例例9 937组成8461支局的电话号码,必须依次经过四个步骤:第1个步骤是确定电话号码第五位上的数字,这时是从0至9这10个数字中取出1个数字放在这个位置上,有10种方法 第2个步骤是确定电话号码第六位上的数字,考虑到在电话号码中允许出现相同数字,这时也是从0至9这10个数字中取出1个数字放在这个位置上,有10种方法例例9 938 第3个步骤是确定电话号码第七位上的数字,也有10种方法;第4个步骤是确定电话号码第八位上的数字,也有10种方法 第4个步骤是确定电话号码第八位上的数字,也有10种方法例例9 939

15、因此这个问题相当于从10个不同元素中每次取出4个元素的元素可重复排列根据乘法原理,共有10101010=10000种方法由于一种方法对应一个电话号码,所以8461支局共有10000个电话号码可重复排列数可重复排列数40定义定义0 0.2 2从n个不同元素中,每次可以重复地取出m个元素排成一列,所有这样排列的个数称为从n个不同元素中取出m个元素的元素可重复排列数可重复排列数可重复排列数可重复排列数41如何计算从如何计算从n个不同元素中取出个不同元素中取出m个元素的元素可个元素的元素可重复排列数重复排列数?从n个不同元素中取出m个元素排成一列,必须依次经过m个步骤:第1个步骤是确定排列第1位置上的

16、元素,这时是从n个不同元素中取出1个元素放在这个位置上,有n种方法 第2个步骤是确定排列第2位置上的元素,由于在排列中允许出现相同元素,因而这时还是从n个不同元素中取出1个元素放在这个位置上,也有n种方法可重复排列数可重复排列数42 第m个步骤是确定排列第m位置上的元素,由于在排列中允许出现相同元素,因而这时仍然是从n个不同元素中取出1个元素放在这个位置上,当然有n种方法由于一种方法对应一个排列由于一种方法对应一个排列,所以所有这样排列的个数等于所以所有这样排列的个数等于nm,即从即从n个不同元素中取出个不同元素中取出m个元素的元素可重复排列数个元素的元素可重复排列数等于等于nm.例例1010

17、43邮政大厅有邮政大厅有4个邮筒个邮筒,现将三封信逐一投入邮筒现将三封信逐一投入邮筒,问共问共有多少种投法有多少种投法?解:将三封信逐一投入邮筒,必须依次经过三个步骤:第1个步骤是将第一封信投入4个邮筒中的1个邮筒,有4种方法 第2个步骤是将第二封信投入4个邮筒中的1个邮筒,也有4种方法 第3个步骤是将第三封信投入4个邮筒中的1个邮筒,也有4种方法例例101044若以邮筒作为元素,则这个问题相当于从4个不同元素中每次取出3个元素的元素可重复排列根据乘法原理,共有444=43=64种方法,即共有64种投法例例111145用用3个数字个数字1,2,3组成三位数组成三位数,问问:(1)可以组成多少个

18、数字可重复的三位数可以组成多少个数字可重复的三位数?(2)可以组成多少个数字一定重复的三位数可以组成多少个数字一定重复的三位数?解:(1)用3个数字1,2,3组成数字可重复的三位数,相当于从3个不同元素中每次取出3个元素的元素可重复排列,这样的排列共有33个所以可以组成33=27个数字可重复的三位数例例111146(2)注意到用3个数字1,2,3组成的数字可重复的三位数包括两部分:另一部分则是数字一定重复的三位数说明所求数字一定重复的三位数的个数等于数字可重复的三位数的个数减去数字不重复的三位数的个数四、组合四、组合 例例121247从从10人中选举人中选举2名代表参加座谈会名代表参加座谈会,

19、问共有多少种选问共有多少种选举结果举结果?解:这个问题同例6中选举正副组长各1名是不一样的,尽管都是选出2人,但在选举正副组长各1名时,这2人须排队不妨规定排在前面的是正组长,排在后面的是副组长;而在选举2名代表时,这2人不需排队例例121248还可以依次经过下面两个步骤解决这个问题:第第1个步骤是从个步骤是从10人中选出人中选出2人人,相当于从10人中选举2名代表,已设有x种方法例例121249得到所以从10人中选举2名代表共有45种选举结果例例121250这是容易理解的,如甲、乙当选,对于选举正副组长各1名,有两种选举结果而对于选举2名代表,却只是一种选举结果.说明选举正副组长各1名的每两

20、种选举结果对应选举2名代表的一种选举结果由于选举正副组长各1名共有90种选举结果,所以选举2名代表当然共有45种选举结果组合数组合数51定义定义0 0.3 3如何计算组合数如何计算组合数52还可以依次经过下面两个步骤解决这个问题:如何计算组合数如何计算组合数53于是有关系式所以得到组合数如何计算组合数如何计算组合数54组合数性质组合数性质55性质性质组合数满足关系式组合数满足关系式组合数性质组合数性质56所以得到关系式例例131357根据组合数的计算公式,有组合数例例131358根据组合性质,有组合数对于实际问题,必须正确判别是排列问题还是组合问题,关键在于要不要计较所取出元素的先后关键在于要

21、不要计较所取出元素的先后顺序顺序，即即要不要将所取出元素排队要不要将所取出元素排队若要排队若要排队,则是排列问题则是排列问题;若不要排队若不要排队,则是组合问题则是组合问题例例1414已知已知100件产品中有件产品中有3件是次品件是次品,其余其余97件是合格品件是合格品,问问:若任意抽取若任意抽取3件产品中恰好有件产品中恰好有1件次品件次品,有多少种有多少种取法取法?解:从100件产品中任意抽取3件产品,并不计较所取产品的次序,从而这个问题是组合问题,从100件产品抽取3件产品中恰好有1件次品,意味着抽取3件产品中有1件次品与2件合格品例例141460根据乘法原理,所以任意抽取3件产品中恰好有

22、1件次品,有=34656=13968 种取法完成这件事情必须依次经过两个步骤:例例1515617支足球队进行比赛支足球队进行比赛,问问:(1)若采用主客场赛制若采用主客场赛制,共有多少场比赛共有多少场比赛?(2)若采用单循环赛制若采用单循环赛制,共有多少场比赛共有多少场比赛?例例151562解:(1)采用主客场赛制意味着每两支球队之间进行两场比赛,比赛双方各有一个主场这时从7支球队中每次挑选2支球队进行比赛,要计较所挑选球队的顺序,即需要将它们排队,不妨规定排在前面的球队是在主场比赛例例151563(2)采用单循环赛制意味着每两支球队之间只进行一场比赛这时从7支球队中每次挑选2支球队进行比赛,

23、不计较所挑选球队的顺序,即不需要将它们排队,因此这个问题是组合问题例例161664书桌上有书桌上有11本不同的书本不同的书,问问:(1)从中任取从中任取3本书本书,共有多少种取法共有多少种取法?(2)从中任取从中任取3本书分给甲、乙、丙三个人本书分给甲、乙、丙三个人,每人一本每人一本,共有多少种分法共有多少种分法?解:(1)由于从11本不同的书中任取3本书,并不计较所取出书的先后顺序,即不需要将它们排队,因此这个问题是组合问题例例161665(2)由于从11本不同的书中任取3本书分给甲、乙、丙三个人,每人一本,相当于从11本不同的书中任取3本不同的书排队,不妨规定排在前面、中间、后面位置的书分

24、别分给甲、乙、丙,因此这个问题是排列问题例例171766口袋里装有口袋里装有5个黑球与个黑球与4个白球个白球,任取任取4个球个球,问问:(1)共有多少种取法共有多少种取法?(2)其中恰好有其中恰好有1个黑球个黑球,有多少种取法有多少种取法?(3)其中至少有其中至少有3个黑球个黑球,有多少种取法有多少种取法?(4)其中至多有其中至多有1个黑球个黑球,有多少种取法有多少种取法?例例171767解:由于在取球时不计较所取出球的先后顺序,即不需要将它们排队,因此这个问题是组合问题.例例171768(2)任取4个球中恰好有1个黑球,意味着所取4个球中有1个黑球与3个白球,完成这件事情必须依次经过两个步骤

25、:例例171769(3)任取4个球中至少有3个黑球,包括恰好有3个黑球与恰好有4个黑球两类情况,完成这件事情有两类方式:例例171770根据加法原理,有=104+51=45种取法例例171771(4)任取4个球中至多有1个黑球,包括恰好有1个黑球与没有黑球两类情况,完成这件事情有两类方式:例例171772根据加法原理,有=54+11=21种取法例例181873从从3名男生、名男生、4名女生中任意挑选名女生中任意挑选4名学生参加座谈名学生参加座谈会会,问问:(1)共有多少种选法共有多少种选法?(2)其中至少有其中至少有1名男生名男生,有多少种选法有多少种选法?解:由于在挑选学生时不计较所挑选学生

26、的先后顺序,即不需要将它们排队,因此这个问题是组合问题(1)从7名学生中任意挑选4名学生,共有种选法例例181874(2)任意挑选4名学生中至少有1名男生,包括恰好有1名男生、恰好有2名男生及恰好有3名男生三类情况,完成这件事情有三类方式:例例181875例例181876根据加法原理,有种选法例例181877此题尚有简便解法:注意到符合要求即任意挑选4名学生中至少有1名男生包括三类情况由于包括情况比较多,从而直接计算其选法比较麻烦,而不符合要求意味着挑选4名学生中没有男生,即所挑选4名学生中有0名男生与4名女生例例181878显然,符合要求的选法种数等于总选法种数减去不符合要求的选法种数,所以任意挑选4名学生中至少有1名男生,有种选法例例181879例18说明:若符合要求的情况比较多,从而直接计算符合要求的方法种数比较麻烦,这时不符合要求的情况一定比较少,计算不符合要求的方法计算不符合要求的方法种数当然比较简单于是应该首先计算总方法种数与不符合要求的方法种数,然后总方法种数减去不符合要求的方法种数,就得到所求符合要求的方法种数80