斯特林数学习笔记

· · 个人记录

引入：差分

1、首先可以递归地定义p阶差分：

\displaystyle \Delta ^{p}h_n=\Delta (\Delta ^{p-1}h_n)

2、差分具有线性性：

\Delta ^{p}(cg_n+df_n)=c\Delta ^{p}g_n+d\Delta ^{p}f_n

3、p次多项式，经过了p+1次差分就全部变成0

1、差分三角形可以由其第0条对角线决定，讨论以下这种特殊的第0条对角线

0,0,0,0,1,0,0,...

那么其确定的差分三角就是（不用考虑1后面的0）：

0\quad 0\quad 0\quad 0\quad 1 \,\,\,0\quad 0\quad 0\quad 1 \quad \,0\quad 0\quad1 \quad 0\quad 1 \quad1

如果h_n是一个四次多项式，那么它就有四个根：0,1,2,3

所以h_n=cn(n-1)(n-2)(n-3)。同时又因为h_4=1，所以c=\dfrac{1}{4!}

得到：\displaystyle \frac{n(n-1)(n-2)(n-3)}{4!}=\binom{n}{4}

更一般的：

其差分表的的第$0$条对角线为：$0,0,...,0(\text{共p个}),1,0,0,...

继续推广可得：

差分表的第0条对角线等于：

c_0,c_1,...,c_p,0,0,...

的序列的通项是下面式子的n的p次多项式：

h_n=\sum_{i=0}^{p}c_i\binom{n}{i}

2、由上面的结论，可以快速地去计算多项式的部分和：

\displaystyle \sum_{i=0}^{k}h_i=\sum_{i=0}^{k}\sum_{j=0}^{p}c_j\binom{i}{j}=\sum_{i=0}^{p}c_i\sum_{j=0}^{k}\binom{j}{i}

利用上指标求和公式得到：\displaystyle =\sum_{i=0}^{p}c_i\binom{k+1}{i+1}

第二类Stirling数

考虑对h_n=n^p的第0条对角线：

c(p,0),c(p,1),...,c(p,p),0,... \displaystyle n^p=\sum_{i=0}^{p}c(p,i)\binom{n}{i}

定义下降幂n^{\underline{k}}（或\displaystyle [n]_k）为n(n-1)...(n-k+1)，其实等价于P(n,k)

由其定义可知：\displaystyle n^{\underline{k+1}}=(n-k)n^{\underline{k}}

那么

\displaystyle n^p=\sum_{i=0}^{p}c(p,i)\frac{n^{\underline{i}}}{i!}

引入S(p,k)=\dfrac{c(p,k)}{k!}，即第二类Stirling数

首先考虑S(p,k)的边界条件：

