✧排列问题题型分类: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类办法中有M n种不同的方法,那么完成这件事情共有M1+M2+……+M n种不同的方法。
二.乘法原理:如果完成某项任务,可分为k个步骤,完成第一步有n1种不同的方法,完成第二步有n2种不同的方法,……完成第k步有nk种不同的方法,那么完成此项任务共有n1×n2×……×nk种不同的方法。
三.两个原理的区别⏹做一件事,完成它若有n类办法,是分类问题,每一类中的方法都是独立的,故用加法原理。
每一类中的每一种方法都可以独立完成此任务;两类不同办法中的具体方法,互不相同(即分类不重);完成此任务的任何一种方法,都属于某一类(即分类不漏)⏹做一件事,需要分n个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才算完成,因此用乘法原理.任何一步的一种方法都不能完成此任务,必须且只须连续完成这n步才能完成此任务;各步计数相互独立;只要有一步中所采取的方法不同,则对应的完成此事的方法也不同这样完成一件事的分“类”和“步”是有本质区别的,因此也将两个原理区分开来.四.排列及组合基本公式1.排列及计算公式从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 P mn表示.P mn=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个元素的组合数.用符号C mn表示.C mn = P mn/m!=n!(n-m)!×m!一般当遇到m比较大时(常常是m>0.5n时),可用C mn = C n-mn来简化计算。
规定:C nn =1, C0n=1.3.n的阶乘(n!)——n个不同元素的全排列P nn=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,c=7,则b=4(即每一组a,c必对应唯一的b,另外1、4、7和7、4、1按同一种等差数列处理)∴C2=10×9=90,同类(同奇或同偶)相加,即本题所求=2×90=180。
10【例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时可以得到下表.分子 分数 分子 分数2 211 11 1111,59613 317 13 131313,,677173 5 529 17 1717,8997 737,3741 191997于是,同时满足题中条件的分数共13个.5.一个六位数能被11整除,它的各位数字非零且互不相同的.将这个六位数的6个数字重新排列, 最少还能排出多少个能被11整除的六位数?【分析与解】 设这个六位数为abcdef ,则有()a c e ++、()b d f ++的差为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:BC DE 是满足题意的时刻,有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时的情况.首位数字 5 4 3所 有 满 足 题 意 的 数 字 列 表5544554433321⎧⎧--⎨⎪⎩⎪⎪⎧⎧⎪--⎨⎨⎪⎪⎩⎪-⎨⎪⎧⎪⎪-⎨⎪⎪⎩⎩⎩545453454444323432212⎧-⎧⎪⎪--⎧⎨⎪-⎨⎪⎪⎩⎩⎪⎪⎧-⎧⎪⎪⎪--⎧⎨⎨⎪-⎨⎪⎪⎪⎩⎪⎩⎪-⎨⎪⎧⎧⎪⎪-⎪⎨⎪-⎪⎨⎩⎪⎪⎪-⎪⎩⎩⎩5543544333213543332213121⎧⎧⎧--⎪⎨⎪⎩⎪⎪⎪⎪⎧⎧⎪⎪--⎨⎨⎪⎪⎪⎩⎪-⎪⎨⎪⎧⎪⎪⎪-⎨⎪⎪⎪⎩⎩⎪⎩-⎨⎧⎧⎧⎪-⎪⎨⎪⎪⎪⎩⎪⎪-⎨⎪⎪⎧⎪⎪--⎪⎨⎨⎪⎩⎪⎩⎪⎪⎪⎧⎪⎪--⎨⎪⎪⎩⎩⎩满足题意的数字个数6 912因为对称的缘故,当首位数字为1时的情形等同与首位数字为5时的情形, 首位数字为2时的情形等同于首位数字为4时的情形.所以,满足题意的五位数共有6 + 9 + 12 + 9 + 6 = 42个.11.用数字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个.12.在1001,1002,…,2000这1000个自然数中,可以找到多少对相邻的自然数,满足它们相加时不进位?【分析与解】 设1,bcd xyzw 为满足条件的两个连续自然数,有xyzw =1bcd +1. 我们只用考察1bcd 的取值情况即可.我们先不考虑数字9的情况(因为d 取9,则w 为0,也有可能不进位),则d 只能取0,1,2,3,4;c 只能取0,1,2,3,4;b 只能取0,1,2,3,4;对应的有5×5×5=125组数.当d =9时,有19bc 的下一个数为1(1)0b c +,要想在求和时不进位,必须(1)c c ++≤9,所以c 此时只能取0,1,2,3,4;而b 也只能取0,1,2,3,4;共有5×5=25组数.当cd =99时,有199b 的下一个数为1(1)00b +,要想在求和时不进位,必须b +(b +1)≤9,所以b 此时只能取0,1,2,3,4;共有5组数.所以,在1001,1002,…,2000这1000个自然数中,可以找到125 + 25 + 5 = 155对相邻的自然数, 满足它们相加时不进位.13.把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种不同的填法.14.在图20-2的空格内各填人一个一位数,使同一行内左面的数比右面的数大,同一列内上面的数比下面的数小,并且方格内的6个数字互不相同,例如图20-3为一种填法.那么共有多少种不同的填法?2 3图20-26 4 27 5 3图20-3 【分析与解】 为了方便说明,标上字母:C D 2 A B 3要注意到,A 最大,D 最小,B 、C 的位置可以互换.但是,D 只能取4,5,6,因为如果取7,就找不到3个比它大的一位数了. 当D 取4,5,6时分别剩下5,4,3个一位大数.有B 、C 可以互换位置. 所有不同的填法共35C ×2+34C ×2+33C ×2=10×2+4×2+1×2=30种.补充选讲问题(2003年一零一中学小升初第12题)将一些数字分别填入下列各表中,要求每个小格中填入一个数字,表中的每横行中从左到右数字由小到大,每一竖列中从上到下数字也由小到大排列. (1)将1至4填入表1中,方法有______________ 种: (2)将1至6填入表2中,方法有______________ 种; (3)将1至9填入表3中,方法有______________ 种.【分析与解】 (1)2种:如图,1和4是固定的,另外两格任意选取,故有2种;(2)5种:1和6是固定的,其他的格子不确定.有如下5种:(3)42种:由(2)的规律已经知道,3×2是5种:1、2、3确定后,剩下的6个格子是3×2,为5种.如下:同理也各对应5种;注意到例外,对应的不是5种,因为第一排右边的数限制了其下方的数字,满足条件的只有如下几种:共计5 + 5 + 5 + 4 + 2 = 21种.另外,将以上所有情况翻转过来,也是满足题意的排法,所以共21×2=42种.15.从1至9这9个数字中挑出6个不同的数填在图20-4的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+6=7种.第二种情况:填入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种选法20.一个骰子六个面上的数字分别为0,1,2,3,4,5,现在掷骰子,把每次掷出的点数依次求和,当总点数超过12时就停止不再掷了,这种掷法最有可能出现的总点数是几?1.从甲地到乙地有2种走法,从乙地到丙地有4种走法,从甲地不经过乙地到丙地有3种走法,则从甲地到丙地的不。