跳到正文
MathCheng数学讲义

概率与统计

分类计数、排列组合与二项式定理

先判断分类、分步和顺序,再用组合数求二项展开式的指定项。

知识点

  • 分类加法计数原理适用于每一类都能独立完成任务,且各类互不重叠、合起来覆盖全部结果的情形。
  • 分步乘法计数原理适用于完成任务需要依次做完各步,且第 i 步在任一前面步骤的选法下都有 m_i 种选择的情形。各分支的选法数不同,可以先分类再分步。
  • 从不同元素中选取时,若交换顺序产生新的结果,用排列。若只关心选了哪些元素,用组合。
  • 二项展开式按从因式中选取第二项的次数编号。T_{k+1} 对应选 k 次第二项,第一项从 k=0 开始。

公式速查

  • 若分类中第 i 类有 m_i 种选法,按类相加为 m_1+\cdots+m_s。若分步中第 i 步有 m_i 种选法,按步相乘为 m_1\cdots m_s。
  • 从 n 个不同元素中取 m 个且不重复,0\le m\le n。有序排列数和无序组合数分别为
\begin{aligned} A_n^m&=\frac{n!}{(n-m)!},\\ C_n^m&=\binom nm=\frac{n!}{m!(n-m)!}. \end{aligned}
  • 空选有一种方法,约定 0!=1。由所选元素与未选元素的对应,\binom nm=\binom n{n-m}。
  • 对正整数 n,二项式展开式和它的通项为
(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k.
T_{k+1}=\binom nk a^{n-k}b^k,\qquad 0\le k\le n.
  • \binom nk 是二项式系数。若 a,b 含有数值因子或负号,求指定幂的系数时要把这些因子代入通项。

基础公式推导

从 n 个不同元素中取 m 个按顺序排入 m 个位置。第一个位置有 n 种选法,第二个有 n-1 种,直到第 m 个有 n-m+1 种。由分步乘法计数原理,相乘得

\begin{aligned} A_n^m&=n(n-1)\cdots(n-m+1)\\ &=\frac{n!}{(n-m)!}. \end{aligned}

如果只关心取到哪些元素,每个固定的 m 元素集合都会产生 m! 个排列。将全部排列按所取的集合分类,每一类恰有 m! 个,故 A_n^m=C_n^m m!。除以 m! 即得组合数公式,m=0 的情形也符合约定。

进阶公式推导

从逐个因式选择推导展开式。 把 (a+b)^n 写成 n 个 (a+b) 相乘。每个展开项从每个因式贡献一个 a 或一个 b。若最终乘积为 a^{n-k}b^k,必有恰好 k 个因式选了 b。只要确定这 k 个位置,其余位置便必须选 a。因此这样的选择有 \binom nk 种,合并后得到展开式的第 k+1 项。最后让 k 遍历 0 到 n,便计入全部展开项。

同一个计数思路也能导出二项式系数的递推关系。从 n 个位置选 k 个,将选法分成「含最后一个位置」和「不含最后一个位置」两类。前者还要从前 n-1 个位置选 k-1 个,后者要选 k 个。由分类加法计数原理,当 1\le k<n 时有

\binom nk=\binom{n-1}{k-1}+\binom{n-1}k.

典型例题

例 1 · 先选代表再指定发言人

一个小组有 3 名数学兴趣组成员和 2 名物理兴趣组成员,这 5 人互不相同。现从中选出两名代表,要求至少有一名物理兴趣组成员,并从两名代表中指定一人发言。共有多少种选法?

解析与答案

按代表中物理兴趣组的人数分类。恰好一人时,有 \binom21\binom31=6 种代表选法。恰好两人时,有 \binom22=1 种代表选法。两类合计 7 种。

每选出一对代表,都有 2 种指定发言人的方式。分步相乘得到 7\cdot2=14 种。

例 2 · 求展开式的指定项系数

求 (2x-1)^5 的展开式中 x^2 的系数。

解析与答案

取 a=2x、b=-1,第 k+1 项为 \binom5k(2x)^{5-k}(-1)^k。令 5-k=2,得 k=3,所求系数为

\binom53\cdot2^2\cdot(-1)^3=-40.