第 12 章计数原理与二项式定理

本章把分类加法计数原理、分步乘法计数原理、排列、组合、二项式定理合并在一起。计数问题的核心是“分清是分类还是分步，是有序还是无序”。

12.1 两个基本计数原理

12.1.1 分类加法计数原理

完成一件事，有 $n$ 类办法，在第 $1$ 类办法中有 $m_1$ 种不同的方法，在第 $2$ 类办法中有 $m_2$ 种不同的方法，……，在第 $n$ 类办法中有 $m_n$ 种不同的方法，那么完成这件事共有

$$ N=m_1+m_2+\cdots+m_n $$

种不同的方法。

分类加法计数原理简称加法原理。
使用前提：每一类办法都能独立完成这件事。
各类办法之间必须互斥，不能重复；所有类合起来必须覆盖全部情况，不能遗漏。
关键词：“分类”“或”“要么……要么……”。

12.1.2 分步乘法计数原理

完成一件事，需要分成 $n$ 个步骤，做第 $1$ 步有 $m_1$ 种不同的方法，做第 $2$ 步有 $m_2$ 种不同的方法，……，做第 $n$ 步有 $m_n$ 种不同的方法，那么完成这件事共有

$$ N=m_1\times m_2\times\cdots\times m_n $$

种不同的方法。

分步乘法计数原理简称乘法原理。
使用前提：每一步都完成，这件事才算完成。
各步之间相互依存，缺一不可。
关键词：“分步”“并且”“先……再……”。

分步乘法计数原理示意

12.1.3 两个原理的区别

分类用加法，分步用乘法。
分类时，任选一类就能完成任务；分步时，必须依次完成所有步骤才能完成任务。
复杂问题常常先分类、再分步，分类与分步结合使用。
分类要不重不漏，分步要步骤完整。

12.2 排列与组合

12.2.1 排列

从 $n$ 个不同元素中取出 $m$（$m\le n$）个元素，按照一定的顺序排成一列，叫从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

排列与顺序有关。
排列数：从 $n$ 个不同元素中取出 $m$ 个元素的所有排列的个数，记作 $\mathrm{A}_n^m$。

$$ \mathrm{A}_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!} $$

全排列：$n$ 个不同元素全部取出的排列，$\mathrm{A}_n^n=n!$。
规定 $0!=1$。

12.2.2 组合

从 $n$ 个不同元素中取出 $m$（$m\le n$）个元素合成一组，叫从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。

组合与顺序无关。
组合数：从 $n$ 个不同元素中取出 $m$ 个元素的所有组合的个数，记作 $\mathrm{C}_n^m$。

$$ \mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n!}{m!(n-m)!} $$

12.2.3 组合数的性质

$\mathrm{C}_n^m=\mathrm{C}_n^{n-m}$。
$\mathrm{C}_n^0=\mathrm{C}_n^n=1$。
$\mathrm{C}_n^1=n$。
递推公式：$\mathrm{C}_{n+1}^m=\mathrm{C}_n^m+\mathrm{C}_n^{m-1}$。
组合数公式中，$m,n$ 都是非负整数，且 $m\le n$。

12.2.4 排列与组合的区别

排列：取出元素后还要考虑顺序，交换两个元素的位置会得到不同的排列。
组合：取出元素后不考虑顺序，交换两个元素的位置仍是同一个组合。
判断方法：看交换两个元素的位置是否产生新的结果。

12.2.5 常见计数方法

特殊元素优先法：优先安排有特殊要求的元素或位置。
捆绑法：要求某些元素相邻时，把它们捆绑成一个整体，再考虑整体内部顺序。
插空法：要求某些元素不相邻时，先安排其他元素，再把不相邻的元素插入空隙。
隔板法：把相同的元素分成若干组，每组至少一个，用隔板隔开。
间接法：正面情况复杂时，用总数减去不符合条件的情况。
定序问题：某些元素顺序固定时，先按全排列计算，再除以这些元素的全排列数。
平均分组：平均分成若干组时，要除以组数的阶乘，避免重复计数。
分组分配：先分组，再分配给不同对象，分组后乘以对象数的阶乘。

