第二类斯特林数
定义:
第二类斯特林数 \(\begin{Bmatrix}n\\k\end{Bmatrix}\),表示将 \(n\) 个两两不同的元素,划分为 \(k\) 个互不区分的非空子集的方案数量。
比如 \(\begin{Bmatrix} a_{1},a_{2},a_{3}\end{Bmatrix}\) 只能划分成 \(\begin{Bmatrix}a_{1}\end{Bmatrix}\), \(\begin{Bmatrix}a_{2},a_{3}\end{Bmatrix}\) 和 \(\begin{Bmatrix}a_{1},a_{2}\end{Bmatrix}\), \(\begin{Bmatrix}a_{3}\end{Bmatrix}\) 和 \(\begin{Bmatrix}a_{1},a_{3}\end{Bmatrix}\), \(\begin{Bmatrix}a_{2}\end{Bmatrix}\)。因此 \(S(3,2)=3\)。
递推式
\[h_{i,j}=h_{i-1,j-1}+j \times h_{i-1,j} \]边界条件为 \(h_{0,0}=1\)。
考虑第 \(i\) 个元素是怎么来的,第一种是新建了一个集合,从 \(h_{i-1,j-1}\) 来。第二种是以前放在以前的 \(j\) 个集合里,因此是 \(j \times h_{i-1,j}\)。
通项公式
考虑二项式反演。
记 \(g(i)\) 表示将 \(n\) 个元素分成 \(i\) 个两两不同的集合的方案数(允许为空),\(f(i)\) 表示将 \(n\) 个元素分成 \(i\) 个两两不同的集合的方案数(不允许为空)。
显然 \(g(i)=i^n\)。
那么
\[\begin{aligned} f(i) &=\sum_{j=0}^{i}(-1)^{i-j}C_{i}^{j}g(j) \\&=\sum_{j=0}^{i}\frac{(-1)^{i-j}i!j^{n}}{j!(i-j)!} \end{aligned} \]由于第二类斯特林数不区分集合顺序,因此通项公式为:
\[S(n,k)=\sum_{i=0}^{k}\frac{(-1)^{k-i}i^{n}}{i!(k-i)!} \]应用:
- \(x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\)(普通幂转下降幂)
证明:
考虑有 \(n\) 个小球丢进 \(x\) 个盒子里(允许空),枚举非空的 \(i\) 个盒子,即 \(\sum_{i=0}^{min(n,x)}C_{x}^{i}\begin{Bmatrix}n\\i\end{Bmatrix}i!\)。
整理一下得到原式。
- \(x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^{\bar i}\)(普通幂转上升幂)
证明:
由于 \(x^{\bar i}=(-1)^i(-x)^{\underline i}\),原式可化简为:
\[(-1)^{n}\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-x)^{\bar i} \]即 \((-1)^n(-x)^{n}\)。
第一类斯特林数
定义:
第一类斯特林数 \(\begin{bmatrix}n\\k \end{bmatrix}\),表示将 \(n\) 个两两不同的元素,划分成 \(k\) 个互不区分的非空轮换的方案数。
递推式:
\[h_{i,j}=h_{i-1,j-1}+h_{i-1,j} \times (i-1) \]边界条件 \(h_{0,0}=1\),考虑第 \(i\) 个元素是怎么来的,第一种是新建了一个轮换,从 \(h_{i-1,j-1}\) 来。第二种是以前放在以前的 \(n-1\) 个数的后面,因此是 \((i-1) \times h_{i-1,j}\)。
应用:
- \(x^{\underline n}=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i\)。(下降幂转普通幂)
证明:
考虑归纳法,\(n=1\) 时显然成立。
\[\begin{aligned} x^{\underline {n+1}} &=x^{\underline {n}} \times (x-n) \\&=(x-n) \times \sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i \\&=\sum_{i=1}^{n+1}\begin{bmatrix}n\\i-1 \end{bmatrix}(-1)^{n-i+1}x^i+n \times \sum_{i=1}^{n+1}\begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i+1}x^i \\&= \sum_{i=1}^{n+1}(\begin{bmatrix}n\\i-1 \end{bmatrix}+n \times \begin{bmatrix}n\\i \end{bmatrix}) \times (-1)^{n-i+1}x^i \\&= \sum_{i=0}^{n+1} \begin{bmatrix}n+1\\i \end{bmatrix}(-1)^{n+1-i}x^i \end{aligned} \]
- \(x^{\bar n}=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}x^i\)(上升幂转普通幂)。
证明:
标签:begin,end,Bmatrix,斯特林,sum,times,bmatrix From: https://www.cnblogs.com/xcs123/p/17950173由于 \(x^{\bar i}=(-1)^i(-x)^{\underline i}\),原式可化简为:
\[\begin{aligned} x^{\bar n} &=(-1)^{n}(-x)^{\underline i} \\&= (-1)^{n}\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}(-x)^i \\&=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}x^i \end{aligned} \]