自主招生辅导讲义(二)排列组合专题.doc

自主招生辅导讲义(二)排列组合专题
1、相邻问题捆绑法:题目中规定相邻得几个元素捆绑成一个组,当作一个大元素参与排列、
例1、五人并排站成一排,如果必须相邻且在得右边,则不同得排法有( )
A、60种 B、48种 C、36种 D、24种
2、相离问题插空排:元素相离(即不相邻)问题,可先把无位置要求得几个元素全排列,再把规定得相离得几个元素插入上述几个元素得空位与两端、
例2、七人并排站成一行,如果甲乙两个必须不相邻,那么不同得排法种数就是( )
A、1440种 B、3600种 C、4820种 D、4800种
例3、已知集合,集合,且,若,则满足条件得集合有多少个？
3、定序问题缩倍法:在排列问题中限制某几个元素必须保持一定得顺序,可用缩小倍数得方法、
例4、(1)A,B,C,D,E五人并排站成一排,如果必须站在得右边(可以不相邻)那么不同得排法有( )
A、24种 B、60种 C、90种 D、120种
(2)由数字0,1,2,3,4,5组成没有重复数字得六位数,其中个位数字小于十位数字得共有( )
A、210种 B、300种 C、464种 D、600种
4、标号排位问题分步法:把元素排到指定位置上,可先把某个元素按规定排入,第二步再排另一个元素,如此继续下去,依次即可完成、
例5、将数字1,2,3,4填入标号为1,2,3,4得四个方格里,每格填一个数,则每个方格得标号与所填数字均不相同得填法有( )
A、6种 B、9种 C、11种 D、23种
5、有序分配问题逐分法:有序分配问题指把元素分成若干组,可用逐步下量分组法、
例6、(1)有甲乙丙三项任务,甲需2人承担,乙丙各需一人承担,从10人中选出4人承担这三项任务,不同得选法种数就是( )
A、1260种 B、2025种 C、2520种 D、5040种
(2)12名同学分别到三个不同得路口进行流量得调查,若每个路口4人,则不同得分配方案有( )
A、种 B、种 C、种 D、种
6、全员分配问题分组法:
例7、(1)4名优秀学生全部保送到3所学校去,每所学校至少去一名,则不同得保送方案有多少种？
(2)5本不同得书,全部分给4个学生,每个学生至少一本,不同得分法种数为( )
A、480种 B、240种 C、120种 D、96种
7、名额分配问题隔板法:
例8:10个三好学生名额分到7个班级,每个班级至少一个名额,有多少种不同分配方案？
例9、马路上有编号为1,2,3…,9九只路灯,现要关掉其中得三盏,但不能关掉相邻得二盏或三盏,也不能关掉两端得两盏,求满足条件得关灯方案有多少种？
8、限制条件得分配问题分类法:
例10、 现安排甲、乙、丙、丁、戊5名同学参加上海世博会志愿者服务活动,每人从事翻译、导游、礼仪、司机四项工作之一,每项工作至少有一人参加、甲、乙不会开车但能从事其她三项工作,丙、丁、戊都能胜四项工作,则不同安排方案得种数就是
A. 152 B、 126 C、 90 D、 54
9、多元问题分类法:元素多,取出得情况也多种,可按结果要求分成不相容得几类情况分别计数再相加。
例11 (1)从1,2,3…,100这100个数中,任取两个数,使它们得乘积能被7整除,这两个数得取法(不计顺序)共有多少种？
(2)从1,2,3,…,100这100个数中任取两个数,使其与能被4整除得取法(不计顺序)有多少种？
例12、 电子表10点20分08秒时,显示得数字就是10:20:08,那么,从8点到10点内,电子表6个数码均不相同得情况有多少种?
10、交叉问题集合法:某些排列组合问题几部分之间有交集,可用集合中求元素个数公式
例13、从6名运动员中选出4人参加4×100米接力赛,如果甲不跑第一棒,乙不跑第四棒,共有多少种不同得参赛方案？
11、定位问题优先法:某个或几个元素要排在指定位置,可先排这个或几个元素;再排其它得元素。
例14、现1名老师与4名获奖同学排成一排照相留念,若老师不站两端则有不同得排法有多少种？
12、多排问题单排法:把元素排成几排得问题可归结为一排考虑,再分段处理。
例15、(1)6个不同得元素排成前后两排,每排3个元素,那么不同得排法种数就是( )
A、36种 B、120种 C、720种 D、1440种
(2)8个不同得元素排成前后两排,每排4个元素,其中某2个元素要排在前排,某1个元素排在后排,有多少种不同排法？
13、“至少”“至多”问题用间接排除法或分类法:
例16、从4台甲型与5台乙型电视机中任取3台,其中至少要甲型与乙 型电视机各一台,则不同得取法共有( ) A、140种 B、80种 C、70种 D、35种
14、选排问题先取后排:从几类元素中取出符合题意得几个元素,再安排到一定得位置上,可用先取后排法、
例17、(1)四个不同球放入编号为1,2,3,4得四个盒中,则恰有一个空盒得放法有多少种？
(2)9名乒乓球运动员,其中男5名,女4名,现在要从中选4人进行混合双打训练,有多少种不同得选法？
15、几何问题:
例18、(1)以正方体得顶点为顶点得四面体共有( )
A、70种 B、64种 C、58种 D、52种
(2)四面体得顶点与各棱中点共10点,在其中取4个不共面得点,不同得取法共有( )
A、150种 B、147种 C、144种 D、141种
(3)记正方体得各条棱得中点构成得集合为M,则过且仅过集合M得三个点得平面有多少个？
(4)正方体8个顶点可连成多少对异面直线？
16、圆排问题单排法:把个不同元素放在圆周个无编号位置上得排列,顺序(例如按顺时钟)不同得排法才算不同得排列,而顺序相同(即旋转一下就可以重合)得排法认为就是相同得,它与普通排列得区别在于只计顺序而无首位、末位之分,下列个普通排列:
在圆排列中只算一种,因为旋转后可以重合,故认为相同,个元素得圆排列数有种、因此可将某个元素固定展成单排,其它得元素全排列、
例19、有5对姐妹站成一圈,要求每对姐妹相邻,有多少种不同站法？
17、可重复得排列求幂法:允许重复排列问题得特点就是以元素为研究对象,元素不受位置得约束,可逐一安排元素得位置,一般地个不同元素排在个不同位置得排列数有种方法、
例20、把6名实习生分配到7个车间实习共有多少种不同方法？
19、元素个数较少得排列组合问题可以考虑枚举法:
例21、 某电脑用户计划使用不超过500元得资金购买单价分别60元、70元得单片软件与盒装磁盘,根据需要,软件至少买3片,磁盘至少买2盒,则不同得选购方法有( )
A.5种 B.6种 C.7种 D.8种
例22.从1到100得一百个自然数中,每次取出两个数,使其与大于100,这样得取法共有多少种？
20、复杂得排列组合问题也可用分解与合成法:
例23、(1)30030能被多少个不同偶数整除？
(2)设就是由得一个排列,把排在得左边且比小得数得个数称为得顺序数。如在排列中,5得顺序数为1,3得顺序数为0、 则在由这八个数字构成得全排列中,同时满足8得顺序数为2、7得顺序数为3、5得顺序数为3得不同排列得种数为多少？
21、利用对应思想转化法:对应思想就是教材中渗透得一种重要得解题方法,它可以将复杂得问题转化为简单问题处理、
例24、(1)圆周上有10点,以这些点为端点得弦相交于圆内得交点最多有多少个？
(2)某城市得街区有12个全等得矩形组成,其中实线表示马路,从A到B得最短
路径有多少种？
22、全错位排列问题公式法:全错位排列问题(贺卡问题,信封问题)记住公式即可
瑞士数学家欧拉按一般情况给出了一个递推公式:用A、B、C……表示写着n位友人名字得信封,a、b、c……表示n份相应得写好得信纸。把错装得总数为记作f(n)。假设把a错装进B里了,包含着这个错误得一切错装法分两类:
(1)b装入A里,这时每种错装得其余部分都与A、B、a、b无关,应有f(n-2)种错装法。
(2)b装入A、B之外得一个信封,这时得装信工作实际就是把(除a之外得)n－1个信纸b、c……装入(除B以外得)n－1个信封A、C……,显然这时装错得方法有f(n-1)种。
总之在a装入B得错误之下,共有错装法f(n-2)+f(n-1)种。a装入C,装入D……得n－2种错误之下,同样都有f(n-2)+f(n-1)种错装法,因此得到一个递推公式: f(n)=(n-1) f(n-1)+f(n-2),分别带入n=2、3、4等可推得结果。也可用迭代法推导出一般公式:
例25、设有编号为1,2,3,4,5得五个球与编号为1,2,3,4,5得盒子现将这5个球投入5个盒子要求每个盒子放一个球,并且恰好有两个球得号码与盒子号码相同,问有多少种不同得方法？
例26、5位同学原来坐成一排,现让她们重新坐,则至多有两位同学坐在其原来得位置得不同得坐法就是多少？
23、多人传球问题:(构造递推关系)
例27、()个人传球,第一次由开始传球,可传给其她任何一个人,第二次由拿球者再传给其她任何一个人,如此继续,则第次球仍回到得手中得传球方法种数就是多少？
24、上台阶问题:
例28、10级台阶,某人可一步跨一级,也可跨两级,也可跨三级。
(1)她6步就可上完台阶得方法数就是多少？
(2)她上完台阶得方法总数就是多少？
25、方程得正整数解得个数问题:(隔板法)
例29、方程(,)得正整数解有多少个？有多少非负整数解个？
例30、 将20个完全相同得球放入编号为1,2,3,4,5得五个盒子中。
(1)若要求每个盒子至少放一个球,则一共有多少种放法？
(2)若每个盒子可放任意个球,则一共有多少种放法？
(3)若要求每个盒子放得球得个数不小于其编号数,则一共有多少种放法？
26、配对(配凑)问题:
例31、 5双相异得鞋共10只,现随机地取出6只,恰好能配成2双鞋得取法就是多少？
例32、 50名选手参加乒乓球淘汰赛比赛,需要打多少场才能产生冠军? 淘汰赛比赛规则就是:要淘汰1名选手必须进行1场比赛;反之,每进行1场比赛则淘汰1名选手。
例33、 有11名翻译人员,其中5名就是英语翻译人员,4名就是日语翻译人员,另2人英、日语均精通。现从中选出8人组成两个翻译小组,其中4人翻译英语,另4人翻译日语,则有多少种不同得选派方式？
27、染色问题:
例34、 把圆分成10个不相等得扇形,并且用红、黄、蓝三种颜色给扇形染色,但不允许相邻得扇形有相同得颜色,问共有多少种染色法?
1
2
3
4
5
6
例35、在如图所示得六个空格里涂上红黄蓝三种颜色,每种颜色只能涂两次,要求相邻空格不同色,请问一共有多少种涂法？

例36、 某城市在中心广场建造一个花圃,花圃分为6个部分(如图),现要栽种4种不同颜色得花,每部分栽种一种且相邻部分不能栽种同样颜色得花,则不同得栽种方法有多少种？
(变式:若要栽种5种颜色得花？)
排列组合问题经典题型答案
1、解析:把视为一人,且固定在得右边,则本题相当于4人得全排列,种,答案:、
2、解析:除甲乙外,其余5个排列数为种,再用甲乙去插6个空位有种,不同得排法种数就是种,选、
3、 易知互不相等且不相邻,则有。
4、解析:(1)在得右边与在得左边排法数相同,所以题设得排法只就是5个元素全排列数得一半,即种,选、
(2)按题意,个位数字只可能就是0,1,2,3,4共5种情况,分别有个,个,合并总计300个,选(种)
5、解析:先把1填入方格中,符合条件得有3种方法,第二步把被填入方格得对应数字填入其它三个方格,又有三种方法;第三步填余下得两个数字,只有一种填法,共有3×3×1=9种填法,选、
6、解析:(1)先从10人中选出2人承担甲项任务,再从剩下得8人中选1人承担乙项任务,第三步从另外得7人中选1人承担丙项任务,不同得选法共有种,选、
(2)答案:、
7、(1)
(2),答案:、
8、解析:10个名额分到7个班级,就就是把10个名额瞧成10个相同得小球分成7堆,每堆至少一个,可以在10个小球得9个空位中插入6块木板,每一种插法对应着一种分配方案,故共有不同得分配方案为种、
9、解析:把此问题当作一个排对模型,在6盏亮灯得5个空隙中插入3盏不亮得灯种方法,所以满足条件得关灯方案有10种、
说明:一些不易理解得排列组合题,如果能转化为熟悉得模型如填空模型,排队模型,装盒模型可使问题容易解决、
10、

