gf24118 的博客
GF2025C2排列与组合
gf24118 LV 8 @ 2025-8-6 16:53:56

排列与组合！！！

编者注:遇到最左侧箭头请点击查看详情，再次点击回退

排列

加法原理

咱们做一件事，比如说学习信奥，完成它可以有 $n$ 类办法(可以是自主学习，也可以是跟dxd学等等)，在第一类办法中有 $m1$ 种不同的方法，在第二类办法中有 $m2$ 种不同的方法，以此类推，故在第 $n$ 类办法中自然就有 $mn$ 种不同的办法，所以完成这件事有 $n=m1+m2+m3+...+mn$ 种不同的方式，可学习信奥的方式却是 $\infty$ 的。(doge)

加法原理中每一类的每一种方法可以独立完成此任务，分类不重，且分类不漏。

乘法原理

乘法原理其实和上面的差不多，就是完成种类有 $n=m1m2m3...mn$ 罢了，而且必须连续完成n步，称分步计数法。

定义

为了方便理解，接下来用栗子说明。

编者注:以下举例无特指，请不要对号入座。

都爱吃土豆吧，现在你要从 $n$ 个形状大小不同的土豆中选择 $m(m \leqslant n)$ 个土豆，用一定顺序排成一列，叫做从n个不同的元素中取出m个元素的一个排列。

公式

计算公式如下：

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

对了，当m=n时，称为全排列，它是一种特殊的排列。

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

方法：

捆绑法:

顾名思义，捆绑嘛，就是把一些相邻在一起的土豆扎成一捆，将它们看做一个大整体，简称大土豆，于是再将大土豆和其他元素一同排列，并且注意大土豆内的小土豆排列的方法叫做捆绑法。

公式: $P(n-1,n-1) × 内部排列数$

插空法:

不用土豆了，你面前有几只鸡，每个鸡之间肯定有一定的空间(空位)，选某几只鸡，它们既不相邻，也没有和哥哥的血缘关系。为了解决对于这种某几个元素不相邻的问题，先将其他元素排好，也就是让鸡排成一列，再将指定的不相邻的元素插入已排好的元素间隙或两端位置即可，俗称插空法。

公式： $间隙数为(其他元素数+1)$ ， $选择间隙组合$

排除法:

e，这个方法不细讲了，是个入都会。

公式: $总情况数 - 不符合条件情况数$

插板法(又称隔板法):

插板法（Stars and bars）是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。

使用这个方法有前提，就像哥哥成名要练习两年半一个道理，前提是所有元素必须相同，然后再进行分组(若干组)，每组至少一个元素。

公式： $C(N-1,M-1)（N为元素数，M为组数）$

特殊排列

重复排列:从 $n$ 个不同的物体中，允许重复选取，共选出r个物体排列的方案数: $n^{r}$
全排列:详情见上

组合

定义

还是土豆吧，也是跟上面一样，不过这次是将它们并成一组。

定理(未学，网上摘抄)

编者注:以下纯理论知识，略枯燥

二项式定理

在进入排列组合进阶篇之前，我们先介绍一个与组合数密切相关的定理——二项式定理。二项式定理阐明了一个展开式的系数：

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

证明可以采用数学归纳法，利用 $\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}$ 做归纳。

二项式定理也可以很容易扩展为多项式的形式：

设 $n$ 为正整数， $x_i$ 为实数，

$$(x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} $$

其中的 $\dbinom{n}{n_1,n_2,\cdots,n_t}$ 是多项式系数，它的性质也很相似：

\sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n

公式

看不看得懂看就完啦~~~~

组合记号和公式:

其中 $n$ 和 $m$ 代表元素总数和选取的元素数量。

C^m_n=(^n_m)=\frac{n!}{m!(n-m)!}=C^{n-m}_n

由此可知:

$$A^{m}_{n}=C^{m}_{n}.A^{m}_{n}=C^{n-m}_{n}.A^{m}_{n} $$

C^{m}_{n}=C^{m}_{n-1}+C^{m-1}_{n-1}

C^{0}_{n}=C^{n}_{n}=1

0≠1

特殊组合

重复组合:从 $n$ 个不同的物体中，允许重复选取，共选出r个物体组合的方案数: $C(n+r-1,r)$ ,也可写作 $C^{r}_{n+r-1}$

以下纯干货，自行判断是否继续阅读。编者将不在注入趣味内容。

排列与组合进阶篇

注:GF2025C2阶同学暂未学习,来源网络

接下来我们介绍一些排列组合的变种。

多重集的排列数 | 多重组合数

请大家一定要区分多重组合数与多重集的组合数！两者是完全不同的概念！多重集是指包含重复元素的广义集合。设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2，…$ ， $n_k$ 个 $a_k$ 组成的多重集， $S$ 的全排列个数为

$$\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!} $$

相当于把相同元素的排列数除掉了。具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$ ，且 $n=n_1+n_2+\ldots+n_k$ 。这 $n$ 个球的全排列数就是多重集的排列数。多重集的排列数常被称作多重组合数。我们可以用多重组合数的符号表示上式：

$$\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!} $$

