小笔记 · 两类 Stirling 数行/列怎么求？

· · 算法·理论

第二类 Stirling 数·行

考虑对 [n]\to [k] 的满射计数

\begin{Bmatrix}n\\k\end{Bmatrix}k!=\sum_{i=0}^k\dbinom ki(-1)^ii^n

因此

\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i+j=k}\dfrac{i^n(-1)^i}{i!}\dfrac{1}{j!}

卷积即可。

第二类 Stirling 数·列

设非空集合的 EGF 为

A(x)=\sum_{n=1}^{+\infty}\dfrac{x^n}{n!}

则其 \textsf{MSet}_k 的 EGF 为

\dfrac{(A(x))^k}{k!}

第一类 Stirling 数·行

因为

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

后者直接倍增和多项式平移求出即可。

第一类 Stirling 数·列

设非空圆排列的 EGF 为

B(x)=\sum_{n=1}^{+\infty}\dfrac{(n-1)!x^n}{n!}

则其 \textsf{MSet}_k 的 EGF 为

\dfrac{(B(x))^k}{k!}