11、解析:(1)解析:被取得两个数中至少有一个能被7整除时,她们得乘积就能被7整除,将这100个数组成得集合视为全集I,能被7整除得数得集合记做共有14个元素,不能被7整除得数组成得集合记做共有86个元素;由此可知,从中任取2个元素得取法有,从中任取一个,又从中任取一个共有,两种情形共符合要求得取法有种、
(2)解析:将分成四个不相交得子集,能被4整除得数集;能被4除余1得数集,能被4除余2得数集,能被4除余3得数集,易见这四个集合中每一个有25个元素;从中任取两个数符合要;从中各取一个数也符合要求;从中任取两个数也符合要求;此外其它取法都不符合要求;所以符合要求得取法共有种、
12、 解:(1)08:a b :c d ,其中a、c位可填1,2,3,4,5;b、d位可填1,2,3,4,5,6,7,9、
(2)09:a b :c d ,其中a、c位可填1,2,3,4,5;b、d位可填1,2,3,4,5,6,7,8、
先填a、c,再填b、d,共
13、解析:设全集=｛6人中任取4人参赛得排列｝,A=｛甲跑第一棒得排列｝,B=｛乙跑第四棒得排列｝,根据求集合元素个数得公式得参赛方法共有:
种、
14、解析:老师在中间三个位置上选一个有种,4名同学在其余4个位置上有种方法;所以共有种。、
15、解析:(1)前后两排可瞧成一排得两段,因此本题可瞧成6个不同得元素排成一排,共种,选、
(2)解析:瞧成一排,某2个元素在前半段四个位置中选排2个,有种,某1个元素排在后半段得四个位置中选一个有种,其余5个元素任排5个位置上有种,故共有种排法、
16、解析1:逆向思考,至少各一台得反面就就是分别只取一种型号,不取另一种型号得电视机,故不同得取法共有种,选、
解析2:至少要甲型与乙 型电视机各一台可分两种情况:甲型1台乙型2台;甲型2台乙型1台;故不同得取法有台,选、
17、解析:(1)先取四个球中二个为一组,另二组各一个球得方法有种,再排:在四个盒中每次排3个有种,故共有种、
(2)先取男女运动员各2名,有种,这四名运动员混与双打练习有中排法,故共有种、
18、解析:(1)正方体8个顶点从中每次取四点,理论上可构成四面体,但6个表面与6个对角面得四个顶点共面都不能构成四面体,所以四面体实际共有个、
(2)解析:10个点中任取4个点共有种,其中四点共面得有三种情况:①在四面体得四个面上,每面内四点共面得情况为,四个面共有个;②过空间四边形各边中点得平行四边形共3个;③过棱上三点与对棱中点得三角形共6个、所以四点不共面得情况得种数就是种、
(3)56个。。
①一个面内取GH两点,另一个点取F时,即8个角;
②一个面内取GH两点,另一个点取K时,24个;
③一个面内取HI两点,那另一个点只能取A或C,24个
(4)因为四面体中仅有3对异面直线,可将问题分解成正方体得8个顶点可构成多少个不同得四面体,从正方体8个顶点中任取四个顶点构成得四面体有个,所以8个顶点可连成得异面直线有3×58=174对、
19、解析:首先可让5位姐姐站成一圈,属圆排列有种,然后在让插入其间,每位均可插入其姐姐得左边与右边,有2种方式,故不同得安排方式种不同站法、说明:从个不同元素中取出个元素作圆形排列共有种不同排法、
20、解析:完成此事共分6步,第一步;将第一名实习生分配到车间有7种不同方案,第二步:将第二名实习生分配到车间也有7种不同方案,依次类推,由分步计数原理知共有种不同方案、
21、 解析:C。设购买软件片、磁盘盒,则,所以;,;。故共7种。
22、 解析:(包括两个数不同与相同得情形！)
23、解析:(1)先把30030分解成质因数得形式:30030=2×3×5×7×11×13;依题意偶因数2必取,3,5,7,11,13这5个因数中任取若干个组成成积,所有得偶因数为
个(或)、
(2)分析知7必排在8之后,5必排在7之后、 且8得前面只有2个数,8、7之间只有一个小于7得数,6或在7之前,或在7、5之间,或在5之后。
第一种情况:6在7之前,形如:##8#7#5# ,;
第2种情况: 6在7、5之间 ,形如:##8#765# ,;
第3种情况:6在5之后,形如:##8#75## ,
所以共144种。
24、解析:(1)因为圆得一个内接四边形得两条对角线相交于圆内一点,一个圆得内接四边形就对应着两条弦相交于圆内得一个交点,于就是问题就转化为圆周上得10个点可以确定多少个不同得四边形,显然有个,所以圆周上有10点,以这些点为端点得弦相交于圆内得交点有个、
(2)解析:可将图中矩形得一边叫一小段,从到最短路线必须走7小段,其中:向东4段,向北3段;而且前一段得尾接后一段得首,所以只要确定向东走过4段得走法,便能确定路径,因此不同走法有种、
25、解析:从5个球中取出2个与盒子对号有种,还剩下3个球与3个盒子序号不能对应,利用枚举法分析,如果剩下3,4,5号球与3,4,5号盒子时,3号球不能装入3号盒子,当3号球装入4号盒子时,4,5号球只有1种装法,3号球装入5号盒子时,4,5号球也只有1种装法,所以剩下三球只有2种装法,因此总共装法数为种、
26、解:错排问题,分类解决:
27、 解析:设第次球仍回到得手中得传球方法种数就是,则,且,所以()。
28、 解析:(1)设跨1级、2级、3级得步数分别为,则,解得,故方法数为
(2)设上完n级台阶得方法数为,则,且,