可以看出， $\dbinom{n}{m}$ 等价于 $\dbinom{n}{m,n-m}$ ，只不过后者较为繁琐，因而不采用。

多重集的组合数 1

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2，…$ ， $n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r(r<n_i,\forall i\in[1,k])$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数就是多重集的组合数。这个问题等价于 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为

\binom{r+k-1}{k-1}

多重集的组合数 2

考虑这个问题：设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\} $表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2，…$ ， $n_k$ 个 $a_k$ 组成的多重集。那么对于正整数 $r$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数。

这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：

$$\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r $$

于是很自然地想到了容斥原理。容斥的模型如下：

全集： $\displaystyle \sum_{i=1}^kx_i=r$ 的非负整数解。
属性： $x_i\le n_i$ 。

于是设满足属性 $i$ 的集合是 $S_i$ ， $\overline{S_i}$ 表示不满足属性 $i$ 的集合，即满足 $x_i\ge n_i+1$ 的集合（转化为上面插板法的问题三）。那么答案即为

$$\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right| $$

根据容斥原理，有：

$$\begin{aligned}\left|\bigcup_{i=1}^k\overline{S_i}\right|=&\sum_i\left|\overline{S_i}\right|-\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right|+\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right|-\cdots\\&+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\=&\sum_i\binom{k+r-n_i-2}{k-1}-\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1}-\cdots\\&+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1}\end{aligned} $$

拿全集 $\displaystyle |U|=\binom{k+r-1}{k-1}$ 减去上式，得到多重集的组合数

$$Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1} $$

其中 A 是充当枚举子集的作用，满足 $|A|=p,\ A_i<A_{i+1}$ 。

圆排列

$n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$ 。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。所以有

$$\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)! $$

由此可知部分圆排列的公式：

$$\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!} $$

组合数性质 | 二项式推论

由于组合数在 OI 中十分重要，因此在此介绍一些组合数的性质。

\binom{n}{m}=\binom{n}{n-m}\tag{1}

相当于将选出的集合对全集取补集，故数值不变。（对称性）

$$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2} $$

由定义导出的递推式。

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3} $$

组合数的递推式（杨辉三角的公式表达）。我们可以利用这个式子，在 $O(n^2)$ 的复杂度下推导组合数。

$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4} $$

这是二项式定理的特殊情况。取 $a=b=1$ 就得到上式。

\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5}

二项式定理的另一种特殊情况，可取 $a=1, b=-1$ 。式子的特殊情况是取 $n=0$ 时答案为 $1$ 。

$$\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i} = \binom{m+n}{k}\tag{6} $$

拆组合数的式子，在处理某些数据结构题时会用到。被称为 范德蒙恒等式。

\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7}

这是 $式子6$ 的特殊情况，取 $n=k=m$ 即可。

\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8}

带权和的一个式子，通过对 $式子3$ 对应的多项式函数求导可以得证。

\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9}

与上式类似，可以通过对多项式函数求导证明。

$$\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10} $$

通过组合分析一一考虑 $S=\{a_1, a_2, \cdots, a_{n+1}\}$ 的 $k+1$ 子集数可以得证，在恒等式证明中比较常用。被称为朱世杰恒等式。

$$\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} $$

通过定义可以证明。

\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12}

其中 $F$ 是斐波那契数列。

$$\binom{n+k}{k}^2=\sum_{j=0}^k\binom{k}{j}^2\binom{n+2k-j}{2k}\tag{13} $$

通过 $式子6$ 可以证明。被称为李善兰恒等式。

二项式反演

记 $f_n$ 表示恰好使用 $n$ 个不同元素形成特定结构的方案数， $g_n$ 表示从 $n$ 个不同元素中选出 $i \geq 0$ 个元素形成特定结构的总方案数。

若已知 $f_n$ 求 $g_n$ ，那么显然有：

g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i

若已知 $g_n$ 求 $f_n$ ，那么：

$$f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i $$

上述已知 $g_n$ 求 $f_n$ 的过程，就称为二项式反演。

证明:

将反演公式的 $g_i$ 展开得到：

$$\begin{aligned} f_n &= \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} \left[\sum_{j = 0}^{i} \binom{i}{j} f_j\right] \\ &= \sum_{i = 0}^{n}\sum_{j = 0}^{i}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \end{aligned}$$

先枚举 $j$ ，再枚举 $i$ ，得到：

$$\begin{aligned} f_n &= \sum_{j = 0}^{n}\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \\ &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i} \end{aligned}$$

使用 「组合数性质 | 二项式推论」 的 $公式11$ 得到：

$$\begin{aligned} f_n &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{j}\binom{n - j}{i - j} (-1)^{n-i} \\ &= \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{i = j}^{n}\binom{n - j}{i - j} (-1)^{n-i} \end{aligned}$$

令 $k = i - j$ 。则 $i = k + j$ ，上式转换为：

$$f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{k = 0}^{n - j}\binom{n - j}{k} (-1)^{n-j-k}1^{k} $$

使用 「组合数性质 | 二项式推论」 的 $公式5$ 得到：

$$f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j[n = j] = f_n $$

证毕。

GF2025C2排列与组合