组合计数

加法原理

若完成一件事的方法有 $n$ 类，其中第 $i$ 类方法包括 $a_i$ 种不同的方法，且这些方法互不重合，则完成这件事共有 $a_1+a_2+…+a_n$ 种不同的方法

乘法原理

若完成一件事需要 $n$ 个步骤，其中第 $i$ 个步骤有 $a_i$ 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有 $a_1\*a_2\*…\*a_n$ 种不同的方法

排列数

从 $n$ 个不同的元素中依次取出 $m$ 个元素排成一列，产生的不同排列的数量为：

$$P_n^m = \frac{n!}{(n-m)!} = n \* (n-1) \* … \* (n - m + 1)$$

组合数

从 $n$ 个不同的元素中取出 $m$ 个元素组成一个集合（不考虑顺序），产生的不同集合的数量为：

$$C_n^m = \frac{n!}{m!(n-m)!} = \frac{n\*(n-1)\*…(n-m+1)}{m\*(m-1)\*…\*2\*1}$$

性质

1. $C_n^m = C_n^{n-m}$
2. $C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$
3. $C_n^0 + C_n^1 + C_n^2 + … + C_n^n = 2^n$

证明：

由组合数的定义，对于从 $n$ 个不同的元素中取出 $m$ 个组成的每个集合，剩余未取出的元素也构成一个集合，两个集合一一对应，所以性质 $1$ 成立。

从 $n$ 个不同元素中取出 $m$ 个组成一个集合有两类方法：取 $n$ 号元素，不取 $n$ 号元素。若取 $n$ 号元素，则应在剩余 $n-1$ 个元素中选出 $m-1$ 个，有 $C_{n-1}^{m-1}$ 种取法。若不取 $n$ 号元素，则应在剩余 $n-1$ 个元素中选出 $m$ 个， 有 $C_{n-1}^m$ 种取法。根据加法原理，性质 $2$ 成立。

从 $n$ 个不同元素中取出若干个元素组成一个集合，有 $n+1$ 类方法，分别是取出 $0,1,2,…,n$ 个。根据加法原理，共有 $C_n^0+C_n^1+C_n^2+…+C_n^n$ 种方法。从另一个方面去考虑，$n$ 个元素每个元素可以取或不取，总方法数为 $2^n$，二者相等，故性质 $3$ 成立。

证毕。

组合数的求法

根据性质 $2$，用递推法可求出 $0 \leq y < x \leq n$ 的所有组合数 $C_x^y$，复杂度为 $O(n^2)$

组合数的结果一般较大，若题目求出 $C_n^m$ 对一个数 $p$ 取模后的值，并且 $1 \sim n$ 都存在模数 $p$ 的逆元，则可以先计算分子 $n!~mod~p$，再计算分母 $m!(n-m)!~mod~p$ 的逆元，乘起来得到 $C_n^m~mod~p$，复杂度为 O(n)。

若计算阶乘的过程中，把 $0 \leq k \leq n$ 的每个 $k!~mod~p$ 及其逆元分别保存在两个数组 $jc$ 和 $jc_inv$ 中，则可以在 $O(nlogn)$ 的预处理后，以 $O(1)$ 的时间回答 $0 \leq y < x \leq n$ 的所有组合数 $C_x^y~mod~p=jc[x]\*jc_inv[y]\*jc_inv[x-y]~mod~p$。

若题目要求我们对 $C_n^m$ 进行高精度运算，为避免除法，可用 “阶乘分解” 的做法，把分子、分母快速分解质因数，在数组中保存各项质因子的指数，然后把分子、分母各个质因子的指数对应相减（把分母消去），最后把剩余质因子乘起来，时间复杂度为 $O(nlogn)$

Lucas 定理

若 $p$ 是质数，则对于任意整数 $1 \leq m < n$，有：

$$C_n^m = C_{n~mod~p}^{m~mod~p} \* C_{n/p}^{m/p}~(mod~p)$$

也就是把 $n$ 和 $m$ 表示成 $p$ 进制数，对 $p$ 进制下的每一位分别计算组合数，最近再乘起来。证明需要用到生成函数的知识，也可以看 y 总的算法基础课，有机会再补叭。

二项式定理

$$(a+b)^n = \sum_{k=0}^n C_n^k a^k b^{n-k}$$

证明：

数学归纳法。当 $n=1$ 时，$(a+b)^1=C_n^0a^0b^1+C_n^1a^1b^0 = a+b$ 成立。

假设当 $n=m$ 时命题成立，当 $n=m+1$ 时：

$$(a+b)^{m+1} = (a+b)(a+b^m) = (a+b) \sum_{k=0}^m C_m^k a^kb^{m-k}$$

$$= \sum_{k=0}^{m} C_m^k a^{k+1} b^{m-k} + \sum_{k=0}^m C_m^k a^{k+1} b^{m-k+1} = \sum_{k=1}^{m+1} C_m^{k-1} a^k b^{m-k+1} + \sum_{k=0}^m C_m^k a^k b^{m-k+1}$$

