http://en.wikipedia.org/wiki/Catalan_number

catalan数的身世,wiki(上面链接)有....那里还提供了5种(?)求法~第一种:母函数,第二种:全体数-非法数,第三种:通过定义一个叫exceedance的玩意,然后通过一个很奇葩的构造,说明exceedance等于0,1,2...n的路径数相等,直接得出结果~第四种是基于卡特兰数在多边形的三角划分的,推出个递推式~第五种是根据递推式,死推~

昨天,上海网赛热身,那题http://acm.hdu.edu.cn/showproblem.php?pid=4015,  是一个很像很像catalan数的玩意~大概是:给你两种数,a,b,权值分别是1和-m , a有k*m+1个,m有k个 , 问有几种排列方法,使得前任意项的和都不为0;

m取1时,就是红果果的catalan数~

m!=1时 ~ 不会..不过又找到了卡特兰数一个牛B的不同于wiki那5种的求法,完全兼容上面那题~这是本文存在的原因~

原文在这里,里面还有好几种别的求法:谷歌文档~偷来了,怕丟不好意思

现在 说说那个求法:

给你n+1个'/'和n个'\'  ,  让你用这些随意的首尾相接组到一起, 一共就C(2n+1,n)种组法,我们要求的是除起点外所有点的海拔都大于0的组合数;

每种(含非法)组法就称为一个pattern , 显然这些pattern有一个性质,最后那点比第一点高出一个单位;

还有一个不那么显然的性质:在连接最后一点和第一点的直线上,没有一个\或/的端点落在上面,这是因为最后那点才是1,落在上面就意味着有分数,这不可能;

高潮来了~现在把两个相同的pattern首位相接,从前面不同的2n+1位开始的2n+1位,一共有2n+1个不同(why?我再想想)的pattern:其中,只有一个是合法的!!!(想象一条斜率为1/(2n+1)的直线从底部缓缓升起)

so~总的合法序列就C(2n+1,n)/(2n+1)个~

用这个来做上面的那道题,没压力啊,连化简都省了,直接出结果啊!~~~