组合计数 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-04-09 13:07

点击数:148

其实不是什么学习笔记,只是稍微整理一下。

排列组合

排列

从 $n$ 个元素中有序的选择 $k$ 个元素的方案数:
$$
n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} = n^{\underline{k}}
$$

组合

从 $n$ 个元素中选出无序的 $k$ 个元素的方案数:
$$
\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}
$$

计算组合数的方法

  1. 根据杨辉三角递推,时间复杂度 $\mathcal O(n^2) – \mathcal O(1)$。
  2. 预处理阶乘、逆元、阶乘逆元,时间复杂度 $\mathcal O(n) – \mathcal O(1)$。

  3. Lucas 定理:
    当 $p$ 为质数时,有:
    $$
    \binom nm \equiv \binom {n \bmod p}{m \bmod p} \cdot \binom{\lfloor \frac np \rfloor}{\lfloor \frac mp \rfloor} \pmod p
    $$
    时间复杂度 $\mathcal O(p) – \mathcal O(\log_pn)$。

隔板法

将 $n$ 个一样的小球放进 $m$ 个不同的盒子内的方案数,
等价于将 $n$ 个小球划分成 $m$ 段,段可以为空的方案数,
等价于将 $n+m$ 个小球划分成 $m$ 段,段不能为空的方案数,
等价于从 $n+m-1$ 个空隙中选 $m-1$ 个空隙作为划分点的方案数:
$$
\binom {n+m-1}{m-1}
$$

二项式定理

一般二项式定理

$n$ 为非负整数:
$$
(x+y)^n = \sum_{k=0}^n \binom nk x^ky^{n-k}
$$

扩展二项式定理

$n$ 为非负整数:
$$
\left(\sum_{i=1}^t x_i\right)^n = \sum_{\sum_{i=1}^tn_i = n} \left(\binom{n}{n_1,n_2,\cdots,n_t} \prod_{j=1}^t x_j^{n_j}\right)
$$

广义二项式定理

$n$ 为实数:
$$
(x+y)^n = \sum_{k} \frac{n^{\underline{k}}}{k!} x^ky^{n-k}
$$

特殊数列

$\text{Fibonacci}$ 数

A000045
递推公式:
$$
F_{n} =
\begin{cases}n & n \le 1 \\
F_{n-1} + F_{n-2} & n \ge 2
\end{cases}
$$
通项公式:
$$
F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}
$$
OGF:
$$
F(x) = \frac x{1-x-x^2} = \frac{\left(\frac{1}{1-\frac{1+\sqrt5}{2}x} – \frac{1}{1-\frac{1-\sqrt5}{2}x}\right)}{\sqrt5}
$$
性质:

  • $F_{n-1}F_{n+1} – F_n^2 = (-1)^n$。
  • $\gcd(F_n, F_m) = F_{\gcd(n,m)}$。
  • $\sum_{i=0}^n F_i = F_{n+2}-1$。
  • $\text{Fibonacci}$ 数列模 $m$ 意义下循环节长度 $\le 6m$。

$\text{Catalan}$ 数

A000108

意义:$C_n$ 表示 $n$ 对括号的合法括号序列数,以及延伸出来的无数种意义。

递推公式:
$$
C_{n} =
\begin{cases}1 & n = 0 \\
\sum_{i=0}^{n-1} C_{i}C_{n-1-i} & n \ge 1
\end{cases}
$$
通项公式:
$$
C_{n} = \binom {2n}{n} – \binom {2n}{n-1} = \frac{\binom{2n}{n}}{n+1} = \frac{C_{n-1}(4n-2)}{n+1}
$$
OGF:
$$
C(x)=\frac{1 – \sqrt{1-4 x}}{2 x}
$$

第一类 $\text{Stirling}$ 数

