排列组合_专项题单练习

排列组合基础

排列组合是组合数学的基础内容。排列是指从一组元素中取出指定数量的元素并进行排序；组合则是指仅取出指定数量的元素，不考虑顺序。排列组合的核心是研究满足特定条件的排列与组合可能出现的总数，这一理论与古典概率论有密切联系。

加法原理与乘法原理

加法原理

若完成一件事有 $n$ 类不同方法，其中第 $i$ 类方法有 $a_i$ 种方式（$1 \leq i \leq n$），则完成这件事共有：

$$ S = a_1 + a_2 + \cdots + a_n $$

种不同方法。加法原理强调“分类进行，方法相加”。

乘法原理

若完成一件事需要分 $n$ 个步骤，第 $i$ 步有 $a_i$ 种方式（$1 \leq i \leq n$），则完成这件事共有：

$$ S = a_1 \times a_2 \times \cdots \times a_n $$

种不同方法。乘法原理强调“分步进行，方法相乘”。

排列与组合基础

排列数

从 $n$ 个不同元素中取出 $m$（$m \leq n$，$m,n$ 为自然数）个元素，按一定顺序排成一列，称为一个排列。所有不同排列的个数称为排列数，记作 $A_n^m$ 或 $P_n^m$。

计算公式为：

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

其中 $n!$ 表示 $n$ 的阶乘，如 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。

理解：从 $n$ 人中选 $m$ 人排队（$m \leq n$），第1位有 $n$ 种选法，第2位有 $n-1$ 种，……，第 $m$ 位有 $n-m+1$ 种，因此：
$$ A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n-m)!} $$

全排列：当 $m = n$ 时，即所有元素参与排列：

$$ A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! $$

全排列是排列数的特例。

组合数

从 $n$ 个不同元素中取出 $m$（$m \leq n$）个元素组成一组，称为一个组合。所有不同组合的个数称为组合数，记作 $\binom{n}{m}$，读作“$n$ 选 $m$”。

计算公式

$$ \binom{n}{m} = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!} $$

推导：先考虑顺序得 $A_n^m$，再除去 $m$ 个元素内部的全排列 $m!$，因为同一组合的 $m$ 个元素有 $m!$ 种不同排列方式：

$$ \begin{aligned} \binom{n}{m} \times m! &= A_n^m \\ \binom{n}{m} &= \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned} $$

组合数也写作 $C_n^m$，即 $C_n^m = \binom{n}{m}$，但现代数学更常用 $\binom{n}{m}$。

组合数亦称为二项式系数，在二项式定理中有重要作用。

规定：当 $m n$ 时，$A_n^m = \binom{n}{m} = 0$。

插板法

插板法（Stars and bars）用于解决相同元素分组问题及线性不定方程的整数解个数问题。

情形一：每组至少一个（正整数解）

将 $n$ 个相同元素分成 $k$ 组，每组至少一个元素，有多少种分法？

解法：在 $n$ 个元素形成的 $n-1$ 个空隙中插入 $k-1$ 块板子：

$$ \binom{n-1}{k-1} $$

等价于求 $x_1 + x_2 + \cdots + x_k = n$（$x_i \geq 1$）的正整数解组数。

情形二：每组可为空（非负整数解）

若允许某些组为空，则先借 $k$ 个元素，使每组至少有一个，再归还：

$$ \binom{n+k-1}{k-1} = \binom{n+k-1}{n} $$

等价于求 $x_1 + x_2 + \cdots + x_k = n$（$x_i \geq 0$）的非负整数解组数。

情形三：每组有不同下限

若第 $i$ 组至少 $a_i$ 个元素（$\sum a_i \leq n$），令 $x_i' = x_i - a_i \geq 0$，则：

$$ x_1' + x_2' + \cdots + x_k' = n - \sum a_i $$

解数为：

$$ \binom{n - \sum a_i + k - 1}{n - \sum a_i} $$

不相邻的组合

从 $1$ 到 $n$ 中选 $k$ 个数，要求任意两数不相邻，组合数为：

$$ \binom{n-k+1}{k} $$

二项式定理

定理形式

$$ (a+b)^n = \sum_{i=0}^n \binom{n}{i} a^{n-i} b^i $$

证明可用数学归纳法，基于组合恒等式 $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$。

容斥原理

一句话概括：

先全加，再减重，减多了就加回来。

------

两个集合

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

------

三个集合

$$ \begin{aligned} |A \cup B \cup C| &= |A| + |B| + |C| \ &\quad - (|A \cap B| + |A \cap C| + |B \cap C|) \ &\quad + |A \cap B \cap C| \end{aligned} $$

------

口诀

$$ \textbf{奇加偶减} $$

1 个集合：加
2 个集合交集：减
3 个集合交集：加
4 个集合交集：减

C++ 常见应用示例

$1 \sim N$ 中能被 2 或 3 整除的数的个数：

$\left\lfloor \frac{N}{2} \right\rfloor$
$\left\lfloor \frac{N}{3} \right\rfloor$
$\left\lfloor \frac{N}{6} \right\rfloor$

对应 C++ 思想：

int ans = N / 2 + N / 3 - N / 6;