小学奥数专题--排列组合推理篇

《小学奥数专题--排列组合推理篇》由会员分享，可在线阅读，更多相关《小学奥数专题--排列组合推理篇（5页珍藏版）》请在装配图网上搜索。

1、排列组合问题 排列问题题型分类：1.信号问题2.数字问题3.坐法问题4.照相问题5.排队问题 组合问题题型分类：1.几何计数问题2.加乘算式问题 3.比赛问题 4.选法问题 常用解题方法和技巧：1.优先排列法2.总体淘汰法3.合理分类和准确分步4.相邻问题用捆绑法 5.不相邻问题用插空法6.顺序问题用除法7.分排问题用直接法8.试验法9.探索法10.消序法12.住店法对应法13.去头去尾法14.树形图法15.类推法16.几何计数法17.标数法18.对称法分类相加,分步组合,有序排列,无序组合基础知识数学概率方面的基本原理 加法原理：做一件事情,完成它有N类办法,在第一类办法中有M1中不同的方法

2、,在第二类办法中有M2中不同的方法,在第N类办法中有Mn种不同的方法,那么完成这件事情共有M1+M2+Mn种不同的方法. 乘法原理：完成某项任务,可分为k个步骤,完成第一步有n1种不同的方法,完成第二步有n2种不同的方法,完成第步有种不同的方法,那么完成此项任务共有种不同的方法. 两个原理的区别 做一件事,完成它若有n类办法,是分类问题,每一类中的方法都是独立的,故用加法原理.每一类中的每一种方法都可以独立完成此任务；两类不同办法中的具体方法,互不相同；完成此任务的任何一种方法,都属于某一类 做一件事,需要分n个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才

3、算完成,因此用乘法原理任何一步的一种方法都不能完成此任务,必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同,则对应的完成此事的方法也不同 这样完成一件事的分类和步是有本质区别的,因此也将两个原理区分开来一. 排列与组合基本公式1. 排列与计算公式 ：从n个不同元素中,任取m个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 Pmn表示.Pmn =n=. 2. 组合与计算公式 ：从n个不同元素中,任取m个元素并成一组,叫做从n个不同元素中取出

4、m个元素的一个组合；从n个不同元素中取出m个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号Cmn表示.Cmn = Pmn /m!=一般当遇到m比较大时常常是m0.5n时,可用Cmn = Cn-mn来简化计算.规定：Cnn =1, C0n=1.3. n的阶乘n个不同元素的全排列Pnn=n!=n321二. 两个基本计数原理与应用例1从1、2、3、20这二十个数中任取三个不同的数组成等差数列,这样的不同等差数列有_个. 分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题.设a,b,c成等差, 2b=a+c, 可知b由a,c决定,又 2b是偶数, a,c同奇

5、或同偶,即：从1,3,5,19或2,4,6,8,20这十个数中选出两个数进行排列,由此就可确定等差数列,如：a=1,=7,则b=4即每一组a,c必对应唯一的b,另外1、4、7和7、4、1按同一种等差数列处理C21010990,同类同奇或同偶相加,即本题所求=290180. 例2某城市有4条东西街道和6条南北的街道,街道之间的间距相同,如图.若规定只能向东或向北两个方向沿图中路线前进,则从M到N有多少种不同的走法? 分析：对实际背景的分析可以逐层深入 从M到N必须向上走三步,向右走五步,共走八步. 每一步是向上还是向右,决定了不同的走法. 事实上,当把向上的步骤决定后,剩下的步骤只能向右.从而,

6、任务可叙述为：从八个步骤中选出哪三步是向上走,就可以确定走法数, 本题答案为：C38=56.注意加法原理与乘法原理的特点,分析是分类还是分步,是排列还是组合.采用加法原理首先要做到分类不重不漏,如何做到这一点？分类的标准必须前后统一.注意排列组合的区别与_所有的排列都可以看作是先取组合,再做全排列；同样,组合如补充一个阶段可转化为排列问题.例3在一块并排的10垄田地中,选择二垄分别种植A,B两种作物,每种种植一垄,为有利于作物生长,要求A,B两种作物的间隔不少于6垄,不同的选法共有_种.分析：条件中要求A、B两种作物的间隔不少于6垄这个条件不容易用一个包含排列数,组合数的式子表示,因而采取分类

