盒子
盒子
文章目录
  1. 第一类斯特林数
    1. 1
    2. 2
  2. 第二类斯特林数
    1. 1
    2. 2
    3. 3
  3. 反转公式
    1. 1
    2. 2
  4. 斯特林反演
  5. 参考资料

斯特林数学习笔记

第一类斯特林数

1

$n$ 个元素划分为 $k$ 个环的方案数

$$
\begin{aligned}
& \begin{bmatrix} n \\ m\end{bmatrix}=\begin{bmatrix}n - 1 \\ m - 1\end{bmatrix}+(n-1)\begin{bmatrix} n - 1 \\ m\end{bmatrix} \\
\Rightarrow
& F_n(x)=\sum_{i=0}^{\infty}
\begin{bmatrix}
n \\
i
\end{bmatrix}
x^i
\\
\Rightarrow
& F_n(x)=F_{n-1}(x)x+(n-1)F_{n-1}(x)=F_{n-1}(x)(x+n-1) \\
\Rightarrow
& F_n(x)=\prod_{i=0}^{n-1}(x+i)
\end{aligned}
$$

假设已经求得了 $F(x)$,现在要求 $F(x+n)$:

$$
\begin{aligned}
F(x+n)
=&\sum_{i} a_i(x+n)^i \\
=&\sum_{i}a_i \sum_{j=0}^{i} \frac{i!}{j!(i-j)!} x^jn^{i-j} \\
=&\sum_{j} \frac{x^j}{j!} \sum_{i \ge j} a_ii! \frac{n^{i-j}}{(i-j)!}
\end{aligned}
$$

对于后半部分,翻转后直接多项式乘法,时间复杂度 $T(n)=T(\frac{n}{2})+O(n \log n)=O(n \log n)$

2

$$
n^{\overline m}=\sum_{k=0}^{m}\begin{bmatrix} m \\ k \end{bmatrix} n^k
$$

第二类斯特林数

1

$n$ 个元素划分成 $k$ 类的方案数
$$
\begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k \begin{Bmatrix}n-1\\k \end{Bmatrix}\\
$$

2

$n^m$ 的意义是有一个长度为 $m$ 的序列,每个位置可以填 $n$ 种数字,填完这个序列的方案数,考虑乘法原理,这个过程相当于先选出 $k$ 种数字,然后把 $m$ 个位置划分成 $k$ 类,每类对应的填上选出的数字,然后做全排列

$$
n^m=\sum_{k=0}^{m}{n \choose k}\begin{Bmatrix}m\\k \end{Bmatrix}k!=\sum_{k=0}^{m}\begin{Bmatrix}m\\k \end{Bmatrix}n^{\underline k}
$$

一个应用是把 $n^m$ 的计数转化为 ${n \choose k}$ 的计数,其中 $0 \le k \le m$

还有一个应用是,可以证明 $F(x)=\sum a_ix^i$ 是可以转化为 $F(x)=\sum b_ix^{\underline i}$ 的形式

3

如果把 $m$ 个元素划分成 $k$ 类,然后做全排列,相当于容斥掉先从 $k$ 类选出 $i$ 类,然后每个元素可以染成 $i$ 种颜色之一

$$
\begin{aligned}
& k! \begin{Bmatrix}m \\ k\end{Bmatrix}=\sum_{i=0}^{k} (-1)^{k-i}{k \choose i} i^m \\
\Rightarrow
& \begin{Bmatrix}m \\ k\end{Bmatrix}=\sum_{i=0}^{k}\frac{(-1)^{k-i}}{(k-i)!}\frac{i^m}{i!} \\
\end{aligned}
$$

反转公式

1

$$
\sum_{k=m}^{n}\begin{Bmatrix}n \\ k\end{Bmatrix}\begin{bmatrix}k \\ m\end{bmatrix}(-1)^{n-k}=[n=m]
$$

2

$$
\sum_{k=m}^{n}\begin{bmatrix}n \\ k\end{bmatrix}\begin{Bmatrix}k \\ m\end{Bmatrix}(-1)^{n-k}=[n=m]
$$

换而言之,两类斯特林数互为逆矩阵

斯特林反演

本质上就是把反转公式代入

$$
f(n)=\sum_{k=0}^{n}\begin{Bmatrix}n \\ k\end{Bmatrix}g(k) \Leftrightarrow g(n)=\sum_{k=0}^{n}(-1)^{n-k}\begin{bmatrix}n \\ k\end{bmatrix}f(k)
$$

这里有一个应用:【TCO2014 Wildcard】CountTables

参考资料

【斯特林数-斯特林反演】hec0411

支持一下
扫一扫,支持nekko
  • 微信扫一扫