斯特林数

标签：begin end matrix 斯特林 Large aligned brace

斯特林数

第二类斯特林数

\({n \brace k}\) 表示 \(n\) 个元素划分为 \(k\) 个非空子集的方案数.

递推式：

\[{\Large \begin{aligned} & {n\brace k}={n-1\brace k-1}+k{n-1\brace k} \\ & 其中 {n\brace 0}=[n=0] \end{aligned} } \]

某些特殊值：

\[{\Large \begin{aligned} & {n\brace 0}=[n=0]\\ & {n\brace 1}={n\brace n}=1\\ & {n\brace 2}={n\brace n-1}=2^{n-1}-1 \end{aligned} } \]

通项公式（二项式反演证明）：

\[{\Large \begin{aligned} & \left\{ \begin{array}{l} n \\ m \end{array} \right\} = \sum_{i=0}^{m} \frac{(-1)^{m-i} i^n}{i!(m-i)!} \end{aligned} } \]

第一类斯特林数

\({n\brack k}\) 表示 \(n\) 个元素划分为 \(k\) 个非空轮换的方案数。
如果将两个序列首尾相接后本质相同，那这两个序列就被视为一个轮换，如 \([a,b,c,d]\) 与 \([b,c,d,a]\) 是一个轮换。
递推式：

\[{\Large \begin{aligned} & \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor = \left\lfloor \begin{matrix} n-1 \\ k-1 \end{matrix} \right\rfloor + (n-1) \left\lfloor \begin{matrix} n-1 \\ k \end{matrix} \right\rfloor \end{aligned} } \]

重要关系：

\[{\Large \begin{aligned} & \sum_k^n{n\brack k}=n!\\ & {n\brack k}\ge {n\brace k}\\ & 当且仅当 n=k 或 k=n-1 时等号成立 \end{aligned} } \]

常规幂、下降幂与上升幂

常规幂：

\[{\Large \begin{aligned} & x^n \end{aligned} } \]

下降幂：

\[{ \Large \begin{aligned} & x^{\underline n}={x!\over (x-n)!} \end{aligned} } \]

上升幂：

\[{\Large \begin{aligned} & x^{\overline n}={(x+n-1)!\over (x-1)!} \end{aligned} } \]

标签：begin,end,matrix,斯特林,Large,aligned,brace
From： https://www.cnblogs.com/allforgod/p/18688553