7、的方法.第一类：A在第一垄,B有3种选择； 第二类：A在第二垄,B有2种选择； 第三类：A在第三垄,B有1种选择, 同理A、B位置互换 ,共12种.经典题目： 1恰好能被6,7,8,9整除的五位数有多少个?分析与解 6、7、8、9的最小公倍数是504,五位数中,最小的是10000,最大为99999 因为10000504：19424,99999504=198207所以,五位数中,能被504整除的数有198-19=179个 所以恰好能被6,7,8,9整除的五位数有179个2小明的两个衣服口袋中各有13张卡片,每张卡片上分别写着1,2,3,13如果从这两个口袋中各拿出一张卡片来计算它们所写两数的乘积

8、,可以得到许多不相等的乘积那么,其中能被6整除的乘积共有多少个?分析与解 这些积中能被6整除的最大一个是1312=266,最小是6但在l6266之间的6的倍数并非都是两张卡片上的乘积,其中有256,236,216,196,176这五个不是所求的积共有26-5=21个31,2,3,4,5,6这6个数中,选3个数使它们的和能被3整除那么不同的选法有几种?分析与解被3除余1的有1,4；被3除余2的有2,5；能被3整除的有3,6从这6个数中选出3个数,使它们的和能被3整除,只能是从上面3类中各选一个,因为每类中的选择是相互独立的,共有222=8种选法 4同时满足以下条件的分数共有多少个?大于,并且小于

9、； 分子和分母都是质数； 分母是两位数 分析与解 由知分子是大于1,小于20的质数如果分子是2,那么这个分数应该在与之间,在这之间的只有符合要求如果分子是3,那么这个分数应该在与之间,15与18之间只有质数17,所以分数是同样的道理,当分子是5,7,11,13,17,19时可以得到下表分子分数分子分数211313517719于是,同时满足题中条件的分数共13个5一个六位数能被11整除,它的各位数字非零且互不相同的将这个六位数的6个数字重新排列,最少还能排出多少个能被11整除的六位数?分析与解 设这个六位数为,则有、的差为0或11的倍数且、均不为0,任何一个数作为首位都是一个六位数 先考虑、偶数

10、位内,、奇数位内的组内交换,有=36种顺序；再考虑形如这种奇数位与偶数位的组间调换,也有=36种顺序 所以,用均不为0的、最少可以排出36+36=72个能被11整除的数 所以最少还能排出72-1=71个能被11整除的六位数6在大于等于1998,小于等于8991的整数中,个位数字与十位数字不同的数共有多少个? 分析与解 先考虑20008999之间这7000个数,个位数字与十位数字不同的数共有710=6300 但是1998,89928998这些数的个位数字与十位数字也不同,且1998在19988991内,89928998这7个数不在19988991之内所以在19988991之内的个位数字与十位数字

11、不同的有6300+1-7=6294个7个位、十位、百位上的3个数字之和等于12的三位数共有多少个?分析与解 12=0+6+6=0+5+7 = 0+4+8 = 0+3+9 = 1+5+6= 1+4+7=1+3+8=1+2+9=2+5+5=2+4+6=2+3+7=2+2+8=3+4+5=3+3+6=4+4+4 其中三个数字均不相等且不含0的有7组,每组有种排法,共7=42种排法；其中三个数字有只有2个相等且不含0的有3组,每组有2种排法,共有32=9种排法；其中三个数字均相等且不含0的只有1组,每组只有1种排法； 在含有0的数组中,三个数字均不相同的有3组,每组有2种排法,共有32=12种排法；在

