一个蒟蒻小学生尝试学习高级排列组合

呃呃呃呃呃呃,我不咋会写,如有不对的地方欢迎纠正

紧接上文我们已经了解了基础的排列组合,我们可以接着往下学习排列组合的变种了.

1.排列组合的变种

1-1.多重集的排列数 + 多重组合数

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

多重集是指包含重复元素的广义集合。设 S={n1⋅a1,n2⋅a2,⋯ ,nk⋅ak}S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\} 表示由 n1n_1 个 a1a_1，n2n_2 个 a2a_2，…，nkn_k 个 aka_k 组成的多重集，SS 的全排列个数为

n!∏i=1kni!=n!n1!n2!⋯nk!\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}

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

(nn1,n2,⋯ ,nk)=n!∏i=1kni!\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}

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

1-2.多重集的组合数 1

设 S={n1⋅a1,n2⋅a2,⋯ ,nk⋅ak}S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\} 表示由 n1n_1 个 a1a_1，n2n_2 个a2a_2，…，nkn_k 个aka_k 组成的多重集。那么对于整数 r(r<ni,∀i∈[1,k])r(r<n_i,\forall i\in[1,k])，从SS 中选择 rr 个元素组成一个多重集的方案数就是 多重集的组合数。这个问题等价于 x1+x2+⋯+xk=rx_1+x_2+\cdots+x_k=r 的非负整数解的数目，可以用插板法解决，答案为

(r+k−1k−1)\binom{r+k-1}{k-1}

1-3.多重集的组合数 2

考虑这个问题：设 S={n1⋅a1,n2⋅a2,⋯ ,nk⋅ak,}S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\} 表示由 n1n_1 个 a1a_1，n2n_2 个 a2a_2，…，nkn_k 个 组 aka_k 成的多重集。那么对于正整数 rr，从 SS 中选择 rr 个元素组成一个多重集的方案数。

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

∀i∈[1,k], xi≤ni, ∑i=1kxi=r\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r

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

  1. 全集：∑i=1kxi=r\displaystyle \sum_{i=1}^kx_i=r 的非负整数解。
  2. 属性：xi≤nix_i\le n_i。

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

∣⋂i=1kSi∣=∣U∣−∣⋃i=1kSi‾∣\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|

根据容斥原理，有：

∣⋃i=1kSi‾∣=∑i∣Si‾∣−∑i,j∣Si‾∩Sj‾∣+∑i,j,k∣Si‾∩Sj‾∩Sk‾∣−⋯+(−1)k−1∣⋂i=1kSi‾∣=∑i(k+r−ni−2k−1)−∑i,j(k+r−ni−nj−3k−1)+∑i,j,k(k+r−ni−nj−nk−4k−1)−⋯+(−1)k−1(k+r−∑i=1kni−k−1k−1)\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}

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

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

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

1-4.圆排列

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

Qnn×n=Ann⟹Qn=Annn=(n−1)!\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!

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

Qnr=Anrr=n!r×(n−r)!\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}

2-1.组合数性质 | 二项式推论

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

(nm)=(nn−m)(1)\binom{n}{m}=\binom{n}{n-m}\tag{1}

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

(nk)=nk(n−1k−1)(2)\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2}

由定义导出的递推式。

(nm)=(n−1m)+(n−1m−1)(3)\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3}

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

(n0)+(n1)+⋯+(nn)=∑i=0n(ni)=2n(4)\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4}

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

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

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

∑i=0m(ni)(mm−i)=(m+nm)   (n≥m)(6)\sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6}

拆组合数的式子，在处理某些数据结构题时会用到。

∑i=0n(ni)2=(2nn)(7)\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7}

这是 66 的特殊情况，取 n=mn=m 即可。

∑i=0ni(ni)=n2n−1(8)\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8}

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

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

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

∑l=0n(lk)=(n+1k+1)(10)\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10}

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

(nr)(rk)=(nk)(n−kr−k)(11)\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11}

通过定义可以证明。

∑i=0n(n−ii)=Fn+1(12)\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12}

其中 FF 是斐波那契数列。

2-2.二项式反演

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

若已知 fnf_n 求 gng_n，那么显然有：

gn=∑i=0n(ni)fig_n = \sum_{i = 0}^{n} \binom{n}{i} f_i

若已知 gng_n 求 fnf_n，那么：

fn=∑i=0n(ni)(−1)n−igif_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i

上述已知 gng_n 求 fnf_n 的过程，就称为 二项式反演。

证明

将反演公式的 gig_i 展开得到：

fn=∑i=0n(ni)(−1)n−i[∑j=0i(ij)fj]=∑i=0n∑j=0i(ni)(ij)(−1)n−ifj\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}

先枚举 jj，再枚举 ii，得到：

fn=∑j=0n∑i=jn(ni)(ij)(−1)n−ifj=∑j=0nfj∑i=jn(ni)(ij)(−1)n−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) 得到：

fn=∑j=0nfj∑i=jn(nj)(n−ji−j)(−1)n−i=∑j=0n(nj)fj∑i=jn(n−ji−j)(−1)n−i\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−jk = i - j。则 i=k+ji = k + j，上式转换为：

fn=∑j=0n(nj)fj∑k=0n−j(n−jk)(−1)n−j−k1kf_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) 得到：

fn=∑j=0n(nj)fj[n=j]=fnf_n = \sum_{j = 0}^{n}\binom{n}{j}f_j[n = j] = f_n

证毕。

The End

鸣谢:

  • OI Wiki
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 115ms
  • Powered by Hydro v4.9.27 Community