斯特林数
第二类斯特林数
定义
记作 \(\begin{Bmatrix} n \\m \end{Bmatrix}\)，其组合意义为将 \(n\) 个物品划分为 \(m\) 个无标号集合的方案数。
递推式
\[\begin{Bmatrix} n \\ m \end{Bmatrix}=\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} + m\begin{Bmatrix} n-1 \\ m \end{Bmatrix}
\]
可以组合意义理解一下，要么新开一个集合，要么并到前面一个集合去。
第一类斯特林数
定义
记作 \(\begin{bmatrix} n \\m \end{bmatrix}\)，其组合意义为将 \(n\) 个物品划分为 \(m\) 个无标号非空轮换，也就是圆排列的方案数。
递推式
\[\begin{bmatrix} n \\m \end{bmatrix} = \begin{bmatrix} n-1 \\ m-1 \end{bmatrix} + (n-1)\begin{bmatrix} n-1 \\m \end{bmatrix}
\]
要么新开一个集合，要么放在某个元素之前并入一个轮换中。
第二类斯特林数的通项公式
我们来看这样一个组合式子：
\[n^m = \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} \left(\begin{matrix} n \\ k \end{matrix} \right) k!
\]
可以这么理解，你要给 \(m\) 个格子染 \([1,n]\) 的颜色的方案数，一种是直接算；另一种就是说，你先枚举总共用到的颜色数，然后你将序列划分为 \(k\) 组，然后选择 \(k\) 个颜色后定序。这显然都能算出这个方案数，大概是双计数的思想。
把等式右侧看成二项式反演的形式，反演得：
\[n! \begin{Bmatrix} m \\ n \end{Bmatrix} = \sum_{k=0}^n (-1)^{n-k} \left(\begin{matrix} n \\ k \end{matrix} \right) k^m
\]
\[\begin{Bmatrix} m \\ n \end{Bmatrix} = \sum_{k=0}^n \frac{(-1)^{n-k} k^m}{k!(n-k)!}
\]
这是第二类斯特林数的通项公式。
下降幂与上升幂
定义
\[x^{\underline{n}} = x(x-1) \cdots (x-n+1)
\]
\[x^{\overline{n}} = x(x+1) \cdots (x+n-1)
\]
非常直观，就是往上或者往下乘一段数。
一点性质
有上下幂的一个转化：
\[\left \{ \begin{matrix}
x^{\underline{n}} = (-1)^n(-x)^{\overline{n}} \\x^{\overline{n}} = (-1)^n(-x)^{\underline{n}} \\
\end{matrix}\right.
\]
方幂与下降幂与上升幂
方幂转下降幂
\[n^m = \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} \left(\begin{matrix} n \\ k \end{matrix} \right) k! \Rightarrow n^m = \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} n^{\underline{k}}
\]
上升幂转方幂
\[n^{\overline{m}} = \sum_{k=0}^m \begin{bmatrix} m \\ k \end{bmatrix} x^k
\]
斯特林反演
反转公式
先正向推导一下：
\[\begin{align}
n^m &= \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} n^{\underline{k}} \\&= \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} (-1)^k (-n)^{\overline{k}} \\&= \sum_{k=0}^m \begin{Bmatrix} m \\ k \end{Bmatrix} (-1)^k \sum_{j=0}^k \begin{bmatrix} k \\ j \end{bmatrix} (-n)^j \\&= \sum_{j=0}^m n^j \sum_{k=j}^m \begin{Bmatrix} m \\ k \end{Bmatrix} \begin{bmatrix} k \\ j \end{bmatrix} (-1)^{k-j} \\
\end{align} \rightarrow
\]
可以得到：
\[\sum_{k=n}^m \begin{Bmatrix} m \\ k \end{Bmatrix} \begin{bmatrix} k \\ n \end{bmatrix} (-1)^{k-n} = [n=m]
\]
同理变换可得：
\[\sum_{k=n}^m \begin{bmatrix} m \\ k \end{bmatrix} \begin{Bmatrix} k \\ n \end{Bmatrix} (-1)^{k-n} = [n=m]
\]
懒得写了，随便证一下吧。
斯特林反演式
\[f(n) = \sum_{i=0}^n \begin{Bmatrix} n \\ i \end{Bmatrix} g(i) \Leftrightarrow g(n) = \sum_{i=0}^n (-1)^{n-i} \begin{bmatrix} n \\ i \end{bmatrix} f(i)
\]
这里正向推导一下，已知：
\[\left \{ \begin{matrix}f(n ) = \sum_{i=0}^n \left \{ \begin{matrix} n \\ i \end{matrix} \right \} g(i) \\f(n ) = \sum_{i=0}^n [i=n]f(i)\end{matrix}\right.
\]
\[\begin{align}f(n ) &= \sum_{i=0}^n [i=n]f(i) \\
&= \sum_{i=0}^n \sum_{j=i}^n \begin{Bmatrix} n \\ j \end{Bmatrix} \begin{bmatrix} j \\ i \end{bmatrix} (-1)^{j-i} f(i)\\&= \sum_{j=0}^n \begin{Bmatrix} n \\ j \end{Bmatrix} \sum_{i=0}^j (-1)^{j-i} \begin{bmatrix} j \\ i \end{bmatrix} f(i)\end{align}
\]
\[\Rightarrow g(j) = \sum_{i=0}^j (-1)^{j-i} \begin{bmatrix} j \\ i \end{bmatrix} f(i)
\]
超集形式
\[f(n) = \sum_{i \ge n} \begin{Bmatrix} i \\ n \end{Bmatrix} g(i) \Leftrightarrow g(n) = \sum_{i \ge n}(-1)^{n-i} \begin{bmatrix} i \\ n \end{bmatrix} f(i)
\]
同样懒得证了。