12、含有0的数组中,二个数字相等的只有1组,每组有22种排法,共有2种排法 所以,满足条件的三位数共有42+9 + 1+12+2 = 66个8一个自然数,如果它顺着看和倒过来看都是一样的,那么称这个数为回文数例如1331,7,202都是回文数,而220则不是回文数问：从一位到六位的回文数一共有多少个?其中的第1996个数是多少? 分析与解 我们将回文数分为一位、二位、三位、六位来逐组计算,所有的一位数均是回文数,即有9个；在二位数中,必须为形式的,即有9个；在三位数中,必须为形式的,即有910 =90个；在四位数中,必须为形式的,即有910个；在五位数中,必须为形式的,即有91010=900个；在

13、六位数中,必须为形式的,即有91010=900个所以共有9+9+90+90+900+900=1998个,最大的为999999,其次为998899,再次为997799 而第1996个数为倒数第3个数,即为997799所以,从一位到六位的回文数一共有1998个,其中的第1996个数是9977999一种电子表在6时24分30秒时的显示为6:24,那么从8时到9时这段时间里,此表的5个数字都不相同的时刻一共有多少个?分析与解 设A:BC是满足题意的时刻,有A为8,B、D应从0,1,2,3,4,5这6个数字中选择两个不同的数字,所以有种选法,而C、E应从剩下的7个数字中选择两个不同的数字,所以有种选法,

14、所以共有=1260种选法,即从8时到9时这段时间里,此表的5个数字都不相同的时刻一共有1260个10用数字1,2组成一个八位数,其中至少连续四位都是1的有多少个?分析与解 当只有四个连续的1时,可以为11112 * * *,211112 * * ,* 211112*,* *211112,*21111,因为*号处可以任意填写1或2,所以这些数依次有23,22,22,22,23个,共28个；当有五个连续的l时,可以为111112*,2111112*,*2111112,*211111,依次有22,2,2,22个,共12个；当有六个连续的1时,可以为1111112*,21111112,*2111111

15、,依次有2,1,2个,共5个；当有七个连续的1时,可以为11111112,21111111,共2个：当有八个连续的l时,只能是11111111,共1个 所以满足条件的八位数有28+12+5+2+1=48个11在1001,1002,2000这1000个自然数中,可以找到多少对相邻的自然数,满足它们相加时不进位?分析与解 设为满足条件的两个连续自然数,有=+1我们只用考察的取值情况即可我们先不考虑数字9的情况,则只能取0,1,2,3,4；只能取0,1,2,3,4；只能取0,1,2,3,4；对应的有555=125组数当=9时,有的下一个数为,要想在求和时不进位,必须9,所以此时只能取0,1,2,3,

16、4；而也只能取0,1,2,3,4；共有55=25组数当=99时,有的下一个数为,要想在求和时不进位,必须+9,所以此时只能取0,1,2,3,4；共有5组数所以,在1001,1002,2000这1000个自然数中,可以找到125+25+5=155对相邻的自然数,满足它们相加时不进位12把1995,1996,1997,1998,1999这5个数分别填入图20-1中的东、南、西、北、中5个方格内,使横、竖3个数的和相等那么共有多少种不同填法? 分析与解 显然只要有东+西=南+北即可,剩下的一个数字即为中因为题中五个数的千位、百位、十位均相同,所以只用考虑个位数字,显然有5+9=6+8,5+8=6+7

17、,6+9=7+8先考察5+9=6+8,可以对应为东+西=南+北,因为东、西可以调换,南、北可以对调,有22=4种填法,而东、西,南、北可以整体对调,于是有42=8种填法 5 + 8 = 6+7,6+9=7+8同理均有8种填法,所以共有83=24种不同的填法13在图20-2的空格内各填人一个一位数,使同一行内左面的数比右面的数大,同一列内上面的数比下面的数小,并且方格内的6个数字互不相同,例如图20-3为一种填法那么共有多少种不同的填法?23 图20-2642753 图20-3分析与解 为了方便说明,标上字母：CD2AB3要注意到,A最大,D最小,B、C的位置可以互换但是,D只能取4,5,6,因

