stirling

斯特林数

第一类斯特林数：无符号版本

• 概念：将1-n划分成k个圆排列的方案数，圆排列没有顺序，记作$s(n,k)$或者$n \brack k$。

  另一种形式，上升幂的形式：$x^{\overline{n}} = \sum_{k=0}^{n}{n\brack k}x^k$

• 递推来求：${n \brack k } = {n-1\brack k-1}+{n-1\brack k}*(n-1)$

性质：

• $s(0,0) = 1$

• $s(n,0) = 0$

• $s(n,n) = 1$

• $s(n,1) = (n-1)! = \dfrac{n!}{n}$

• $s(n,n-1) = C(n,2)$

• $s(n,2) = \dfrac{1}{2}\sum_{i=1}^{n-1}C(n,i)*(i-1)!*(n-i-1)! = (n-1)!\sum_{i=1}^{n-1}\dfrac{1}{i}$(手膜去吧)

• $s(n,n-2) = 2*C(n,3)+3*C(n,4)$

• $\sum_{k=0}^{n}{n\brack k} = n!$，这个证明的时候就需要用到另一个概念了：

  如果说我们把x设成1的话会发生什么呢？

  $1^{\overline{n}} = \sum_{k=0}^{n}{n\brack k} = n!$

第二类斯特林数

• 概念：把n个数划分成k个非空子集的方案数，记作：$S(n,k)$或者${n \brace k}$
• 递推求法：${n\brace k} = {n-1\brace k-1}+{n-1\brace k}*k$

性质：

• $S(n,0) = 0^n$
• $S(n,1) = 1$
• $S(n,n) = 1$
• $S(n,2) = 2^{n-1}-1$
• $S(n,n-1) = C(n,2)$
• $S(n,n-2) = C(n,3)+3*C(n,4)$
• $\sum_{k=0}^{n}{n\brack k}{k\brace m} = \sum_{k=0}^{n}{n\brace k}{k\brack m}$

普通幂转下降幂

$x^n = \sum_k{n\brace k}x^{\underline{k}}$

我们有公式：$x^{\underline{k+1}} = x^{\underline{k}}(x-k)$

$x \cdot x^{\underline{k}} = x^{\underline{k+1}}+kx^{\underline{k}}$

归纳法证明：

$$x\cdot x^{n-1} \\ = x\sum_k{n-1\brace k}x^{\underline{k}}\\ =\sum_k{n-1\brace k}x^{\underline{k+1}}+\sum_k{n-1\brace k}kx^{\underline{k}}\\ =\sum_k{n-1\brace k-1}x^{\underline{k}}+\sum_k{n-1\brace k}kx^{\underline{k}}\\ =\sum_k(k{n-1\brace k}+{n-1\brace k-1})x^{\underline{k}} = \sum_k{n\brace k}x^{\underline{k}}$$

上升幂转普通幂

$x^{\overline{n}} = (x+n-1)x^{\overline{n-1}} = (x+n-1)\sum_k{n-1\brack k}x^k = \sum_k{n\brack k}x^k$

普通幂转上升幂和下降幂转普通幂

$x^n = \sum_k{n\brace k}(-1)^{n-k}x^{\overline{k}}$

$x^{\underline{n}} = \sum_k{n\brack k}(-1)^{n-k}x^k$

他们成立的原因：$x^{\underline{4}} = x(x-1)(x-2)(x-3)=x^4-6^3+11x^2-6x$

就像是$x^{\overline{4}} = x^4+6x^3+11x^2+6x$

所以把上下的x取反就得到了：$x^{\underline{n}} = (-1)^n(-x)^{\overline{n}}$

基本的斯特林数恒等式

$${n\brace k} = k{n-1\brace k}+{n-1\brace k-1}\\ {n\brack k} = (n-1){n-1 \brack k}+{n-1\brack k-1}\\ x^n = \sum_k{n\brace k}x^{\underline{k}} = \sum_k{n\brace k}(-1)^{n-k}x^{\overline{k}}\\ x^n = {n\brace k}x^{\underline{k}}\\ x^{\underline{n}} = \sum_k{n\brack k}(-1)^{n-k}x^k\\ x^{\overline{n}} = \sum_k{n\brack k}x^k\\ {n\brack k} = {-k\brace -n}\\ m^n = \sum_{i=0}^{m}{n\brace i}\binom{m}{i}i!\\ {n\brace m} = \dfrac{!}{m!}\sum_{k=0}^{m}(-1)^k*C(m,k)(m-k)^n\\$$

第二类斯特林数与自然数幂的关系

$$sum(n) = \sum_{i=0}^ni^k\\ = \sum_{i=0}^n\sum_{j=0}^k{k\brace j}i^{\underline{j}}\\ = \sum_{j=0}^k{k\brace j}\sum_{i=0}^ni^{\underline{j}}\\ = \sum_{j=0}^k{k\brace j}j!\sum_{i=0}^n\binom{i}{j}\\ = \sum_{j=0}^k{k\brace j}j!\binom{n+1}{j+1}\\ = \sum_{j=0}^k{k\brace j}\dfrac{(n+1)^{\underline{j+1}}}{j+1}$$

斯特林反演

$$f(n) = \sum_{k=0}^n{n\brace k}g(k) \leftrightarrow g(n) = \sum_{k=0}^n(-1)^{n-k}{n\brack k}f(k)$$

首先证明反转公式：

$$\sum_k{n\brack k}{k\brace m}(-1)^{n-k} = [m=n]\\ \sum_k{n\brace k}{k\brack m}(-1)^{n-k} = [m=n]\\ n^m = \sum_{k=0}^m{m\brace k}(-1)^kn^{\underline{k}}\\ =\sum_{k=0}^m{m\brace k}(-1)^k(-n)^{\overline{k}}\\ =\sum_{k=0}^m{m\brace k}(-1)^k\sum_{j=0}^k{k\brack j}(-n)^j\\ =\sum_{j=0}^mn^j\sum_{k=j}^m{m\brace k}{k\brack j}(-1)^{k-j}$$

由于这个东西等于$n^m$并且后边的东西和n无关，所以其他项的系数都是0

那么有了上面的反转公式我们就可以知道第一类斯特林书和第二类斯特林数（乘上-1的对应次方）的矩阵互为逆

所以我们就可以知道上面的斯特林反演公式