组合意义笔记

· · 个人记录

组合数学好难。

因为是组合意义，所以公式推导不多，文字多。

记一些经典模型，组合意义。

感觉组合意义，就是首先你有一些推出来的式子，然后你觉得这太抽象了，做题的时候，大多数情况不是直接给式子，而是给一个应用问题来解决。

所以你需要为你的式子，找一个实际意义上去，这样不仅好理解，还便于从题目联想起来。

所以你需要见多识广，只要这个式子，你记得它的组合意义，那碰到有运用的题，都能很快做出来，所以要做一个组合意义的积累

先来一些众所周知的情况，作为基础。

然后推导一些式子出来，再为推导出来的式子找找组合意义。

最后放一些例题，做一做。

众所周知的

先来点 十二重计数法。

大家应该都很会小球和盒子吧。

将 n 个小球放到 m 个盒子里的方案数。

下文小球不同，可以理解为把小球从 1 \sim n 编号，盒子同理，相同就是编号都为 1 。两种方案相同，可以理解为，把盒子按编号从小到大排序，盒子中的小球也从小到大排序，然后若能一一对应上，则说明相同。

球不同，盒子相同，每个盒子至多装一个球

因为你每个球往哪个盒子中放，都是一样的，而且每个盒子也最多放一个球，所以答案就是 [n\leq m] 。

球相同，盒子相同，每个盒子至多装一个球

仔细思考，发现比上一问还弱的条件，但是答案是和上一问一样的 [n\leq m] .

球相同，盒子不相同，每个盒子至多装一个球

就是从 m 个盒子里面选出 n 个盒子放球，每个球都是一样的，所以答案是 m\choose n 。

球相同，盒子不相同，每个盒子至少装一个球

插板法，考虑拿 m-1 个隔板插到 n 个球形成的 n-1 个空位里面，这样求恰好被分成了 n 组，盒子是有标号的，球没有，所以第 i 组对应第 i 个盒子，方案数就是 {n-1}\choose {m-1} 。

球相同，盒子不相同

还是插板法，但是可以有空盒子，如果我们现在，每个盒子里面都已经有一个球了，那答案就和上一个问题一样了，所以我们先借 m 个球过来，保证每个盒子里面都有一个球，最后再拿走，答案就是 {n+m-1}\choose {m-1} 。

还有一个意义，就是在一个 (n+1)\times m 的网格图中，从左上角走到右下角的方案数，放球就是向下走，去下一个盒子就是向右走，所以就是从 n+m-1 步中选出 n 步向下走，那答案就是 {n+m-1}\choose {n} 。

球不同，盒子也不同

每个球都有 m 种放法，所以方案数是 m^n 。

球不同，盒子也不同，每个盒子至多装一个球

对于第 i+1 个球，可以从剩下的 (m-i) 个盒子中选一个，所以答案就是 m^{\underline n} 。

球不同，盒子也不同，每个盒子至少装一个球

我们发现这个限制不好处理的，没有这个限制则是好处理的，所以我们想把这个限制容斥掉。

我们先钦定至少有 i 个盒子是空的，因为盒子不同，所以你要从 m 个盒子里面选 i 个出来，然后剩下的小球每个都有 m-i 种选择，且每个小球都是不同的，所以这一步的方案数是 {m\choose i }(m-i)^n 。

然后你考虑每种情况会算重多少次，容斥之后，答案就是 \sum_{i=0}^m (-1)^i{m\choose i }(m-i)^n 。

球不同，盒子相同，每个盒子至少装一个球

这一次除了盒子全都是相同的之外，与上一问是一致的，所以你考虑，我们把这一问的任意一种情况拿出来，上一问都有 m! 中情况可以对应到，所以这一问的答案就是上一问的答案除以 m! 。

整理一下就是。

\sum_{i=0}^m \frac{(-1)^i(m-i)^n}{i!(m-i)!}

然后其实这个就是第二类斯特林数的通项了，我们一般记为 S_{n,m} 。

再给一个递推关系： S_{n,m}=S_{n-1,m-1}+m\times S_{n-1,m} 。

用组合意义理解一下，你想像之前是没有这个球的，你拿一个新的球进来，都有多少种方法，也就两种情况，放到一个新盒子里，和放到一个之前就有的盒子里。

如果是放到一个新盒子里，那方案数就是没有这个球，也少一个盒子的情况数，就是 S_{n-1,m-1} 。

如果是放到之前就有的盒子里，那方案数就是，在之前就有的 m 个盒子中选一个，然后放进去，也就是 m\times S_{n-1,m} 。

