组合数学

卢卡斯定理

$ \binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod 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_1n_2\cdots n_t}} = t^n $

模型

多重集的组合数 1

设 $S={n_1\cdot a_1,n_2\cdot a_2,\cdots,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+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为

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

多重集的组合数 2

考虑这个问题：设 $S={n_1\cdot a_1,n_2\cdot a_2,\cdots,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$ 个数中任何两个数都不相邻的组合有 $\displaystyle \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$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有

$$ \mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)! $$

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

$$ \mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!} $$

组合数性质 | 二项式推论

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

$$ \binom{n}{m}=\binom{n}{n-m}\tag{1} $$

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

$$ \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2} $$

由定义导出的递推式。

$$ \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3} $$

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

$$ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4} $$

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

$$ \sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5} $$

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

$$ \sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6} $$

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

$$ \sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7} $$

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

$$ \sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8} $$

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

$$ \sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9} $$

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

$$ \sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10} $$

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

$$ \binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} $$

通过定义可以证明。

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

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

$$ \sum_{l=0}^n \binom{l}{k} = \binom{n+1}{k+1}\tag{13} $$

通过组合分析——考虑 $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{2n}{n} - \binom{2n}{n-1} $$

路径计数问题

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

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

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

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

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

用类似的方法可以得到：$\dfrac{2}{n+1}\dbinom{2n}{n}$

第二类斯特林数（Stirling Number)

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

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

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

通项公式

$$ \begin{Bmatrix}n\ m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-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{bmatrix}n\ k\end{bmatrix}$，也可记做 $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{bmatrix}n\ k\end{bmatrix}=\begin{bmatrix}n-1\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\ k\end{bmatrix}$

边界是 $\begin{bmatrix}n\ 0\end{bmatrix}=[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)(2n+1)}{6} = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n$

$\sum_{i=1}^{n} i^{3} = \left[\frac{n(n+1)}{2}\right]^{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)(2n+1)(3n^2+3n-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}(2n^2+2n-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;
}

递推公式：

$$ \begin{aligned} S_m{(n)}&=\frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1 n^m+\dots+\binom{m+1}{m}Bm n) \ &=\frac{1}{m+1}\sum{k=0}^{m}\binom{m+1}{k}B_kn^{m+1-k} \end{aligned} $$