组合数学和组合计数（二）

组合计数模型

分组模型
有一堆元素，要分成 $k$ 组，其中第 $i$ 组有 $a_i$ 个元素，求一共有几种分法？
问题还有一种问法是，有 $k$ 个元素，第 $i$ 个元素有 $a_i$ 个，求全排列的个数

结论，对于 $k$ 组这样的数，排列方法一共有

$\frac{(a_1+a_2+\cdots a_k)!}{(a_1)! \cdot (a_2)! \cdots (a_k)!}$

证明如下，假设排列方案数为 $x$ ，每一种方案数，如果对相同的元素进行编号，比如 $(a, a, a) \to (a_1, a_2, a_3)$
这种排列方案数可以对应为 $(a_1 + a_2 + \cdots a_n)$ 的全排列，个数为 $(a_1 + a_2 + \cdots a_n)!$

另外，对于每一种方案数，又有多少种可能的情况呢？每一组内部都可以全排列，所以每一种方案数
可以构造出 $(a_1)!\cdot (a_2)! \cdot \cdots \cdot (a_{n})!$ 种排列

所以有 $x \cdot (a_1)!\cdot (a_2)! \cdots (a_n)! = (a_1 + a_2 + \cdots a_n)!$ ，求解 $x$ 即得以上结论

隔板法

$n$ 个球放入 $k$ 个盒子，不允许有空盒子，求方法数
实际上等于在 $n-1$ 个空档处插入 $k-1$ 个隔板，方案数为 $\displaystyle\binom{n-1}{k-1}$
$n$ 个球放入 $k$ 个盒子，允许有空盒子，求方法数
实际上，可以在 $k$ 个盒子中预放入 $1$ 个球，总共有 $n+k$ 个球
转为上一类问题，方案数为 $\displaystyle\binom{n+k-1}{k-1}$

可重复选择的组合
问题描述如下，有 $n$ 个元素，每个元素可以选多次，从中选出 $k$ 个，有多少种方法？
假设第 $i$ 个元素有 $x_i$ 个， $x_i \geqslant 0$ ，等价于
$x_1 + x_2 + \cdots x_n = k$ 有多少组 $\geqslant 0$ 的整数解？

令 $y_i = x_i + 1$ ，则问题变为 $y_1 + y_2 + \cdots y_n = k+n$ 有多少个 $> 0$ 的整数解？
将等式右边看成 $k+n$ 个 $1$ ，用隔板法，插入 $n-1$ 个隔板，不允许有“空盒子”

问题答案为 $\displaystyle\binom{k+n-1}{n-1} = \binom{n+k-1}{k}$

单色三角形
给定没有三点共线的 $n$ 个点，对于每个点 $i$ ，给出它与其他点 $j$ 之间的边的颜色 $g(i, j)$
问能组成的三边同色三角形的个数

直接考虑比较复杂，只需要求出非单色三角形即可，对于每个点 $i$ ，可以统计出这个点
连接了 $a_i$ 条红边，从而求出连接的蓝边个数为 $n-1-a_i$
于是以这个点为顶点构成的单色三角形个数为 $a_i \cdot (n-1-a_i)$

另外每一个单色三角形，考虑顶点 $u \to v$ 这条边的时候，之后计算到 $v \to u$ 也会再被考虑一次
所以最后答案要 $\times \displaystyle\frac{1}{2}$

$\displaystyle \binom{n}{3} - \frac{1}{2}\cdot \left(\sum_{i = 1}^{n}a_i(n-1-a_i)\right)$

计数方法

象棋中的皇后

Bits
题目大意：用 $A(x)$ 表示 $x$ 的二进制表示中，连续两个 $1$ 出现的次数，比如 $A(15) = A(1111) = 3$
求 $A(x)$ 的前缀和

首先可以想到这么一个朴素算法，将 $0 \to x$ 的数选出来，构造 $(x+1) \times 64$ 的矩阵，如下所示

