组合数学

卢卡斯定理

$(\binom{n}{m}) mod p = (\binom{⌊ n / p ⌋}{⌊ m / p ⌋}) \cdot (\binom{n mod p}{m mod p}) mod p$

 LL Lucas(LL n, LL m, LL mod) {
  if (m == 0) return 1;
  return (C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod)) % mod;
}

拓展卢卡斯定理

 LL calc(LL n, LL x, LL mod) {
  if (!n) return 1;
  LL s = 1;
  for (LL i = 1; i <= mod; i++)
    if (i % x) s = s * i % mod;
  s = ksm(s, n / mod, mod);
  for (LL i = n / mod * mod + 1; i <= n; i++)
    if (i % x) s = i % mod * s % mod;
  return s * calc(n / x, x, mod) % mod;
}
 
LL multilucas(LL m, LL n, LL x, LL mod) {
  int cnt = 0;
  for (LL i = m; i; i /= x) cnt += i / x;
  for (LL i = n; i; i /= x) cnt -= i / x;
  for (LL i = m - n; i; i /= x) cnt -= i / x;
  return ksm(x, cnt, mod) % mod * calc(m, x, mod) % mod *
         ksm(calc(n, x, mod), mod - 2, mod) % mod *
         ksm(calc(m - n, x, mod), mod - 2, mod) % mod;
}
 
LL exlucas(LL m, LL n, LL mod) {
  int cnt = 0;
  LL p[20], a[20];
  for (LL i = 2; i * i <= mod; i++)
    if (mod % i == 0) {
      p[++cnt] = 1;
      while (mod % i == 0) p[cnt] = p[cnt] * i, mod /= i;
      a[cnt] = multilucas(m, n, i, p[cnt]);
    }
  if (mod > 1) p[++cnt] = mod, a[cnt] = multilucas(m, n, mod, mod);
  return CRT(cnt, a, p);
}

二项式定理

$(a + b)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) a^{n - i} b^{i}$

$\sum (\binom{n}{n_{1} n_{2} \dots n_{t}}) = t^{n}$

模型

多重集的组合数 1

设 $S = n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k},$ 表示由 $n_{1}$ 个 $a_{1}$ ， $n_{2}$ 个 $a_{2}$ ，…， $n_{k}$ 个 $a_{k}$ 组成的多重集。那么对于整数 $r (r < n_{i}, \forall i \in [1, k])$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数就是 多重集的组合数。这个问题等价于 $x_{1} + x_{2} + \dots + x_{k} = r$ 的非负整数解的数目，可以用插板法解决，答案为

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

多重集的组合数 2

考虑这个问题：设 $S = n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k},$ 表示由 $n_{1}$ 个 $a_{1}$ ， $n_{2}$ 个 $a_{2}$ ，…， $n_{k}$ 个 $a_{k}$ 组成的多重集。那么对于正整数 $r$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数。

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

$$ \forall i\in [1,k],\ x_i\le ni,\ \sum{i=1}^kx_i=r $$

$$ Ans=\sum{p=0}^k(-1)^p\sum{A}\binom{k+r-1-\sum{A} n{A_i}-p}{k-1} $$

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

不相邻的排列

$1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数都不相邻的组合有 $(\binom{n - k + 1}{k})$ 种。

错位排列

我们把错位排列问题具体化，考虑这样一个问题：

$n$ 封不同的信，编号分别是 $1, 2, 3, 4, 5$ ，现在要把这五封信放在编号 $1, 2, 3, 4, 5$ 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

错位排列的递推式为 $f (n) = (n - 1) (f (n - 1) + f (n - 2))$ 。

圆排列

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

$Q_{n}^{n} \times n = A_{n}^{n} ⟹ Q_{n} = \frac{A_{n}^{n}}{n} = (n - 1)!$

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

$Q_{n}^{r} = \frac{A_{n}^{r}}{r} = \frac{n!}{r \times (n - r)!}$

组合数性质 | 二项式推论

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

$\begin{matrix} (1) & (\binom{n}{m}) = (\binom{n}{n - m}) \end{matrix}$

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

$\begin{matrix} (2) & (\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1}) \end{matrix}$

由定义导出的递推式。

$\begin{matrix} (3) & (\binom{n}{m}) = (\binom{n - 1}{m}) + (\binom{n - 1}{m - 1}) \end{matrix}$

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

$\begin{matrix} (4) & (\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = \sum_{i = 0}^{n} (\binom{n}{i}) = 2^{n} \end{matrix}$

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

$\begin{matrix} (5) & \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) = [n = 0] \end{matrix}$

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

