计数原理
从具体问题出发,理解"计数"的基本方法——分类加法、分步乘法、排列、组合与二项式定理。
一、分类加法计数原理
先看一个问题
问题:小明从 A 地到 B 地,可以坐飞机、火车或汽车。飞机有 2 个班次,火车有 3 个班次,汽车有 1 个班次。小明从 A 地到 B 地共有多少种不同的选择?
思考:坐飞机有 2 种选择,坐火车有 3 种选择,坐汽车有 1 种选择。
这些方式是互斥且不重叠的——选择了飞机就不会同时选择火车。
所以总选择数 = 2 + 3 + 1 = 6 种。
引出原理
上面的问题中,我们把所有方式分成了三类(飞机、火车、汽车),每一类内部有若干种选择,且不同类之间没有重叠。这就是分类加法计数原理:
分类加法计数原理:完成一件事有 n 类不同的方案,在第 1 类方案中有 m1 种不同方法,在第 2 类方案中有 m2 种不同方法,……,在第 n 类方案中有 mn 种不同方法,那么完成这件事共有
N = m1 + m2 + … + mn
种不同的方法。
再巩固一个例子
例:书架上有 5 本不同的语文书、3 本不同的数学书、2 本不同的英语书。从中任取一本,有多少种不同的取法?
分析:取一本书有三类方案——取语文书、取数学书、取英语书。
取语文书有 5 种方法,取数学书有 3 种方法,取英语书有 2 种方法。
总取法 = 5 + 3 + 2 = 10 种。
二、分步乘法计数原理
先看一个问题
问题:小明有 3 件上衣和 2 条裤子。他要选一件上衣和一条裤子搭配出门,共有多少种不同的穿法?
思考:先选上衣,有 3 种选择;再选裤子,有 2 种选择。
穿上衣的每一种都可以搭配 2 条不同的裤子。
所以总搭配数 = 3 × 2 = 6 种。
引出原理
上面的问题中,我们把"穿好衣服"这件事分成了两个步骤——先选上衣、再选裤子。两个步骤必须依次完成才能达成目标。这就是分步乘法计数原理:
分步乘法计数原理:完成一件事需要 n 个步骤,做第 1 步有 m1 种不同方法,做第 2 步有 m2 种不同方法,……,做第 n 步有 mn 种不同方法,那么完成这件事共有
N = m1 × m2 × … × mn
种不同的方法。
再巩固一个例子
例:设置一个 4 位数字密码(每位 0~9),共有多少种不同的密码?
分析:设置密码需要 4 个步骤——依次确定第 1 位、第 2 位、第 3 位、第 4 位数字。
每一位都有 10 种选择(0~9)。
总密码数 = 10 × 10 × 10 × 10 = 104 = 10000 种。
两种原理的对比
| 分类加法 | 分步乘法 | |
|---|---|---|
| 特征 | "要么…要么…",任选一类即可 | "先…再…",依次做完所有步骤 |
| 关系 | 各类互斥且不重叠 | 各步依次完成 |
| 运算 | 加法 | 乘法 |
| 生活类比 | 菜单上选一道主菜(选一个就行) | 先选主菜再选饮品(两个都要) |
| 判定口诀 | "分类用加法" | "分步用乘法" |
三、排列
先看一个问题
问题:有 3 个同学 A、B、C 要排成一排照相,共有多少种不同的排法?
思考:第一个位置有 3 种选择(A、B、C 都可以);
第二个位置有 2 种选择(剩下 2 人中选);
第三个位置只有 1 种选择(最后 1 人)。
总排法 = 3 × 2 × 1 = 6 种。
引出排列的概念
上面的问题,本质上是"从 3 个不同元素中取出 3 个,按顺序排成一列"。在计数原理中,我们把这类问题称为排列问题。
排列:从 n 个不同元素中取出 m (m ≤ n) 个元素,按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列。
排列数公式:
P(n,m) = n × (n−1) × (n−2) × … × (n−m+1)
即 P(n,m) = n! / (n−m)!
(其中 n! = 1 × 2 × 3 × … × n,读作"n 的阶乘")
再巩固一个例子
例:从 4 本不同的书中选出 3 本,按从左到右的顺序摆放在书架上,有多少种不同的摆放方式?
分析:这是从 4 个元素中取 3 个的排列问题,顺序重要。
方法一(分步):第 1 位有 4 种选择,第 2 位有 3 种,第 3 位有 2 种。
总排法 = 4 × 3 × 2 = 24 种。
方法二(公式):P(4,3) = 4! / (4−3)! = 24 / 1 = 24 种。
四、组合
先看一个问题
问题:从 A、B、C 三人中选出 2 人组成一个小组,有多少种不同的选法?
思考:可能的组合有——(A,B)、(A,C)、(B,C),共 3 种。
注意:(A,B) 和 (B,A) 是同一个小组,顺序不重要!
与排列的对比
如果是排列(顺序重要),从 3 人中选 2 人排列有 P(3,2) = 6 种。但如果是组合(顺序不重要),只有 3 种。区别就在于是否考虑顺序。
组合:从 n 个不同元素中取出 m (m ≤ n) 个元素,不考虑顺序地组成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合。
组合数公式:
C(n,m) = P(n,m) / m! = n! / [m!(n−m)!]
也记作 Cnm 或 ( nm )
关系:P(n,m) = C(n,m) × m! —— 先组合再排列。
再巩固一个例子
例:从 5 本书中选 3 本送给朋友(不区分顺序),有多少种不同的送法?
分析:从 5 个元素中取 3 个的组合问题,顺序不重要。
C(5,3) = 5! / (3! × 2!) = 120 / (6 × 2) = 10 种。
对比:如果是从 5 本书中选 3 本排列到书架上(顺序重要),则有 P(5,3) = 60 种。
也可以利用性质:C(6,4) = C(6,2) = 6×5/2 = 15。
五、二项式定理
先看一个规律
我们来做几个展开式,观察它们的规律:
(a + b)0 = 1
(a + b)1 = a + b
(a + b)2 = a2 + 2ab + b2
(a + b)3 = a3 + 3a2b + 3ab2 + b3
(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4
观察各展开式的系数:
这个三角形就是杨辉三角(Pascal's Triangle)。每个数等于它上方两数之和。第 n 行第 k 列的数(行、列均从 0 开始编号)恰好是组合数 C(n, k)。
二项式定理:对于任意非负整数 n(约定 0! = 1),
(a + b)n = C(n,0)an + C(n,1)an−1b + C(n,2)an−2b2 + … + C(n,n)bn
即 (a + b)n = ∑k=0n C(n,k) · an−k · bk
举个例子
例:求 (x + 2)5 展开式中 x3 的系数。
分析:根据二项式定理,展开式中 x3 项对应的 k = 2(因为 x5−2 = x3)。
该项为 C(5,2) · x3 · 22 = 10 × x3 × 4 = 40x3。
所以 x3 的系数为 40。
六、综合练习
以下 5 道综合题覆盖了本节全部知识点,动手试试吧!
练习 1(10 分)
某班有 10 名班干部候选人。(注意区分分类/分步)
(1) 从中选 1 人担任班长,有多少种选法?(3 分)
(2) 从中选 1 人担任班长、1 人担任副班长(不可兼任),有多少种选法?(3 分)
(3) 从中选 3 人组成一个学习小组(无职务),有多少种选法?(4 分)
请回答 (1) 的答案:
请回答 (2) 的答案:
请回答 (3) 的答案:
(1) 班长可以是 10 名候选人中的任意一人,因此直接计数得 10 种选法。若逐人分类,也可看成 10 个互斥且无遗漏的单元素类别。
(2) 先选班长(10 种)再选副班长(剩下 9 种),是分步排列,P(10,2) = 10 × 9 = 90 种。
(3) 选 3 人组成小组,顺序不重要,是组合问题,C(10,3) = 120 种。
练习 2(10 分)
用数字 1、2、3、4、5 可以组成多少个:
(1) 无重复数字的三位数?
(2) 无重复数字的三位偶数?
请回答 (1) 的答案:
请回答 (2) 的答案:
(1) 三位数的每一位数字都不同,是排列问题:P(5,3) = 5 × 4 × 3 = 60 个。
(2) 三位偶数要求个位为偶数(只能是 2 或 4):
步骤 1:个位有 2 种选择(2 或 4);
步骤 2:十位从剩下 4 个数字中选 1 个;
步骤 3:百位从剩下 3 个数字中选 1 个。
总数 = 2 × 4 × 3 = 24 个。
练习 3(10 分)
从 4 名男同学和 3 名女同学中选出 3 人:
(1) 至少选 1 名女生,有多少种选法?
请回答答案:
方法一(分类讨论):至少 1 名女生 = 1 女 2 男 + 2 女 1 男 + 3 女 0 男
C(3,1)C(4,2) + C(3,2)C(4,1) + C(3,3) = 3×6 + 3×4 + 1 = 18 + 12 + 1 = 31 种。
方法二(排除法):无限制 - 全是男生 = C(7,3) - C(4,3) = 35 - 4 = 31 种。
练习 4(10 分)
求 (2x + 1)4 展开式中 x2 项的系数。
请回答答案:
根据二项式定理,展开式中 x2 项对应 k = 2:
C(4,2) · (2x)2 · 12 = 6 × 4x2 × 1 = 24x2。
所以 x2 的系数为 24。
练习 5(10 分)
某班有 6 名同学报名参加 4 项不同的比赛(每人限报一项):
(1) 每项比赛至少有一人参加,这样的分配方案有多少种?
提示:先分组再分配——把 6 名同学分成 4 组(每组至少 1 人),再将 4 组分配到 4 项不同的比赛。
请回答答案:
6 人分 4 组,每组至少 1 人,可能的方案是 3+1+1+1 或 2+2+1+1。
情况一(3,1,1,1):先选 3 人成一组,其余各 1 人:C(6,3) = 20 种分组法。
情况二(2,2,1,1):选 2 人、再选 2 人(注意两两对称除重):C(6,2)×C(4,2)/2! = 15×6/2 = 45 种分组法。
总分组数:20 + 45 = 65 种。
分配:将 4 组对应到 4 项不同比赛,有 P(4,4) = 24 种。
总数:65 × 24 = 1560 种。