1 加法原理与乘法原理
1.1 加法原理（分类计数原理）
内容：完成一件事有 $n$ 类不同方案，在第 $1$ 类方案中有 $m_1$ 种不同方法，在第 $2$ 类方案中有 $m_2$ 种不同方法，……，在第 $n$ 类方案中有 $m_n$ 种不同方法，那么完成这件事共有：
$$ N = m_1 + m_2 + \cdots + m_n $$种不同方法。
核心特征：分类完成。各类方法之间相互独立，任意一类中的任意一种方法都可以独立完成这件事。
注意：分类时要不重不漏，即各类之间没有交集，且并集为全集。
1.2 乘法原理（分步计数原理）
内容：完成一件事需要 $n$ 个不同步骤，做第 $1$ 步有 $m_1$ 种不同方法，做第 $2$ 步有 $m_2$ 种不同方法，……，做第 $n$ 步有 $m_n$ 种不同方法，那么完成这件事共有：
$$ N = m_1 \times m_2 \times \cdots \times m_n $$种不同方法。
核心特征：分步完成。各个步骤之间相互依存，只有各个步骤都完成了，这件事才算完成。
注意：分步时要保证各步之间相互独立，即某一步的方法数不受前一步选择的影响。
2 排列
定义：从 $n$ 个不同元素中取出 $m$（$m \leq n$）个元素，按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。
排列数：从 $n$ 个不同元素中取出 $m$ 个元素的所有不同排列的个数，记作 $A_n^m$（或 $P_n^m$，沪教版常用 $P_n^m$）。
$$ A_n^m = P_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!} $$全排列：$n$ 个不同元素全部取出的排列，$A_n^n = P_n^n = n!$
规定：$0! = 1$
注意：排列与顺序有关。$A_n^m$（$P_n^m$）的推导依据乘法原理——依次选 $m$ 个位置。
3 组合
定义：从 $n$ 个不同元素中取出 $m$（$m \leq n$）个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。
组合数：从 $n$ 个不同元素中取出 $m$ 个元素的所有不同组合的个数，记作 $C_n^m$（或 $\binom{n}{m}$）。
$$ C_n^m = \frac{A_n^m}{A_m^m} = \frac{P_n^m}{P_m^m} = \frac{n(n-1)(n-2)\cdots(n-m+1)}{m!} = \frac{n!}{m!(n-m)!} $$注意：组合与顺序无关。
组合数的性质：
- $C_n^m = C_n^{n-m}$（对称性）
- $C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$（帕斯卡恒等式）
- $C_n^0 + C_n^1 + \cdots + C_n^n = 2^n$
4 排列组合的运用
（以下各小节的公式中，排列数统一标注为 $A_n^m$（$P_n^m$），表示两者通用，沪教版优先使用 $P_n^m$。）
4.1 捆绑法
- 适用场景：解决相邻问题（若干元素必须排在一起）。
- 操作方法：将必须相邻的元素捆绑成一个整体（视作一个"大元素"），先与其他元素一起排列，再考虑捆绑内部元素的顺序。
- 注意：捆绑后内部元素之间也要排列。
4.2 插空法
- 适用场景：解决不相邻问题（若干元素不能排在一起）。
- 操作方法：先排其他元素（无限制条件），形成若干空位（含两端），再将不相邻的元素插入这些空位中。
- 注意：若不相邻元素之间有区别，则插入后还需排列。
4.3 特殊位置法
- 适用场景：某些元素或位置有特殊限制（如某人不能站在某位置）。
- 操作方法：优先处理有特殊限制的元素或位置，先安排这些"特殊"对象，再安排其余普通对象。
4.4 隔板法
- 适用场景：解决相同元素的分配问题（如将 $n$ 个相同小球放入 $k$ 个不同盒子，每个盒子至少一个）。
- 操作方法：将 $n$ 个相同元素排成一排，在它们之间的 $n-1$ 个空隙中插入 $k-1$ 个隔板，分成 $k$ 组。方法数为 $C_{n-1}^{k-1}$。
- 推广：若允许有空盒，则先借 $k$ 个元素（转化为每个盒子至少一个），方法数为 $C_{n+k-1}^{k-1}$。
4.5 排除法（间接法）
- 适用场景：从总体中排除不合条件的方案，即"正难则反"。
- 操作方法：先计算总的方法数，再减去不符合条件的方法数。
- 常用情形：“至多"“至少"类问题，或正面分类较多时。
4.6 分组分配法
适用场景：将若干元素分成若干组，再分配到不同对象（如将 $n$ 个不同元素分到 $k$ 个不同盒子中）。
核心思路：先分组（组合），再分配（排列）。分组与分配是两个不同的阶段。
类型一：均匀分组（组间无区别）
- 将 $mn$ 个不同元素平均分成 $m$ 组，每组 $n$ 个。
- 方法数：$\dfrac{C_{mn}^n \cdot C_{(m-1)n}^n \cdots C_n^n}{m!}$
- 除以 $m!$ 的原因：组与组之间无区别，先分出的 $A$ 组与后分出的 $B$ 组调换顺序是同一分法。
类型二：非均匀分组（组间无区别）
- 将 $n$ 个不同元素分成元素个数互不相同的 $m$ 组。
- 方法数：$C_n^{n_1} \cdot C_{n-n_1}^{n_2} \cdots$（无需除以阶乘，因为各组元素个数不同，已天然区别）
类型三：部分均匀分组（组间无区别）
- 如有若干组元素个数相同，则只需对均匀的组数除以阶乘。
- 例：将 $6$ 个不同元素分成 $2$ 个、$2$ 个、$1$ 个、$1$ 个四组，方法数为 $\dfrac{C_6^2 \cdot C_4^2 \cdot C_2^1 \cdot C_1^1}{2! \cdot 2!}$。
类型四：分配问题（组间有区别）
- 先按上述分组方法分组（无论是否均匀），再乘以组数的全排列。
- 例：将 $5$ 个不同元素分给甲、乙、丙三人，甲得 $2$ 个、乙得 $2$ 个、丙得 $1$ 个：方法数为 $C_5^2 \cdot C_3^2 \cdot C_1^1$（因为对象已指定，无需再乘排列）。
注意：分组分配法最容易出错的地方在于是否除以阶乘，关键判断在于——组与组之间是否有区别。若分组后还需分配给有区别的对象，则先按无区别分组，再乘以 $m!$ 分配。
4.7 定序法
适用场景：解决部分元素顺序固定的问题（如 $m$ 个元素中有几个元素必须按某一特定顺序出现，但不要求相邻）。
操作方法一（除法） ：先不考虑定序条件，进行全排列，再除以定序元素的排列数。
- 若有 $n$ 个元素，其中 $m$ 个元素的顺序固定，则排列数为 $\dfrac{A_n^n}{A_m^m} = \dfrac{P_n^n}{P_m^m} = \dfrac{n!}{m!}$。
操作方法二（组合法） ：先从 $n$ 个位置中选 $m$ 个位置给定序元素（位置选好后顺序自然确定），其余元素任意排列。
- 方法数为 $C_n^m \cdot A_{n-m}^{n-m}$（即 $C_n^m \cdot P_{n-m}^{n-m}$）。
特例：若定序元素完全相同（即 $n$ 个元素中有 $m$ 个相同元素），则方法数为 $\dfrac{n!}{m!}$（即重复排列问题）。
常见题型：如”$A, B, C$ 三人中，$A$ 必须在 $B$ 前面（不要求相邻）"。
5 二项式定理
定理：
$$ (a + bx)^n = \sum_{k=0}^n C_n^k a^{n-k} (bx)^k = C_n^0 a^n + C_n^1 a^{n-1}(bx) + \cdots + C_n^k a^{n-k} b^k x^k + \cdots + C_n^n b^n x^n $$其中 $n \in \mathbb{N}^*$。
通项公式：第 $k+1$ 项（$k = 0, 1, \cdots, n$）：
$$ T_{k+1} = C_n^k a^{n-k} b^k x^k $$二项式系数：$C_n^k$（$k = 0, 1, \cdots, n$）叫做二项式系数。
项的系数：指的是展开后每一项的数字因数（包括常数和字母前的倍数），即 $C_n^k a^{n-k} b^k$（若为 $(a+bx)^n$，则 $x^k$ 的系数为 $C_n^k a^{n-k} b^k$，注意 $b$ 可能贡献常数倍数）。
注意区分：
- 二项式系数：$C_n^k$，与 $a, b$ 无关；
- 项的系数：$C_n^k a^{n-k} b^k$，含 $a, b$ 的幂次。
二项式系数的性质：
- 对称性：$C_n^k = C_n^{n-k}$
- 单调性：先增后减，当 $n$ 为偶数时，$C_n^{\frac{n}{2}}$ 最大；当 $n$ 为奇数时，$C_n^{\frac{n-1}{2}} = C_n^{\frac{n+1}{2}}$ 最大（且同时最大）
- 各二项式系数之和：$C_n^0 + C_n^1 + \cdots + C_n^n = 2^n$
- 奇数项二项式系数和 = 偶数项二项式系数和：$C_n^0 + C_n^2 + C_n^4 + \cdots = C_n^1 + C_n^3 + C_n^5 + \cdots = 2^{n-1}$
5.1 赋值法求系数相关问题
- 核心思想：二项展开式中，各项系数之和或特定项的系数可通过给 $x$ 赋特殊值来求解，而不必将每一项展开。
设
$$ (a + bx)^n = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n $$其中 $a_k$ 为 $x^k$ 项的系数（$k = 0, 1, \cdots, n$），则 $a_k = C_n^k a^{n-k} b^k$。
令 $x = 1$，得所有项系数之和：
$$ a_0 + a_1 + a_2 + \cdots + a_n = (a + b)^n $$令 $x = -1$，得各项系数交替和：
$$ a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^n a_n = (a - b)^n $$令 $x = 0$，得常数项：
$$ a_0 = a^n $$奇次项系数之和：
$$ a_1 + a_3 + a_5 + \cdots = \frac{(a+b)^n - (a-b)^n}{2} $$偶次项系数之和：
$$ a_0 + a_2 + a_4 + \cdots = \frac{(a+b)^n + (a-b)^n}{2} $$所有项系数绝对值之和： 将 $(a + bx)^n$ 中每一项系数取绝对值，等价于将 $b$ 替换为 $|b|$ 后的系数之和，即：
$$ |a_0| + |a_1| + |a_2| + \cdots + |a_n| = (|a| + |b|)^n $$特别地，若 $(a + bx)^n$ 中 $a$ 和 $b$ 均为正数，则所有项系数之和与系数绝对值之和相等，均为 $(a+b)^n$。
求特定 $x^m$ 项的系数：利用通项公式 $T_{k+1} = C_n^k a^{n-k} b^k x^k$，令 $k = m$，得 $a_m = C_n^m a^{n-m} b^m$。
多个二项式乘积的系数求法：通常通过组合搭配，寻找产生 $x^m$ 的所有可能组合，再分别计算系数后相加。