排列组合

排列组合基础ψ(｀∇´)ψ

计数原理ψ(｀∇´)ψ

加法原理: 如果完成一个事情有 \(n\) 类方法，其中第 \(i\) 类方法有 \(a_i\) 种策略，因为这些方法是独立的，所以总共的方案数为 \(\sum a_i\) 种。
乘法原理：如果完成一个事情有 \(n\) 个步骤，其中第 \(i\) 个步骤有 \(a_i\) 种策略，因为这些方法是前后关联的，所以总共的方案数为 \(\prod a_i\) 种。

排列数和组合数ψ(｀∇´)ψ

排列数ψ(｀∇´)ψ

定义从 \(n\) 个不同元素中选 \(m\) 个元素出来（\(m \le n\)），进行排列（有序），所能得到的总排列数为 \(\text A_n^m\)。

比如 \(1, 2, 3\)，任意拿两个出来排列就有 \([1, 2]; [1,3]; [2, 1]; [2, 3]; [3,1]; [3,2]\) 这六种，即 \(\text A_3^2 = 6\)

计算可以考虑把问题转化成有 \(n\) 个人，排长度为 \(m\) 的一个队，第 \(1\) 个位置有 \(n\) 种选法，第 \(2\) 个位置有 \(n - 1\) 种选法，第 \(m\) 个位置有 \(n - m + 1\) 种选法，根据乘法原理可以得到排列数的计算公式：

\[ \text{A}_n^m = \prod\limits_{i = 1}^{m}(n - i + 1) = \dfrac{n!}{(n - m)!} \]

其中全排列为 \(\text A_n^n = n!\)。

组合数ψ(｀∇´)ψ

定义从 \(n\) 个不同元素种拿 \(m\) 个元素出来 \((m \le n)\)，进行组合（无序），所能得到的总排列数为 \(\text C_n^m\)，也记作 \(\dbinom{n}{m}\)。

比如 \(1,2,3\)，任意拿两个出来组合就有 \(\{1,2\}; \{2, 3\}; \{1, 3\}\) 这三种，即 \(\dbinom{3}{2} = 3\)。

计算可以从排列数那里转化，假设我们拿了 \(m\) 个人出来排列，显然这 \(m\) 个人的 \(m!\) 种排列都会被计算，在组合里面会被算作一个，所以在排列数的基础上除掉 \(m!\) 即可。

\[ \dbinom{n}{m} = \dfrac{n!}{m!(n-m)!} \]

其中边界为： \(\dbinom{n}{0} = 1\)。

二项式定理ψ(｀∇´)ψ

\[ (a + b)^n = \sum\limits_{i = 0}^{n}\dbinom{n}{i}a^{n - i}b^{i} \]

其中 \(\displaystyle \dbinom{n}{i} a^{n - i}b^i\) 叫做 \((a + b)^n\) 展开式的第 \(i + 1\) 项 \(T_{i + 1}\)，注意 \((a + b)^n, (b + a)^n\) 的展开式的第 \(i\) 项是不一样的。

\((a - b)^n\) 的展开式通项多了一个容斥系数一样的东西：\(\displaystyle T_{i + 1} = (-1)^i \dbinom{n}{i} a^{n - i}b^i\)。

二项式定理也可以扩展为多项式的形式，在此不展开。

所以，\(\dbinom{n}{m}\) 也被叫做二项式系数。

组合数性质ψ(｀∇´)ψ

I.

\[ \dbinom{n}{m}=\dbinom{n}{n-m} \]

这个是显然的，因为你选 \(m\) 个和选 \(n - m\) 个的情况是捆绑起来的。

II.

\[ \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n-1}{k-1} \]

这个也是显然的，根据定义展开就可以得到。

也可以写作

\[ k\dbinom{n}{k} = n\dbinom{n - 1}{k - 1} \]

III.

\[ \dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1} \]

这个就是组合数的递推式，也可以看作是杨辉三角。

IV.

\[ \dbinom{n}{0}+\dbinom{n}{1}+\cdots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n \]

这是二项式定理的特殊情况。取 \(a=b=1\) 就可以了。

V.

\[ \sum_{i=0}^n(-1)^i\dbinom{n}{i}=[n=0] \]

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

后面那个是 Iverson Bracket.

VI.

\[ \sum_{i=0}^m \dbinom{n}{i}\dbinom{m}{m-i} = \dbinom{m+n}{m}\ \ \ (n \geq m) \]

这个就是范德蒙德卷积的推论。

VII.

\[ \sum_{i=0}^n\dbinom{n}{i}^2=\dbinom{2n}{n} \]

仍旧是范德蒙德卷积的推论.

VIII.

\[ \sum_{l=0}^n\dbinom{l}{k} = \dbinom{n+1}{k+1} \]

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

IX.

\[ \dbinom{n}{r}\dbinom{r}{k} = \dbinom{n}{k}\dbinom{n-k}{r-k} \]

用定义展开一下就可以证明了，式子形式很好记。

X.

\[ \sum_{i=0}^n\dbinom{n-i}{i}=F_{n+1} \]

其中 \(F\) 是斐波那契数列。

这个我不会证明，暂时咕了。

几个基本方法ψ(｀∇´)ψ

捆绑法ψ(｀∇´)ψ

要求某几个元素排列组合的时候必须相邻。

做法大概就是把他们捆绑起来，然后算成一个元素做排列，再在内部做排列。

例题

