Thursday, November 15, 2012

2n个MM围成一圈,求相互接吻而不打扰另一对的方法数

将2n个人从0开始编号,从0到2n-1,从此往后,0只能和奇数号MM接吻,否则和一个偶数号MM发生关系的情况下,她们中间剩下奇数个MM,最后必然落单一个人
假设2n个人共有h(n)种接吻方法,当0号MM和1号MM接吻时,仅剩下2n-2个人,共有h(n-1)种方法,当0号MM和3号MM接吻时,她们的一边有2个人,有h(1)种方法,一边有2n-4个人,有h(n-2)种方法,当0号MM和5号MM接吻时,她们的一边有4个人,有h(2)种方法,一边有2n-6个人,有h(n-3)种方法,。。。。当0号MM和2n-1号MM接吻时,仅剩下2n-2个人,共有h(n-1)种方法。
可见,h(n)=h(0)×h(n-1)+h(1)×h(n-2)+h(2)×h(n-3)+......+h(n-1)×h(0)
这是Catalan数的一种形式,共有C(n,2n)/(n+1)种方法。

No comments:

Post a Comment