【斯巴达高考】斯巴达教育集团总裁武继周：中国数学奥林匹克竞赛“高级教练”.ppt

第七部分：计数原理 【斯巴达高考】斯巴达教育集团武继周中国数学奥林匹克竞赛“高级教练” 一、乘法原理,加法原理 1.乘法原理：做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2不同的方法，……，做第n步有mn不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。 2.加法原理：做一件事情，完成它有N类方式，第一类方式有M1种方法，第二类方式有M2种方法，……，第N类方式有M(N)种方法，那么完成这件事情共有M1+M2+……+M(N)种方法。 二、排列数公式 注意：1.规定0！=1！ 2.n?m=(n+1)!- n! 3. 4. 三、组合数公式 对于组合数有两个公式 ： 四、排列组合题型 1.直接法 例:高二某班要从7名运动员出思铭组成4×100米接力队，参加运动会，其中甲，乙两人都不跑中间两棒的安排方法有多少种？ 再考虑每一类要如何安排棒数 先分组 四、排列组合题型 2.排除法 例：某小组共有10名学生，其中女生3名，现选举2名代表，至少有1名女生当选的不同选法共有多少种？ 四、排列组合题型 3.捆绑法 所谓捆绑法，指在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个整体参与排序，然后再单独考虑这个整体内部各元素间顺序。 一般都应用在不同物体的排序问题中。 例1：有10本不同的书：其中数学书4本，外语书3本，语文书3本。若将这些书排成一列放在书架上，让数学书排在一起，外语书也恰好排在一起的排法共有多少种？ 四、排列组合题型 4.插空法 先把一般元素排列好，然后把待定元素插排在它们之间或两端的空档中，此法主要解决“元素不相邻”问题。 例：有3名男生和5名女生站成一排照相，如果男生不排在最左边且不相邻，则不同的排法有多少种？ 四、排列组合题型 5.占位法 从元素的特殊性上将，对问题中的特殊元素应优先排列，然后再排其他一般元素。 例：五个不同的元素 （i=1,2,3，4,5）排成一排，规定a1不许排第一，a2不许排第二，不同的排法共有多少种？ 四、排列组合题型 6.平均法 若把kn个不同元素平均分成k组，每组n个，共有 种分法。用于分堆、分组问题。 例：将10个人分成三组，一组4人，另外两组均3人，共有几种分法？ 四、排列组合题型 7.隔板法 常用于解正整数解组数的问题。 例：x1+x2+x3+x4=12的正整数解有多少组？ 解：将12个完全相同的球排成一列，在它们之间形成的11个空隙中任选三个插入3块隔板，把球分成4组。每一种方法所得球的数目依次为x1,x2,x3,x4,显然x1+x2+x3+x4=12，故（x1,x2,x3,x4）是方程的一组解。反之，方程的任何一组解(y1,y2,y3,y4),对应着唯一的一种在12个球之间插入隔板的方式。故方程的解和插板的方法一一对应。即方程的解的组数等于插板的方法数 习题1 （华约）三个朋友，每人写一张明信片，一共三封明信片，寄给这三位中除本人以外的另两位之一，则这三人收到明信片的不同结果共有多少种？ A.24种 B.16种 C.8种 D.4 种 答案：C 解析：23 =8 习题2 A B C D E （卓越）如图所示，在A,B,C,D,E五个区域中栽培3种植物，要求同一区域只种1种植物，相邻两区域所种植物不同，则不同的栽培方法的总数为多少？ A.21 B.24 C.30 D.48 答案：C 习题3 （华约）设A=｛x|x≥10,x∈N｝,B?A,且B中元素满足：?任一元素的各位数字互不相同，?任一元素的任意两个数位之和不等于9. (1)求B中的两位数和三位数的个数 (2)B中是否存在五位数，六位数； (3)若从小到大排列B中元素，求第1081个元素； 设B1=｛0,9｝，B2=｛1,8｝,B3=｛2,7｝,B4=｛3,6｝,B5=｛4,5｝，则B中元素的每个数位上的数字只能从上述五个不同的集合中分别抽取，每一个集合中至多抽取一个，所以 （1）两位数个数： 三位数个数： （2）存在五位数，从五个集合Bi（i=1,2,3,4,5）中各取一个构成； 不存在六位数 （3）因为四位数共有 所以第1081个元素应是一个四位数，且是四位数中第577(1728-72-432=577)个，而千位分别是1,2,3的四位数共有 ，所以，第1081个元素是4012。