科数网知识库
首页
目录
排列与组合进阶篇
日期:
2023-09-02 21:42
查看:
88
次
接下来我们介绍一些排列组合的变种。 多重集的排列数 | 多重组合数 请大家一定要区分 **多重组合数** 与 **多重集的组合数**！两者是完全不同的概念！ 多重集是指包含重复元素的广义集合。设 $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 $$ 于是很自然地想到了容斥原理。容斥的模型如下： 1. 全集：$\displaystyle \sum_{i=1}^kx_i=r$ 的非负整数解。 2. 属性：$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}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6} $$ 拆组合数的式子，在处理某些数据结构题时会用到。 $$ \sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7} $$ 这是 $(6)$ 的特殊情况，取 $n=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$ 是斐波那契数列。
本系统使用
启明星知识库Kbase
搭建，最后更新于
2023-09-02 21:42
，如果您有意见或建议请点击
反馈
。