$\bm{A} = \begin{pmatrix} 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & \cdots & 1 & 1 \\ \ & \vdots & \vdots & \vdots \\ 1 & 1 & \cdots & 1 & 1 \end{pmatrix}$

定义 $mask = (11)_2$ ，对于 $\forall u \in [0, x]$ ， $\text{calc}(u)$ 计算出每一个 $u$ 有多少个 $(11)_2$
具体来说，从低位到高位遍历， $i \in [0, 63]$ ，如果 $u \ \& \ mask = 1$ ，那么 $ans++, mask \ll 1$

那么在 $n = 2^{63}-2$ 这么大的数，肯定会超时，需要换一种思路，计算每个位出现的 $(11)_2$ 的贡献
将 $[0\to n]$ 的数表示成 $\text{left} + (11)_2 + \text{right}$ ，其中 $+$ 为连接符

首先令 $i$ 从低位到高位遍历，考虑 $(i+1, i)$ 这两位，什么时候可以填上 $(11)_2$
$\text{left} = (n \gg (i+2))$ ，那么前缀为 $[0, \text{left}-1]$ 的数一定 $\in [0\to n]$ ，都比 $n$ 小
所以这些前缀后面都可以接上 $(11)_2$ ，令 $(i-1, i) = (11)_2$ ，前缀可选的值有 $\text{left}$ 种
后缀可以自由选择 $[\underbrace{00\cdots 0}_{i \text{ 位}} \to \underbrace{11\cdots 1}_{i \text{ 位}}]$ ，一共是 $(1\ll i)$ 种

所以 $(i+1, i) = (11)_2$ 对答案的贡献为 $\text{left} \cdot (1\ll i)$

另外，如果 $n$ 的 $(i+1, i)$ 位为 $(11)_2$ ，上述答案中，我们只统计了前缀 $[0, \text{left}-1]$ 的部分
前缀恰好为 $\text{left}$ 的时候还没有统计，此时前缀与 $(i+1, i) = (11)_2$ 构成可行解，取 $n$ 的低位 $[i-1\cdots 0]$
$tail = n \ \& ((1\ll i)-1)$ ，那么需要在上述答案中加上 $(tail + 1)$

这样我们就求出来每一位出现 $(11)_2$ 时候，对答案的贡献，将它们加起来，就解决了这个问题

Pinary

令 $f(i)$ 表示位数为 $i$ 的 $01$ 串的个数，不难发现 $f(i)$ 即为第 $i$ 个斐波那契数
记 $S(i)$ 为 $f(i)$ 的前缀和，那么第 $k$ 个串有多少位呢？

实际上只要递推求 $S(i)$ ，当发现 $S(i) \geqslant k$ 的时候，马上退出循环，此时的 $i$ 即为第 $k$ 个串的位数
如果 $S(i) = k$ ，那么输出 $\underbrace{1010 \cdots 10}_{i \text{ 位}}$ 就是答案

难点在于 $S(i) \neq k$ 的时候怎么办

递归结构
令 $\Delta = k - S(i-1)$ ，记 $1 \underbrace{00\cdots 0}_{(i-1) \text{ 位}}$ 为下标 $0$
需要从这个下标 $0$ 的位置开始，往前找到下标为 $\Delta - 1$ 位置处的数，令 $\Delta = \Delta - 1$

如果 $\Delta = 0$ ，直接在 $1$ 后面填入 $\underbrace{00\cdots 0}_{i-1 \text{ 位}}$ ，并且结束递归返回

否则的话还需要再填入 $\Delta$ 个数，那么刚好填入的第 $\Delta$ 个数，有几位呢？
只要对前缀和数组二分查找，找到第一个满足 $S(p) \geqslant \Delta$ 的 $p$ ，那么填入的这个数恰为 $p$ 位
这个时候，在 $1$ 后面添加 $i-1-p$ 个 $0$ ，再添加一个 $1$