$\begin{matrix} (6) & \sum_{i = 0}^{m} (\binom{n}{i}) (\binom{m}{m - i}) = (\binom{m + n}{m}) (n \geq m) \end{matrix}$

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

$\begin{matrix} (7) & \sum_{i = 0}^{n} {(\binom{n}{i})}^{2} = (\binom{2 n}{n}) \end{matrix}$

这是 $(6)$ 的特殊情况，取 $n = m$ 即可。

$\begin{matrix} (8) & \sum_{i = 0}^{n} i (\binom{n}{i}) = n 2^{n - 1} \end{matrix}$

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

$\begin{matrix} (9) & \sum_{i = 0}^{n} i^{2} (\binom{n}{i}) = n (n + 1) 2^{n - 2} \end{matrix}$

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

$\begin{matrix} (10) & \sum_{l = 0}^{n} (\binom{l}{k}) = (\binom{n + 1}{k + 1}) \end{matrix}$

可以通过组合意义证明，在恒等式证明中较常用。

$\begin{matrix} (11) & (\binom{n}{r}) (\binom{r}{k}) = (\binom{n}{k}) (\binom{n - k}{r - k}) \end{matrix}$

通过定义可以证明。

$$ \sum{i=0}^n\binom{n-i}{i}=F{n+1}\tag{12} $$

其中 $F$ 是斐波那契数列。

$\begin{matrix} (13) & \sum_{l = 0}^{n} (\binom{l}{k}) = (\binom{n + 1}{k + 1}) \end{matrix}$

通过组合分析——考虑 $S={a_1, a2, \cdots, a{n+1}} $的$ k+1$ 子集数可以得证。

卡特兰数

$$ Hn = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N{+}}) $$

$$ Hn = \begin{cases} \sum{i=1}^{n} H{i-1} H{n-i} & n \geq 2, n \in \mathbf{N_{+}}\ 1 & n = 0, 1 \end{cases} $$

$$ Hn = \frac{H{n-1} (4n-2)}{n+1} $$

$H_{n} = (\binom{2 n}{n}) - (\binom{2 n}{n - 1})$

路径计数问题

非降路径是指只能向上或向右走的路径。

从 $(0, 0)$ 到 $(m, n)$ 的非降路径数等于 $m$ 个 $x$ 和 $n$ 个 $y$ 的排列数，即 $(\binom{n + m}{m})$ 。
从 $(0, 0)$ 到 $(n, n)$ 的除端点外不接触直线 $y = x$ 的非降路径数：

先考虑 $y = x$ 下方的路径，都是从 $(0, 0)$ 出发，经过 $(1, 0)$ 及 $(n, n - 1)$ 到 $(n, n)$ ，可以看做是 $(1, 0)$ 到 $(n, n - 1)$ 不接触 $y = x$ 的非降路径数。

所有的的非降路径有 $(\binom{2 n - 2}{n - 1})$ 条。对于这里面任意一条接触了 $y = x$ 的路径，可以把它最后离开这条线的点到 $(1, 0)$ 之间的部分关于 $y = x$ 对称变换，就得到从 $(0, 1)$ 到 $(n, n - 1)$ 的一条非降路径。反之也成立。从而 $y = x$ 下方的非降路径数是 $(\binom{2 n - 2}{n - 1}) - (\binom{2 n - 2}{n})$ 。根据对称性可知所求答案为 $2 (\binom{2 n - 2}{n - 1}) - 2 (\binom{2 n - 2}{n})$ 。

从 $(0, 0)$ 到 $(n, n)$ 的除端点外不穿过直线 $y = x$ 的非降路径数：

用类似的方法可以得到： $\frac{2}{n + 1} (\binom{2 n}{n})$

第二类斯特林数（Stirling Number)

第二类斯特林数（斯特林子集数） ${\begin{matrix} n k \end{matrix}}$ ，也可记做 $S (n, k)$ ，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。

${\begin{matrix} n k \end{matrix}} = {\begin{matrix} n - 1 k - 1 \end{matrix}} + k {\begin{matrix} n - 1 k \end{matrix}}$

边界是 ${\begin{matrix} n 0 \end{matrix}} = [n = 0]$ 。

通项公式

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

性质：

n^k=∑{ S(k,i) × i! × C(n,i) } i∈[0,k]

n^m = ∑ S(m,k) *[ n! / (n-k)! ] k∈[0,m]

S(m,k) = (1/k!)*∑[ (−1)^(k−i) * C(k,i) * i^m ] i∈[0,k]

