天使和魔鬼

东邪

n个天使和m个魔鬼排队进入一个空房间(n>=m)。如果房间里的魔鬼多于天使，天使就会遭殃。

例如，对于11001011011000011001这样的排列（1--天使，0--魔鬼），在第8个魔鬼进去前，天使都是安全的，当第8个魔鬼进去后，魔鬼就比天使多了，天使就会遭殃。

问一：总共有多少种排列，天使不会遭殃？

问二：如果如果进入房间的魔鬼等于或多于天使，天使就会遭殃。又有多少种排列？

问三：更一般情况，如果进入房间的天使个数a-进入房间的魔鬼个数b<某个常数c，天使就会遭殃。又有多少种排列？

winxos

似乎最近这些题目都是ACM题，不过我不会。

shshsh_0510

2# winxos


相当于不超过y=x的从(0,0)到(n,m)的Lattice Path的计数，好像是catalan数吧，你可以用这些关键字查一下。

winxos

http://en.wikipedia.org/wiki/Catalan_number
http://mathworld.wolfram.com/CatalanNumber.html
找到了两个详细的链接，希望对楼主有帮助。

nlrte13

没那么复杂，第一问：
1、若必须天使第一个进入
m=0, 答案 = 1
m=1, 答案 = n
m>1, 答案 = (n-1)*(n+2)/2

2、若天使=0，魔鬼=1时，天使不遭殃，即允许第一个进入魔鬼，则
m=0, 答案=1
m=1, 答案=n+1
m>1, 答案=(n-1)*(n+4)/2

后面两问同样道理可以得出

nlrte13

上面答案不完善，仅是m=n的情况，完整描述应如下：
1、若必须天使第一个进入( ^表示乘方 )
m=0, 答案 = 1
m>0, 答案 = [ 2^(m-1) ] * ( n - m + 1 )
上为2的(m-1)次方

2、若天使=0，魔鬼=1时，天使不遭殃，即允许第一个进入魔鬼，则
m=0, 答案=1
m=1, 答案= [ 2^(m-1) ] * ( n - m + 1 ) + 1
m>1, 答案= [ 2^(m-2) ] * ( n - m + 1 ) * 3

mathe

基本是链接中问题的扩充:
http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid16991