还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
排列组合问题经典题型与通用方法相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组,当作一个大元素参与排列.L例民五人并排站成一排,如果必须相邻且在的右边,则不同的排法有
1.A,CDE A38A、种、种、种、种A60B48C36D
24.相离问题插空排:元素相离即不相邻问题,可先把无位置要求的几个元素全排列,再把规定的相2离的几个元素插入上述几个元素的空位和两端.例.七人并排站成一行,如果甲乙两个必须不相邻,那么不同的排法种数是
2、种、种、种、种A1440B3600C4820D4800例.已知集合集合{卜生,/,%},且若3A={1,2,3,,19,20},8=3uA,lij=则满足条件的集合B有多少个I q|W1,2,3,4,.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序,可用缩小倍数的方法.3例五人并排站成一排,如果必须站在的右边可以不相邻那么不同
4.1A,B,C,D,E3A A,3的排法有、种、种、种、种A24B6C9D12由数字,组成没有重复数字的六位数,其中个位数字小于十位数字的共有21,2,3,4,
5、种、种、种、种A21B30C464D60解析解析被取的两个数中至少有一个能被整除时,他们的乘积就能被整除,将这
11.177100个数组成的集合视为全集能被整除的数的集合记做共有个元素,不能被整I,7A={7,14,21,98}147除的数组成的集合记做共有个元素;由此可知,从中任取个元素的取法有N={1,2,3,4,,100}86A2C,从中任取一个,又从入中任取一个共有两种情形共符合要求的取法有种.A C+C\C;6=1295解析将/=分成四个不相交的子集,能被整除的数集2{1,2,3,100}4能被除余的数集能被除余的数集A={4,8,12,100};418={1,5,9,97},42={能被除余的数集』易见这四个集合中每一个有个元素;从人中任取两2,6,,98},43{3,71,99},25个数符合要;从民中各取一个数也符合要求;从中任取两个数也符合要求;此外其它取法都不C符合要求;所以符合要求的取法共有种.C;5+C;55+C;5=1225解,其中、位可填、位可填
12.108a b c da c1,2,3,4,5;b d123,4,5,6,7,
9.,其中、位可填、位可填209a b c da c1,2,3,4,5;b d123,4,5,6,7,
8.先填、再填、共点耳a c,b d,2=
1200.解析设全集二{人中任取人参赛的排列},二{甲跑第一棒的排列},二{乙跑第四棒1364A B的排列},根据求集合元素个数的公式得参赛方法共有〃(/)-〃()n(A)二父—£—£+种.A—“⑻+c B4=
252.解析老师在中间三个位置上选一个有种,名同学在其余个位置上有种方法;所以共1444A有种.=
72.解析)前后两排可看成一排的两段,因此本题可看成个不同的元素排成一排,共种,15(164=720选C.)解析看成一排,某个元素在前半段四个位置中选排个,有种,某个元素排在后半段(2221的四个位置中选一个有种,其余个元素任排个位置上有反种,故共有看种排法.45546=
5760.解析逆向思考,至少各一台的反面就是分别只取一种型号,不取另一种型号的电视机,故不同161的取法共有《一种,选.C;—=70C解析至少要甲型和乙型电视机各一台可分两种情况甲型台乙型台;甲型台乙型台;故21221不同的取法有ClC\+台,选=70C..解析)先取四个球中二个为一组,另二组各一个球的方法有种,再排在四个盒中每次17(1C排个有团种,故共有种.3CM=144)先取男女运动员各名,有种,这四名运动员混和双打练习有反中排法,故共有(22种.=
120.解析正方体个顶点从中每次取四点,理论上可构成四面体,但个表面和个对角面1818C;66的四个顶点共面都不能构成四面体,所以四面体实际共有个.C;-12=58解析个点中任取个点共有种,其中四点共面的有三种情况
①在四面体的四个面2104上,每面内四点共面的情况为盘,四个面共有个;
②过空间四边形各边中点的平行四边形共个;4C3
③过棱上三点与对棱中点的三角形共个.所以四点不共面的情况的种数是6品种.-4C-3-6=141个3568+1x4x6+2x2x6=56
①一个面内取两点,另一个点取时、即个角;GH F8
②一个面内取两点,另一个点取时,个;GH K2x2x6=24
③一个面内取两点,那另一个点只能取或个HI A C,2x2x6=24因为四面体中仅有对异面直线,可将问题分解成正方体的个顶点可构成多少个不同的四面438体,从正方体个顶点中任取四个顶点构成的四面体有个,所以个顶点可连成的异面8C;-12=588直线有对.3x58=
174.解析首先可让位姐姐站成一圈,属圆排列有种,然后在让插入其间,每位均可插入其姐姐195A的左边和右边,有种方式,故不同的安排方式种不同站法.说明从几个不同元素中取224x25=768出用个元素作圆形排列共有「俨种不同排法..解析完成此事共分步,第一步;将第一名实习生分配到车间有种不同方案,第二步将第二2067名实习生分配到车间也有种不同方案,依次类推,由分步计数原理知共有种不同方案.776x3,y
2.解析设购买软件工片、磁盘盒,则{所以尢=x.yeN21Co y60x+70y W500,3,y=2,3,4;x=4,故共种y=2,3,4;x=5,y=
27.解析包括两个数不同和相同的情形!2221+2++49+50=
2500.解析先把分解成质因数的形式依题意偶因数必取,2313003030030=2x3x5x7x11x13;23,5,7,这个因数中任取若干个组成成积,所有的偶因数为11,135个或C;+C+C;+C;+C;+C=321・25=
32.分析知必排在之后,必排在之后.且的前面只有个数,、之间只有一个小于的数,2785782877或在之前,或在、之间,或在之后67755第一种情况在之前,形如67##8#7#5#,C;A=72;第种情况在、之间,形如=24;2675##8#765#,第种情况在之后,形如365##8#75##,=48所以共种
144.解析因为圆的一个内接四边形的两条对角线相交于圆内一点,一个圆的内接四边形就对应241着两条弦相交于圆内的一个交点,于是问题就转化为圆周上的个点可以确定多少个不同的四边形,10显然有个,所以圆周上有点,以这些点为端点的弦相交于圆内的交点有个.C210=210解析可将图中矩形的一边叫一小段,从到最短路线必须走小段,其中向东段,向2A874北段;而且前一段的尾接后一段的首,所以只要确定向东走过段的走法,便能确定路径,因此不34同走法有仁种.=
35.解析从个球中取出个与盒子对号有种,还剩下个球与个盒子序号不能对应,利用枚2552C;33举法分析,如果剩下号球与号盒子时,号球不能装入号盒子,当号球装入号盒3,4,53,4,53334子时,号球只有种装法,号球装入号盒子时,号球也只有种装法,所以剩下三球只4,51354,51有种装法,因此总共装法数为种.22C;=
20.解错排问题,分类解决26C;/5+C;/4+C3=
109.解析设第%次球仍回到的手中的传球方法种数是以,则且27q4=0,%=〃—La=n-lk-[-a_所以k ki9ak—I”=1]=akn nx=2,3,4y=x+y+z=6,4,2,z=,解得《解析设跨级、级、级的步数分别为则
28.1123x,y,z,x+2y+3z=10」,02故方法数为C;+C C;+C=15+60+15=90设上完级台阶的方法数为/〃,则且/〃一fn-2n/1=1,/2=2,/3=4,/H=/D+2+3〃,4・・・/4=7,/5=136=24⑺=44,/8=81,f9=149,/10=274解析;C匕t
29.C;;解析二以;先在编号为的五个盒子中依次放
30.143876;231,2,3,4,5入个球,再只要保证余下的个球每个盒子至少放一个,则0,123,410C=126解析
31.C;・C;♦22=
120.解析:
3249.解析:
33.C C;+C C;C+C C;C;=35+120+30=185解析前个扇形依次染色并不难,但第个扇形既与第九个相邻也与第个相邻,这两个扇形
34.911颜色可能相同也可能不相同,所以直接用记数原理有困难,但建立递推关系并不难.设将圆分成个不相等的扇形时,满足题设的染法有〃〃种.依次记个扇形为〃.显然尸.n ns],…s a3当时,先对染色,有种方法;染色后再对染色,有种方法,故.当时,我n=2si3si S22@2=6nN3们依次对染色.对染色,有种方法,对染色后再对染色有种方法,同样的对Sj,S2,...S S13S1S22Z1分别有种方法,由乘法原理共有局种染色方法.但这样做际与有可能同色.即在S3,S4…,Sn23・2S13・向种染色方法中包含了与同色的染色方法.对于与同色的情形,拆去即与的边界使2Sn S1Sn S1S]际与合并,便得到将圆分为个扇形时同色不相邻的染色方法,这样的情况有种.故S]n-1a.i a„=3-2n向密田n
3.所以3=6,nN3时.,a=2,+2-—1,,.*.aio=2lo+2=lO
26.n.解由题意,红黄蓝三种颜色,每种颜色恰好涂了两次,分为两类35第一类可按一下步骤进行第步涂第一格,有种方法;13第步涂第二格,有种方法;22第步用与第一格不同的颜色涂第三格,有种方法;31第步第四格可以涂与第三格颜色不同的,有种方法42第步用不同的两色涂剩下的两格,有种方法;52所以有种3*2*1*2*2=24第二类可按一下步骤进行第步涂第一格,有种方法;13第步涂第二格,有种方法;22第步用与第一格相同的颜色涂第三格,有种方法;31第步第四格只能用没有用过的颜色涂,有种方法4第步第五格只能用涂第二格的颜色,第六格只能用涂第四格的颜色,有种方法;51所以有种3*2*1*1*1=6所以,共有种涂法24+6=
30.解析:注意种颜色的花都有种上364A;l+1+1+2=120变式硕C;C;+3+2・2]=
960.标号排位问题分步法:把元素排到指定位置上,可先把某个元素按规定排入,第二步再排另一个元4素,如此继续下去,依次即可完成.例.将数字填入标号为的四个方格里,每格填一个数,则每个方格的标号与所填51,2,3,41,2,3,4数字均不相同的填法有、种、种、种、种A6B9C11D
23.有序分配问题逐分法:有序分配问题指把元素分成若干组,可用逐步下量分组法.5例有甲乙丙三项任务,甲需人承担,乙丙各需一人承担,从人中选出人承担这三项任务,
6.12104不同的选法种数是、种、种、种、种A1260B2025C2520D5040名同学分别到三个不同的路口进行流量的调查,若每个路口人,则不同的分配方案有
2124、种、种、黑/种、或军种A dB3c:C;CC C;D
14.全员分配问题分组法6例名优秀学生全部保送到所学校去,每所学校至少去一名,则不同的保送方案有多少种?
7.143本不同的书,全部分给个学生,每个学生至少一本,不同的分法种数为
254、种、种、种、种A480B240C120D
96.名额分配问题隔板法例个三好学生名额分到个班级,每个班级至少一个名额,有多少78107种不同分配方案例.马路上有编号为…,九只路灯,现要关掉其中的三盏,但不能关掉相邻的二盏或三盏,也91,2,39不能关掉两端的两盏,求满足条件的关灯方案有多少种?.限制条件的分配问题分类法8例现安排甲、乙、丙、丁、戊名同学参加上海世博会志愿者服务活动,每人从事翻译、导游、礼
1.5仪、司机四项工作之一,每项工作至少有一人参加.甲、乙不会开车但能从事其他三项工作,丙、丁、戊都能胜四项工作,则不同安排方案的种数是A.152B.126C.90D.
54.多元问题分类法元素多,取出的情况也多种,可按结果要求分成不相容的几类情况分别计数再相9加例从这个数中,任取两个数,使它们的乘积能被整除,这两个数的取法不1111,2,3…,1001007计顺序共有多少种?从1,…,这个数中任取两个数,使其和能被整除的取法不计顺序有多少种?22,3,1001004例电子表点分秒时,显示的数字是那么,从点到点内,电
12.10200810:20:08,810子表个数码均不相同的情况有多少种?
6.交叉问题集合法某些排列组合问题几部分之间有交集,可用集合中求元素个数公式10nAu B=nA+nB-nA Bn例.从名运动员中选出人参加米接力赛,如果甲不跑第一棒,乙不跑第四棒,共有多少种13644x100不同的参赛方案?定位问题优先法某个或几个元素要排在指定位置,可先排这个或几个元素;再排其它的元素1L例.现名老师和名获奖同学排成一排照相留念,若老师不站两端则有不同的排法有多少种
1414.多排问题单排法:把元素排成几排的问题可归结为一排考虑,再分段处理12例个不同的元素排成前后两排,每排个元素,那么不同的排法种数是
15.
163、种、种、种、种A36B120C720D1440个不同的元素排成前后两排,每排个元素,其中某个元素要排在前排,某个元素排在28421后排,有多少种不同排法?至少,,“至多,,问题用间接排除法或分类法13,例.从台甲型和台乙型电视机中任取台,其中至少要甲型和乙型电视机各一台,则不同的取16453法共有、种、种、种、种A140B80C70D
35.选排问题先取后排:从几类元素中取出符合题意的几个元素,再安排到一定的位置上,可用先取后14排法.例四个不同球放入编号为的四个盒中,则恰有一个空盒的放法有多少种?
17.11,2,3,4名乒乓球运动员,其中男名,女名,现在要从中选人进行混合双打训练,有多少种29544不同的选法?.几何问题15例以正方体的顶点为顶点的四面体共有
18.
1、种、种、种、种A70B64C58D52四面体的顶点和各棱中点共点,在其中取个不共面的点,不同的取法共有
2104、种、种、种、种A150B147C144D141记正方体的各条棱的中点构成的集合为则过且仅过集合的三个点的平面有多少个?3M,M正方体个顶点可连成多少对异面直线
48.圆排问题单排法:把〃个不同元素放在圆周几个无编号位置上的排列,顺序(例如按顺时钟)不16同的排法才算不同的排列,而顺序相同(即旋转一下就可以重合)的排法认为是相同的,它与普通排列的区别在于只计顺序而无首位、末位之分,下列〃个普通排列,〃〃;出,,〃〃,在圆排列中只算一种,因为旋转后可以重合,故认q,〃2,〃33,4,为相同,〃个元素的圆排列数有里种.因此可将某个元素固定展成单排,其它的元素全排列.n例.有对姐妹站成一圈,要求每对姐妹相邻,有多少种不同站法?
195.可重复的排列求募法:允许重复排列问题的特点是以元素为研究对象,元素不受位置的约束,可17逐一安排元素的位置,一般地几个不同元素排在加个不同位置的排列数有mn种方法.例把名实习生分配到个车间实习共有多少种不同方法?
20.
67.元素个数较少的排列组合问题可以考虑枚举法19例某电脑用户计划使用不超过元的资金购买单价分别元、元的单片软件和盒装磁盘,
21.5006070根据需要,软件至少买片一,磁盘至少买盒,则不同的选购方法有()32种种种种A.5B.6C.7D.8例从到()的一百个自然数中,每次取出两个数,使其和大于这样的取法共有多少种?
22.110100,.复杂的排列组合问题也可用分解与合成法例()例能被多少个不同偶数整除
2023.1030设是由,〃的一个排列,把排在的左边且比小的数的个数称为的2L2,q qq顺序数/如在排列中,的顺序数为的顺序数为则在0=1,2,6,4,5,3,2151,
30.由这八个数字构成的全排列中,同时满足的顺序数为、的顺序数为、的顺序1,2,,882735数为的不同排列的种数为多少?
3.利用对应思想转化法:对应思想是教材中渗透的一种重要的解题方法,它可以将复杂的问题转化21为简单问题处理.例圆周上有点,以这些点为端点的弦相交于圆内的交点最多有多少个?
24.110某城市的街区有个全等的矩形组成,其中实线表示马路,从到的最短212A B路径有多少种?.全错位排列问题公式法:全错位排列问题贺卡问题,信封问题记住公式即可22瑞士数学家欧拉按一般情况给出了一个递推公式用、、表示写着位友人名字的信封,、A BC……n a、表示份相应的写好的信纸把错装的总数为记作假设把错装进里了,包含着bc.…・・n fna B这个错误的一切错装法分两类装入里,这时每种错装的其余部分都与、、、无关,应有种错装法1b AA B a bfn-2装入、之外的一个信封,这时的装信工作实际是把除之外的个信纸、装入除2b ABan-1bcB以外的个信封、,显然这时装错的方法有种n—1AC……fn-l总之在装入的错误之下,共有错装法种装入装入的种错误之下,a Bfn.2+fn.l aC,D……n—2同样都有种错装法,因此得到一个递推公式:分别fn・2+fn-l fn=n-l-[fn-l+fn-2],带入、、等可推得结果也可用迭代法推导出一般公式:n=234n\1!2!3!例.设有编号为的五个球和编号为的盒子现将这个球投入个盒子要求每251,2,3,4,51,2,3,4,555个盒子放一个球,并且恰好有两个球的号码与盒子号码相同,问有多少种不同的方法?例、位同学原来坐成一排,现让他们重新坐,则至多有两位同学坐在其原来的位置的不同的坐法265是多少?.多人传球问题(构造递推关系)23例、由,(〃)〃个人传球,第一次由开始传球,可传给其他任何一个人,第二274,,4〃23q次由拿球者再传给其他任何一个人,如此继续,则第次球仍回到的手中的传球方法种数k4是多少?.上台阶问题24例、()级台阶,某人可一步跨一级,也可跨两级,也可跨三级281他步就可上完台阶的方法数是多少?
(1)6)他上完台阶的方法总数是多少?(
2.方程的正整数解的个数问题(隔板法)25例.方程为+々++x〃=k(k,neN*,kNn)的正整数解有多少个?有多少非负整数解个?29例将个完全相同的球放入编号为的五个盒子中
30.201,2,3,4,5若要求每个盒子至少放一个球,则一共有多少种放法?
(1)()若每个盒子可放任意个球,则一共有多少种放法?2)若要求每个盒子放的球的个数不小于其编号数,则一共有多少种放法?(
3.配对(配凑)问题26例双相异的鞋共只,现随机地取出只,恰好能配成双鞋的取法是多少?
31.51062例名选手参加乒乓球淘汰赛比赛,需要打多少场才能产生冠军?淘汰赛比赛规则是:要淘汰
32.501名选手必须进行场比赛;反之,每进行场比赛则淘汰名选手111例有名翻译人员,其中名是英语翻译人员,名是日语翻译人员,另人英、日语均精通现
33.11542从中选出人组成两个翻译小组,其中人翻译英语,另人翻译日语,则有多少种不同的选派844方式?.染色问题27例把圆分成个不相等的扇形,并且用红、黄、蓝三种颜色给扇形染色,但不允许相邻的扇形有相
34.10同的颜色,问共有多少种染色法?例.在如图所示的六个空格里涂上红黄蓝三种颜色,每种颜色只能35涂两次,要求相邻空格不同色,请问一共有多少种涂法?123456例某城市在中心广场建造一个花圃,花圃分为个部分(如图),现要栽种种不同颜色的花,
36.64每部分栽种一种且相邻部分不能栽种同样颜色的花,则不同的栽种方法有多少种?(变式若要栽种种颜色的花?)5排列组合问题经典题型答案解析把视为一人,且固定在的右边,则本题相当于人的全排列,禺=种,答案:L A,8B A424D..解析除甲乙外,其余个排列数为耳种,再用甲乙去插个空位有可种,不同的排法种数是256种,选反64=3600易知互不相等且不相邻,则有
3.4,〃2,3,4=
2380.解析在的右边与在的左边排法数相同,所以题设的排法只是个元素全排列数的一413A3A5半,即工种,选6=
603.按题意,个位数字只可能是共种情况,分别有个,尺可隹馈,隹20,123,456HAS,个,合并总计个,选工种3003A—6=
300.解析先把填入方格中,符合条件的有种方法,第二步把被填入方格的对应数字填入其它三个513方格,又有三种方法;第三步填余下的两个数字,只有一种填法,共有种填法,选B.3x3xl=
9.解析先从人中选出人承担甲项任务,再从剩下的人中选人承担乙项任务,第三步从6110281另外的人中选人承担丙项任务,不同的选法共有比以;=种,选712520C.答案
27.1=36答案B.2C;A=240,.解析个名额分到个班级,就是把个名额看成个相同的小球分成堆,每堆至少一个,可810710107以在个小球的个空位中插入块木板,每一种插法对应着一种分配方案,故共有不同的分配1096方案为种.C=
84.解析把此问题当作一个排对模型,在盏亮灯的个空隙中插入盏不亮的灯种方法,所以9653C;满足条件的关灯方案有种.10说明一些不易理解的排列组合题,如果能转化为熟悉的模型如填空模型,排队模型,装盒模型可使问题容易解决.
10.。