然后考虑后缀的 $p$ 位，这 $p$ 位是什么情况呢？它是形如 $1 \underbrace{00 \cdots 0}_{p-1 \text{ 位}}$
令 $\Delta' = \Delta - S(p-1)$ ， $\Delta' = \Delta'-1$
此时递归结构为 $(p-1, \Delta')$ ，即在 $1 \underbrace{00\cdots 0}_{p-1 \text{ 个}}$ 开始，找到下标为 $\Delta'$ 位置的数

$(i-1, \Delta) \to (p-1, \Delta')$
当 $\Delta \leqslant 0$ 的时候返回

错位排列

取集合 $\bm{X} = \{1, 2, \cdots, n\}$ ，它的一个错位排列是 $\{i_1, i_2, \cdots, i_n\}$
其中没有一个整数在它的自然位上，即 $i_1 \neq 1, i_2 \neq 2, \cdots i_n \neq n$

结论 1，对于 $n \geqslant 1$ ，我们有

$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^{n}\frac{1}{n!}\right)$

实际上，这个问题只需要证明

$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^{n} \binom{n}{n}0!$

记性质 $P_i$ 为 $i$ 在其自然位上，于是根据容斥原理， $\sum |A_i|$ 为任意 $1$ 个元素在其自然位上的方案数，为 $\displaystyle\binom{n}{1}(n-1)!$
$\sum |A_i \cap A_j|$ 为任意两个元素在其自然位上的方案数，值为 $\displaystyle\binom{n}{2}(n-2)!$ ，以此类推，即可证明

结论 2 $n$ 个元素的错位排列数目满足递推关系

$D_n = (n-1)(D_{n-1} + D_{n-2})\quad (n = 3, 4, 5, \cdots)$

其中 $D_1 = 0, D_2 = 1$ ，特别地， $D_0 = 1$

证明如下
令 $n \geqslant 3$ ， $\{1, 2, \cdots, n\}$ 的 $D_n$ 个错位排列， $1$ 可以与任意的 $n-1$ 个数交换位置
然后除了第一个位置外，剩下的位置错位排列，不妨记除了第一个位置外，错位排列的个数为 $d_n$
那么有 $D_n = (n-1) \cdot d_n$

考虑 $d_n$ ，从第二个位置开始看，不妨设第一个位置我们放了 $2$ ，那么根据排列 $\{i_2, i_3, \cdots, i_n\}$
依据第二个位置是否为 $1$ 分为 $2$ 类， $i_2 = 1$ 记为 $d_n'$ ， $i_2 \neq 1$ 记为 $d_n''$ ， $d_n = d_n' + d_n''$

其中， $d_n' = (2, 1, \bm{3}, \bm{4}, \bm{\cdots,} \bm{n})$ ，加粗部分需要错位排列
此时加粗部分的方案数等于 $3$ 不在第 $1$ 个位置， $4$ 不在第 $2$ 个位置，以此类推，方案数恰好为 $D_{n-2}$
另外， $d_n'' = (2, \bm{1,} \bm{3,} \bm{4,}) \bm{\cdots, } \bm{n})$ ，此时 $1$ 不在 $i_1$
$3$ 不在 $i_2$ ，以此类推，排列方案数为 $D_{n-1}$

证明完成

推论将 $D_n$ 递推稍加处理，可以得到

$D_n - nD_{n-1} = (-1) \cdot (D_{n-1} - (n-1)D_{n-2})$

最后可以得到

$D_n = nD_{n-1} + (-1)^{n-2}$

等价于

$D_n = nD_{n-1} + (-1)^{n}$

Arrange the Numbers

首先前 $[1, m]$ 个数中有 $k$ 个在自然位上，剩下 $m-k$ 个数错位排列
接着枚举剩下的 $n-m$ 个数，有 $i$ 个在自然位上，选出这 $n$ 个数，剩下的构成错位排列
那么这部分有 $(n-m-i)$ 个数错位排列，全序列有 $(n-m-i + m-k = n-k-i)$ 个错位排列