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

. 排列组合问题²²²² “除法分类相加，分步组合，有序排列，无序组合根底知识数学概率方面的根本原理² 加法原理：做一件事情，完成它有N类方法，在第一类方法中有M1中不同的方法，在第二类方法中有M2中不同的方法，在第N类方法中有Mn种不同的方法，那么完成这件事情共有M1+M2+Mn种不同的方法。 ² 乘法原理：完成某项任务，可分为k个步骤，完成第一步有n1种不同的方法，完成第二步有n2种不同的方法，完成第步有种不同的方法，那么完成此项任务共有×××种不同的方法。² 两个原理的区别² 做一件事，完成它假设有n类方法，是分类问题，每一类中的方法都是独立的，故用加法原理。每一类中的每一种方法都可以独立完成此任务；两类不同方法中的具体方法，互不一样(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)² 做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的假设干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，那么对应的完成此事的方法也不同 这样完成一件事的分“类和“步是有本质区别的，因此也将两个原理区分开来一. 排列与组合根本公式1. 排列与计算公式 ：从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 Pmn表示.Pmn =n(n-1)(n-2)(n-m+1)=(规定0!=1). 2. 组合与计算公式 ：从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号Cmn表示.Cmn = Pmn /m!=一般当遇到m比拟大时常常是m>0.5n时，可用Cmn = Cn-mn来简化计算。规定：Cnn =1, C0n=1.3. n的阶乘(n!)n个不同元素的全排列Pnn=n!=n×(n-1)×(n-2)3×2×1二. 两个根本计数原理与应用例1从1、2、3、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有_个。 分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。设a,b,c成等差， 2b=a+c, 可知b由a,c决定，又 2b是偶数， a,c同奇或同偶，即：从1，3，5，19或2，4，6，8，20这十个数中选出两个数进展排列，由此就可确定等差数列，如：a=1，=7，那么b=4即每一组a,c必对应唯一的b，另外1、4、7和7、4、1按同一种等差数列处理C21010×990，同类同奇或同偶相加，即此题所求=2×90180。 例2某城市有4条东西街道和6条南北的街道，街道之间的间距一样，如图。假设规定只能向东或向北两个方向沿图中路线前进，那么从M到N有多少种不同的走法? 分析：对实际背景的分析可以逐层深入 从M到N必须向上走三步，向右走五步，共走八步。 每一步是向上还是向右，决定了不同的走法。 事实上，当把向上的步骤决定后，剩下的步骤只能向右。从而，任务可表达为：从八个步骤中选出哪三步是向上走，就可以确定走法数， 此题答案为：C38=56。注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合。采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。例3在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有_种。分析：条件中“要求A、B两种作物的间隔不少于6垄这个条件不容易用一个包含排列数，组合数的式子表示，因而采取分类的方法。第一类：A在第一垄，B有3种选择； 第二类：A在第二垄，B有2种选择； 第三类：A在第三垄，B有1种选择， 同理A、B位置互换 ，共12种。经典题目： 1恰好能被6，7，8，9整除的五位数有多少个?【分析与解】 6、7、8、9的最小公倍数是504，五位数中，最小的是10000，最大为99999 因为10000÷504：19424，99999÷504=198207所以，五位数中，能被504整除的数有198-19=179个 所以恰好能被6，7，8，9整除的五位数有179个2小明的两个衣服口袋中各有13卡片，每卡片上分别写着1，2，3，13如果从这两个口袋中各拿出一卡片来计算它们所写两数的乘积，可以得到许多不相等的乘积那么，其中能被6整除的乘积共有多少个?【分析与解】 这些积中能被6整除的最大一个是13×12=26×6，最小是6但在l×626×6之间的6的倍数并非都是两卡片上的乘积，其中有25×6，23×6，21×6，19×6，17×6这五个不是所求的积共有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类中各选一个，因为每类中的选择是相互独立的，共有2×2×2=8种选法 4同时满足以下条件的分数共有多少个?大于，并且小于； 分子和分母都是质数； 分母是两位数 【分析与解】 由知分子是大于1，小于20的质数如果分子是2，那么这个分数应该在与之间，在这之间的只有符合要求如果分子是3，那么这个分数应该在与之间，15与18之间只有质数17，所以分数是同样的道理，当分子是5，7，11，13，17，19时可以得到下表分子分数分子分数211313517719于是，同时满足题中条件的分数共13个5一个六位数能被11整除，它的各位数字非零且互不一样的将这个六位数的6个数字重新排列，最少还能排出多少个能被11整除的六位数?【分析与解】 设这个六位数为，那么有、的差为0或11的倍数且、均不为0，任何一个数作为首位都是一个六位数 先考虑、偶数位，、奇数位的组交换，有×=36种顺序；再考虑形如这种奇数位与偶数位的组间调换，也有×=36种顺序 所以，用均不为0的、最少可以排出36+36=72个能被11整除的数(包含原来的) 所以最少还能排出72-1=71个能被11整除的六位数6在大于等于1998，小于等于8991的整数中，个位数字与十位数字不同的数共有多少个? 【分析与解】 先考虑20008999之间这7000个数，个位数字与十位数字不同的数共有7×10×=6300 但是1998，89928998这些数的个位数字与十位数字也不同，且1998在19988991，89928998这7个数不在19988991之所以在19988991之的个位数字与十位数字不同的有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种排法，共有3×÷2=9种排法；其中三个数字均相等且不含0的只有1组，每组只有1种排法； 在含有0的数组中，三个数字均不一样的有3组，每组有2种排法，共有3×2×=12种排法；在含有0的数组中，二个数字相等的只有1组，每组有2÷2种排法，共有2种排法 所以，满足条件的三位数共有42+9 + 1+12+2 = 66个8一个自然数，如果它顺着看和倒过来看都是一样的，那么称这个数为“回文数例如1331，7，202都是回文数，而220那么不是回文数问：从一位到六位的回文数一共有多少个?其中的第1996个数是多少? 【分析与解】 我们将回文数分为一位、二位、三位、六位来逐组计算，所有的一位数均是“回文数，即有9个；在二位数中，必须为形式的，即有9个(因为首位不能为0，下同)；在三位数中，必须为(、可一样，在此题中，不同的字母代表的数可以一样)形式的，即有9×10 =90个；在四位数中，必须为形式的，即有9×10个；在五位数中，必须为形式的，即有9×10×10=900个；在六位数中，必须为形式的，即有9×10×10=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个数字中选择两个不同的数字，所以有种选法，所以共有×=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，依次有2，1，2个，共5个；当有七个连续的1时，可以为11111112，21111111，共2个：当有八个连续的l时，只能是11111111，共1个 所以满足条件的八位数有28+12+5+2+1=48个11在1001，1002，2000这1000个自然数中，可以找到多少对相邻的自然数，满足它们相加时不进位?【分析与解】 设为满足条件的两个连续自然数，有=+1我们只用考察的取值情况即可我们先不考虑数字9的情况(因为取9，那么为0，也有可能不进位)，那么只能取0，1，2，3，4；只能取0，1，2，3，4；只能取0，1，2，3，4；对应的有5×5×5=125组数当=9时，有的下一个数为，要想在求和时不进位，必须9，所以此时只能取0，1，2，3，4；而也只能取0，1，2，3，4；共有5×5=25组数当=99时，有的下一个数为，要想在求和时不进位，必须+(+1)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，6+9=7+8先考察5+9=6+8，可以对应为“东+“西=“南+“北，因为“东、“西可以调换，“南、“北可以对调，有2×2=4种填法，而“东、西，“南、北可以整体对调，于是有4×2=8种填法 5 + 8 = 6+7，6+9=7+8同理均有8种填法，所以共有8×3=24种不同的填法13在图20-2的空格各填人一个一位数，使同一行左面的数比右面的数大，同一列上面的数比下面的数小，并且方格的6个数字互不一样，例如图20-3为一种填法那么共有多少种不同的填法?23 图20-2642753 图20-3【分析与解】 为了方便说明，标上字母：CD2AB3要注意到，A最大，D最小，B、C的位置可以互换但是，D只能取4，5，6，因为如果取7，就找不到3个比它大的一位数了当D取4，5，6时分别剩下5，4，3个一位大数有B、C可以互换位置所有不同的填法共×2+×2+×2=10×2+4×2+1×2=30种14从1至9这9个数字中挑出6个不同的数填在图204的6个圆圈，使任意相邻两个圆圈数字之和都是质数那么共能找出多少种不同的挑法?(6个数字一样、排列次序不同的都算同一种) 【分析与解】 显然任意两个相邻圆圈中的数一奇一偶，因此，应从2、4、6、8中选3个数填入3个不相邻的圆圈中：填入2、4、6，这时3与9不能同时填入(否那么总有一个与6相邻，和3+6或9+6不是质数)没有3、9的有1种；有3或9的，其他3个奇数l、5、7要去掉1个，因而有2×3=6种，共1+67种：填入2、4、8这时7不能填入(因为7+2，7+8都不是质数)，从其余4个奇数中选3个，有4种选法，都符合要求：填入2、6、8这时7不能填入，而3与9只能任选1个，因而有2种选法：填入4、6、8这时3与9只能任选1个，1与7也只能任选1个因而有2×2=4种选法共有7+4+2+4 = 17种选法15.一个骰子六个面上的数字分别为0，1，2，3，4，5，现在掷骰子，把每次掷出的点数依次求和，当总点数超过12时就停止不再掷了，这种掷法最有可能出现的总点数是几？课下练习：1.         从甲地到乙地有2种走法，从乙地到丙地有4种走法，从甲地不经过乙地到丙地有3种走法，那么从甲地到丙地的不同的走法共有       种2.         甲、乙、丙3个班各有三好学生3，5，2名，现准备推选两名来自不同班的三好学生去参加校三好学生代表大会，共有       种不同的推选方法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本不同的书，从中选出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名教师照相，教师不能站排头，也不能站排尾，共有       种不同的站法15.     4名学生和3名教师排成一排照相，教师不能排两端，且教师必须要排在一起的不同排法有       种16.     停车场有7个停车位，现在有4辆车要停放，假设要使3个空位连在一起，那么停放的方法有       种17.     在7名运发动中选出4名组成接力队参加4×100米比赛，那么甲、乙都不跑中间两棒的安排方有       种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人中选；6 / 6