12.3 二项式定理

12.3.1 二项式定理

对任意 $n\in\mathbb{N}^*$，

$$ (a+b)^n=\mathrm{C}_n^0a^n+\mathrm{C}_n^1a^{n-1}b+\cdots+\mathrm{C}_n^ka^{n-k}b^k+\cdots+\mathrm{C}_n^nb^n $$

即：

$$ (a+b)^n=\sum_{k=0}^{n}\mathrm{C}_n^ka^{n-k}b^k $$

右边的多项式叫二项展开式。
展开式共有 $n+1$ 项。
各项的次数都等于 $n$。
字母 $a$ 的指数从 $n$ 逐项减到 $0$，字母 $b$ 的指数从 $0$ 逐项增到 $n$。

12.3.2 二项展开式的通项

第 $k+1$ 项：

$$ T_{k+1}=\mathrm{C}_n^ka^{n-k}b^k\quad(k=0,1,2,\ldots,n) $$

通项公式中的 $k$ 从 $0$ 开始，所以第 $k+1$ 项对应组合数 $\mathrm{C}_n^k$。
求指定项、常数项、有理项，通常设通项中的指数满足条件，解出 $k$。

12.3.3 二项式系数的性质

对称性：$\mathrm{C}_n^k=\mathrm{C}_n^{n-k}$。
二项式系数先增后减，中间项最大：
- 当 $n$ 为偶数时，中间一项（第 $\frac n2+1$ 项）的二项式系数最大；
- 当 $n$ 为奇数时，中间两项（第 $\frac{n+1}{2}$ 项和第 $\frac{n+3}{2}$ 项）的二项式系数相等且最大。
各二项式系数之和：

$$ \mathrm{C}_n^0+\mathrm{C}_n^1+\cdots+\mathrm{C}_n^n=2^n $$

奇数项二项式系数之和等于偶数项二项式系数之和：

$$ \mathrm{C}_n^0+\mathrm{C}_n^2+\cdots=\mathrm{C}_n^1+\mathrm{C}_n^3+\cdots=2^{n-1} $$

12.3.4 赋值法

令 $a=b=1$，得各项系数之和。
令 $a=1,b=-1$，得奇数项系数和与偶数项系数和之差。
令 $a=0,b=1$，得常数项。
赋值法是求系数和、系数差、特定项系数的常用方法。
证明整除或求余数：把幂的底数写成除数的倍数与余数之和，展开后只保留与余数有关的部分。
近似计算：当 $|x|$ 很小时，$(1+x)^n\approx1+nx$（一阶近似）。

12.3.5 二项式系数与项的系数

二项式系数：$\mathrm{C}_n^k$，只与 $n,k$ 有关。
项的系数：该项中除字母外的常数部分，包括符号和字母前面的数字因数。
求“二项式系数最大项”和“系数最大项”是不同的问题，后者需要比较相邻两项的系数。

12.4 计数综合

12.4.1 数字排列问题

用若干个数字组成没有重复数字的数，要注意最高位不能为 $0$。
有特殊要求的数字（如偶数个位为偶数、能被 $3$ 整除各位数字和为 $3$ 的倍数）要优先处理。
可以按特殊位置分类，也可以用间接法。

12.4.2 相邻与不相邻问题

相邻问题用捆绑法：把相邻元素捆绑成一个整体，注意整体内部还要排列。
不相邻问题用插空法：先排其他元素，再把不相邻元素插入空隙，注意首尾空隙。
既有相邻又有不相邻的问题，通常先处理相邻，再处理不相邻。

12.4.3 分组与分配问题

分组问题：把元素分成若干组，组与组之间没有区别。
分配问题：把元素分给不同对象，对象之间有区别。
平均分组要除以组数的阶乘；非平均分组不需要。
分配问题：先分组，再乘以对象数的阶乘。

12.4.4 染色问题

按区域依次染色，注意相邻区域不能同色。
可以从颜色数少的区域或相邻关系多的区域入手。
染色问题常用分类讨论和分步乘法原理。

练习

从甲地到乙地，一天中有火车 $3$ 班、汽车 $4$ 班、轮船 $2$ 班。（1）一天中从甲地到乙地共有多少种不同的走法？（2）若往返都从这些班次中选择，且去、回可以相同，共有多少种不同的往返方式？
$5$ 个人排成一排，甲必须站在排头，共有多少种不同的排法？
从 $7$ 个人中选出 $3$ 人参加一项活动，共有多少种不同的选法？
用 $0,1,2,3,4$ 组成没有重复数字的三位数，共有多少个？
$4$ 名男生和 $3$ 名女生排成一排，$3$ 名女生必须相邻，共有多少种不同的排法？
$4$ 名男生和 $3$ 名女生排成一排，$3$ 名女生互不相邻，共有多少种不同的排法？
把 $6$ 个人平均分成 $3$ 组，每组 $2$ 人，共有多少种不同的分法？
求 $(x+2)^6$ 的展开式中 $x^3$ 的系数。
求 $\left(x-\frac1x\right)^6$ 的展开式中的常数项。
已知 $(1+x)^n$ 的展开式中各二项式系数之和为 $64$，求 $n$。
计算 $\mathrm{C}{10}^3+\mathrm{C}{10}^4$，并用组合数性质验证结果。
把 $5$ 名志愿者分配到 $3$ 个不同的岗位，每个岗位至少分配 $1$ 人，共有多少种不同的分配方法？

检测题

判断下面各题，并说明理由。（1）分类加法计数原理中，各类办法之间可以重复。（2）排列与顺序有关，组合与顺序无关。（3）$\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{m!}$。（4）$(a+b)^n$ 的展开式中各二项式系数之和为 $2^n$。
计算下列各值。（1）$\mathrm{A}_6^3$ （2）$\mathrm{C}8^3$ （3）$\mathrm{C}{10}^7$
用 $1,2,3,4,5$ 组成没有重复数字的四位偶数，共有多少个？
$5$ 个人排成一排，甲不站在排头，乙不站在排尾，共有多少种不同的排法？
$3$ 名男生和 $2$ 名女生排成一排，$2$ 名女生不相邻，共有多少种不同的排法？
求 $(2x-1)^5$ 的展开式中 $x^3$ 的系数。
求 $(x+1)^8$ 的展开式中二项式系数最大的项。
下面是小明的解题过程，请判断是否正确，并说明理由。从 $5$ 个人中选出 $3$ 人站成一排，共有 $\mathrm{C}_5^3=10$ 种不同的站法。
写出满足下列条件的一个计数问题各一个。（1）用分类加法计数原理解决的问题。（2）用分步乘法计数原理解决的问题。（3）用组合数解决的问题。
把 $6$ 个人分成一组 $4$ 人、一组 $2$ 人的两组，其中 $4$ 人组去甲地，$2$ 人组去乙地，共有多少种不同的安排方法？

参考答案与提示