球不同，盒子相同

枚举有多少个盒子装了球的，然后就变成上一种情况了，那么答案就是 \sum_{i=1}^m S_{n,i} ，其实这就是 第二类斯特林数·行 。

球相同，盒子也相同

这是很经典的划分数问题，我们记 P_{n,m} 为这个问题的答案，那么有 P_{n,m} = P_{n-m,m}+P_{n,m-1} 。

这个的意思是，我们要将 n 个球，放入 m 个盒子的方案数，可以由两种方式得到，分别是在 “将 n-m 个球，放入 m 个盒子” 的情况中，往每个盒子里多方一个球，和“将 n 个球，放入 m-1 个盒子”的情况中，多放一个空盒子，你考虑把盒子按放入的顺序排个序，那么盒子中的球数就是单调不增的，所以每种构造方案都会不重不漏的被考虑一次。

球相同，盒子也相同，每个盒子至少装一个球

往每个盒子里面先放入一个球后，变成上一种情况，所以该问题答案为 P_{n-m,m} 。

上面这些就是十二重计数法了，下面是一些其他的小球与盒子。

球相同，盒子不相同，每个盒子至多装一个球，且编号相邻的盒子中至多一个有球

你考虑，每次选了一个盒子后，就把这个盒子的下一个盒子扔掉，这样就不会选到相邻的盒子了，答案就是和上一问一样的了。

但是你会发现，最后一个盒子没法仍下一个，所以我们先借来一个盒子，放到最后一个盒子的后面，现在我们有 m+1 个盒子了，然后我们一共会扔掉 n 个盒子，所以我们就在 m+1-n 个盒子，里面选出 n 个即可，方案数为 {m+1-n} \choose n 。

球相同，盒子不相同，第 i 个盒子至少装 k_i 个球

可以和上一问题一样解决，往第 i 个盒子里面先装 k_i 个球，但是我们这次借的不用还了，所以直接从 n 个里面拿就行，球没有区别，拿谁都一样的，从 n 个球中，拿走 \sum k_i 之后，问题就变成上一个了，所以答案就是 {n-\sum k_i+m -1}\choose {m-1}

球相同，盒子不相同，每个盒子至多装 k 个球

没有限制是好做的，上文提到过，答案是 {n+m-1}\choose {m-1} 。

然后我们考虑把限制容斥掉，我们钦定现在至少有 i 个盒子装的球数大于等于 k ，首先我们要从 m 个盒子里面选 i 个出来，方案是 {{m}\choose{i}} 。然后问题变成简单的，现在只剩下 n-i(k+1) 个球，方案是 {{n-i(k+1)+m-1}\choose{m-1}} 。

然后你容斥一下，就得到了答案。

\sum_{i=0}^{k}(-1)^i {{m}\choose{i}} {{n-i(k+1)+m-1}\choose{m-1}}

环排列：将 n 个不同的球摆成一个环的方案数。

大家都知道，如果是排成一排的方案数，是 n! 。

每个环的情况，都可以有 n 个地方可以断开，然后变成一排，所以排的方案数除以 n 就得到了环的方案数：(n-1)! 。

卡特兰数

首先介绍一个简单的推法。

根据卡特兰数的定义，有一种组合意义，想象一个平面直角坐标系，初始时在 (0,0) ，要走到 (2n,0) ，每次可以使当前坐标的 x+1,y+1 或 x+1,y-1 ，不能碰到直线 y=-1，最后走到 (2n,0) 的方案数。

我们考虑先不考虑那个限制的方案数，显然就是 {2n}\choose{n} ，然后考虑减掉违反限制的方案数。

我们在第一次碰到直线 y=-1 的之后所有的走法，将其按直线 y=-1 对折，那么最后的终点也会对折，所以终点就变成了 (2n,-2) 。所以违法限制的方案数也就等于从起点走到 (2n,-2) 的方案数，为 {2n}\choose{n-1}。

所以总方案数就是

{{2n}\choose{n}} -{{2n}\choose{n-1}} =\frac{(2n)!}{(n+1)(n!)^2}

另一种网上找到的组合意义，感觉比上面的晦涩一点，一起记录一下。

有 n 个黑球和 n 个白球，排成一排，在任意一个位置之前，黑球的数量都大于白球的数量的方案数。

为了方便，我们先讲所有黑球从 1\sim n 编号，白球从 n+1 \sim 2n 编号，最后我们将这种情况的答案除以 (n!)^2 即可。

我们考虑再加入一个编号为 2n+1 的白球，然后把这 2n+1 个球排成一个环。由环排列方案数知，这一步方案数是 (2n)! 。