18、为如果取7,就找不到3个比它大的一位数了当D取4,5,6时分别剩下5,4,3个一位大数有B、C可以互换位置所有不同的填法共2+2+2=102+42+12=30种14从1至9这9个数字中挑出6个不同的数填在图204的6个圆圈内,使任意相邻两个圆圈内数字之和都是质数那么共能找出多少种不同的挑法? 分析与解 显然任意两个相邻圆圈中的数一奇一偶,因此,应从2、4、6、8中选3个数填入3个不相邻的圆圈中：填入2、4、6,这时3与9不能同时填入没有3、9的有1种；有3或9的,其他3个奇数l、5、7要去掉1个,因而有23=6种,共1+67种：填入2、4、8这时7不能填入,从其余4个奇数中选3个,有4种选法,

19、都符合要求：填入2、6、8这时7不能填入,而3与9只能任选1个,因而有2种选法：填入4、6、8这时3与9只能任选1个,1与7也只能任选1个因而有22=4种选法共有7+4+2+4 = 17种选法15.一个骰子六个面上的数字分别为0,1,2,3,4,5,现在掷骰子,把每次掷出的点数依次求和,当总点数超过12时就停止不再掷了,这种掷法最有可能出现的总点数是几？课下练习：1.从甲地到乙地有2种走法,从乙地到丙地有4种走法,从甲地不经过乙地到丙地有3种走法,则从甲地到丙地的不同的走法共有种2.甲、乙、丙3个班各有三好学生3,5,2名,现准备推选两名来自不同班的三好学生去参加校三好学生代表大会,共有种不同

20、的推选方法3.从甲、乙、丙三名同学中选出两名参加某天的一项活动,其中一名同学参加上午的活动,一名同学参加下午的活动有种不同的选法4.从a、b、c、d这4个字母中,每次取出3个按顺序排成一列,共有种不同的排法5.若从6名志愿者中选出4人分别从事翻译、导游、导购、保洁四项不同的工作,则选派的方案有种6.有a,b,c,d,e共5个火车站,都有往返车,问车站间共需要准备种火车票7.某年全国足球甲级联赛有14个队参加,每队都要与其余各队在主、客场分别比赛一场,共进行场比赛8.由数字1、2、3、4、5、6可以组成个没有重复数字的正整数9.用0到9这10个数字可以组成个没有重复数字的三位数10.1有5本不同

21、的书,从中选出3本送给3位同学每人1本,共有种不同的选法；2有5种不同的书,要买3本送给3名同学每人1本,共有种不同的选法11.计划展出10幅不同的画,其中1幅水彩画、4幅油画、5幅国画,排成一行陈列,要求同一品种的画必须连在一起,那么不同的陈列方式有种12.1将18个人排成一排,不同的排法有少种；2将18个人排成两排,每排9人,不同的排法有种；3将18个人排成三排,每排6人,不同的排法有种13.5人站成一排,1其中甲、乙两人必须相邻,有种不同的排法；2其中甲、乙两人不能相邻,有种不同的排法；3其中甲不站排头、乙不站排尾,有种不同的排法14.5名学生和1名老师照相,老师不能站排头,也不能站排尾

22、,共有种不同的站法15.4名学生和3名老师排成一排照相,老师不能排两端,且老师必须要排在一起的不同排法有种16.停车场有7个停车位,现在有4辆车要停放,若要使3个空位连在一起,则停放的方法有种17.在7名运动员中选出4名组成接力队参加4100米比赛,那么甲、乙都不跑中间两棒的安排方有种18.一个口袋内装有大小相同的7个白球和1个黑球1从口袋内取出3个球,共有种取法；2从口袋内取出3个球,使其中含有1个黑球,有种取法；3从口袋内取出3个球,使其中不含黑球,有种取法19.甲,乙,丙,丁4个足球队举行单循环赛：1共需比赛场；2冠亚军共有种可能20.按下列条件,从12人中选出5人,有种不同选法1甲、乙、丙三人必须当选；2甲、乙、丙三人不能当选；3甲必须当选,乙、丙不能当选；4甲、乙、丙三人只有一人当选；5甲、乙、丙三人至多2人当选；6甲、乙、丙三人至少1人当选；5 / 5