斯特林数学习笔记

怎么感觉组合数用 C 几几更方便写

Posted by ethan-zhou on June 18, 2021

第一类斯特林数

几何意义

把 n 各不同的数放进为 k 个环的方案数,用 $\begin{bmatrix}n\cr k\end{bmatrix}$ 表示。

代数意义

\[\begin{aligned} x^{\overline{n}}&=\sum_{i=1}^n \begin{bmatrix}n\cr i\end{bmatrix}x^i\cr x^{\underline{n}}&=\sum_{i=1}^n (-1)^{n-i}\begin{bmatrix}n\cr i\end{bmatrix}x^i \end{aligned}\]

计算方式

$O(nk)$ 递推:

\[\begin{bmatrix}n\cr k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\cr k\end{bmatrix}+\begin{bmatrix}n-1\cr k-1\end{bmatrix}\]

第二类斯特林数

组合意义

把 n 各不同的数放进为 k 个非空集合的方案数,用 $\begin{Bmatrix}n\cr k\end{Bmatrix}$ 表示。

代数意义

\[\begin{aligned}i^k&=&&\sum_{j=1}^k i^{\underline{j}}\begin{Bmatrix}k\cr j\end{Bmatrix}\cr &=&&\sum_{j=1}^k \binom i j j! \begin{Bmatrix}k\cr j\end{Bmatrix}\cr \end{aligned}\]

计算方式

$O(nk)$ 递推:

\[\begin{Bmatrix}n\cr k\end{Bmatrix}=k\begin{Bmatrix}n-1\cr k\end{Bmatrix}+\begin{Bmatrix}n-1\cr k-1\end{Bmatrix}\]

$O(k \log n)$ 容斥:

\[\begin{Bmatrix}n\cr k\end{Bmatrix}=\frac 1 {k!}\sum_{i=0}^k (-1)^i \binom k i (k-i)^n\]

斯特林反演

哪些题可能是斯特林反演

  • 求和 $\sum_{i=1}^n (\cdots) i^k$
  • n 超级大,但 $k^2$ 能过

步骤

  • 反演
\[\begin{aligned}i^k&=&&\sum_{j=1}^k i^{\underline{j}}\begin{Bmatrix}k\cr j\end{Bmatrix}\cr &=&&\sum_{j=1}^k \binom i j j! \begin{Bmatrix}k\cr j\end{Bmatrix}\cr \end{aligned}\]
  • 换序求和
\[=\sum_{j=1}^k j! \begin{Bmatrix}k\cr j\end{Bmatrix}\sum_{i=1}^n \binom i j (\cdots)\]
  • 化简后面一部分:
    • 重组组合数,尽量多凑成与 i 无关的形式,比如:
    \[\sum_{i=1}^n \binom i j \binom n i=\binom n j \sum_{i=1}^n \binom {n-j} {i-j}\]
    • 利用组合意义求和,比如:
    \[\sum_{i=1}^n \binom i j=\binom {n+1}{j+1}\]

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon