跳转至

计数原理

知识点

分类加法与分步乘法计数原理

定义 1. 分类加法计数原理与分步乘法计数原理

如果完成一件事有\(n\)类方案,在第1类方案中有\(m_1\)种不同的方法,在第2类方案中有\(m_2\)种方法\(\cdots\)在第\(n\)类方案中有\(m_n\)种不同的方法, 那么完成这件事共有 \(N = m_1 + m_2+\cdots + m_n\) 种不同的方法.

如果完成一件事需要\(n\)个步骤,做第1步有\(m_1\)种不同的方法,做第2步有\(m_2\)种不同方法\(\cdots\)做第\(n\)步有\(m_n\)种不同的方法． 那么完成这件事共有 \(N = m_1\times m_2\times\cdots\times m_n\) 种不同的方法.

排列与组合

定义 1. 排列数与组合数

排列数公式,其中\(m,n\in\mathbf{N}^{*}\),且\(m\leq n\)

\[ A_{n}^{m}=n(n - 1)(n - 2)\cdots(n - m + 1)=\htmlClass{blank}{\dfrac{n!}{(n - m)!}} \]

组合数公式,其中\(m,n\in\mathbf{N}^{*}\)且\(m\leq n\),另外,我们规定\(C_{n}^{0}=1\)

\[ C_{n}^{m}=\dfrac{A_{n}^{m}}{A_{m}^{m}}=\dfrac{n(n - 1)(n - 2)\cdots(n - m + 1)}{m!}=\htmlClass{blank}{\dfrac{n!}{m!(n - m)!}} \]

排列数公式推导：排好\(m\)个有序空位依次填入元素，第1位从\(n\)个不同元素中任选有\(n\)种填法，第2位有\(n - 1\)种，\(\cdots\)，第\(m\)位有\(n - m + 1\)种，由分步乘法计数原理\(A_{n}^{m}=n(n - 1)\cdots(n - m + 1)=\dfrac{n!}{(n - m)!}\).

组合数公式推导：从\(n\)个不同元素中取\(m\)个的排列，可分两步完成：先取出\(m\)个元素（即得一个组合，共\(C_{n}^{m}\)种），再把取出的\(m\)个元素作全排列（共\(A_{m}^{m}=m!\)种），由分步乘法计数原理\(A_{n}^{m}=C_{n}^{m}\cdot A_{m}^{m}\)，故\(C_{n}^{m}=\dfrac{A_{n}^{m}}{A_{m}^{m}}=\dfrac{n!}{m!(n - m)!}\).

性质 1. 组合恒等式

\[ \begin{aligned} & C_{n}^{m} = C_{n}^{n - m} & & C_{n}^{m} + C_{n}^{m - 1} = \htmlClass{blank}{C_{n + 1}^{m}} \\ & C_{n}^{0} + C_{n}^{1} + \cdots + C_{n}^{n} = \htmlClass{blank}{2^{n}} & & C_{n}^{1} + C_{n}^{3} + \cdots = C_{n}^{0} + C_{n}^{2} + \cdots = \htmlClass{blank}{2^{n - 1}} \\ & C_{n}^{m} = \frac{n - m + 1}{m} C_{n}^{m - 1} & & C_{n}^{m} = \frac{n}{n - m} C_{n - 1}^{m} \\ & k C_{n}^{k} = n C_{n - 1}^{k - 1} \Rightarrow C_{n}^{m} = \frac{n}{m} C_{n - 1}^{m - 1} & & C_{n}^{1} + 2 C_{n}^{2} + \cdots + n C_{n}^{n} = \htmlClass{blank}{n 2^{n - 1}} \\ & C_{r}^{r} + C_{r + 1}^{r} + C_{r + 2}^{r} + \cdots + C_{n}^{r} = C_{n + 1}^{r + 1} & & C_{m}^{r} C_{n}^{0} + C_{m}^{r - 1} C_{n}^{1} + \cdots + C_{m}^{0} C_{n}^{r} = \htmlClass{blank}{C_{m + n}^{r}} \end{aligned} \]

两个基本恒等式的证明：\(C_{n}^{m}=C_{n}^{n - m}\)——从\(n\)个元素中取出\(m\)个，与留下\(n - m\)个一一对应，故两者组合数相等.   \(C_{n}^{m - 1}+C_{n}^{m}=C_{n + 1}^{m}\)（帕斯卡公式）——从\(n + 1\)个元素中取\(m\)个，按某个特定元素\(x\)是否被取分类：含\(x\)的取法须再从其余\(n\)个中取\(m - 1\)个，有\(C_{n}^{m - 1}\)种；不含\(x\)的须从其余\(n\)个中取\(m\)个，有\(C_{n}^{m}\)种，两类相加即得.

结论 1. 常见排列组合题型思路

  1. 考查两个计数原理的简单题型：相关考题属概念题,难度不高,解题的核心是分清楚何时 分类,何时分步,做到分类标准清晰,分步层次清楚,不重不漏即可.

  2. 排数字问题：这类题可画出数位,往数位上依次填入数字即可.

    若供选择的数字中有\(0\),则\(0\)不能排最高位,故常先用其它数字把最高位排了；

    若要求排出的数是奇数或偶数,则考虑最低位的数字为奇数数字或偶数数字；

    若要求排出的数字比某数大或比某数小,则先排最高位的数字,因为最高位对数的大小的 影响最重.

  3. 元素相邻问题（捆绑法）：将\(n\)个不同元素排成一排，其中某\(k\)个元素排在相邻位置上. 先将这\(k\)个元素捆绑在一起，看成一个整体，当作一个元素同其他元素一起排列，共有\(\mathrm{A}_{n-k+1}^{n-k+1}\)种排法；再将捆绑在一起的元素内部进行排列，共有\(\mathrm{A}_{k}^{k}\)种排法. 因此符合条件的排法共有 \(\mathrm{A}_{n-k+1}^{n-k+1} \cdot \mathrm{A}_{k}^{k}\)种.

  4. 元素不相邻问题（插空法）：将\(n\)个不同的元素排成一排，其中\(k\)个元素互不相邻（\(k \leqslant n-k+1\)）. 先将没有要求的\((n-k)\)个元素排成一排，其排列方法有\(\mathrm{A}_{n-k}^{n-k}\)种；再将要求互不相邻的\(k\)个元素插入\((n-k+1)\)个空中，其排列方法有\(\mathrm{A}_{n-k+1}^{k}\)种. 因此符合条件的排法共有 \(\mathrm{A}_{n-k}^{n-k} \cdot \mathrm{A}_{n-k+1}^{k}\) 种.

  5. 特殊元素： 解题原则是谁“特殊”谁优先.一般从以下三种思路考虑：

    1. 以元素为主考虑，即先安排特殊元素，再安排其他元素；

    2. 以位置为主考虑，即先安排特殊位置，再安排其他位置；

    3. 用间接法解题，先不考虑限制条件，计算出排列总数，再减去不符合要求的排列数.

    当限制条件有两个或两个以上时，若互不影响，则按分步解决；若相互影响，则先分类，然后在每一类中再分步.

