【笔记】斯特林数学习笔记

Author Avatar
Sakits 11月 29, 2076

第二类斯特林数

简介

  第二类斯特林数表示把nn个元素分成mm个非空集合的方案数,可用S(n,m)S(n,m){nm}\begin{Bmatrix} n\\ m \end{Bmatrix}表示。

公式1

公式1

S(n,m)=m×S(n1,m)+S(n1,m1)S(n,m)=m\times S(n-1,m)+S(n-1,m-1)

公式1证明

  第nn个元素可以分到之前的mm个集合,有mm种分法,或者可以分在一个新的集合。

公式2

公式2

nk=i=1k{ki}×i!×(ni)n^k=\sum_{i=1}^k\begin{Bmatrix} k\\ i \end{Bmatrix} \times i!\times \binom{n}{i}

公式2证明

  等式左边为nn个元素任意分在kk个集合(可空)中的方案数。
  等式右边枚举有ii个非空集合,kk个元素分在ii个非空集合的方案×\times选出kk个集合的方案数。注意左边算的是排列,所以右边乘的是i!×(ni)i!\times \binom{n}{i}
  故等式左右两边等价。

公式3

公式3

{nm}=1m!i=0m(1)i(mi)(mi)n=i=0m(1)ii!×(mi)n(mi)!\begin{aligned} \begin{Bmatrix} n\\ m \end{Bmatrix} &=\frac{1}{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n\\ &=\sum_{i=0}^m\frac{(-1)^i}{i!}\times\frac{(m-i)^n}{(m-i)!} \end{aligned}

公式3证明1

  由公式2二项式反演易得。
  公式2:

nk=i=1k{ki}×i!×(ni)n^k=\sum_{i=1}^k\begin{Bmatrix} k\\ i \end{Bmatrix} \times i!\times \binom{n}{i}

  令Fi=ik,Gi={ki}×i!F_i=i^k,G_i=\begin{Bmatrix} k\\ i \end{Bmatrix} \times i!,由公式2得:

Fi=j=1k(ij)Gj=j=0i(ij)Gj\begin{aligned} F_i&=\sum_{j=1}^k\binom{i}{j}G_j\\ &=\sum_{j=0}^i\binom{i}{j}G_j\\ \end{aligned}

  二项式反演得:

Gi=j=0i(1)ij(ij)Fj=j=0i(1)j(ij)Fij\begin{aligned} G_i&=\sum_{j=0}^{i}(-1)^{i-j}\binom{i}{j}F_j\\ &=\sum_{j=0}^i(-1)^j\binom{i}{j}F_{i-j}\\ \end{aligned}

  将F,GF,G代回原式:

{ki}×i!=j=0i(1)j(ij)(ij)k{ki}=1i!j=0i(1)j(ij)(ij)k\begin{gathered} \begin{Bmatrix} k\\ i \end{Bmatrix}\times i!=\sum_{j=0}^i(-1)^j\binom{i}{j}(i-j)^k\\ \begin{Bmatrix} k\\ i \end{Bmatrix}=\frac{1}{i!}\sum_{j=0}^i(-1)^j\binom{i}{j}(i-j)^k \end{gathered}

  得证。

公式3证明2

  从实际意义去证明,更易于理解和记忆。
  可以看出实际上公式3是个容斥,其实很多二项式反演实际上都是容斥。
  枚举空集的个数,元素随意分在剩下的集合中(剩下的集合也可空),因为斯特林数的集合是无区别的,所以要除以m!m!

应用

  把公式3的组合数拆开后可以发现是个卷积的形式,用FFT可以以O(nlogn)O(nlogn)的复杂度求出一行斯特林数。

例题

  1.bzoj2159:Crash 的文明世界