组合意义

· · 个人记录

组合意义

虽然人人都说 “组合意义天地灭，代数推导保平安” ，但仍然不能否认组合意义是求解一类化简式子（仅限组合意义）的良好工具。

听学长 LHW 讲课有感。

组合意义本质上是和代数推导等价的，然而在组合计数相关问题中题目中的计数类问题和计数式子之间有着很大的联系。

用大白话来讲，就是将一个式子经过一个固定的套路 “翻译” ，在将它 “翻译” 回来，这样子做是等价的，于是我们yy出了一个组合恒等式。

这就好比将一句话从中文翻译成英文，再翻译法语、德语绕上这么一圈，最后翻译成中文，它们的意思是大差不差的。（出现意思偏差其实是翻译软件的问题）

但是，组合意义是一个极其不严谨的做法，至少在数学上是这样。由于这里是信息学竞赛，我们通过牺牲数学家的严谨，换来了一个比数学推导更加可做的做法。

这也有了本文开头的一句话：组合意义天地灭，代数推导保平安。

常见运算的组合意义

P.S. 设球总数为 x ，盒子染色的颜色数为 y ，将一个盒子又染色又放入球，总情况数为 x\times y 。

P.S. 设红色球总数为 x ，蓝色球总数为 y ，将一个盒子放入这两种球，总情况数为 x+y 。

P.S. 设有 k 个盒子，盒子染色的颜色数为 x ，总情况数为 x^k 。

以上的运算都相当灵活，其组合意义多变，可以配合其它的组合数一起使用。上文主要探讨了这些其组合意义的共性和其中的一个例子，请读者根据例子发散思维。

P.S. 圆排列的意思是：一个排列，将它首位相接。与正常排列不同的是，将这个环沿任意位置断开，可以得到许多原来的排列。

圆排列可以用在一组数内，第一个/最后一个元素已经确定，求总的方案数，我们将第一个元素转到开头，再将环断开就是一组方案。总而言之，每个圆排列都对应着一组情况。

通常题目中考察的就是这些基本运算，结合这些运算，尝试理解一些组合恒等式。

常见的组合恒等式

  1. \begin{pmatrix}a \\b \end{pmatrix}=\begin{pmatrix}a-1 \\b-1 \end{pmatrix}+\begin{pmatrix}a-1 \\b \end{pmatrix}

先考虑等式左边的组合意义，前文已经提到，就是在 a 个元素中无序的选择 b 个。

在考虑如何将这个组合意义用其他的方式表达出来，我们将 a 个元素分成 a-1 和单个元素两部分。分类讨论。

  1. 如果单个元素取，那么就要从前面 a-1 个元素中取 b-1 个。

  2. 如果第二个元素不取，那么前面 a-1 个元素中就要取 b 个。

将两部分的贡献相加得到总的情况数，即为等式右边。

  1. \begin{bmatrix}a \\b \end{bmatrix}=\begin{bmatrix}a-1 \\b-1 \end{bmatrix}+(a-1)\times\begin{bmatrix}a -1\\b \end{bmatrix}

和上面的等式一样，将 a 分成 a-1 和单个元素两部分，分类讨论。

  1. 将这个元素单独放入一个圆排列中。

  2. 将这个元素放入之前 a-1 的任意元素的后面。

两部分相加即证。

  1. 读者可自行推导：
\begin{Bmatrix} a \\b \end{Bmatrix}=\begin{Bmatrix} a-1 \\b-1 \end{Bmatrix}+b\times\begin{Bmatrix} a-1 \\b \end{Bmatrix}
  1. \sum_{i=0}^k\begin{pmatrix}n \\i \end{pmatrix}\times\begin{pmatrix}m \\k-i \end{pmatrix}=\begin{pmatrix}n+m \\k \end{pmatrix}

等式左边：在 n 个数中选 i 个数和在 m 个数中选 k−i 个数总共的方案数。

等式右边：将 n 和 m 合并，一共选 k 个。

等式左右两边等价。

  1. \begin{Bmatrix} a \\b \end{Bmatrix}=\frac{1}{b!}\sum_{k=0}^b(-1)^k\begin{pmatrix}b \\k \end{pmatrix}(b-k)^a

