Stirling 数

第一类斯特林数

\({n\brack m}\) 为第一类斯特林数，表示将 \(n\) 个不同元素划分为 \(k\) 个圆排列的方案数。

有递推式

\[{n\brack m}={n-1\brack k-1}+(n-1){n-1\brack k} \]

第二类斯特林数

\({n\brace m}\) 为第二类斯特林数，表示将 \(n\) 个不同元素划分为 \(k\) 个非空子集的方案数。

有递推式和通项式

\[{n\brace m}={n-1\brace k-1}+k{n-1\brace k}\\ {n\brace m}=\sum_{i=0}^{m} \frac{(-1)^{m-i}i^n}{i!(m-i)!} \]

上升幂和下降幂

上升幂和下降幂的定义

\[x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)\\ x^{\underline{n}}=\prod_{k=0}^{n-1} (x-k) \]

斯特林数可以把上升/下降幂和普通幂结合起来

\[x^{\overline{n}}=\sum_{k} {n\brack k} x^k\\ x^n=\sum_{k}{n\brace k} (-1)^{n-k} x^{\overline{k}}\\ x^n=\sum_{k} {n\brace k} x^{\underline{k}}\\ x^{\underline{n}}=\sum_{k}{n\brack k} (-1)^{n-k} x^k \]

从上升/下降幂转到普通幂用的是第二类，否则用的是第一类。

P4609 [FJOI2016]建筑师

考虑枚举高度为 \(n\) 的建筑放在哪里。这样就把左边和右边切开了，分成独立的两块。我们不妨考虑左边的情况（右边本质是相同的）

\(f(i,j)\) 表示 \(i\) 个建筑，从左向右看能看到 \(j\) 个建筑的方案数。

\[f(i,j)=f(i-1,j-1)+(i-1)\times f(i-1,j) \]

这是第一类斯特林数的递推式。

考虑左右两个答案合并起来。

\[ans=\sum_{i=1}^{n} \binom{n-1}{i-1} {i-1\brack A-1} {n-i\brack B-1} \]

这东西可以变成（具体数学 P221 6.29）

\[ans=\binom{A+B-2}{A-1} {n-1\brack A+B-2} \]

具体理解为把左右两边的圆排列合起来考虑，即 \(n-1\) 个数中选取 \(A+B-2\) 个圆排列，然后分 \(A-1\) 个到左边，\(A+B-2\) 个到右边。

code: https://www.luogu.com.cn/record/46537669