$$= \sum_{k=0}^{m+1} (C_m^{k-1}+C_m^k) a^k b^{m-k+1} = \sum_{k=0}^{m+1} C_{m+1}^k a^k b^{m+1-k}$$

证毕。

容斥原理

设 $S_1,S_2,…,S_n$ 为有限集合，$\vert S \vert$ 表示集合 $S$ 的大小，则：

$$\vert \bigcup_{i=1}^n S_i \vert = \sum_{i=1}^n \vert S_i \vert - \sum_{1\leq i<j \leq n} \vert S_i \cap \S_j \vert + \sum_{1 \leq i<j<k \leq n} \vert S_i \cap S_j \cap S_k \vert + … + (-1)^{n+1} \vert S_1 \cap … \cap S_n \vert$$

可以查找文氏图来帮助理解公式。

多重集的排列数

多重集是指包含重复元素的广义集合。设 $S = \lbrace n_1 \cdot a_1, n_2 \cdot a_2, …, n_k \cdot a_k \rbrace$ 是由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$ $…$ $n_k$ 个 $a_k$ 组成的多重集，记 $n = n_1+…+n_k$。$S$ 的全排列个数为：

$$\frac{n!}{n_1!n_2!…n_k!}$$

多重集的组合数

设 $S = \lbrace n_1 \cdot a_1, n_2 \cdot a_2, …, n_k \cdot a_k$ 是由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$ $…$ $n_k$ 个 $a_k$ 组成的多重集，设整数 $r \leq n_i~(\forall i \in [1, k])$。从 $S$ 中取出 $r$ 个元素组成一个多重集（不考虑元素的顺序），产生的不同多重集的数量为：

$$C_{k+r-1}^{k-1}$$

证明：

原问题等价于统计下列集合的数量：$\lbrace x_1 \cdot a_1, x_2 \cdot a_2, …, x_k \cdot a_k$，其中 $\sum_{i=1}^k x_i = r$ 并且 $x_i \leq n_i$。因为 $r \leq n_i$，必定有 $x_i \leq n_i$，所以只需考虑 $\sum_{i=1}^k x_i = r$ 这一个条件。

故原问题等价于 $r$ 个 $0$，$k-1$ 个 $1$ 构成的全排列数———$k-1$ 个 $1$ 把 $r$ 个 $0$ 分成 $k$ 组，每组的 $0$ 的数量对应 $x_i$，而多重集 $\lbrace r \cdot 0, (k-1) \cdot 1 \rbrace$ 的全排列数为：

$$\frac{(r+k-1)!}{r!(k-1)!} = C_{k+r-1}^r = C_{k+r-1}^{k-1}$$

证毕。

对于更为一般的 $r$ 的情况，则需进一步分析。

设 $S= \lbrace n_1 \cdot a_1, n2\cdot a_2,…,n_k\cdot a_k \rbrace$ 是由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，$…$，$n_k$ 个 $a_k$ 组成的多重集。设 $n=\sum_{i=1}^k n_i$，对于任意整数 $r \leq n$，从 $S$ 中取出 $r$ 个元素组成一个多重集（不考虑顺序），产生的不同多重集的数量为：

$$C_{k+r-1}^{k-1} - \sum_{i=1}^k C_{k+r-n_i-2}^{k-1} + \sum_{1\leq i<j \leq k} C_{k+r-n_i-n_j-3}^{k-1} - … + (-1)^k C_{k+r-\sum_{i=1}^k n_i-(k+1)}^{k-1}$$

证明：

不考虑 $n_i$ 的限制，从 $S$ 中任选 $r$ 个元素，相当于从多重集 $\lbrace \infty \cdot a_1,\infty \cdot a_2,…,\infty \cdot a_k \rbrace$ 中取出 $r$ 个元素。根据上面的证明，可知方法数为 $C_{k+r-1}^{k-1}$

设 $S_i~(1\leq i \leq k)$ 表示至少包含 $n_i+1$ 个 $a_i$ 的多重集，我们先从 $S$ 中取出 $n_i+1$ 个 $a_i$，然后再任选 $r-n_i-1$ 个元素，即可构成 $S_i$。与上面同理，可以构成的不同 $S_i$ 的数量为 $C_{k+r-n_i-2}^{k-1}$

进一步分析，先从 $S$ 中取出 $n_i+1$ 个 $a_i$ 和 $n_j+1$ 个 $a_j$，然后再任选 $r-n_i-n_j-2$ 个元素，即可构成 $S_i \cap S_j$，方法数为：

$$C_{k+r-n_i-n_j-3}^{k-1}$$

根据容斥原理，至少有一种 $a_i$ 选取的数量超过 $n_i$ 限制的多重集共有：

$$\vert \bigcup_{i=1}^k S_i \vert = \sum_{i=1}^k C_{k+r-n_i-2}^{k-1} - \sum_{1 \leq i<j \leq k} C_{k+r-n_i-n_j-3}^{k-1}+…+ (-1)^{k-1} C_{k+r-\sum_{i=1}^k n_i-(k+1)}^{k+1}$$

