高中数学培优竞赛强基计划讲义数学竞赛教案：第12讲 计数基本原理：分步与分类

第12讲 分步与分类 加法原理和乘法原理是计数研究中最常用、也是最基本的两个原理． 加法原理 如果做一件事，完成它有m类不同的方法，在第l类方法中有n1种不同的方法，在第2类方法中有以n2种不同的方法，……，在第m类方法中有nm种不同的方法，那么完成这件事共有n1+n2…+nm种不同的方法． 乘法原理 如果做一件事，完成它需要m个步骤，完成第1步有n1种不同的方法，完成第2步有n2种不同的方法，……，完成第m步有nm种不同的方法，那么完成这件事共有n1n2…nm种不同的方法． 下面我们通过一些例子来说明这两个原理在计数中的应用． 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(a≠0)?其中有实根的方程有多少个？ 分析 一元二次方程有实根需满足，所以有实根的方程个数对应于满足的（a,b,c）个数，分类的标准是b的不同取值。 解 x的系数a≠0,a有4种取法；对于每一种a的取法，b,c可以从余下的4个数字中任何两个排列，有A种方法，共可组成一元二次方程4A=48个。又要方程要有实根，必须满足Δ=b-4ac≥0。若c=0,则a,b在1，3，5，7中任取两个作排列，有A种方法；若c≠0，则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种同一种植物，此时共有4×3×3×3=108种方法；考虑A、C、E种两种植物，此时共有3×4×3×3×2×2=432种方法；考虑A、C、E种三种植物，此时共有A×2×2×2=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位数共有9×8×6×4=1728个；⑵由题意知，S中1位数有9个，两位数有72个，3位数有432个，则9+72+432=531<2000<513+1728=2241。所以第2000个数是4位数。又大于8695的四位数有1+2×（6×4）+8×6×4=241个，从而知第2000个数是8695。 说明 第2000个数接近最大的满足题意的四位数，所以可以倒推寻找符合题意的数。 例6设S={1，2，3，…，499，500}，从S中任取4个不同的数，按照从小到大的顺序排列成一个公比为正整数的等比数列，求这样的等比数列的个数． 分析 确定满足题意的等比数列可以从首项和公比着手，公比的整数特征是解题的关键。 解 设所求等比数列为a1，a1q，a1q2，a1q3 (a1，q∈N+，q≥2)，则a1q2≤500， q≤≤，所以2≤q≤7，且l≤a1，即公比为q的等比数列有个． 由加法原理得满足条件的等比数列共有 =62+18+7+4+2+1=94(个)． 说明 本题计数分类的标准取决与公比的离散取值。 情景再现 3．(1999年全国高中联赛试题)已知直线ax+by+c=0中，a,b,c取自集合{-3，-2，-1，0，l，2，3}中三个不同元素，并设该直线的倾斜角为锐角，那么这样直线的条数是 . 4．(2002年湖南省中学生夏令营试题)2×3的矩形花坛被分成6个l×1的小正方形区域：A，B，C，D，E，F，在每个区域内栽种一种植物，相邻两个区域内栽种的植物不同，今有6种植物可供选择，则共有 种不同的栽种方法． 5．（1998年全国高中数学联赛）在正方体的8个顶点、12条棱的中点、6个面的中心及正方体的中心共27个点中，共线的三点组的个数是（ ） A． 57 B． 49 C． 43 D． 37 6．从0，l，2，3，4，5，6，7，8，9中取出3个不同的数字组成一个3位数，且使得这个3位数的各位数字之和为不小于10的偶数，问一共有多少个这样的3位数? C类例题 例7 (2000年全国高中联赛试题)如果(1)a，b，c，d都属于{1，2，3，4}；(2)a≠b，b≠c，c≠d，d≠a；(3)a是a，b，c，d中最小值，那么可组成不同的四位数的个数是 . 分析 本题可以从参与组成的数的个数进行分类。 解 中恰有2个不同数字时，从4个数字中取2个数字有种方法，其中较小的数字放在第1，3位，较大的数字放在第2，4位，只能组成一个四位数，故这时不同的四位数有=6个；中恰有3个不同数字时，从4个数字中取3个数字有种取法．组成第l，3位数字相同的四位数有个，组成第2，4位数字相同的四位数也有个，故这时不同的四位数有(+)=16个；中恰有4个数字不同时，取最小的数字放在第1位，其余3个数字任意排列，这时不同的四位数有=6个．综上可得不同的四位数的个数为6+16+6=28个． 例8 4对夫妇去看电影，8个人坐成一排，若女性的邻座只能是其丈夫或其他女性，共有几种坐法? 分析 本题可从女性间的相对位置展开分类讨论。 解 先将女性的顺序排定有4！种方法，女性与女性之间若坐有男性(一定包括女性的丈夫)必不少于两个，同样，男性与男性之间若有女性也必不少于两个．把座位连在一起的女性视为一组，则4位女性的无序分组方式有4，3+1，2+2，2+1+l，1+l+l+1等5种． 因为孤立的女性必须在这一排座位的两端，所以1+1+l+1的分组方式不符合要求． (1)女性分成2+1+l时，两端必须坐着女性，这时男性只能分成2+2，即只有下列第①类： ①女男男女女男男女 这时男性的入座方法只有1种． (2)女性分成2+2时，有下列第②，③，④，⑤4类： ②女女男男男男女女 ③男女女男男男女女　或　女女男男男女女男 ④男男女女男男女女　或　女女男男女女男男 ⑤男女女男男女女男 这时每类男性的入座的方法分别有2！，l，1，1种，共计2！+1×2+1×2+1＝7种． (3)女性分成3+1时，有下列第⑥，⑦，⑧3类： ⑥女女女男男男男女　或　女男男男男女女女 ⑦男女女女男男男女　或　女男男男女女女男 ⑧男男女女女男男女　或　女男男女女女男男 这时每类男性入座的方法分别有2！，1，1种，共计2(2！+1+1)＝8种． (4)女性4人连排时，有下列第⑨，⑩，（11）类： ⑨女女女女男男男男 或　男男男男女女女女 ⑩男男男女女女女男 或　男女女女女男男男 （11）男男女女女女男男男男 这时每类男性的入座方法分别有3！，2！，2！种，共计有3！×2+2！×2+2！=18种． 综上得不同的入座方法总数为 4！×(1+7+8+18)一24×34＝816种 说明 列举是计数最基本的方式，注意按规律列举，以免遗漏。 情景再现 7．由104条直线：x+y-1=0，2x+y-2=0，……，100x+y-100=0， 100x+200y-100=0，50x+100y-7=0，4x+8y-3=0，x+2y+1=0所组成的图形中，同旁内角共有多少对？ 8．（第6届IMO数学竞赛题）平面上给定五个点，这些点两两之间的连线互不平行，又不垂直，也不重合。从任何一点开始，向其余四个点两两之间的连线作垂线，如果不计已知的五个点，所有这些垂线间的交点数最多是多少？ 习题12 习题[来源:学科网] A[来源:学。科。网] 1．（1993年上海高考题）1名老师和4名获奖同学排成一排照相留念，若老师不排在两端，则有不同的排法共有________________种。 2．将n+1件不同奖品全部发给n个同学，每人至少一件，则发放的方法数为( )． A．n B．(n+1)： C． D． 3．从5位男同学和4位女同学中选出4人组成一个代表团参加全校辩论比赛．若要求男同学和女同学都至少一人，则不同的选法种数为( )． A．60种 B．80种 C．120种 D．420种 4．如图，A、B、C、D为海上的四个小岛，要建三座桥，将这四个岛连接起来，则不同的建桥方案共有 （ ） A．8种 B．12种 C．16种 D．20种 5．直线方程Ax+By=0的系数A、B∈{0，1，2，3，6，7}，且A≠B，则这方程表示的不同直线有多少条？ 6．在6×6的棋盘上剪下一个由四个小方格组成的凸字形，如图，有多少种不同的剪法？ 习题