斯特林数学习笔记

第二类斯特林数

定义：将(n)个物品分成(k)个非空集合的方案数，记作(left{egin{matrix}n\kend{matrix} ight})，称为斯特林子集数.
递推：

[left{egin{matrix}n\kend{matrix} ight}=kleft{egin{matrix}n-1\kend{matrix} ight}+left{egin{matrix}n-1\k-1end{matrix} ight} ]
意义：放入最后一个物品时，若新成立一个集合，方案数为(left{egin{matrix}n-1\k-1end{matrix} ight})，若加入原来的集合，方案数为(kleft{egin{matrix}n-1\kend{matrix} ight}).

定义：将(n)个物品分成(k)个非空轮换的方案数，记作(left[egin{matrix}n\kend{matrix} ight])，称为斯特林轮换数.
轮换？

轮换即为环形排列，如([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C])

(n)元素的轮换的方案数为((n-1)!)
递推

[left[egin{matrix}n\kend{matrix} ight]=(n-1)left[egin{matrix}n-1\kend{matrix} ight]+left[egin{matrix}n-1\k-1end{matrix} ight] ]
意义：放入最后一个物品，新成立方案数为(left[egin{matrix}n-1\k-1end{matrix} ight])，放在前面的集合，每个元素可以产生一个方案，为((n-1)left[egin{matrix}n-1\kend{matrix} ight])，可以从一个大小为(n)的轮换放进去一个元素，方案数是(n)来说明，其实就是一个求和。
(n)元素的轮换与(n)元素的排列构成双射，有

[sumlimits_{k=0}^nleft[egin{matrix}n\kend{matrix} ight]=n! ]
举个例子感性说明一下，比如(123456)与(361254)，将它们如下排列

[egin{matrix}1 2 3 4 5 6\3 6 1 2 5 4end{matrix} ]
然后你发现(1->3,3->1;2->6,6->4,4->2;5->5)，那么(361254)可以映射到轮换([1,3][2,6,4][5])上了。

证明就是一般化的说明这个过程。

上升幂与下降幂

下降幂：(x^{underline n}=x(x-1)dots(x-n+1))

上升幂：(x^{overline n}=x(x+1)dots(x+n-1))
斯特林子集数是产生通常幂的下降幂的系数。

[x^n=sumlimits_{k=0}^nleft{egin{matrix}n\kend{matrix} ight}x^{underline k} ]
斯特林轮换数是产生上升幂的通常幂的系数。

[x^{overline n}=sumlimits_{k=0}^nleft[egin{matrix}n\kend{matrix} ight]x^k ]
以上两者均可用数学归纳法证明。

具体数学第二版