故满足所有限制的合法多重集共有 $C_{k+r-1}^{k-1} - \vert \cup_{i=1}^k S_i \vert$ 个，两式相减即得原命题。

证毕。

Mobius 函数

设正整数 $N$ 按照算术基本定理分解质因数为 $N=p_1^{c_1}p_2^{c_2}…p_m{c_m}$，定义函数

$$\mu(N) = \begin{cases} 0 \quad \quad \exists i \in [1,m],c_i>1 \newline 1 \quad \quad m \equiv 0~(mod~2),\forall i \in [1, m], c_i=1 \newline -1 \quad m \equiv 1~(mod~2),\forall i \in [1, m], c_i=1 \end{cases}$$

称 $\mu(N)$ 为 Mobius 函数（莫比乌斯函数）

直白点说，当 $N$ 包含相等的质因子时，$\mu(N)=0$。当 $N$ 的所有质因子各不相等时，若 $N$ 有偶数个质因子，$\mu(N) = 1$，若 $N$ 有奇数个质因子，$\mu(N) = -1$

若只求一项 Mobius 函数，则分解质因数就能计算。若求 $1 \sim N$ 的每一项 Mobius 函数，可以利用线性筛法计算，实现代码如下：

void get_primes(int n) //线性筛法求莫比乌斯函数
{
    mobius[1] = 1; //1 有 0 个质因子，是偶数个质因子
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            mobius[i] = -1; //质数的质因子只有一个，是奇数
        }

        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                //到这说明 primes[j] * i 中至少有 2 个 primes[j]，因此质因子数量 > 1
                mobius[primes[j] * i] = 0;
                break;
            }
            //到这说明 i 中没有质因子 primes[j]，因此 primes[j] * i 的质因子个数就是 i 的质因子个数 + 1
            mobius[primes[j] * i] = mobius[i] * -1;
        }
    }
}

Mobius 函数的作用

假设要求与 $N$ 互质的个数。

可以用容斥原理来求，假设 $S_p$ 为 $1 \sim N$ 中 $p$ 的个数

那么与 $N$ 互质的个数：$N - S_2 - S_3 … + S_{2, 3} + S_{2, 5} + … - S_{2, 3, 5} -…$

可以发现 $Mobius(2) = -1, Mobius(3) = -1, Mobius(6) = 1, Mobius(10) = 1$，容斥原理中每一项 $S_i$ 的系数就是 $Mobius(i)$

Catalan 数列

给定 $n$ 个 $0$ 和 $n$ 个 $1$，它们按照某种顺序拍成长度为 $2n$ 的序列，满足任意前缀中 $0$ 的个数都不少于 $1$ 的个数的序列数量为：

$$Cat_n = \frac{C_{2n}^n}{n+1}$$

证明：

令 $n$ 个 $0$ 和 $n$ 个 $1$ 随意排成一个长度为 $2n$ 的序列 $S$，若 $S$ 不满足任意前缀中 $0$ 的个数都不少于 $1$ 的个数，则存在一个最小的位置 $2p+1 \in [1,2n]$，使得 $S[1 \sim 2p+1]$ 中有 $p$ 个 $0$、$p+1$ 个 $1$。而把 $S[2p+2 \sim 2n]$ 中所有数字取反后，包含 $n-p-1$ 个 $0$ 和 $n-p$ 个 $1$。于是我们得到了由 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 排成的序列。

同理，令 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 随意排成一个长度为 $2n$ 的序列 $S’$，也必定存在一个最小的位置 $2p’+1$，使得 $S[1 \sim 2p’+1]$ 中有 $p’$ 个 $0$、$p’+1$ 个 $1$。把 $S’[2p’+2 \sim 2n]$ 中所有数字取反，就得到了由 $n$ 个 $0$ 和 $n$ 个 $1$ 排成的、存在一个前缀 $0$ 比 $1$ 多的序列。

因此，以下两种序列构成一个双射：

1. 由 $n$ 个 $0$ 和 $n$ 个 $1$ 排成的、存在一个前缀 $0$ 比 $1$ 多的序列。
2. 由 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 排成的序列。

根据组合数的定义，后者显然有 $C_{2n}^{n-1}$ 个。

综上所述，由 $n$ 个 $0$ 和 $n$ 个 $1$ 排成的，任意前缀中 $0$ 的个数都不少于 $1$ 的个数的序列数量为：

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

证毕。

推论

以下问题都与 Catalan 数有关。

1. $n$ 个左括号和 $n$ 个右括号组成的合法括号序列的数量为 $Cat_n$。
2. $1,2,…,n$ 经过一个栈，形成的合法出栈序列序列的数量为 $Cat_n$。
3. $n$ 个节点构成的不同二叉树的数量为 $Cat_n$。
4. 在平面直角坐标系上，每一步只能向上或向右走，从 $(0,0)$ 走到 $(n,n)$ 并且除两个端点外不接触直线 $y=x$ 的路线数量为 $2Cat_{n-1}$