意义:$S_1(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个圆排列的方案数。

递推公式:
$$
S_1(n,m) = S_1(n-1,m-1)+(n-1) \cdot S_1(n-1,m)
$$
性质:

  • $n! = \sum_{i=0}^n S_1(n,i)$。
  • 上升幂 $\to$ 常幂:$x^{\bar{n}}=\sum_{i=0}^{n} S_1(n, i) x^{i}$。
  • 下降幂 $\to$ 常幂:$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i} S_1(n, i) x^{i}$。
  • 上面两个同时成立是因为:$(-x)^{\underline{n}}=(-1)^{n} x^{\bar{n}}$。

第二类 $\text{Stirling}$ 数

意义:$S_2(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个非空集合的方案数。

递推公式:
$$
S_2(n,m) = S_2(n-1,m-1) + m \cdot S_2(n-1,m)
$$
通项公式:
$$
S_2(n,m) = \frac{\sum_{k=0}^m (-1)^k \binom mk (m-k)^n}{m!}
$$

性质:

  • 常幂 $\to$ 下降幂:$x^{n}=\sum_{i=0}^{n} S_2(n,i) x^{\underline{i}}$。
  • 常幂 $\to$ 上升幂:$x^n = \sum_{i=0}^n (-1)^{n-i}S_2(n,i)x^{\bar{i}}$。
  • 广义上:$S_2(n,m) = S_1(-m,-n)$。

$\text{Bell}$ 数

A000110

意义:$B_n$ 表示将 $n$ 个集合划分成若干个非空集合的方案数。

递推公式:
$$
B_{n} = \sum_{i=0}^{n-1} \binom {n-1}{i} B_i
$$
通项公式:
$$
B_n = \frac 1e \sum_{i \ge 0} \frac{i^n}{i!}
$$
性质:

  • $B_n = \sum_{i=0}^n S_2(n,i)$。
  • 对于质数 $p$,$B_{p^m+n} = mB_{n}+B_{n+1}$。
  • $\text{Bell}$ 数列模质数 $p$ 意义下循环节长度为 $\frac {p^p-1}{p-1}$。

EGF:
$$
B(x) = e^{e^x-1}
$$
$\text{Bell}$ 三角 A011971

  • $b_{0,0} = 1$。
  • 对于 $n > 0$,$a_{n,1} = a_{n-1,n-1}$。
  • 对于 $n,m > 0$,$a_{n,m} = a_{n,m-1} + a_{n-1,m-1}$。
  • $B_{n} = b_{n,0}$。

分拆数

A000041 LOJ6268

意义:将 $n$ 进行整数分拆的方案数。

递推公式:
$$
F_{n} =
\begin{cases}
0 & n < 0 \\
1 & n = 0 \\
\sum_{k \ge 1} -(-1)^k (F_{n-\frac{k(3k-1)}{2}} + F_{n-\frac{k(3k+1)}{2}}) & n > 0
\end{cases}
$$
按照递推公式求分拆数是 $\mathcal O(n \sqrt n)$ 的。

OGF:
$$
F(x) = \prod_{n > 0} \frac{1}{1-x^n} = \frac1{\sum_{k\ge 1}(-1)^k(x^{k(3k-1)} + x^{k(3k+1)})}
$$

$\text{Bernoulli}$ 数

等幂和 $S_m(n) = \sum_{k=1}^n k^m$,有公式:
$$
S_m(n) = \frac1{m+1} \sum_{k=0}^m \binom {m+1}{k} B^+_k n^{m+1-k}
$$
其中 $B^+_k$ 为 $\text{Bernoulli}$ 数,$B^+_n$ 与 $B^-_n$ 为两种不同的定义,仅在 $n=1$ 时有区别:$B^+_1 = \frac 12$,$B^-_1 = -\frac 12$。

递推公式:
$$
\sum_{k=0}^m \binom {m+1}{k} B^-_k = 0
$$
边界为 $B^-_0 = 1$。

EGF:
$$
B(x) = \frac x{e^x-1}
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注