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

排列问题题型分类：1.信号问题2.数字问题3.坐法问题4.照相问题5.排队问题组合问题题型分类：1.几何计数问题2.加乘算式问题3.比赛问题4.选法问题常用解题方法和技巧1.优先排列法2.总体淘汰法3.合理分类和准确分步4.相邻问题用捆绑法5.不相邻问题用插空法6.顺序问题用“除法”7.分排问题用直接法8.试验法9.探索法10.消序法11.住店法12.对应法13.去头去尾法14.树形图法15.类推法16.几何计数法17.标数法18.对称法分类相加，分步组合，有序排列，无序组合基础知识（数学概率方面的基本原理）一.加法原理：做一件事情，完成它有N类办法，在第一类办法中有M1中不同的方法，在第二类办法中有M2中不同的方法，……，在第N类办法中有Mn种不同的方法，那么完成这件事情共有M1+M2+……+Mn种不同的方法。二.乘法原理：如果完成某项任务，可分为k个步骤，完成第一步有n1种不同的方法，完成第二步有n2种不同的方法，……完成第ｋ步有ｎｋ种不同的方法，那么完成此项任务共有ｎ１×ｎ２×……×ｎｋ种不同的方法。三.两个原理的区别做一件事，完成它若有n类办法，是分类问题，每一类中的方法都是独立的，故用加法原理。每一类中的每一种方法都可以独立完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理．任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来．四.排列及组合基本公式1.排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号Pmn表示.Pmn=n(n-1)(n-2)……(n-m+1)=n!(n-m)!(规定0!=1).2.组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号Cmn表示.Cmn=Pmn/m!=n!(n-m)!×m!一般当遇到m比较大时（常常是m0.5n时），可用Cmn=Cn-mn来简化计算。规定：Cnn=1,C0n=1.3.n的阶乘(n!)——n个不同元素的全排列Pnn=n!=n×(n-1)×(n-2)…3×2×1五.两个基本计数原理及应用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按同一种等差数列处理）∴C210＝10×9＝90，同类（同奇或同偶）相加，即本题所求=2×90＝180。【例2】某城市有4条东西街道和6条南北的街道，街道之间的间距相同，如图。若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法?分析：对实际背景的分析可以逐层深入（一）从M到N必须向上走三步，向右走五步，共走八步。（二）每一步是向上还是向右，决定了不同的走法。（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数，∴本题答案为：C38=56。2.注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合。采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。【例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：19……424，99999÷504=198……207．所以，五位数中，能被504整除的数有198-19=179个．所以恰好能被6，7，8，9整除的五位数有179个．2．小明的两个衣服口袋中各有13张卡片，每张卡片上分别写着1，2，3，…，13．如果从这两个口袋中各拿出一张卡片来计算它们所写两数的乘积，可以得到许多不相等的乘积．那么，其中能被6整除的乘积共有多少个?【分析与解】这些积中能被6整除的最大一个是13×12=26×6，最小是6．但在l×6～26×6之间的6的倍数并非都是两张卡片上的乘积，其中有25×6，23×6，21×6，19×6，17×6这五个不是．∴所求的积共有26-5=21个．3．1，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．同时满足以下条件的分数共有多少个?①大于16，并且小于15；②分子和分母都是质数；③分母是两位数．【分析与解】由①知分子是大于1，小于20的质数．如果分子是2，那么这个分数应该在210与28之间，在这之间的只有211符合要求．如果分子是3，那么这个分数应该在315与318之间，15与18之间只有质数17，所以分数是317．同样的道理，当分子是5，7，11，13，17，19时可以得到下表．分子分数分子分数2211111111,5961331713131313,,6771735529171717,8997737,3741191997于是，同时满足题中条件的分数共13个．5．一个六位数能被11整除，它的各位数字非零且互不相同的．将这个六位数的6个数字重新排列，最少还能排出多少个能被11整除的六位数?【分析与解】设这个六位数为abcdef，则有()ace、()bdf的差为0或11的倍数．且a、b、c、d、e、f均不为0，任何一个数作为首位都是一个六位数．先考虑a、c、e偶数位内，b、d、f奇数位内的组内交换，有33P×33P=36种顺序；再考虑形如badcfe这种奇数位与偶数位的组间调换，也有33P×33P=36种顺序．所以，用均不为0的a、b、c、d、e、f最少可以排出36+36=72个能被11整除的数(包含原来的abcdef)．所以最少还能排出72-1=71个能被11整除的六位数．6．在大于等于1998，小于等于8991的整数中，个位数字与十位数字不同的数共有多少个?【分析与解】先考虑2000～8999之间这7000个数，个位数字与十位数字不同的数共有7×10×210P=6300．但是1998，8992～8998这些数的个位数字与十位数字也不同，且1998在1998～8991内，8992～8998这7个数不在1998～8991之内．所以在1998～8991之内的个位数字与十位数字不同的有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组，每组有33P种排法，共7×33P=42种排法；其中三个数字有只有2个相等且不含0的有3组，每组有33P÷2种排法，共有3×33P÷2=9种排法；其中三个数字均相等且不含0的只有1组，每组只有1种排法；在含有0的数组中，三个数字均不相同的有3组，每组有222P种排法，共有3×2×22P=12种排法；在含有0的数组中，二个数字相等的只有1组，每组有222P÷2种排法，共有2种排法．所以，满足条件的三位数共有42+9+1+12+2=66个．8．一个自然数，如果它顺着看和倒过来看都是一样的，那么称这个数为“回文数”．例如1331，7，202都是回文数，而220则不是回文数．问：从一位到六位的回文数一共有多少个?其中的第1996个数是多少?【分析与解】我们将回文数分为一位、二位、三位、…、六位来逐组计算．所有的一位数均是“回文数”，即有9个；在二位数中，必须为aa形式的，即有9个(因为首位不能为0，下同)；在三位数中，必须为aba(a、b可相同，在本题中，不同的字母代表的数可以相同)形式的，即有9×10=90个；在四位数中，必须为abba形式的，即有9×10个；在五位数中，必须为abcba形式的，即有9×10×10=900个；在六位数中，必须为abccba形式的，即有9×10×10=900个．所以共有9+9+90+90+900+900=1998个，最大的为999999，其次为998899，再次为997799．而第1996个数为倒数第3个数，即为997799．所以，从一位到六位的回文数一共有1998个，其中的第1996个数是997799．9．一种电子表在6时24分30秒时的显示为6:2430，那么从8时到9时这段时间里，此表的5个数字都不相同的时刻一共有多少个?【分析与解】设A:BCDE是满足题意的时刻，有A为8，B、D应从0，1，2，3，4，5这6个数字中选择两个不同的数字，所以有26P种选法，而C、E应从剩下的7个数字中选择两个不同的数字，所以有27P种选法，所以共有26P×27P=1260种选法，即从8时到9时这段时间里，此表的5个数字都不相同的时刻一共有1260个．10．有些五位数的各位数字均取自1，2，3，4，5，并且任意相邻两位数字(大减小)的差都是1．问这样的五位数共有多少个?【分析与解】如下表，我们一一列出当首位数字是5，4，3时的情况．首位数字543所有满足题意的数字列表55445544333215454534544443234322125543544333213543332213121满足题意的数字个数6912因为对称的缘故，当首位数字为1时的情形等同与首位数字为5时的情形，首位数字为2时的情形等同于首位数字为4时的情形．所以，满足题意的五位数共有6+9+12+9+6=42个．11．用数字1，2组成一个八位数，其中至少连续四位都是1的有多少个?【分析与解】当只有四个连续的1时，可以为11112***,211112**,*211112*,**211112，***2