现在我们得到了，一个有 n 个黑球，n+1 个白球的环，我们想扔掉一个白球，之后从这里断开，使得任意前缀黑球数大于等于白球数，对于每个环，这个位置是唯一的。为什么呢？

反过来。

你考虑对于一个非法的排列，你可以将他进行一个循环移位，对于每个排列，我们取最小的移动距离，使其变得合法，这个是显然的，我们称能通过循环移位互相得到的排列为 循环同构 的。

那么每个 循环同构 的类里面都会有 2n+1 个排列，而这 2n+1 个排列，对应的都是同一个环，其中有一个是合法的排列，其他的排列都是通过循环移位得到这个合法排列的，所以一个环对应的所有排列中，断开的位置，也就是对应着不需要循环移位的那个排列，是唯一的。

然后我们又想到，不是每个白球都能被扔掉的，我们要保证剩下的白球编号为 n+1 \sim 2n ，所以扔掉的只能是编号为 2n+1 的，在 n+1 个白球中恰好是这一个，概率是 \frac{1}{n+1} 。

所以我们的答案，就是环的方案数乘以扔掉的球编号恰好是 2n+1 的概率再除以我们赋予球编号时多的系数。

Cat_n = \frac{(2n)!}{(n+1)(n!)^2}

性质与推论

下面这些，都是相同的球，不同的盒子，每个盒子最多放一个球的限制。

{ n\choose m } = {n \choose n-m} \quad\quad (1)

显然。但是很多时候非常需要这个，不然很不直观。

{ n\choose m } = {n-1 \choose m} +{n-1 \choose m-1} \quad\quad (2)

把 m 个相同的球放到 n 个不同的盒子里，每个盒子里面最多放一个球的方案数。那么你第 n 个盒子，要么放球，要么不放球，如果放球，那就是 {n-1 \choose m-1} ，因为我们钦定了第 n 个盒子一定放。如果不放球，就是 {n-1 \choose m} 。

\sum_{i=0}^n{ n\choose i } = 2^n \quad\quad (3)

依次将 i 个球放入 n 个盒子，的总情况数，其实就是，对于每个盒子，要么放球，要么不让球的方案数，可以一一对应而得。

\sum_{i=0}^k{ n\choose i }{m\choose k-i} = {n+m \choose k} \quad\quad (4)

一共有 n+m 个盒子，要放 k 个球，如果前 n 个盒子放了 i 个，那么后 m 个盒子就要放 k-i 个。这个看起来很简单的东西就是范德蒙德卷积了，合并组合式的时候常用。

{n\choose m}{m\choose k}={n\choose k}{n-k \choose m-k}\quad\quad (5)

通过组合数的定义证明是简单的，但是我们还是想寻找一个组合意义。

式子左边的意思是，你从 n 个盒子中选出 m 个，往里面放 1 个球，然后再从选出的 m 个里面再选 k 个，往里面再放 1 个球。所以最后，就是 n 个盒子里面，有 k 个有 2 个球，有 m-k 个有 1 个球，所以就是和直接 n 个里面选 k 个放 2 个球，然后剩下的 n-k 个里面选 m-k 个放 1 个球是等价的。

应用

例一：制服穿

求有多少个长度为 n 的 01 串，恰好包含 m 个 1 ，且最长的连续 1 长度恰好为 k 。

最长连续段恰好为 k 时难处理的，我们考虑对答案做一个前缀和，计算 最长连续段不超过 k的方案数。考虑 0 的个数是固定的，发现这些 0 把 1 分成了（ 0 的个数 +1 ）段，当然可能有一些段是空的。

那现在我们要计数的对于一个给定的 m, k, n ，选 m 个 0\sim k 之间的数使得和恰好为 n ,这里的 n, m, k 和题面中的含义可能不同。

所以问题变成了，我们所熟悉的，上文提到过的，球相同，盒子不相同，每个盒子至多装 k 个球 的方案数。

例二：你的生命已如风中残烛

有 m=\sum_{i=1}^n w_i 个数，前 n 个中第 i 个为 w_i -1 ，剩下的都是 -1。

求在共 m! 中排列中，有多少种排列满足任意前缀和非负。

这个形式让我们想起了卡特兰数，那我们求用类似卡特兰数的方法做做。

在序列最后放一个 -1，然后组成一个环。

类似地，删掉一个 -1 构成合法序列的法案是唯一的。

而我们只能删我们加进去的那个 -1 。

然后你发现完全一样。

所以答案就是 \frac{m!}{m-n+1} 。