计数原理

计数原理

一、知识导学

1.分类计数原理：完成一件事，有ｎ类办法，在第1类办法中，有1m种不同的方法，在第2类办法中，有2m种不同的方法，„„在第ｎ类办法中，有nm种不同的方法，那么完成这件事共有N＝1m＋2m＋„„＋nm种不同的方法.

注：“完成一件事，有ｎ类办法”这是对完成这件事的所有办法的一个分类.分类时，首先要根据问题的特点，确定一个适合它的分类标准，然后在这个标准下进行分类，其次，分类时要注意满足两条基本原则：第一，完成这件事的任何一种方法必须属于某一类；第二，分别属于不同类的两种方法是不同的方法.前者保证完成这件事的立法不遗漏，后者保证不重复.

2. 分步计数原理：完成一件事，需要分成ｎ个步骤，做第1步，有1m种不同的方法，做第2步，有2m种不同的方法，„„做第ｎ步，有nm种不同的方法，那么完成这件事共有N＝1m×2mׄ×nm种不同的方法.

注：“完成一件事，需要分成ｎ个步骤”这就是说完成这件事的任何一种方法，都要完成这ｎ个步骤.分步时，首先要根据问题的特点确定一个可行的分步标准，其次，步骤的设置要满足完成这件事必须并且只需连续完成这ｎ个步骤，这件事才算最终完成.

注：分类计数原理又称加法原理 分步计数原理又称乘法原理

二、典型习题导练

1.有5本不同的中文书，4本不同的数学书，3本不同的英语书，每次取一本，不同的取法有（ ）种.

.A3 .B12 .C60 .D不同于以上的答案

2.体育场南侧有4个大门，北侧有3个大门，某学生到该体育场练跑步，则他进出门的方案有 （ ） A．12 种 B．7种 C．24种 D．49种

3.从6人中选4人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这6人中甲、乙两人不去巴黎游览，则不同的选择方案共有

（ ）.300种 .B240种 .C144种 .D96种

4.同室4人各写一张贺年卡，先集中起来，然后每人从中拿1张别人送出的贺年卡，则4张贺年卡不同的分配方式有 （ ）

.23种 .B11种 .C9种 .D6种

5.设集合54321，，，，I，选择I的两个非空子集和，要使中最小的数大于中最大的数，则不同的选择方法共有（ ）

.50种 .B49种 .C48种 .D47种

6.从1,2，3，„,10中选出3个不同的数，使这三个数构成等差数列，则这样的数列共有____个

7三张卡片的正反面分别写有1和2,3和4,5和6，若将三张卡片并列，可得到_______个不同的三位数（6不能作9用）.

8集合A＝｛1,2，3,4｝，集合B＝｛－1，－2｝，可建立______个以A为定义域B为值域的不同函数

9. 用0，1,2，3,4，5这六个数字，

（1）可以组成多少个数字不重复的三位数？

（2）可以组成多少个数字允许重复的三位数？

（3）可以组成多少个数字不重复的三位奇数？

（4）可以组成多少个数字不重复的小于1000的自然数？

（5）可以组成多少个数字不重复的大于3000，小于5421的四位数？

答案：

1 解析 每次取一本书分三类：取一本中文书有5种，取一本数学书有4种，取一本英语书有3种，共有5+4+3=12种. 答案 

2解析：学生进门有7种选择，同样出门也有7种选择，由分步计数原理，该学生的进出门方案有7×7＝49种. ∴应选D．

3 解析 能去巴黎的有4个人，依次能去伦敦、悉尼、莫斯科的有5个、4个、3个，不同的选择方案有：4×5×4×3=240种，选.B

4 解析 设4人为甲、乙、丙、丁分步进行，第一步，让甲拿，有三种方法，第二步，没拿到卡片的人去拿，有三种方法，剩余两人只有一种拿法，所以共有3×3=9种方法. 答案 C

5 答案 

6解析：根据构成的等差数列的公差，分为公差为±1、±2、±3、±4四类.公差为±1时，有8×2＝16个；公差为±2时，满足要求的数列共6×2＝12个；公差为±3时，有4×2＝8个；公差为±4时，只有2×2＝4个.由分类计数原理可知，共构成了不同的等差数列16＋12＋8＋4＝40个

