Zoj 3344 （第一类斯特林数）附第二类斯特林数和Bell数的总结

斯特林数）附第二类斯特林数和Bell数的总结"/>

Zoj 3344 （第一类斯特林数）附第二类斯特林数和Bell数的总结

题意：有个游戏，两个人玩。有n个卡片，洗牌后放入编号为1到n的盒子里，然后两个人轮流做如下操作，拿出盒子中编号最小的卡片k，然后再去编号为k的盒子中拿出卡片，依次类推，直到没有卡片可拿为止。拿走最后一张卡片的玩家获胜。求先手能够在K次操作以内获胜的概率，（以分数形式输出）

思路：就是一个第一类斯特林数，然而并不会斯特林数，学习了一波，先上代码，下面是对第一第二类斯特林数，还有Bell数的总结。

这题要用大数，所以用java写

import java.io.*;
import java.math.*;
import java.util.*;import sun.management.GcInfoCompositeData;public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger dp[][] = new BigInteger[55][55];BigInteger f[] = new BigInteger[55];for(int i = 1; i <= 50; i++){dp[i][0] = BigInteger.valueOf(0);dp[i][i] = BigInteger.valueOf(1);for(int j = 1; j < i; j++){dp[i][j] = dp[i-1][j].multiply(BigInteger.valueOf(i-1));dp[i][j] = dp[i][j].add(dp[i-1][j-1]);}}f[0] = BigInteger.valueOf(1);for(int i = 1; i <= 50; i++){f[i] = f[i-1].multiply(BigInteger.valueOf(i));}while(cin.hasNext()){int n,k;BigInteger sum,g;n = cin.nextInt();k = cin.nextInt();sum = BigInteger.valueOf(0);for(int i = 1; i <= k; i += 2){sum = sum.add(dp[n][i]);}g = sum.gcd(f[n]);System.out.println(sum.divide(g)+"/"+f[n].divide(g));}}}

一.第一类斯特林数

定义：第一类Stirling数s(p,k)计数是把p个对象的排成k个非空循环排列的方法数。

s(p,p) = 1 (p>=0) 有p个人和p个循环，每个循环只有一个人。

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

分两种情况：

1.一个循环只有p自己,排法有s(p-1,k-1);

2.p至少和另一个人在循环里，这样可以先把1，2，...，p-1排好，再把p放到任何一个的左边，这样就有(p-1)*s(p-1,k);

所以s(p,k) = s(p-1,k-1)+(p-1)*s(p-1,k);

二.第二类斯特林数

定义：第二类Stirling数s(p,k)计数的是把p元素集合划分到k个不可区分的盒子里且没有空盒子的划分数。

s(p,p) = 1;

s(p,0)  = 0;

和第一类斯特林数一样，同样分两种情况

1.p单独在一个盒子里的划分有s(p-1,k-1)种情况

2.p不单独在一个盒子里，首先对剩下的p-1个盒子进行划分，有s(p-1,k)种情况，再把p任意的放到k个划分里，有k中选择。所以一共有k*s(p-1,k)种情况。

所有s(p,k) = s(p-1,k-1)+k*s(p-1,k);

三.Bell数

定义：Bell数B(p)是将p元素集合划分到非空且不可区分的盒子的划分数（没有说分到几个盒子里面）

B(p) = s(p,0)+s(p,1)+……+s(p,k);

所有要先求出第二类斯特林数。