（1）$3+4+2=9$ 种；（2）去有 $9$ 种，回有 $9$ 种，共 $9\times9=81$ 种。
甲站排头，其余 $4$ 人全排列：$4!=24$ 种。
$\mathrm{C}_7^3=\frac{7\times6\times5}{3\times2\times1}=35$ 种。
百位不能为 $0$，有 $4$ 种选法；十位有 $4$ 种；个位有 $3$ 种。共 $4\times4\times3=48$ 个。
把 $3$ 名女生捆绑成一个整体，与 $4$ 名男生共 $5$ 个元素全排列，再考虑女生内部顺序：$5!\times3!=120\times6=720$ 种。
先排 $4$ 名男生，形成 $5$ 个空隙；从 $5$ 个空隙中选 $3$ 个安排女生，并考虑女生顺序：$4!\times\mathrm{A}_5^3=24\times60=1440$ 种。
平均分组：$\frac{\mathrm{C}_6^2\mathrm{C}_4^2\mathrm{C}_2^2}{3!}=\frac{15\times6\times1}{6}=15$ 种。
通项 $T_{k+1}=\mathrm{C}_6^kx^{6-k}2^k$。令 $6-k=3$，得 $k=3$，系数为 $\mathrm{C}_6^3\times2^3=20\times8=160$。
通项 $T_{k+1}=\mathrm{C}_6^kx^{6-k}\left(-\frac1x\right)^k=(-1)^k\mathrm{C}_6^kx^{6-2k}$。令 $6-2k=0$，得 $k=3$，常数项为 $(-1)^3\mathrm{C}_6^3=-20$。
$2^n=64$，所以 $n=6$。
$\mathrm{C}{10}^3=120$，$\mathrm{C}{10}^4=210$，和为 $330$；由性质 $\mathrm{C}{10}^3+\mathrm{C}{10}^4=\mathrm{C}_{11}^4=330$。
分两类：$3,1,1$ 型有 $\mathrm{C}_5^3\times3!=60$ 种；$2,2,1$ 型有 $\frac{\mathrm{C}_5^2\mathrm{C}_3^2}{2!}\times3!=15\times6=90$ 种。共 $60+90=150$ 种。

检测题参考答案

（1）错误，各类办法必须互斥，不能重复；（2）正确，排列有序，组合无序；（3）正确，组合数等于排列数除以 $m$ 个元素的全排列；（4）正确，令 $a=b=1$ 即可得到。
（1）$\mathrm{A}6^3=6\times5\times4=120$；（2）$\mathrm{C}8^3=\frac{8\times7\times6}{3\times2\times1}=56$；（3）$\mathrm{C}{10}^7=\mathrm{C}{10}^3=120$。
末位只能排 $2$ 或 $4$，有 $2$ 种；前三位从剩余 $4$ 个数字中选 $3$ 个排列，有 $\mathrm{A}_4^3=24$ 种。共 $2\times24=48$ 个。
用间接法：总排列 $5!=120$；甲站排头有 $4!=24$ 种，乙站排尾有 $4!=24$ 种；甲站排头且乙站排尾有 $3!=6$ 种。所以共有 $120-24-24+6=78$ 种。
先排 $3$ 名男生，形成 $4$ 个空隙；从 $4$ 个空隙中选 $2$ 个安排女生，并考虑女生顺序：$3!\times\mathrm{A}_4^2=6\times12=72$ 种。
通项 $T_{k+1}=\mathrm{C}_5^k(2x)^{5-k}(-1)^k$。令 $5-k=3$，得 $k=2$，系数为 $\mathrm{C}_5^2\times2^3\times(-1)^2=10\times8=80$。
$n=8$ 为偶数，二项式系数最大的是中间第 $5$ 项：$T_5=\mathrm{C}_8^4x^4=70x^4$。
不正确。选出 $3$ 人后还要站成一排，与顺序有关，应选排列数 $\mathrm{A}_5^3=5\times4\times3=60$ 种。
示例：（1）从甲地到乙地可以乘火车（$3$ 班）或汽车（$4$ 班），共有多少种走法；（2）从甲地经乙地到丙地，甲到乙有 $2$ 条路，乙到丙有 $3$ 条路，共有多少种走法；（3）从 $8$ 人中选 $3$ 人参加座谈会，有多少种选法。
从 $6$ 人中选 $4$ 人去甲地，剩下 $2$ 人去乙地：$\mathrm{C}_6^4=15$ 种；也可以先选 $2$ 人去乙地，同样为 $\mathrm{C}_6^2=15$ 种。

第12章-计数原理与二项式定理

第 12 章 计数原理与二项式定理