第一类斯特林数（Stirling Number）

第一类斯特林数（斯特林轮换数） $[\begin{matrix} n k \end{matrix}]$ ，也可记做 $s (n, k)$ ，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空轮换的方案数。

一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 $[A, B, C, D]$ ，并且我们认为 $[A, B, C, D] = [B, C, D, A] = [C, D, A, B] = [D, A, B, C]$ ，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 $[A, B, C, D] \neq [D, C, B, A]$ 。

递推式 $[\begin{matrix} n k \end{matrix}] = [\begin{matrix} n - 1 k - 1 \end{matrix}] + (n - 1) [\begin{matrix} n - 1 k \end{matrix}]$

边界是 $[\begin{matrix} n 0 \end{matrix}] = [n = 0]$ 。

贝尔数

$B_{0} = 1, B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15, B_{5} = 52, B_{6} = 203, \dots$

$B_{n}$ 是基数为 $n$ 的集合的划分方法的数目。集合 $S$ 的一个划分是定义为 $S$ 的两两不相交的非空子集的族，它们的并是 $S$ 。例如 $B_{3} = 5$ 因为 3 个元素的集合 $a, b, c$ 有 5 种不同的划分方法：

递推公式：

$$ B{n+1}=\sum{k=0}^n\binom{n}{k}B_{k} $$

欧拉数

在计算组合中，欧拉数（Eulerian Number）是从 $1$ 到 $n$ 中正好满足 $m$ 个元素大于前一个元素（具有 $m$ 个“上升”的排列）条件的排列个数。

 int eulerianNumber(int n, int m) {
  if (m >= n || n == 0) return 0;
  if (m == 0) return 1;
  return (((n - m) * eulerianNumber(n - 1, m - 1)) +
          ((m + 1) * eulerianNumber(n - 1, m)));
}

等幂求和

$\sum_{i = 1}^{n} i^{1} = \frac{n (n + 1)}{2} = \frac{1}{2} n^{2} + \frac{1}{2} n$

$\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6} = \frac{1}{3} n^{3} + \frac{1}{2} n^{2} + \frac{1}{6} n$

$\sum_{i = 1}^{n} i^{3} = {[\frac{n (n + 1)}{2}]}^{2} = \frac{1}{4} n^{4} + \frac{1}{2} n^{3} + \frac{1}{4} n^{2}$

$\sum_{i = 1}^{n} i^{4} = \frac{n (n + 1) (2 n + 1) (3 n^{2} + 3 n - 1)}{30} = \frac{1}{5} n^{5} + \frac{1}{2} n^{4} + \frac{1}{3} n^{3} - \frac{1}{30} n$

$\sum_{i = 1}^{n} i^{5} = \frac{n^{2} (n + 1)^{2} (2 n^{2} + 2 n - 1)}{12} = \frac{1}{6} n^{6} + \frac{1}{2} n^{5} + \frac{5}{12} n^{4} - \frac{1}{12} n^{2}$

预处理逆元预处理组合数

$\sum{i=0}^n i^k = \frac{1}{k+1} \sum{i=0}^k \binom{k+1}{i} B_{k+1-i} (n+1)^i$.

也可以 $\sum{i=0}^n i^k = \frac{1}{k+1} \sum{i=0}^k \binom{k+1}{i} B^+_{k+1-i} n^i $。区别在于$ B^+_1 =1/2$。

 const int M = 100;
LL inv[M] = {-1, 1};
 
void inv_init(LL n, LL p) {
  for (int i = 2; i < n; ++i) inv[i] = (p - p / i) * inv[p % i] % p;
}
 
LL C[M][M];
 
void init_C(int n) {
  for (int i = 0; i < n; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
}
 
LL B[M] = {1};
 
void init() {
  inv_init(M, MOD);
  init_C(M);
  for (int i = 1; i < M - 1; ++i) {
    LL &s = B[i] = 0;
    for (int j = 1; j < i; ++j) s += C[i + 1][j] * B[j] % MOD;
    s = (s % MOD * -inv[i + 1] % MOD + MOD) % MOD;
  }
}
 
LL p[M] = {1};
 
LL go(LL n, LL k) {
  n %= MOD;
  if (k == 0) return n;
  for (int i = 1; i < k + 2; ++i) p[i] = p[i - 1] * (n + 1) % MOD;
  LL ret = 0;
  for (int i = 1; i < k + 2; ++i)
    ret += C[k + 1][i] * B[k + 1 - i] % MOD * p[i] % MOD;
  ret = ret % MOD * inv[k + 1] % MOD;
  return ret;
}