等式左边：将 a 个元素放入 b 个无序的盒子里。

等式右边：将 a 放入 b 个有序的盒子中，有的盒子可以没有总的情况数为 b^a。

发现可以容斥二项式反演，强制钦定一些盒子为空，设 f(i) 为 i 个盒子强制不放的情况数。

有 ans=\sum_{k=0}^b(-1)^kf(k)。其中我们钦定一些盒子为空的情况数为 \begin{pmatrix}b \\k \end{pmatrix} ，减去这些盒子后放入小球，情况数为 (b-k)^a 。

所以：

f(k)=\begin{pmatrix}b \\k \end{pmatrix}\times (b-k)^a

由于我们这里考虑的箱子是有序的，最后将 ans 乘上 \frac{1}{b!} 即得答案。

组合意义在信息学竞赛中的具体应用

Team Work

题意简述：

给定 n 和 k 。

\sum_{i=1}^n\begin{pmatrix}n \\i \end{pmatrix}\times i^k

数据范围： 1\le k\le 5000 ， 1\le n\le 10^9 。

Solution

考虑组合意义，将题意翻译：在 n 个箱子中选出 i 个，再将 k 个小球放入。

由于有些箱子可能没有球，我们考虑将分别统计一定装球的箱子和一定为空的箱子。

先选出 i 个箱子，方案数为 \begin{pmatrix}n \\i \end{pmatrix} 。

再将 k 个小球放入 i 个相同的箱子，箱子间无序，发现这是第二类斯特林数，方案数为 \begin{Bmatrix} k \\i \end{Bmatrix} 。

将箱子定向为有序，方案数为 i!。

剩下的箱子可选可不选，方案数为 2^{n-i} 。

所以我们得到：

\sum_{i=1}^n\begin{pmatrix}n \\i \end{pmatrix}\times i^k=\sum_{i=1}^ki!\times2^{n-i}\times\begin{pmatrix}n \\i \end{pmatrix}\begin{Bmatrix} k \\i \end{Bmatrix}

这样我们就得到了一个 O(k^2) 的算法，但由于本题的空间限制较为严格，将组合数拆开计算即可通过本题，时间复杂度瓶颈在于预处理第二类斯特林数。

[省选联考 2020 A 卷] 组合数问题

题意简述：

给定 n,x,mod,a(n) ，求模 mod 意义下式子的值：

\sum_{k=0}^nf(k)\times x^k\times \begin{pmatrix}n \\k \end{pmatrix}

其中 f(k)=\sum_{i=0}^ma_mk^m 。

Solution

将 f(k) 拆开：

=\sum_{i=0}^ma_i \sum_{k=0}^nk^i\times x^k\times \begin{pmatrix}n \\k \end{pmatrix}

考虑 \sum_{k=0}^nk^i\times x^k\times \begin{pmatrix}n \\k \end{pmatrix} 的组合意义。

有 n 个不同的盒子，选出 k 个，每个盒子可以染成 x 种颜色，再将 i 个小球随机放入，有的盒子可以为空。

和上题一样，我们考虑选出箱子后，哪些箱子一定有球，哪些箱子没有球。

先选出 j 个箱子，方案数为 \begin{pmatrix}n \\j \end{pmatrix} 。

再将这 j 个箱子染色，方案数为 x^j。

将小球放入这些箱子，先考虑无序的情况，方案数为 \begin{Bmatrix} i \\j \end{Bmatrix} 。

将箱子定向为有序，方案数为 j! 。

剩下的箱子要不不选，选了即可染为 x 种颜色之一，单个箱子的情况数为 x+1 ，剩下所有箱子的情况数为 (x+1)^{n-j}

所以我们有：

ans=\sum_{i=0}^ma_i \sum_{j=0}^i\begin{pmatrix}n \\j \end{pmatrix}\times x^j\times \begin{Bmatrix} i \\j \end{Bmatrix}\times j!\times (x+1)^{n-j}

也可以拆掉组合数继续化简。