结论 2. 方程解的组合数问题（隔板法）

  1. 正整数解问题： 方程 \(x_1 + x_2 + \cdots + x_n = m \ (m \ge n, m, n \in \mathbf{N}^*)\) 的正整数解的组数.

    将 \(m\) 个“1”排成一排，中间有 \(m-1\) 个空隙. 我们需要将这 \(m\) 个“1”分成 \(n\) 部分（每部分至少一个），只需要在 \(m-1\) 个空隙中选 \(n-1\) 个位置插入“隔板”. 因此正整数解有 \(C_{m-1}^{n-1}\) 组.

  2. 非负整数解问题： 方程 \(x_1 + x_2 + \cdots + x_n = m \ (n, m \in \mathbf{N}^*)\) 的非负整数解的组数.

    换元，令 \(y_i = x_i + 1\) (其中 \(x_i \ge 0 \Rightarrow y_i \ge 1\)). 则原方程转化为 \((y_1 - 1) + (y_2 - 1) + \cdots + (y_n - 1) = m\), 整理得 \(y_1 + y_2 + \cdots + y_n = m + n\). 转化为求 \(y_i\) 的正整数解.因此非负整数解有 \(C_{(m+n)-1}^{n-1} = C_{m+n-1}^{n-1} = C_{m+n-1}^{m}\) 组.

  3. 一般下界限制： 方程 \(x_1 + x_2 + \cdots + x_n = m\)的解的组数, 要求 \(x_i \ge a_i \ (a_i \in \mathbf{Z})\).

    令 \(y_i = x_i - a_i + 1 \ge 1\), 则 \(x_i = y_i + a_i - 1\). 代入方程得 \((y_1+a_1-1) + \dots + (y_n+a_n-1) = m\), 即 \(y_1 + \dots + y_n = m - \sum_{i=1}^n a_i + n\). 转化为正整数解问题求解.

    【例】 将20个相同苹果分给3个小朋友，甲至少2个，乙至少3个，丙至少4个，有多少种分法

    解：设甲、乙、丙分得的苹果数分别为 \(x, y, z\)，则 \(x \ge 2, y \ge 3, z \ge 4\). 令 \(x' = x-1, y' = y-2, z' = z-3\)，则 \(x', y', z' \ge 1\). 方程转化为 \((x'+1) + (y'+2) + (z'+3) = 20 \Rightarrow x'+y'+z' = 14\). 问题转化为求 \(x'+y'+z' = 14\) 的正整数解组数，由隔板法，解的个数为 \(C_{14-1}^{3-1} = C_{13}^2 = 78\).

  4. 不等式解的个数： 不等式 \(x_1 + x_2 + \cdots + x_n \le m \ (x_i \in \mathbf{N}^*)\) 的正整数解组数.

    增加一个变量\(y_{n+1}\ge 0\),代表剩余的量, 原不等式等价于 \(x_1 + \cdots + x_n + y_{n+1} = m\). 则问题变为 \(x_1 + \cdots + x_n + (y_{n+1} + 1) = m + 1\) 的正整数解问题. 即相当于 \(n+1\) 个变量和为 \(m+1\) 的正整数解问题.

    因此不等式的正整数解有 \(C_{(m+1)-1}^{(n+1)-1} = C_{m}^{n}\) 组.

结论 3. 分组分派问题

将\(n\)个不同元素分成\(m\)组，且每组的元素个数分别为\(m_1,m_2,m_3,\cdots,m_m\)，记

\[ N = C_n^{m_1} \cdot C_{n-m_1}^{m_2} \cdot C_{n-(m_1+m_2)}^{m_3} \cdot \cdots \cdot C_{n-(m_1+m_2+\cdots+m_{m-1})}^{m_m} \]

(1) 非均匀不编号分组: \(n\)个不同元素分成\(m\)组，每组元素数目均不相等，且不考虑各组间的顺序，分法种数为\(N\).

(2) 均匀不编号分组: 将\(n\)个不同元素分成不编号（即无序）的\(m\)组，每组元素数目相等，分法种数为\(\dfrac{N}{\mathrm{A}_m^m}\).

(3) 部分均匀不编号分组: 将\(n\)个不同元素分成不编号的\(m\)组，其中有\(r\)组元素个数相等，分法种数为\(\dfrac{N}{\mathrm{A}_r^r}\)，如果再有\(k\)组均匀分组，应再除以\(\mathrm{A}_k^k\).

【例】将6本不同的书分成三份,共有多少种分法？

若每份2本,则共有\(\dfrac{C_{6}^{2}C_{4}^{2}C_{2}^{2}}{A_{3}^{3}} = 15\) 种不同的分法.

若三份分别为4本、1本、1本,则共有\(\dfrac{C_{6}^{4}C_{2}^{1}C_{1}^{1}}{A_{2}^{2}} = 15\)种不同的分法.

若三份分别为3本、2本、1本,则共有\(C_{6}^{3}C_{3}^{2}C_{1}^{1} = 60\)种不同的分法.

综上所述，共有 \(15 + 15 + 60 = 90\) 种不同的分法.

【例】现需安排5名学生，分别到3个地点进行实习，每个地点至少安排1名学生，则有多少种不同的安排方案.

解: 先将5人分为三组，每组的人数分别为\(3,1,1\)或\(2,2,1\)，再将三组分配给三个地点，由分步乘法计数原理可知，不同的安排方案数为 \(\left( \dfrac{C_5^3C_2^1C_1^1}{\mathrm{A}_2^2} + \dfrac{C_5^2C_3^2C_1^1}{\mathrm{A}_2^2} \right) \mathrm{A}_3^3 = 150.\)

结论 4. 万能元素（多面手问题）

【例】有12名划船运动员，其中3人只会划左舷，4人只会划右舷，5人既会划左舷又会划右舷.现从中选出6人平均分在左、右舷参赛，求不同的选法种数.

解：以只会划左舷的3人中被选人数为分类依据，分四类讨论：

  1. 左舷选3名只会左舷的人：选法为\(\mathrm{C}_{3}^{3}\mathrm{C}_{9}^{3}\)；

  2. 左舷选2名只会左舷、1名多面手：选法为\(\mathrm{C}_{3}^{2}\mathrm{C}_{5}^{1}\mathrm{C}_{8}^{3}\)；

  3. 左舷选1名只会左舷、2名多面手：选法为\(\mathrm{C}_{3}^{1}\mathrm{C}_{5}^{2}\mathrm{C}_{7}^{3}\)；

  4. 左舷选3名多面手：选法为\(\mathrm{C}_{3}^{0}\mathrm{C}_{5}^{3}\mathrm{C}_{6}^{3}\).

根据分类加法计数原理，总选法为 \(\mathrm{C}_{3}^{3}\mathrm{C}_{9}^{3} + \mathrm{C}_{3}^{2}\mathrm{C}_{5}^{1}\mathrm{C}_{8}^{3} + \mathrm{C}_{3}^{1}\mathrm{C}_{5}^{2}\mathrm{C}_{7}^{3} + \mathrm{C}_{3}^{0}\mathrm{C}_{5}^{3}\mathrm{C}_{6}^{3} = 2174\) 种.

结论 5. 定序问题

在有些排列问题中，某些元素的前后顺序是确定的（不一定相邻），即要把\((m+n)\)个元素排成一列，其中\(m\)个元素之间的先后顺序确定不变，解决这类问题的基本方法有以下三种：

  1. 整体法：将\((m+n)\)个元素排成一列，有\(\mathrm{A}_{m+n}^{m+n}\)种不同的排法，这\(m\)个元素有\(\mathrm{A}_m^m\)种排法，其中只有一个排列是我们需要的，因此满足条件的不同排法共有 \(\frac{\mathrm{A}_{m+n}^{m+n}}{\mathrm{A}_m^m}\) 种.

  2. 空位插空法：因为有\(m\)个元素之间的顺序固定不变，只有一种排法，所以可先排剩余的\(n\)个元素，余下的\(m\)个空留给那\(m\)个元素，共有\(\mathrm{A}_{m+n}^n\)种不同的排法.

  3. 逐步插空法：因为有\(m\)个元素之间的顺序固定不变，所以先将它们依次排好，形成\((m+1)\)个空位，将剩余的\(n\)个元素依次记为\(n_1,n_2,\dots,n_n\)，再排\(n_1\)，有\((m+1)\)种排法，并相应增加一个空位，以此类推排\(n_2,n_3,\dots,n_n\)，逐步插空完成.

结论 6. 多排问题直排法

【例】8人排成前后两排,每排4人,其中甲乙在前排,丙在后排,共有多少排法

解: 8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.先排前4个位置上的特殊元素有\(\mathrm{A}_4^2\)种,再排后4个位置上的特殊元素丙有\(\mathrm{A}_4^1\)种,其余的5人在5个位置上任意排列有\(\mathrm{A}_5^5\)种,则共有\(\mathrm{A}_4^2\mathrm{A}_4^1\mathrm{A}_5^5\)种.

结论 7. 环排问题线排策略

一般地,\(n\)个不同元素作圆形排列,共有\((n - 1)!\)种排法. 从\(n\)个不同元素中取出\(m\)个元素作圆 形排列共有\(\dfrac{\mathrm{A}_{n}^{m}}{m}\)种.

【例】 8人围桌而坐,共有多少种坐法?

解：围桌而坐与坐成一排的不同点在于,坐成圆形没有首尾之分,所以固定一 人\(A\)并从此位置把圆形展成直线其余\(7\)人共有\((8 - 1)!\)种排法即\(7!\)

图

注意：如果是\(n\)个珍珠穿成一条项链,答案是\(\dfrac{(n-1)!}{2}\) （\(n{\gt}2\)且\(n\)是正整数）,因为项链可以翻转.

结论 8. 网格最短路径问题

求从\(M\)点到\(N\)点的不反向路径（最短路径）的走法方法数.

解：任意一条从 \(M\) 到 \(N\) 的不反向路径，本质上只能向右和向上走. 要想到达终点，必定需要向右走 \(m\) 段，向上走 \(n\) 段，总共累积要走 \(m+n\) 段路径. 因此，安排一条具体路线，就等价于在这 \(m+n\) 步中，选出 \(m\) 步用来向右走（剩余的 \(n\) 步向上走）.方法总数即为 \(\mathrm{C}_{m+n}^m\)（或 \(\mathrm{C}_{m+n}^n\)）.

图

拓展：标数法（加法递推）找路径数

当网格不够规则（有缺失等）或含有只能避开的障碍点时，直接列组合数公式会比较麻烦，此时推荐使用标数法.

规则：在每个能通过的格点标上数字，表示从起点到该点的最短路径总数. 因为只能向右或向上走，所以任何一个交叉点处的路线数，等于它左处相邻点和下方相邻点的数字之和 （类似于杨辉三角的递推原理）.遇到障碍点，相当于到达该点的路线数为 \(0\).

图

结论 9. 特殊模型

  1. 求几何体中的\(n\)个顶点连成的直线构成的异面直线的组数: 先确定四面体的个数，而后注意到每个四面体中只有三组异面直线!【答案: \(3(C_n^4 - m)\)，其中\(m\)为四点共面的组合数.】

  2. 由(椭)圆上\(n\)个点确定的直线在圆内交点最多个数，取决于圆内接四边形的个数.【答案: \(C_n^4\).】

  3. \(n\)个连续号码，出现两组\(m\)个连续号码的情形数为\(C_{n-2(m-1)}^2\).（掐头去尾，从中选号，两边连号.）

  4. 求30030能被多少个不同的偶数整除. 先把30030分解成质因数的乘积形式\(30030=2×3×5×7×11×13\)，依题意可知偶因数必先取2,再从其余5个因数中任取若干个组成乘积，所有的偶因数为： \(C_5^1+C_5^2+C_5^3+C_5^4+C_5^5\)

结论 10. 全错位排列问题

一个人写了\(n\)封不同的信及相应的\(n\)个不同的信封,他把这\(n\)封信都装错了信封,问有多少种方 法?

假设正确对应关系为第\(1,2,3,\ldots,n\)个信封分别应该装第\(a_1,a_2,a_3,\ldots,a_n\)封信,\(n\)封 信全部错位的方法有\(S_n\)种.

考虑其中一封信\(a_n\),\(a_n\)不能放到第\(n\)个信封,总共有\(n - 1\)种错位放法

记\(a_n\)错装到第\(k\)个位置,考虑被挤占的\(a_k\)怎么放

  (1) 如果\(a_k\)放到第\(n\)个位置,相当于和\(a_n\)交换,只需要考虑剩 下\(n - 2\)封信怎么错位排,有\(S_{n - 2}\)种方法

  (2) 如果\(a_k\)不放到第\(n\)个位置,只需要考虑包含\(a_k\)在内剩下\(n - 1\)封信的错 排,有\(S_{n - 1}\)种方法.因此

\[ S_n=(n - 1)(S_{n - 1}+S_{n - 2}) \]

  1. 事实上通项公式为 \(S_{n}=n!\sum_{k = 0}^{n}\dfrac{(-1)^{k}}{k!}\)

  2. 推广：若 \(n\) 封信中恰有 \(m(m\leq n)\) 封信装错,则方法数为 \(T_{n}=C_{n}^{m}S_{m}\). 只需先将 \(n\) 封信全部装对,再选出 \(m\) 封需要装错的信件,然后对这 \(m\) 封信进行全错位排列,根据乘法原理即可得到上述结果

  3. 数列 \(\{S_n\}\) 的前10项依次为 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961

结论 11. 环形染色问题

用\(m\)种颜色对如图\(n\)个环形区域进行染色,相邻区域不同色,有多少种方法数？

图中,假定从\(A_1\)开始逆时针染色.对于最后一次染色,先不考虑“邻区域不同色”的限 制条件,也就是不管\(A_n\)和\(A_1\)颜色相同与否,那么染色方法数显然有\(m\times(m - 1)^{n - 1}\) 种.运用分类加法原理,\(A_n\)和\(A_1\)颜色相同时的方法数与\(A_n\)和\(A_1\)颜色不同时的方 法数之和就是上面的这个结果.设\(A_n\)和\(A_1\)颜色不同的方法数为\(a_n\),若\(A_n\)和\(A_1\)颜色相同,可将它们视为同一区域,方法数为\(a_{n-1}\),

因此,得到递推式

图

\[ a_{n - 1}+a_{n}=m(m - 1)^{n - 1}(n\geq3) \]

用累加法求通项公式,只需要左右两侧同时乘上\((-1)^{n}\),得到

\[ a_{n}\cdot(-1)^{n}-a_{n - 1}\cdot(-1)^{n - 1}=-m(1 - m)^{n - 1} \]

为了让形式更简洁,设\(T_{n}=a_{n}\cdot(-1)^{n}\),进行累加,得到

\[ T_{n}=-m\cdot[(1 - m)^{n - 1}+(1 - m)^{n - 2}+(1 - m)^{n - 3}+\ldots+(1 - m)^{3}]+T_{3} \]

容易得到边界\(T_{3}=-1\times m(m - 1)(m - 2)=-m\times((1 - m)^{2}+(1 - m))\),代入得

\[ \begin{aligned} T_{n} & =-m\cdot[(1 - m)^{n - 1}+(1 - m)^{n - 2}+(1 - m)^{n - 3}+\ldots+(1 - m)^{3}]+T_{3} \\ & =-m\cdot[(1 - m)^{n - 1}+(1 - m)^{n - 2}+(1 - m)^{n - 3}+\ldots+(1 - m)^{3}+(1 - m)^{2}+(1 - m)] \\ & =(1 - m)^{n}-(1 - m) \end{aligned} \]

除以\((-1)^{n}\)得到答案

\[ a_{n}=(-1)^{n}(m - 1)+(m - 1)^{n}=\htmlClass{blank}{(-1)^{n}(\text{色} - 1)+(\text{色} - 1)^{n}} \]

结论 12. 传球问题

\(m\)个人进行篮球传球游戏,规则为每个人接球后再传给别人.规定由甲第一次传球,若第\(n\)次传球后,球又回到甲的手中,求所有的传球方法数?

暂且不管第\(n - 1\)次传给了谁,注意到第\(n - 1\)次传球后拿到球的人把球传给甲就行了,因此总方法数为\(n - 1\)次传球的方法数即\((m - 1)^{n - 1}\).但是如果第\(n - 1\)次传球给了甲,由于他不能传给自己,因此这种情况是不成立的,减去即可.设第\(n\)次传球后回到甲手中的方法数为\(a_{n}\),得到递推式\(a_{n} = (m - 1)^{n - 1} - a_{n - 1}\),整理得

\[ a_{n}+a_{n - 1}=(m - 1)^{n - 1} \]

边界条件\(a_{1} = 0\)（甲第一次只能传给别人）.这个递推式的处理方法和多边形染色类似,这里给出结果

\[ a_{n}=\dfrac{(-1)^{n}(m - 1)+(m - 1)^{n}}{m} \]

二项式定理

定义 1. 二项式定理

\[ (a + b)^n = C_{n}^{0}a^{n}+C_{n}^{1}a^{n - 1}b^{1}+\cdots + C_{n}^{k}a^{n - k}b^{k}+\cdots + C_{n}^{n}b^{n},\; n\in\mathbf{N}^{*}. \tag{1} \]

由于\((a + b)^n\)是\(n\)个\((a + b)\)相乘,每个\((a + b)\)在相乘时有两种选择,选\(a\)或\(b\),而且每个\((a + b)\)中的\(a\)或\(b\)都选定后,才能得到展开式的一项. 因此,由分步乘法计数原理可知,在合并同类项之前,\((a + b)^n\)的展开式共有\(2^n\)项,其中每一项都是\(a^{n - k}b^{k}\)（\(k = 0, 1, \cdots, n\)）的形式.

对于每个\(k\)（\(k = 0, 1, 2, \cdots, n\)）,对应的项\(a^{n - k}b^{k}\)是由\((n - k)\)个\((a + b)\)中选\(a\),另外\(k\)个\((a + b)\)中选\(b\)得到的. 由于\(b\)选定后,\(a\)的选法也随之确定,因此,\(a^{n - k}b^{k}\)出现的次数相当于从\(n\)个\((a + b)\)中取\(k\)个\(b\)的组合数\(C_{n}^{k}\). 这样,\((a + b)^n\)的展开式中,\(a^{n - k}b^{k}\)共有\(C_{n}^{k}\)个,将它们合并同类项,就可以得到上述二项展开式.

公式\((1)\)叫做{二项式定理},右边的多项式叫做\((a + b)^n\)的二项展开式,其中各项的系数\(C_{n}^{k}\)（\(k = 0, 1, 2, \cdots, n\)）叫做{二项式系数}. 式中的\(C_{n}^{k}a^{n - k}b^{k}\)叫做二项展开式的{通项},用\(T_{k + 1}\)表示,即通项为展开式的第\(k + 1\)项：

\[ T_{k + 1}=\htmlClass{blank}{C_{n}^{k}a^{n - k}b^{k}} \]

在二项式定理中,若设\(a = 1\),\(b = x\),则得到公式：

\[ (1 + x)^n = C_{n}^{0}+C_{n}^{1}x+C_{n}^{2}x^{2}+\cdots + C_{n}^{k}x^{k}+\cdots + C_{n}^{n}x^{n}. \]

性质 1. 二项式定理的性质

  1. 对称性：与首末两端“等距离”的两个二项式系数相等. 事实上,这一性质可直接由 \(C_{n}^{m}=C_{n}^{n - m}\)得到.

    直线 \(r = \dfrac{n}{2}\) 将函数 \(f(r)=C_{n}^{r}\) 的图象分成对称的两部分，它是图象的对称轴.

  2. 增减性与最大值：

    \(\text{因为 } C_{n}^{k}=\dfrac{n(n - 1)\cdots(n - k)(n - k + 1)}{(k - 1)!k}=C_{n}^{k - 1}\dfrac{n - k + 1}{k} \text{,即} \dfrac{C_{n}^{k}}{C_{n}^{k - 1}}=\dfrac{n - k + 1}{k} \text{ 所以 , 当} \dfrac{n - k + 1}{k}{\gt}1\)

    即 \(k{\lt}\dfrac{n + 1}{2}\) 时,\(C_{n}^{k}\) 随 \(k\) 的增加而增大；由对称性知,当 \(k{\gt}\dfrac{n + 1}{2}\) 时,\(C_{n}^{k}\) 随 \(k\) 的增加而减小.

    当 \(n\) 是偶数时,中间的一项 \(C_{n}^{\frac{n}{2}}\) 取得最大值；

    当 \(n\) 是奇数时,中间的两项 \(C_{n}^{\frac{n - 1}{2}}\) 与 \(C_{n}^{\frac{n + 1}{2}}\) 相等,且同时取得最大值.

  3. 二项式系数的和：

    因为 \((1+1)^n = C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots + C_{n}^{n}\)，所以 \((a + b)^n\) 的展开式的各二项式系数的和等于 \(2^n\).

  4. 奇数项与偶数项的二项式系数和：

    因为\((1-1)^n = C_{n}^{0}-C_{n}^{1}+C_{n}^{2}-\cdots + (-1)^n C_{n}^{n}\),所以 \(C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+\cdots = C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+\cdots = \frac{2^n}{2} = \htmlClass{blank}{2^{n-1}}\)，即奇数项的二项式系数和等于偶数项的二项式系数和等于 \(2^{n-1}\).

结论 1. 求特定项

  1. 求形如 \((a + b)^n\ (n \in \mathbb{N}^*)\) 的展开式中与特定项相关的量（常数项、参数值、特征项）

    利用二项式定理写出展开式的通项公式 \(T_{k+1} = C_n^k a^{n-k} b^k\)，通常把字母和系数分离开（注意符号不要出错）； 根据题目中的相关条件（如常数项要求指数为零，有理项要求指数为整数）先列出相应方程(组)或不等式(组)，解出 \(k\)； 把 \(k\) 代入通项公式中，即可求出 \(T_{k+1}\)，有时还需要先求 \(n\)，再求 \(k\)，才能求出 \(T_{k+1}\) 或其他量.

  2. 求形如\((a+b+c)^n\)的多项展开式中与特定项相关的量

    1. 转化为二项式：将三项中的两项当作一个整体， 根据二项式定理求出 \(\left[(a + b) + c\right]^n\) 的展开式的通项；根据特定项的系数进行分析， 弄清特定项是由 \((a + b)^{n-k}\) 的展开式中的哪些项和 \(c^k\) 项相乘得到； 把相乘后的项合并即可得特定项或相关量 展开后再对 \((a+b)\) 的乘方运用二项式定理求解.

    2. 组合角度： 将 \((a + b + c)^n = (a + b + c)(a + b + c) \dots (a + b + c)\) 展开，本质是从 \(n\) 个因式中选 \(k\) 个因式取 \(a\)，有 \(C_n^k\) 种选法； 再从剩余 \(n-k\) 个因式中选 \(l\) 个因式取 \(b\)，有 \(C_{n-k}^l\) 种选法； 最后剩余 \(m = n - k - l\) 个因式取 \(c\)，有 \(C_m^m = 1\) 种选法. 因此，其展开式的通项为： \(C_n^k a^k C_{n-k}^l b^l C_m^m c^m = \dfrac{n!}{k! \cdot l! \cdot m!} a^k b^l c^m\).

  3. 求形如 \((a+b)^m(c+d)^n\) (\(n,m \in \mathbf{N}^*\)) 的展开式中与特定项相关的量

    利用二项式定理把 \((a+b)^m\) 与 \((c+d)^n\) 分别展开，并写出其通项公式； 根据特定项的要求（如未知数的指数）,分析特定项是由 \((a+b)^m\) 与 \((c+d)^n\) 展开式中的哪些项相乘得到； 最后合并相乘后的项即可得特定项相关是量.

结论 2. 求系数和

设 \((ax + b)^n = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n = f(x)\).

  1. 常数项：\(a_0 = \htmlClass{blank}{f(0)}\).

  2. 所有项系数和：\(a_0 + a_1 + a_2 + \cdots + a_n = \htmlClass{blank}{f(1)}\). (对于 \((ax + by)^n\) 型，令 \(x=1, y=1\) 即可求得).

  3. 奇偶交替符号和：\(a_0 - a_1 + a_2 - \cdots + (-1)^n a_n = \htmlClass{blank}{f(-1)}\).

    奇数项系数和：\(a_0 + a_2 + a_4 + \cdots = \dfrac{f(1) + f(-1)}{2}\). 偶数项系数和：\(a_1 + a_3 + a_5 + \cdots = \dfrac{f(1) - f(-1)}{2}\).

  4. 系数绝对值之和：求 \(|a_0| + |a_1| + \cdots + |a_n|\) 的值.

    利用 \((|a|x + |b|)^n = |a_0| + |a_1|x + \cdots + |a_n|x^n\) ，再令 \(x = 1\) ，即等于 \((|a| + |b|)^n\).

  5. 系数加权和（求导法）：求 \(a_1 + 2a_2 + 3a_3 + \cdots + na_n\) 的值.

    对原式两边求导得：\(n(ax + b)^{n-1} \cdot a = a_1 + 2a_2x + 3a_3x^2 + \cdots + na_nx^{n-1}\)， 再令 \(x = 1\) ，即等于\(na(a + b)^{n-1}\).

结论 3. 求系数最大的项

二项式\((ax + by)^n\)（\(a,b \in \mathbb{R}\)且\(a,b \neq 0, n \in \mathbb{N}^*\)）展开式中,若第\(r + 1\)项系数的绝对值最大,

则 \(\begin{cases} C_{n}^{r} |a|^{n - r} |b|^r \geq C_{n}^{r - 1} |a|^{n - r + 1} |b|^{r - 1} \\ C_{n}^{r} |a|^{n - r} |b|^r \geq C_{n}^{r + 1} |a|^{n - r - 1} |b|^{r + 1} \end{cases}\),化简可得 \(r \in \htmlClass{blank}{\left[ \dfrac{|b|(n + 1)}{|a| + |b|} - 1, \dfrac{|b|(n + 1)}{|a| + |b|} \right]}\)

【例】 要求\(\left( \sqrt{x} - \dfrac{2}{x} \right)^7\)展开式中系数最大项. 记第\(k + 1\)项系数绝对值最大,则 \(k \in \left[ \dfrac{2}{1 + 2} \times 8 - 1, \dfrac{2}{1 + 2} \times 8 \right] = \left[ \dfrac{13}{3}, \dfrac{16}{3} \right]\) 即\(k = 5\)时系数的绝对值最大,此时\(T_6 = -2^5 C_{7}^{5} x^{-4}\),系数为负数. 故展开式系数最大项可能出现在第\(5\)项或第\(7\)项. 又\(T_5 = 560x^{-\frac{5}{2}}\),\(T_7 = 448x^{-\frac{11}{2}}\),所以系数最大项为\(T_5 = 560x^{-\frac{5}{2}}\).

结论 4. 杨辉三角（人教A选必三P40）

图

  1. 对称性 ： 即与首末两端“等距离”的两个二项式系数相等,数学表达式为： \(C_n^r = C_n^{n - r}\)

  2. 二项式系数的定义： 第 \(n\) 行的第 \(r\!+\!1\) 个数是组合数： \(C_n^r = \dfrac{n!}{r!(n - r)!}\)

  3. 奇数项与偶数项之和相等： 第 \(n\) 行的奇数项之和等于偶数项之和,即： \(C_n^0 + C_n^2 + C_n^4 + \cdots = C_n^1 + C_n^3 + C_n^5 + \cdots\) 且两者之和均为 \(2^{n-1}\).

  4. 所有项之和为 \(2^n\) ： 第 \(n\) 行的所有数之和等于 \(2^n\),即： \(C_n^0 + C_n^1 + C_n^2 + \cdots + C_n^n = 2^n\)

  5. 相邻两行的递推关系 ： 观察杨辉三角的相邻两行,满足组合数递推公式： \(C_n^r = C_{n-1}^{r-1} + C_{n-1}^r\)

  6. 平行于腰的直线上数的和 ： 自腰上的某个 \(1\) 开始,平行于腰的一条直线上连续 \(n\) 个数之和,等于最后一个数斜右下方的数,即：

    \[ C_r^r + C_{r+1}^r + C_{r+2}^r + \cdots + C_{n-1}^r = C_n^{r+1} \]

结论 5. 整除和余数问题

  1. 用二项式定理证明：\((n + 1)^n - 1\) 能被 \(n^2\) 整除.

    \[ \begin{aligned} (n + 1)^n - 1 & = C_n^0 n^n + C_n^1 n^{n-1} + C_n^2 n^{n-2} + \dots + C_n^{n-2} n^2 + C_n^{n-1} n + C_n^n - 1 \\ & = C_n^0 n^n + C_n^1 n^{n-1} + C_n^2 n^{n-2} + \dots + C_n^{n-2} n^2 + n^2 \\ & = n^2 \bigl( C_n^0 n^{n-2} + C_n^1 n^{n-3} + C_n^2 n^{n-4} + \dots + C_n^{n-2} + 1 \bigr) \end{aligned} \]

    所以 \((n + 1)^n - 1\) 能被 \(n^2\) 整除.

  2. 求证：\(3^{2n+2} - 8n - 9 \, (n \in \mathbb{N}^*)\) 能被 \(64\) 整除.

    \[ \begin{aligned} 3^{2n+2} - 8n - 9 & = 9^{n+1} - 8n - 9 = (8 + 1)^{n+1} - 8n - 9 \\ & = C_{n+1}^0 8^{n+1} + C_{n+1}^1 8^n + C_{n+1}^2 8^{n-1} + \dots + C_{n+1}^{n-1} 8^2 + C_{n+1}^n 8 + C_{n+1}^{n+1} - 8n - 9 \\ & = \bigl( C_{n+1}^0 8^{n+1} + C_{n+1}^1 8^n + C_{n+1}^2 8^{n-1} + \dots + C_{n+1}^{n-1} 8^2 \bigr) + 8(n + 1) + 1 - 8n - 9 \\ & = 64 \bigl( C_{n+1}^0 8^{n-1} + C_{n+1}^1 8^{n-2} + C_{n+1}^2 8^{n-3} + \dots + C_{n+1}^{n-1} \bigr) \end{aligned} \]

    所以 \(3^{2n+2} - 8n - 9 \, (n \in \mathbb{N}^*)\) 能被 \(64\) 整除.

  3. 求证：\(1 + 2 + 2^2 + \dots + 2^{5n-1} \, (n \in \mathbb{N}^*)\) 能被 \(31\) 整除.

    证明： 因为等比数列求和

    \[ 1 + 2 + 2^2 + \dots + 2^{5n-1} = \frac{1 - 2^{5n}}{1 - 2} = 2^{5n} - 1 = 32^n - 1 = (31 + 1)^n - 1 \]

    展开二项式：

    \[ \begin{aligned} (31 + 1)^n - 1 & = C_n^0 31^n + C_n^1 31^{n-1} + C_n^2 31^{n-2} + \dots + C_n^{n-1} 31 + C_n^n - 1 \\ & = 31 \bigl( C_n^0 31^{n-1} + C_n^1 31^{n-2} + C_n^2 31^{n-3} + \dots + C_n^{n-1} \bigr) \end{aligned} \]

    所以 \(1 + 2 + 2^2 + \dots + 2^{5n-1} \, (n \in \mathbb{N}^*)\) 能被 \(31\) 整除.

  4. \(91^{92}\) 除以 \(100\) 的余数是\(\underline{\quad\quad}\).

    \[ \begin{aligned} 91^{92} & = (90 + 1)^{92} = C_{92}^0 90^{92} + C_{92}^1 90^{91} + C_{92}^2 90^{90} + \dots + C_{92}^{90} 90^2 + C_{92}^{91} 90 + C_{92}^{92} \\ & = 90^2 \bigl( C_{92}^0 90^{90} + C_{92}^1 90^{89} + \dots + C_{92}^{90} \bigr) + 92 \times 90 + 1 \\ & = 81 \times 100 \bigl( C_{92}^0 90^{90} + C_{92}^1 90^{89} + \dots + C_{92}^{90} \bigr) + 82 \times 100 + 81 \end{aligned} \]

    所以 \(91^{92}\) 除以 \(100\) 的余数是 \(81\).

  5. \(3^8\) 被 \(5\) 除所得的余数是\(\underline{\quad\quad}\).

    \[ \begin{aligned} 3^8 & = 9^4 = (10 - 1)^4 = C_4^0 10^4 - C_4^1 10^3 + C_4^2 10^2 - C_4^3 10 + C_4^4 = 10 \bigl( C_4^0 10^3 - C_4^1 10^2 + C_4^2 10 - C_4^3 \bigr) + 1 \end{aligned} \]

    所以 \(3^8\) 被 \(5\) 除所得的余数是 \(1\).

  6. 设 \(n \in \mathbb{N}^*\),则 \(4 \times 6^n + 5^{n+1}\) 除以 \(20\) 的余数为\(\underline{\quad\quad}\).

    \[ \begin{aligned} 4 \times 6^n + 5^{n+1} & = 4(5 + 1)^n + 5(4 + 1)^n \\ & = 4 \bigl( C_n^0 5^n + C_n^1 5^{n-1} + \dots + C_n^{n-1} 5 + C_n^n \bigr) + 5 \bigl( C_n^0 4^n + C_n^1 4^{n-1} + \dots + C_n^{n-1} 4 + C_n^n \bigr) \\ & = 20 \bigl( C_n^0 5^{n-1} + C_n^1 5^{n-2} + \dots + C_n^{n-1} \bigr) + 4 + 20 \bigl( C_n^0 4^{n-1} + C_n^1 4^{n-2} + \dots + C_n^{n-1} \bigr) + 5 \end{aligned} \]

    所以 \(4 \times 6^n + 5^{n+1}\) 除以 \(20\) 的余数为 \(9\).

结论 6. 近似计算问题

  1. \(1.02^8 \approx\)（小数点后保留三位小数）

    \(1.02^8 = (1 + 0.02)^8 = 1 + C_8^1\times0.02 + C_8^2\times0.02^2 + C_8^3\times0.02^3 + \cdots + C_8^8\times0.02^8\), 由二项展开式的性质易知,\(C_8^3\times0.02^3 {\lt} 0.001\),\(C_8^4\times0.02^4\)远小于\(0.001\),依次类推, 故\(1.02^8 = (1 + 0.02)^8 \approx 1 + C_8^1\times0.02 + C_8^2\times0.02^2 + C_8^3\times0.02^3 \approx 1.172\)

  2. \((1.05)^6\)的计算结果精确到\(0.01\)的近似值是

    \((1.05)^6 = (1 + 0.05)^6 = 1 + C_6^1\cdot0.05 + C_6^2\cdot0.05^2 + \cdots \approx 1 + 0.3 + 0.0375 = 1.3375 \approx 1.34\)

题型

排列与组合

题型 1. 分类加法与分步乘法

题型识别：完成一件事有若干互斥方案，或必须连续完成若干步骤，要求计数.

核心思路：分类相加、分步相乘. 先判断方案间是否互斥且完备，步骤间是否缺一不可；分类标准必须唯一，避免重复与遗漏.

解题步骤：

  1. 明确最终任务与完成条件；

  2. 按互斥分类或连续步骤拆解；

  3. 分别计算每类、每步的数目；

  4. 用加法或乘法原理合并，并检查覆盖性.

易错点：分类不互斥仍相加；步骤并非独立却机械相乘；遗漏“不选”或特殊情况.

题型 2. 特殊元素优先与特殊位置优先

题型识别：排列中有指定元素、位置、名额或限制，要求排法数.

核心思路：限制最强的元素或位置先安排，再处理剩余自由部分. 先固定特殊元素可避免在全排列后复杂排除.

解题步骤：

  1. 找出限制最多的元素、位置或组别；

  2. 优先安排它并计算可选数；

  3. 对剩余元素按普通排列、组合或分配完成；

  4. 检查特殊元素之间是否仍有额外限制.

易错点：特殊元素重复安排；先后顺序导致重复计数；将“至少”误按“恰好”.

题型 3. 相邻的捆绑法

题型识别：若干元素必须相邻、组成整体或在同一组内排列.

核心思路：将必须相邻的元素捆成一个整体，先排整体与其余元素，再排捆内顺序. 多个捆绑块还要注意块间是否有额外顺序.

解题步骤：

  1. 将每个必须相邻的集合视为一个新元素；

  2. 计算新元素总数并进行外部排列；

  3. 乘以每个捆内元素的排列数；

  4. 检查是否要求“恰好相邻”而需排除更大捆绑.

易错点：捆内顺序漏乘；多个捆绑块相同却未区分；“至少相邻”与“恰好相邻”混淆.

题型 4. 不相邻的插空法

题型识别：若干特殊元素彼此不相邻，或不能与某类元素相邻.

核心思路：先排非特殊元素形成空位，再从空位中选取位置插入特殊元素. 特殊元素彼此不相邻时，每个空位至多放一个.

解题步骤：

  1. 先排列限制较少的普通元素；

  2. 数出首尾和元素间的可插空位；

  3. 选择空位并排列特殊元素；

  4. 若限制只针对某些相邻关系，调整可用空位集合.

易错点：忘记首尾两个空位；一个空位放多个特殊元素破坏不相邻；普通元素本身有重复未除重.

题型 5. 分组分派与多面手

题型识别：将人或物分到不同组、不同岗位，涉及组有无标号、人数限制或一人可承担多个角色.

核心思路：先分组再分配，或先定人数再选人. 组有标号用组合连乘，组无标号要除以组间交换产生的重复；多面手可按是否承担多个任务分类.

解题步骤：

  1. 判断组是否有名称、岗位是否可区分；

  2. 先安排人数、特殊人员或多面手的去向；

  3. 对每种人数方案用组合或排列计算；

  4. 对无标号的同类组去重并求和.

易错点：无标号组未除重；先分后派与直接派重复计算；多面手同时归属两组的规则理解错误.

题型 6. 数字排列与定序问题

题型识别：用数字组成数，或要求若干元素保持相对次序、首位非零、奇偶整除等.

核心思路：首位、末位和整除条件优先处理；相对顺序固定的元素可把其内部排列数从全排列中消去，或按定序插入处理.

解题步骤：

  1. 先处理首位非零、末位奇偶或整除限制；

  2. 再安排其余数字，注意是否允许重复；

  3. 定序元素用“总排列除内部排列”或逐个插入；

  4. 检查构成的对象是否允许前导零和重复数字.

易错点：将\(0\)与普通数字同等处理；重复数字仍用排列数；定序元素内部顺序被重复计算.

题型 7. 染色、传球与递推计数

题型识别：环形、相邻限制染色，或传球、走格子等多步过程，要求方案总数.

核心思路：局部相邻限制可按起点分类或建立状态递推；传球问题按“是否回到起点、最后持球者类型”分类，必要时列递推或矩阵状态.

解题步骤：

  1. 确定状态：当前位置、颜色、是否与首项冲突等；

  2. 写出一步转移或按起始状态分类；

  3. 用递推、分类或补集计算总数；

  4. 对环形问题额外检查首尾相邻条件.

易错点：环形按线形处理漏首尾限制；递推初值错误；传球允许传给自己的规则未明确.

题型 8. 隔板法与非负整数解

题型识别：求\(x_1+\cdots+x_k=n\)的正整数、非负整数解个数，或资源分配中每组至少、至多若干个.

核心思路：非负整数解用\(\binom{n+k-1}{k-1}\)，正整数解先令\(x_i=y_i+1\). 有上下界时先平移下界，再用容斥或分类处理上界.

解题步骤：

  1. 将实际分配翻译为整数方程；

  2. 通过代换消去“至少”限制；

  3. 插入隔板计算无上界解数；

  4. 有上界时分类或用容斥扣除超限情形.

易错点：正整数和非负整数公式混用；隔板数写成变量数；上界约束完全忽略.

二项式定理

题型 1. 二项展开式的指定项与系数

题型识别：求\((a+b)^n\)或变式展开中的常数项、\(x^r\)项或其系数.

核心思路：先写通项\(T_{k+1}=\binom nk a^{n-k}b^k\)，再令变量指数满足目标条件. 区分“项”“系数”“二项式系数”.

解题步骤：

  1. 写出通项并明确\(k\)范围；

  2. 合并变量指数，令其等于目标指数；

  3. 解出整数\(k\)并检查范围；

  4. 代入通项计算完整系数.

易错点：将\(k\)与第\(k\)项混淆；指数方程解非整数仍保留；漏掉常数因子与符号.

题型 2. 多项乘积与非标准二项式展开

题型识别：两个或多个二项式乘积、含分式或替换变量的展开，求特定幂的系数.

核心思路：分别写各因子的通项，再由各项指数和等于目标指数列方程；非标准形式先提取公因子、换元或化成标准二项式.

解题步骤：

  1. 将每个因子整理成可展开形式；

  2. 写出各因子的通项与变量指数；

  3. 枚举满足指数条件的所有组合；

  4. 将每种组合的系数相加.

易错点：只找一组指数搭配；提取公因子后漏乘；多项乘积中同类项没有合并.

题型 3. 系数和、交错和与余数

题型识别：求展开式所有系数和、奇偶项系数和、交错和，或多项式除以\(x\pm1\)、\(x^m\pm1\)的余数.

核心思路：令\(x=1\)求系数和，令\(x=-1\)求交错和；奇偶项和由两式相加减获得. 余数问题用代入法或将\(x\)按模多项式化简.

解题步骤：

  1. 将多项式记为\(P(x)\)；

  2. 代\(1,-1\)得到所需线性组合；

  3. 对余数按除式的根代值或按周期化简幂次；

  4. 结合题目要求解出奇偶项系数和或余数.

易错点：把系数和当作\(P(0)\)；奇偶项和的加减系数漏除\(2\)；除式有多个根时条件不足.

题型 4. 二项式系数最大项

题型识别：求二项式系数或展开式中各项系数的最大值、最大项位置.

核心思路：研究相邻两项或相邻二项式系数之比，找从大于\(1\)到小于\(1\)的临界位置. 当比值等于\(1\)时可能出现相邻两个最大项.

解题步骤：

  1. 写出相邻系数或相邻项的比值；

  2. 解比值与\(1\)的大小关系；

  3. 定位最大项的下标；

  4. 检查临界处是否有两个并列最大值.

易错点：只比较二项式系数却题目问完整系数；漏掉并列最大项；比值分母为零的端点未检查.