S(p,0)= \left\{ \begin{array}{lcl} 0&& {p\geq 1}\\ 1&&{p=0} \\ \end{array} \right. \displaystyle S(p,p)=\frac{c(p,p)}{p!}=1

其递推公式为：

S(p,k)=kS(p-1,k)+S(p-1,k-1)

证明：

\displaystyle n^p=\sum_{i=0}^{p}S(p,i)n^{\underline{i}}\quad \quad n^{p-1}=\sum_{i=0}^{p-1}S(p-1,i)n^{\underline{i}} \displaystyle n^p=n^{p-1}\times n=\sum_{i=0}^{p-1}S(p-1,i)n\times n^{\underline{i}}=\sum_{i=0}^{p-1}S(p-1,i)(n-i+i)n^{\underline{i}} \displaystyle =\sum_{i=0}^{p-1}S(p-1,i)(n-i )\times n^{\underline{i}}+\sum_{i=0}^{p-1}S(p-1,i)i\times n^{\underline{i}} \displaystyle =\sum_{i=0}^{p-1}S(p-1,i)n^{\underline{i+1}}+\sum_{i=0}^{p-1}S(p-1,i)i\times n^{\underline{i}} \displaystyle =\sum_{i=1}^{p}S(p-1,i-1)n^{\underline{i}}+\sum_{i=1}^{p-1}S(p-1,i)i\times n^{\underline{i}} \displaystyle =\sum_{i=1}^{p-1}[S(p-1,i-1)+i\times S(p-1,i)]n^{\underline{i}}+S(p-1,p-1)n^{\underline{p}} \displaystyle \because n^p=\sum_{i=1}^{p-1}S(p,i)n^{\underline{i}}+S(p,p)n^{\underline{p}} \therefore S(p,k)=S(p-1,k-1)+k\times S(p-1,k)

这样就可以类似杨辉三角一样递推了，可以发现以下几个性质

\displaystyle S(p,1)=1 \displaystyle S(p,2)=S(p-1,1)+2\times S(p-1,2)=2\times S(p-1,2)+1=2^{p-1}-1 \displaystyle S(p,p-1)=S(p-1,p-2)+(p-1)S(p-1,p-1)=S(p-1,p-2)+(p-1)=(p-1)+...+1=\binom{p}{2}

S(p,k)计数的是把p元素集合划分到k个不可区分的盒子且没有空盒子的划分个数

要证明这个，只需证明其和第二类Stirling数有着相同的初始条件和递归公式即可

令\bar{S}(p,k)表示这个计数方案

那么显然由：\bar S(p,p)=1\quad \bar S(p,0)=0(p\geq 1)

然后考虑递推公式，讨论第p个求是否单独在一个盒子中

如果p单独在一个盒子中，那么前p-1个球就要放在剩下k-1个盒子中

如果p不是单独放在一个盒子中，那么p就要在这k个盒子中选择一个放进去

\displaystyle \bar S(p,k)=\bar S(p-1,k-1)+k\times \bar S(p-1,k)

所以\bar S(p,k)=S(p,k)

有了组合意义，上面的那些式子都可以直接用组合意义证明了

为了方便叙述令\displaystyle S'(n,k)表示放入可区分的盒子里，也就是S'(n,k)=k!S(n,k)

为什么上面要弄一个可区分的盒子呢？因为可以容斥计算：

S'(p,k)=\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^p

枚举i表示选择i个盒子是空的，球可以在剩下的盒子随便放

Q：为什么这个计算的是可区分的盒子，而不是不可区分的盒子呢？

A：考虑容斥原理的实质：

设A_i表示在所有划分中，第i个盒子是空的那些划分构成的集合

所以有S'(p,k)=|\bar A_1\cap \bar A_2 ...\cap \bar A_k|

这里已经看出了，如果盒子是不可区分的，那么这些集合也就是不可区分的，也就没有什么容斥原理了

关键是就是用好其容斥式：\displaystyle S(p,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^p

把组合数拆开，卷积就好了

\displaystyle S(p,k)=\sum_{i=0}^{k}\frac{(-1)^i}{i!}\times \frac{(k-i)^p}{(k-i)!}

第一类Stirling数

前面我们是用下降幂去表示普通幂，那能不能反过来呢？

n^{\underline{p}}=n(n-1)(n-2)...(n-(p-1))

右边乘开来就得到了一个p次多项式，并且显然没有常数项

对于n^i项，有p-i个是取到了-1，所以展开得到的多项式是正负交替的，即：

\displaystyle n^{\underline{p}}=\sum_{i=1}^{p}(-1)^{p-i}s(p,i)n^i

现在同样来研究一下s(p,i)的性质：

边界：

s(p,0)=0(p\geq 1)\quad\quad s(p,p)=1(p\geq 0)

递推式：

s(p,k)=(p-1)s(p-1,k)+s(p-1,k-1)

证明：

\displaystyle n^{\underline{p}}=\sum_{i=0}^{p}(-1)^{p-i}s(p,i)n^i\quad \quad \quad n^{\underline{p-1}}=\sum_{i=0}^{p-1}(-1)^{p-1-i}s(p-1,i)n^i \displaystyle n^{\underline{p}}=n^{\underline{p-1}}\times (n-p+1)=(n-p+1)\sum_{i=0}^{p-1}(-1)^{p-1-i}s(p-1,i)n^i \displaystyle =\sum_{i=0}^{p-1}(-1)^{p-1-i}s(p-1,i)n^{i+1}+\sum_{i=0}^{p-1}(-1)^{p-i}(p-1)s(p-1,i)n^i \displaystyle =\sum_{i=1}^{p}(-1)^{p-i}s(p-1,i-1)n^i+\sum_{i=0}^{p-1}(-1)^{p-i}(p-1)s(p-1,i)n^i

类似上面讨论一下边界，比较系数得到：

s(p,k)=s(p-1,k-1)+(p-1)s(p-1,k)

s(p,k)计数的是把p个对象排成k个非空循环排列的方案数

证明过程也类似上面：考虑第p个人所在的位置

它可以自己单独站在一个圆圈中，前面p-1个就要站在k-1个圈中

它可以和前面的人站在一个圈中，即站在前面p-1个人中任意一个人的左边（因为是循环排列，所以没有左右之分）

斯特林数之间的关系

第二类Stirling数，作为下降幂表示普通幂的系数

第一类Stirling数，作为普通幂表示下降幂的系数

第一类Stirling数计数的，就是把p个元素分配到k个非空且不可区分的盒子中，然后把每个盒子内的元素排成一个循环排列