第一类斯特林数和第二类斯特林数

2017年08月22日 8点热度 0人点赞 0条评论

【概念】

  第一类Stirling数s(p,k)是将p个有区别的求排列成k个非空的圆排列的方案数。其中任一方案可表为:将p个求分成非空的k份,再把每份中的球排成一个圆,n个球的圆排列数为(n-1)!。

  第二类Stirling数S(p,k)是将p个有区别的球放到k个相同的盒子中,要求没有空盒子的方案总数。

【性质】

1.s(p,k)是将p个有区别的求排成k个非空的圆排列的方案数。

(1) s(p,0)=0 (p>=1)

(2) s(p,p)=1 (p>=1)

(3) 1<=k<=p-1.假设前p-1个球都已放好,考察第p个球:

a.单独放在一个盒子里。因为盒子是无区别的,1个球的圆排列只有1种,这种情况的方案数为s(p-1,k-1).

b.放在一个已有球的盒子里,即插入一个非空的圆中。每个圆定义顺时针方向为正方向。考虑第p个球在顺时针方向遇到的第一个球是哪个球,这个球有p-1中选择。所以这种情况的方案数为

(p-1)s(p-1,k)。

综上,得到第一类斯特林数的递推式

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

2.S(p,k)是将p个有区别的球放到k个相同的盒子中,要求没有空盒的方案总数。

(1) S(p,0)=0(p>=1)

(2) S(p,p)=1(p>=1)

(3) S(p,1)=1(p>=1)

(4) 1<=k<=p-1。假设前p-1个球都已放好,考察第p个球:

a.单独放在一个盒子里。因为盒子是无区别的,这种情形的方案数为S(p-1,k-1)。

b.放在一个已有球的盒子里。因为盒子是有区别的,所以与第p个球共盒子的球是有区别的,需要选一个盒子放入第p个球。因此这种情形的方案数为kS(p-1,k).

综上,得到第二类斯特林数的递推式

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

未经允许不得转载!第一类斯特林数和第二类斯特林数

update

纸上得来终觉浅, 绝知此事须躬行。