排列组合问题解法PPT学习教案

1、会计学1排列组合问题解法排列组合问题解法(0).,.!:,!()!:1.,2.Arrangement,3.,mnnnmnnnnmmnnmAmnnAnAAnnmAP定义:从 个不同元素中取出个元素的所有排列的个数,叫做从 个不同元素中取出 个元素的排列数,记为特别地,当时 这种取法的个数叫做这 个不同元素的全排列,记为计算公式说明排列数公式的推导过程由乘法原理给出证明从略排列数用 表示是由于排列的英文为取其首字母早期的排列数曾用 表示 是由于Permutation.,PA排列的另一种翻译为现在 一些教材和资料中仍可见到用 表示的排列数.本课件中的排列数符号一律用 表示第1页/共48页11(0).

2、!:,1()! !:1.( ,)2.( ,):1.,2.Combination,mnmnnnmn mnnmmmnnnnmmnnmCnCCnm mCCm nNmnCCCm nNmnC定义:从 个不同元素中取出个元素的所有组合的个数,叫做从 个不同元素中取出 个元素的组合数,记为计算公式性质且且说明组合数公式的推导过程由排列数公式给出证明从略组合数用 表示是由于组合的英文为取其首字母第2页/共48页:!()! !()!:mmmnnmmmmnmnAC AnnC AmAnm mnmnmnm区别排列是一个有序的概念,而组合是一个无序的概念联系:排列数与组合数存在如下恒等的关系:利用公式证明根据定义理解从

3、 个不同元素中取出 个元素进行排列,等效于从 个不同元素中取出 个元素进行组合,然后再对这些已经取出的元素进行全排列第3页/共48页第4页/共48页第5页/共48页第6页/共48页第7页/共48页C14A34C13解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 第8页/共48页254512 1201440A A 第9页/共48页乙乙甲甲丁丁丙丙解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排 225225480A A A 第10页/共48页解：命中的三枪捆绑成一枪，与命中的另一枪插入未

4、命中的四枪的5个空位，共有 种不同的情形2520A 第11页/共48页第一步排2个相声和3个独唱共有 种，55A解:分两步进行： 第二步将4舞蹈插入第一步排好的5个元素中，包含首尾共6个空位，共有 种不同的方法, 46A由分步计数原理,节目的不同顺序共有 545643200A A 第12页/共48页2630A 第13页/共48页解: (倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行全排列,然后用总排列数除以这几个元素之间的全排列数。则共有不同排法种数是： 7373AA (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 种方法，其余的三个位置甲乙丙共有 1种坐法

5、，则共有 种方法 47A47A（插入法)先排甲乙丙三个人,共有1种,再把其余4四人依次插入共有 方法 3474C A第14页/共48页510252C第15页/共48页解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分法。依此类推,由分步计数原理共有 种不同的排法67第16页/共48页86 742;7第17页/共48页第18页/共48页设从n个元素中取出m个元素组成的环形排列数为N个，则对应的直线排列数为mN个，又因为从n个元素中取出m个元素的排成一排的排列数为 个，所以 ，所以 mnAmnmNAmnANm第19页/共48页mnANm!(1)!nnA

6、nNnnn第20页/共48页HFDCAABCDEABEGHGF(8 1)!7!解：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人并从此位置把圆形展成直线其余7人共有种排法，即840种第21页/共48页第22页/共48页解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.先排前个位置，个特殊元素有 种排法 24A再排后4个位置上的特殊元素丙有 种, 14A其余的5人在5个位置上任意排列有 种, 55A则共有 种排法（排好后，按前个为前排，后人为后排分成两排即可） 2154455760A A A 第23页/共48页11116181417108238346C CC C第

7、24页/共48页解:第一步从5个球中选出2个组成复合元素，共有 种方法.25C再把4个元素(包含一个复合元素)装入4个不同的盒内，有 种方法， 44A根据分步计数原理装球的方法共有 2454240C A 第25页/共48页134244192C CA 第26页/共48页解：把,当作一个小集团与排队共有 种排法， 22A再排小集团内部，共有 种排法 2222A A由分步计数原理，共有 种排法.2222228A A A 第27页/共48页2542545760A A A 25525528800A A A 第28页/共48页一一班班二二班班三三班班四四班班五五班班六六班班七七班班解：因为10个名额没有差

8、别，把它们排成一排相邻名额之间形成个空隙在个空档中选个位置插个隔板，可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法，共有 种分法6984C 第29页/共48页第30页/共48页49126C 3103176851C第31页/共48页所取的三个数，含有3个偶数的取法有 ，只含有1个偶数的取法有 35C1255C C则和为偶数的取法共有 12355560C CC再淘汰和小于10的偶数共9种，符合条件的取法共有60-9=51 第32页/共48页554340304590CC第33页/共48页解: 分三步取书得 种方法,但这里会出现重复计数的现象, 22264290C C C 不妨记6本书为

9、ABCDEF，若第一步取AB,第二步取CD,第三步取EF，该分法记为(AB,CD,EF),则90种方法中还有：(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有 种取法 336A 而这些取法与(AB,CD,EF)是相同的分堆,故共有种分法 2223642315C C CA第34页/共48页l平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以 (n为均分的组数)避免重复计数。nnA1. 将将13个队分成个队分成3组组,一组一组5队队,其它两组其它两组4队队, 有多少分法？有多少分法？2. 某年级共有某年级共有6个班，

10、现从外地转入个班，现从外地转入4名学生，要安排到两名学生，要安排到两个班且每班安排个班且每班安排2名，则不同的安排方案种数为名，则不同的安排方案种数为 ? 3. 10名学生分成名学生分成3组组,其中一组其中一组4人人, 另两组另两组3人。但正、副班人。但正、副班长不能分在同一组长不能分在同一组,有多少种不同的分组方法有多少种不同的分组方法?44584132245045C CCA2224262290C CAA333342134636310887422221540C CC CCCCCCAA第35页/共48页只会唱的5人中没有人选上唱歌人员共有 种, 2233C C只会唱的5人中只有1人选上唱歌人员

11、 种 112534C C C只会唱的5人中只有2人选上唱歌人员有 种， 2255C C由分类计数原理共有 种22112223353455199C CC C CC C第36页/共48页第37页/共48页乘船方法. 11223334343434C CC CC C2121121123222332()()27C C CCC CC C第38页/共48页解：把此问题当作一个排队模型。在6盏亮灯的5个空隙中插入3个不亮的灯有 种3510C 第39页/共48页45120A 第40页/共48页解：从5个球中取出2个与盒子对号有 种。25C还剩下3球3盒序号不能对应，利用实际操作法，如果剩下3,4,5号球, 3,4,5号盒,3号球只能装入4号或5号盒,共两种装法,当3号球装4号盒时，则4,5号球只有1种装法，同理3号球装5号盒时,4,5号球有也只有1种装法由分步计数原理，共有 种 . 25220C 第41页/共48页543213 (12)911114322(11)72C C CC第42页/共48页123455555531CCCCC把一个复杂问题分解成几个小问题逐一解决把一个复杂问题分解成几个小问题逐一解决, ,然后依据然后依据问题分解后的结构问题分解后的结构, ,用分类计数原理和分步计数原理将用分类计数原理和分步计数原理将问题合成问题合成, ,从