OI-wiki 抄一点，《具体数学》抄一点，抄抄你的，抄抄他的
斯特林数及斯特林反演 - y2823774827y - 博客园 (cnblogs.com)
阶乘幂
我们记下降阶乘幂
\[x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k) \]上升阶乘幂
\[x^{\overline{n}}=\dfrac{(x+n-1)!}{(x-1)!}=\prod_{k=0}^{n-1} (x+k) \]吸收恒等式
\[m^{\underline k}\binom n m=n^{\underline k}\binom {n-k}{m-k} \]组合证明：有 \(n\) 个有标号小球，先无序地选出 \(m\) 个，再从 \(m\) 个中有序地选出 \(k\) 个，等价于选从 \(n\) 个中有序地选出 \(k\) 个，再从剩下的小球中无序地选出 \(m-k\) 个。
代数证明：两边都等于 \(n^{\underline m}/(m-k)!\)。需要用到的公式：
\[\binom n m=n^{\underline m}/m!\iff n^{\underline m}= m!\binom n m \]\[n^\underline k(n-k)^\underline{m-k}=n^\underline m \]第二条由其因式分解形式容易证明。
上下阶乘幂互转
由因式分解形式可以发现
\[x^\underline k=(-1)^k(-x)^\overline k \]或另一个感觉没啥用的
\[x^\underline k=(x-k+1)^\overline k \]下降幂的差分
\[(x+1)^\underline m-x^\underline m=mx^\underline{m-1} \]这个涉及的是《具体数学》中提到的“有限微积分”。
第二类斯特林数
第二类斯特林数（斯特林子集数）记作 \(\begin{Bmatrix}n\\ k\end{Bmatrix}\) 可读作“\(n\) 子集 \(k\)”，表示将 \(n\) 个两两不同的元素划分为 \(k\) 个互不区分的非空子集的方案数。
递推式
\[\begin{Bmatrix}n\\ k\end{Bmatrix}=k\begin{Bmatrix}n-1\\ k\end{Bmatrix}+\begin{Bmatrix}n-1\\ k-1\end{Bmatrix} \]边界是 \(\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]\)。
考虑用组合意义来证明。
我们插入一个新元素时，有两种方案：
- 将新元素单独放入一个子集，有 \(\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}\) 种方案；
- 将新元素放入一个现有的非空子集，有 \(k\begin{Bmatrix}n-1\\ k\end{Bmatrix}\) 种方案。
根据加法原理，将两式相加即可得到递推式。
重要公式：普通幂转下降幂
\[x^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}x^\underline k \]\(k\in [0, n]\)，因为根据定义其它位置不可能有值。证明是归纳法。
证明（来源《具体数学》）
\(n=0\) 时显然成立；若已知 \(n-1\) 情况成立，则因为 \(x^\underline {k+1}=x^\underline {k}(x-k)\)，所以 \(x^\underline {k+1}+kx^\underline {k}=x\cdot x^\underline {k}\)。
\[\begin{aligned} x\cdot x^{n-1}&=x\sum_{k}\begin{Bmatrix}n-1\\ k\end{Bmatrix}x^\underline k\\ &=\sum_{k}\begin{Bmatrix}n-1\\ k\end{Bmatrix}x^\underline {k+1}+\sum_{k}\begin{Bmatrix}n-1\\ k\end{Bmatrix}kx^\underline k\\ &=\sum_{k}\left(\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}\right)x^\underline k=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}x^\underline k\\ \end{aligned} \]第一类斯特林数
第一类斯特林数（斯特林轮换数）记作 \(\begin{bmatrix}n\\ k\end{bmatrix}\) 可读作“\(n\) 轮换 \(k\)”，表示将 \(n\) 个两两不同的元素划分为 \(k\) 个互不区分的非空轮换的方案数。轮换指的是首尾相接的排列（圆排列）。
递推式
\[\begin{bmatrix}n\\ k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}+\begin{bmatrix}n-1\\ k-1\end{bmatrix} \]边界是 \(\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]\)。
考虑用组合意义来证明。
我们插入一个新元素时，有两种方案：
- 将新元素单独放入一个轮换，有 \(\begin{bmatrix}n-1\\ k-1\end{bmatrix}\) 种方案；
- 将新元素放入一个现有的非空轮换。这部分有点智慧，你需要知道将一个数插入到 \(j\) 阶轮换中有 \(j\) 种方法（随意选一个间隔插进去），所以考虑所有轮换的阶数和，有 \((n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}\) 种方案。
根据加法原理，将两式相加即可得到递推式。
重要公式：上升幂转普通幂
\[x^\overline n=\sum_{k}\begin{bmatrix}n\\ k\end{bmatrix}x^ k \]证明（来源《具体数学》）
\(n=0\) 时显然成立；若已知 \(n-1\) 情况成立，则因为 \((x+n-1)x^k=x^{k+1}+(n-1)x^k\)，所以
\[\begin{aligned} (x+n-1)\cdot x^\overline{n-1}&=(x+n-1)\sum_{k}\begin{bmatrix}n-1\\ k\end{bmatrix}x^ k\\ &=\sum_{k}\begin{bmatrix}n-1\\ k\end{bmatrix}x^ {k+1}+\sum_{k}\begin{bmatrix}n-1\\ k\end{bmatrix}(n-1)x^ k\\ &=\sum_{k}\left(\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}\right)x^ k=\sum_{k}\begin{bmatrix}n\\ k\end{bmatrix}x^ k\\ \end{aligned} \]同一行或列的斯特林数的计算
- 斯特林数 - 同一行第二类斯特林数的计算 - OI Wiki (oi-wiki.org) 概括：根据定义施二项式反演
- 斯特林数 - 同一列第二类斯特林数的计算 - OI Wiki (oi-wiki.org) 概括：EGF 意义
- 斯特林数 - 同一行第一类斯特林数的计算 - OI Wiki (oi-wiki.org) 概括：倍增求上升幂的展开式
- 斯特林数 - 同一列第一类斯特林数的计算 - OI Wiki (oi-wiki.org) 概括：EGF 意义
两类斯特林数的比较与联系
递推式
\[\begin{Bmatrix}n\\ k\end{Bmatrix}=k\begin{Bmatrix}n-1\\ k\end{Bmatrix}+\begin{Bmatrix}n-1\\ k-1\end{Bmatrix} \]\[\begin{bmatrix}n\\ k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}+\begin{bmatrix}n-1\\ k-1\end{bmatrix} \]幂的转换
首先有一个直观感受，当 \(x>m>0\) 时
\[x^\underline m<x^m<x^\overline m \]这里为了美观折叠一大段推导
然后有普通幂转下降幂公式，记为 \(x^\underline m\to x^m\)：
\[x^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}x^\underline k \]我们很早就发现了
\[(-x)^\underline k=(-1)^kx^\overline k \]公式 \(x^\underline m\to x^m\) 带入 \(-x\)：
\[(-1)^nx^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}(-1)^kx^\overline k \]所以推出了公式 \(x^m\gets x^\overline k\)：
\[x^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}(-1)^{n-k}x^\overline k \]同样道理，可以由 \(x^m\to x^\overline k\) 推出 \(x^\underline k\gets x^m\)。
下面可以看一下阶乘幂和普通幂相互转化的四条公式：
\[x^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}x^\underline k\quad(x^\underline m\to x^m) \]\[x^\overline n=\sum_{k}\begin{bmatrix}n\\ k\end{bmatrix}x^ k\quad(x^m\to x^\overline m) \]\[x^n=\sum_{k}\begin{Bmatrix}n\\ k\end{Bmatrix}(-1)^{n-k}x^\overline k\quad(x^ m\gets x^\overline m) \]\[x^\underline n=\sum_{k}\begin{bmatrix}n\\ k\end{bmatrix}(-1)^{n-k}x^ k\quad(x^\underline m\gets x^ m) \]总的来说：
- \(x^\underline m\to x^m\to x^\overline m\) 这一条链上，从左往右逐渐往大的幂靠近，不带负号，先子集数再轮换数。
- \(x^\underline m\gets x^m\gets x^\overline m\) 这一条链上，从右往左逐渐往小的幂靠近，所以带负号，也是先子集数再轮换数
反转公式
\[\begin{aligned}\displaystyle \sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]\\ \sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]\end{aligned} \]（写一个证明加深理解）
斯特林数反演
\[f(n)=\sum\limits_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k) \]（写一个证明加深理解）
标签：begin,end,bmatrix,乘幂,sum,斯特林,Bmatrix,underline,从阶 From： https://www.cnblogs.com/caijianhong/p/18409103