第二类Stirling数S(n,4)的表达式

S(n,4)表示把n个有区别的元素分到4个无区别的非空集合里面的方法数
可以用斯递推式解决：
S(n,k) = k*S(n-1,k) + S(n-1,k-1)；S(n,1)=1（n≥1）,S(n,n)=1.
上面的递推式可以用组合证明：一方面,如果将元素1单独拿出来划分成1个集合,那么方法数是S(n-1,k-1)；另一方面,如果元素1所在的集合不止一个元素,那么可以先将剩下的n-1个元素划分好了以后再选一个集合把1放进去,方法数是k*S(n-1,k)；有加法原理得证.
当然,第二类斯特林数还有一个通式：
S(n,k)= Sigma(j=1 to k) [(-1)^{k-j}*j^{n-1}]/[(j-1)!*(k-j)!]
= 1/k!* Sigma(j=0 to k) (-1)^{k-j}j^n*C(k,j)
展开就是
S(n,4)=[(4^{n-1}-3^{n-1})-(4^{n-1}-2^{n-1})+(4^{n-1}-1^{n-1})/3]/2