排列组合复习元媛第四个课题)20091004

1、 排列组合复习 计数的基本原理排列组合排列数Anm公式组合数Cnm公式组合数的两个性质应用本章知识结构分类计数原理分类计数原理 完成完成一件事一件事,有有n类办法类办法,在第在第1类办法中类办法中,有有m1种不同的方法种不同的方法,在第在第2类办类办法中法中,有有m2种不同的方法种不同的方法在第在第n类办法类办法中中,有有mn种不同的方法种不同的方法,则完成这件事有则完成这件事有N=m1+m2+ +mn种不同的方法种不同的方法分步计数原理分步计数原理 完成完成一件事一件事,需要分成需要分成n个步骤个步骤,在第在第1步中步中,有有m1种不同的方法种不同的方法,在第在第2步中步中,有有m2种不同的

2、方法种不同的方法在第在第n步中步中,有有mn种种不同的方法不同的方法,则完成这件事有则完成这件事有N=m1m2 mn种不同的方法种不同的方法分类计数原理分类计数原理与与分步计数原理分步计数原理之间的区别与联系之间的区别与联系 1分类计数原理分类计数原理中各类方法之间是互相独立的，中各类方法之间是互相独立的，每一类每一种方法都能直接完成这件事情，每一类每一种方法都能直接完成这件事情，分步分步计数原理计数原理中，各个步骤之间是相互联系的，依次中，各个步骤之间是相互联系的，依次完成所有步骤才能完成这件事情完成所有步骤才能完成这件事情2分类计数原理分类计数原理的重点在一个的重点在一个“类类”字字，分步

3、分步计数原理计数原理的重点在一个的重点在一个“步步”字字，应用加法原理应用加法原理时，要注意时，要注意“类类”与与“类类”之间的独立性和并列之间的独立性和并列性，在各类办法中彼此是独立的，并列的性，在各类办法中彼此是独立的，并列的应用应用分步计数分步计数原理时，要注意原理时，要注意“步步”与与“步步”之间的之间的连续性，做一件事需分成若干个步骤，每个步骤连续性，做一件事需分成若干个步骤，每个步骤相继完成，最后才算做完整个工作相继完成，最后才算做完整个工作练习练习1： 书架上放有书架上放有3本不同的数学书，本不同的数学书，5本本不同的语文书，不同的语文书，6本不同的英语书本不同的英语书 （1）若

4、从这些书中任取一本，有多少种不）若从这些书中任取一本，有多少种不同的取法？同的取法？ （2）若从这些书中，取数学书、语文书、）若从这些书中，取数学书、语文书、英语书各一本，有多少种不同的取法？英语书各一本，有多少种不同的取法？（3）若从这些书中取不同的科目的书两本，）若从这些书中取不同的科目的书两本，有多少种不同的取法？有多少种不同的取法？ 答案：答案：Nm1m2m335614N=m1m2m3=90N=353656=63练习练习2： 由数字由数字0，1，2，3，4可以组成多少个三可以组成多少个三位整数（各位上的数字允许重复）？位整数（各位上的数字允许重复）？解：解：要组成一个三位数，需要分成三