某国家集训队共 \(7\) 人合影留念，要求甲选手和乙选手必须站在一起，那么一共有多少种不同的排法？

简单的问题，把甲和乙捆绑，然后排列，答案是 \(\text A^{6}_{6} = 6!\) 种。

然后甲乙内部有 \(\text A^2_2 = 2!\) 种答案，乘法原理，答案等于 \(6!2! = 1140\)。

插空法ψ(｀∇´)ψ

要求某几个元素排列组合的时候必须不相邻。

做法大概就是把这几个元素提出来，剩下的排列一次。

然后把这几个提出来的元素插到空里面去。

例题

某国家集训队共 \(7\) 人合影留念，要求甲选手和乙选手必须不站在一起，那么一共有多少种不同的排法？

简单的问题，先把剩下 \(5\) 个人拿出来排列 \(\text A_5^5\) 种情况。

然后甲乙可以站在两两之间的空或者头尾，一共有 \(6\) 个位置可以选，现在要放两个人进去，本质可以转化为 \(6\) 个元素抽两个出来做排列，所以有 \(\text A_6^2\) 种情况。

乘法原理，答案是 \(\text A_5^5 \text A_6^2\)。

和捆绑法结合的例题

某国家集训队共 \(7\) 人合影留念，要求甲选手和乙选手必须站在一起且他们任意一位不能和丙选手站在一起，那么一共有多少种不同的排法？

简单的问题，先把甲乙捆绑，然后甲乙丙拉出来剩下的做排列，插空之后甲乙内部再排列。

答案是 \(\text A_4^4 \text A_5^3 \text A_2^2\)。

插板法ψ(｀∇´)ψ

为什么这里和 OI-wiki 一样

（OI-Wiki 上这部分是我写的，可以看我当时的 Pull Request OI-wiki#4278）

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

正整数和的数目ψ(｀∇´)ψ

问题一：现有 \(n\) 个 完全相同 的元素，要求将其分为 \(k\) 组，保证每组至少有一个元素，一共有多少种分法？

考虑拿 \(k - 1\) 块板子插入到 \(n\) 个元素两两形成的 \(n - 1\) 个空里面。

因为元素是完全相同的，所以答案就是 \(\dbinom{n - 1}{k - 1}\)。

本质是求 \(x_1+x_2+\cdots+x_k=n\) 的正整数解的组数。

非负整数和的数目ψ(｀∇´)ψ

问题二：如果问题变化一下，每组允许为空呢？

显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。

我们考虑创造条件转化成有限制的问题一，先借 \(k\) 个元素过来，在这 \(n + k\) 个元素形成的 \(n + k - 1\) 个空里面插板，答案为

\[ \dbinom{n + k - 1}{k - 1} = \dbinom{n + k - 1}{n} \]

虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解：

开头我们借来了 \(k\) 个元素，用于保证每组至少有一个元素，插完板之后再把这 \(k\) 个借来的元素从 \(k\) 组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一一对应，答案也就是相等的。

由此可以推导出插板法的公式：\(\dbinom{n + k - 1}{n}\)。

本质是求 \(x_1+x_2+\cdots+x_k=n\) 的非负整数解的组数（即要求 \(x_i \ge 0\)）。

不同下界整数和的数目ψ(｀∇´)ψ

问题三：如果再扩展一步，要求对于第 \(i\) 组，至少要分到 \(a_i,\sum a_i \le n\) 个元素呢？

本质是求 \(x_1+x_2+\cdots+x_k=n\) 的解的数目，其中 \(x_i \ge a_i\)。

类比无限制的情况，我们借 \(\sum a_i\) 个元素过来，保证第 \(i\) 组至少能分到 \(a_i\) 个。也就是令

\[ x_i^{\prime}=x_i-a_i \]

得到新方程：

\[ \begin{aligned} (x_1^{\prime}+a_1)+(x_2^{\prime}+a_2)+\cdots+(x_k^{\prime}+a_k)&=n\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-a_1-a_2-\cdots-a_k\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-\sum a_i \end{aligned} \]

其中

\[ x_i^{\prime}\ge 0 \]

然后问题三就转化成了问题二，直接用插板法公式得到答案为

\[ \dbinom{n + \sum a_i - 1}{n} \]

以下摘录自 OI-wiki。

圆排列ψ(｀∇´)ψ

\(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)!} \]

不相邻排列ψ(｀∇´)ψ

\(1 \sim n\) 这 \(n\) 个自然数中选 \(k\) 个，这 \(k\) 个数中任何两个数都不相邻的组合有 \(\dbinom {n-k+1}{k}\) 种。

多重集的排列数 | 多重组合数ψ(｀∇´)ψ

请大家一定要区分 多重组合数 与 多重集的组合数！两者是完全不同的概念！

多重集是指包含重复元素的广义集合。设 \(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\) 个球的全排列数就是 多重集的排列数。多重集的排列数常被称作 多重组合数。我们可以用多重组合数的符号表示上式：

\[ \dbinom{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\) 的非负整数解的数目，可以用插板法解决，答案为

\[ \dbinom{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\dbinom{k+r-n_i-2}{k-1} -\sum_{i,j}\dbinom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\dbinom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\dbinom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned} \]

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

\[ Ans=\sum_{p=0}^k(-1)^p\sum_{A}\dbinom{k+r-1-\sum_{A} n_{A_i}-p}{k-1} \]

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

最后更新: September 6, 2023