7解析：解法一 第一步，选数字.每张卡片有两个数字供选择，故选出3个数字，共有32＝8种选法.第二步，排数字.要排好一个三位数，又要分三步，首先排百位，有3种选择，由于排出的三位数各位上的数字不可能相同，因而排十位时有2种选择，排个位只有一种选择.故能排出3×2×1＝6个不同的三位数.由分步计数原理，共可得到8×6＝48个不同的三位数.解法二：第一步，排百位有6种选择，

第二步，排十位有4种选择，

第三步，排个位有2种选择.

根据分步计数原理，共可得到6×4×2＝48个不同的三位数.

注：如果6能当作9用，解法1仍可行.

8解析：函数是特殊的映射，可建立映射模型解决.BA 从集合A到集合B的映射共有42=16个，只有都与－1，或－2对映的两个映射不符合题意，故以A为定义域B为值域的不同函数共有16－2＝14个.

9解析：（1）分三步：①先选百位数字，由于0不能作为百位数，因此有5种选法；②十位数字有5种选法；③个位数字有4种选法.由分步计数原理知所求三位数共有5×5×4＝100个. （2）分三步：①先选百位数字，由于0不能作为百位数，因此有5种选法；②十位数字有6种选法；③个位数字有6种选法.由分步计数原理知所求三位数共有5×6×6＝180个. （3）分三步：①先选个位数字，由于组成的三位数是奇数，因此有3种选法；②再选百位数字有4种选法；③个位数字也有4种选法.由分步计数原理知所求三位数共有3×4×4＝48个. （4）分三类：①一位数，共有6个；②两位数，共有5×5＝25个；③三位数，共有5×5×4＝100个.因此，比1000小的自然数共有6＋25＋100＝131个 （5）分四类：①千位数字为3,4之一时，共有2×5×4×3＝120个；②千位数字为5，百位数字为0,1，2,3之一时，共有4×4×3＝48个；③千位数字为5，百位数字是4，十位数字为0,1之一时，共有2×3＝6个；④还有5420也是满足条件的1个.故所求自然数共120＋48＋6＋1＝175个评注：排数字问题是最常见的一种题型，要特别注意首位不能排0.

非常规计数方法

一.数形结合思想

例1.如下图所示,有5横8竖构成的方格图,从A到B只能上行或右行共有多少条不同的路线?

二.分类讨论思想

例2.在六个空格里涂上红黄蓝三种颜色，每种颜色只能涂两次，要求相邻不同色，请问一共有多少种涂法。

b4b3b2b1a7a6a5a4a3a2a1BA三．方程不等式思想

例3．一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？

例4．将10个完全相同的小球放入编号为1,2,3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ） A 20种 B15种 C14种 D12种

四.“正难则反”的思想

解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反．

例5．有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？

例6．从1，2，3，„，1995这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？

五. 转化法

例7．有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？

例8 把20个相同的球全部装入编号分别为1，2，3的三个盒子中，要求每个盒子中的球数不小于其编号数，则共有 种不同的放法。

答案

例1解析

将一条路经抽象为如下的一个排法(5-1)+(8-1)=11格:

→ ↑ → ↑ ↑ → → → ↑ → →

其中必有四个↑和七个→组成!

所以, 四个↑和七个→一个排序就对应一条路经,

所以从A到B只能上行或右行共有514(51)(81)11CC条不同的路径.

例2解析：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次，按一下分类进行：

先将两个黄格■■插入到两个红格 ■ ■ 的两端或中间，有5种情况:

■ ■■ ■， ■■■■， ■■■■， ■■■ ■， ■ ■■■， ■■■■，

再将两个蓝格分别插入到四个红黄间隔的的两端或中间，有

4+1+1+10+10+4=30种方法；

所以，共有30种涂法。

例3解析

种符合题意的取法种数有或或则个白球个红球解：设取186142332)60(72)40(5,,164426343624CCCCCCyxyxyxyyxxyxyx

例4解析：设编号为1,2,3的三个盒子中分别放入x,y,z个小球，于是题中不同的放法即为方程: x+y+z=10,且x≥1,y≥2,z≥3的非负整数解的个数．令u=x-1,v=y-2,w=z-3，得u+v+w=4,所以该方程的非负整数解的个数即为所求的放法数目C154134，故选B ．

例5解析：（1）0不能作百位，但可以作十位或个位．（2）0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂．于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求．由于任取三张可以组成不同的三个数的号码有：AC333352，其中0在左边第一位的号码有：AC222242，

故所求的不同三位数共有：AC333352-AC222242=432 个．

例6解析：解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题．

问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”

任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有C91987种方法．

例7解析：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有2828C种走法。