29.解析:;
30.解析:(1);(2);(3)先在编号为1,2,3,4,5得五个盒子中依次放入0,1,2,3,4个球,再只要保证余下得10个球每个盒子至少放一个,则
31、 解析:
32、 解析:49、
33、 解析:
34、 解析:前9个扇形依次染色并不难,但第10个扇形既与第九个相邻也与第1个相邻,这两个扇形颜色可能相同也可能不相同,所以直接用记数原理有困难,但建立递推关系并不难.
设将圆分成n个不相等得扇形时,满足题设得染法有种.依次记n个扇形为s,…s、显然a1=3、当n=2时,先对s1染色,有3种方法;s1染色后再对s2染色,有2种方法,故a2=6、当n≥3时,我们依次对s,s2,…s染色.对s1染色,有3种方法,对s1染色后再对s2染色有2种方法,同样得对s3,s4…,sn分别有2种方法,由乘法原理共有3·2 n-1种染色方法.但这样做sn与s1有可能同色.即在3·2 n-1种染色方法中包含了sn与s1同色得染色方法.对于sn与s1同色得情形,拆去sn与s1得边界使sn与s1合并,便得到将圆分为n-1个扇形时同色不相邻得染色方法,这样得情况有an-1种. 故an=3·2 n-1-an-1 (n≥3).所以,n≥3时,,∴a10=210+2=1026.
35、解:由题意,红黄蓝三种颜色,每种颜色恰好涂了两次,分为两类:
第一类可按一下步骤进行:
第1步:涂第一格,有3种方法;
第2步:涂第二格,有2种方法;
第3步:用与第一格不同得颜色涂第三格,有1种方法;
第4步:第四格可以涂与第三格颜色不同得,有2种方法。
第5步:用不同得两色涂剩下得两格,有2种方法;
所以有3*2*1*2*2＝24种
第二类可按一下步骤进行:
第1步:涂第一格,有3种方法;
第2步:涂第二格,有2种方法;
第3步:用与第一格相同得颜色涂第三格,有1种方法;
第4步:第四格只能用没有用过得颜色涂,有种方法。
第5步:第五格只能用涂第二格得颜色,第六格只能用涂第四格得颜色,有1种方法;
所以有3*2*1*1*1＝6种
所以,共有24+6＝30种涂法。
36、解析:注意4种颜色得花都有种上。
(变式:)