5、个步骤：要组成一个三位数，需要分成三个步骤：第一步第一步确定百位上的数字，从确定百位上的数字，从14这这4个数字中任个数字中任选一个数字，有选一个数字，有4种选法；种选法；第二步第二步确定十位上的数字，由于数字允许重复，确定十位上的数字，由于数字允许重复，共有共有5种选法；种选法；第三步第三步确定个位上的数字，仍有确定个位上的数字，仍有5种选法根据乘种选法根据乘法原理，得到可以组成的三位整数的个数是法原理，得到可以组成的三位整数的个数是 N=455=100 答：可以组成答：可以组成100个三位整数个三位整数)!(!) 1() 2)(1(mnnmnnnnAmn 从从n个不同的元素中，任取个不同的

6、元素中，任取A个元素，个元素，按照一定的顺序排成一列，叫做从按照一定的顺序排成一列，叫做从n个个不同的元素中取出不同的元素中取出A个元素的一个个元素的一个 排排列列 。 排列与排列数排列与排列数所有排列的个数叫做所有排列的个数叫做 排列数排列数 ，用，用表示。表示。 mnA判断判断下列几个问题是不是排列问题下列几个问题是不是排列问题? ?从班级从班级5名优秀团员中选出名优秀团员中选出3人参加上午的团委会人参加上午的团委会1000本参考书中选出本参考书中选出100本本给给100位同学每人一本位同学每人一本1000名来宾中选名来宾中选20名贵宾分名贵宾分别坐别坐120号贵宾席号贵宾席1210114

7、656234444321: 1 Xr)A; ()A; ()A; ()A(计计算算例例组组 合合 两个组合的元素完全相同为相同组合注注n个不同元素mn组合与元素的顺序无关排列与元素的顺序有关 从从n n个不同元素中取出个不同元素中取出m(mn)m(mn)个元素的所有组个元素的所有组合的合的个数个数, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的个元素的组组合数合数表示方法表示方法C Cmmn n从n个不同元素中取出m(mn)个元素并成一组,叫做从n个不同元素中取出m个元素的一个一个组组合合组合数的两个性质性质1)( ,nmCCmnnmn)( ,11nmCCCmnmnmn性质

8、2C Cn nm m= =A An nm mA Am mm m= =n(n-1)(n-2) n(n-1)(n-2) (n-m+1)(n-m+1)m m例2 计算计算: C10 7(2)C7 4(1)C例3 求证求证 mCnCn m+1=m+1n-m判断判断 下列几个问题下列几个问题是排列问题还是是排列问题还是组合问题组合问题? ? 四个足球队举行单循环比赛四个足球队举行单循环比赛( (每两队比赛一每两队比赛一场场) )共有多少种比赛共有多少种比赛? ?四个足球队举行单循环比赛的所有冠亚军四个足球队举行单循环比赛的所有冠亚军的可能性情况有多少种的可能性情况有多少种? ?从从2,3,4,5,62,

9、3,4,5,6中任取两数构成指数中任取两数构成指数, ,有多少个不有多少个不同的指数同的指数? ?从从2,3,4,5,62,3,4,5,6中任取两数相加中任取两数相加, ,有多少个不同有多少个不同的结果的结果? ?十个人相互通了一封信十个人相互通了一封信, ,共有多少封信共有多少封信? ?十个人相互通了一次电话十个人相互通了一次电话, ,共打了多少个电话共打了多少个电话? ? 1） 由数字由数字1，2，3，4，5 组成没有重复数字的组成没有重复数字的五位数，其中偶数共有五位数，其中偶数共有 个。个。2） 用用 0，1，2，3，4，5 组成没有重复数字的组成没有重复数字的三位数，共有三位数，共有

10、 个。个。 3）五名同学排成一排，其中的甲乙两同学必五名同学排成一排，其中的甲乙两同学必须站在两端须站在两端 ，共有，共有 种不同排法。种不同排法。4810012例例1典型例题典型例题例例2 从从1到到6这六个数字中任取这六个数字中任取5个数字组成没有重复个数字组成没有重复数字的五位数数字的五位数,且个位和百位必须是奇数且个位和百位必须是奇数,这样的五位数这样的五位数共有多少个共有多少个?万万 千千百百十十个个34A23A万万 千千百百十十个个45A13A万万 千千百百十十个个34A13A13A解法一解法一:N=34A23A=144个个解法二解法二:34A45A13A13A13AN=-=144

11、个个有条件的排列 问 题有条件的排列 问 题有条件的排列问题有条件的排列问题 例例3 3 七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。a)若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有 种排法，而三个女孩之间有 种排法，所以不同的排法共有： （种）。7203355 AA55A33A捆 绑 法捆 绑 法有条件的排列问题有条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。b)若三个女孩要站在一起，四个男孩也 要站在一起，有多少种不同的排法？不同的排法有：288443

12、322 AAA（种）说一说说一说捆绑法一般适用于 问题的处理。相邻相邻有条件的排列问题有条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c) 若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有 种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入空档中有 种方法，所以共有： （种）排法。35A44A14403544 AA有条件的排列问题有条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c) 若三个女孩互不相邻，有多少种不同的排法？插 空 法插 空 法有条件的排列问题有

13、条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。d) 若三个女孩互不相邻，四个男孩也互不相邻，有多少种不同的排法？不同的排法共有：1443344 AA（种）说一说说一说插空法一般适用于 问题的处理。互不相邻互不相邻B有条件的排列问题有条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e) 若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BAA解：A在B左边的一种排法必对应着A在B右边的一种排法，所以在全排列中， A在B左边与A在B右边的排法数相等，因此有：25207721 A排法。（种

14、）有条件的排列问题有条件的排列问题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e) 若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BA对应思想对应思想252057 A例例4 有有12名划船运动员名划船运动员,其中其中3人只会划左舷人只会划左舷, 4人只人只会划右舷会划右舷, 其它其它5人既会划左舷人既会划左舷, 又会划右舷又会划右舷, 现要从现要从这这12名运动员中选出名运动员中选出6人平均分在左右舷参加划船比人平均分在左右舷参加划船比赛赛,有多少种不同的选法有多少种不同的选法? 例5 某班一天有数学、语文、物理、英语、某班一天有数学、语文、物理、英语、体育、自习六节课体育、自习六节课,按下例要求排课表按下例要求排课表,分别有分别有多少种不同的排法？多少种不同的排法