思科数学【提优教程】江苏省2012高中数学竞赛 第12讲 计数基本原理：分步与分类教案.doc

第12讲 分步与分类加法原理和乘法原理是计数研究中最常用、也是最基本的两个原理加法原理 如果做一件事，完成它有m类不同的方法，在第l类方法中有n1种不同的方法，在第2类方法中有以n2种不同的方法，在第m类方法中有nm种不同的方法，那么完成这件事共有n1+n2+nm种不同的方法乘法原理 如果做一件事，完成它需要m个步骤，完成第1步有n1种不同的方法，完成第2步有n2种不同的方法，完成第m步有nm种不同的方法，那么完成这件事共有n1n2nm种不同的方法下面我们通过一些例子来说明这两个原理在计数中的应用A类例题例1（1998年全国高考题）3名医生和6名护士被分配到3所学校为学生体检，每校分配1名医生和2名护士，不同的分配方法有 （ ）A.90种 B.180种 C.270种 D.540种分析 本题要将所有医生和护士分配到各所学校，可以分两步进行，即先分配医生，再分配护士。在分配过程中，又要分配到每一所学校。故依据乘法原理计算。解 将医生分配到3所学校，每校1人，有种方法，再分配护士，第一所学校有种方法；第二所学校有种方法，第三所学校有种方法，所以由乘法原理共有=540种方法。故应选D。说明 运用乘法原理解题要注意步与步的独立性，即某一步的任何一种完成方式不会影响其它步的方法总数。例2（1999年全国高考题）在一块并排10垄的田地中，选择2垄分别种植A、B两种作物，每种作物种植1垄，为了有利于作物生长，要求A、B两种作物的间隔不小于6垄，在不同的选垄方法共有_种。分析由于A、B两种作物的间隔不小于6垄，即间隔不定，因此，我们需要按分类来做。解间隔8垄时，有种；间隔7垄时，有2种；间隔6垄时，有3种。所以共有（1+2+3）=12种选垄的方法。说明 运用加法原理解题要注意分类时不重不漏。例3 由数字0，1，3，5，7中取出不同的三个数字作系数，可以组成多少个不同的一元二次方程ax2+bx+c=0(a0)?其中有实根的方程有多少个？ 分析 一元二次方程有实根需满足，所以有实根的方程个数对应于满足的（a,b,c）个数，分类的标准是b的不同取值。 解 x的系数a0,a有4种取法；对于每一种a的取法，b,c可以从余下的4个数字中任何两个排列，有A种方法，共可组成一元二次方程4A=48个。又要方程要有实根，必须满足=b-4ac0。若c=0,则a,b在1，3，5，7中任取两个作排列，有A种方法；若c0，则b只能取5或7时，当b=7时，a,c可在1，3，5中取1，3或1，5，排列有2种取法；当b=5时，a,c只能取1，3两次数作排列，有A种取法。综上讨论，有实根的一元二次方程共有+2+=18个。说明 分类与分步是在计数时简化列举的一种手段。情景再现1（第39届美国高中数学竞赛题）一次职业保龄球赛的最后阶段，前五名选手再按下法比赛：首先由第五名与第四名赛，输者得五等奖；赢者与第三名赛，输者得四等奖；赢者与第二名赛，输者得三等奖；赢者与第一名赛，输者得二等奖，赢者得第一名。问有多少种获奖顺序？2（1997年全国高考题）四面体的顶点和各棱中点共10个点，在其中取4个不共面的点，不同取法共有 （ ）A.150种 B.147种 C.144种 D.141种B类例题例4（2001年全国高中数学联赛）在一个正六边形的六个区域栽种观赏植物，如图所示，要求同一块中种同一种植物，相邻的两块种不同的植物。现有4种不同的植物可供选择，则有 种栽种方案。分析 A、C、E所种植物是否为同一类植物对各步方法数产生影响，所以应抓住A、C、E所种植物的种类，分类讨论到结果。解 考虑A、C、E种同一种植物，此时共有4333=108种方法；考虑A、C、E种两种植物，此时共有343322=432种方法；考虑A、C、E种三种植物，此时共有A222=192种方法。故总计有108+432+192=732种方法。说明 请读者从递推的角度考虑本题的一般性解法。例5（2000年日本东京大学入学试题）满足下列条件的正整数的全体用集合S表示“各位数字不相同，且任意两位数字的和不为9”。这里，S的元素用十进制表示，且S含1位整数。试回答下列问题：在S的元素中，4位数有多少个？在S的元素中，从小到大排列，第2000个数是什么？分析 解题的关键有二：考虑各个数位上取可能值；估计第2000个数的位数。解 4位数由高位到低位的数字分别设为a，b，c，d，则由题意知a取9个值，b必取8个值，c必取6个值，d必取4个值，因此4位数共有9864=1728个；由题意知，S中1位数有9个，两位数有72个，3位数有432个，则9+72+432=53120000，由a，b取值集合的对称性，不失一般性可设a0，b0，-0。故a0。因此，这样的二次函数有AA=12个。若顶点在第三象限，则有-0，-0,b0。这样的二次函数有A=12个。由加法原理知，满足条件的二次函数共有AA+A=24个。11.首项为的连续个正整数之和为=，由2000可得6062。当=60时，由2000可得3，故n=1830，1890，1950；当=61时，由2000可得2，故n=1891，1952；当=62时，由2000可得1；故n=1953。于是题中的有6个。12. 因为三棱锥有4个顶点，确定三棱锥的情况有三种：平面N内4点中取3点，平面M内5点中取1点，共有=20个；平面N内3点中取2点，平面M内5点中取2点，共有=60个；平面N内4点中取1点，平面M内5点中取不共线3点，共有=36个。所以共有20+60+36=116个三棱锥。对于四棱锥，共有5个点组成，但其中4点必须