在某公司的笔试中碰到了一道题，隐约感觉以前学过但是记不得。后来一查原来是Catalan数..... 例题：给一个凸n边形，用n-3条不相交的对角线把它分成n-2个三角形，求不同的方法数目。例如，n=5时，有5种剖分方法。 设答案为f（n），按照某种顺序给凸多边形的各个顶点编号为V1，V2，。。。Vn，既然分成的是三角形，边V1Vn在最终的剖分中一定恰好属于某个三角形V1VnVk，所以可以根据k进行分类。不难看出，三角形V1VnVk的左边是一个k边形，右边是一个n-k+1边形。 根据乘法原理，包含三角形V1VnVk的方案数为f(k)f(n-k+1)：根据加法原理有： f(n)=f(2)f(n-1)+f(3)f(n-2)+...+f(n-1)f(2) 边界是f(2) = f(3) = 1.不难算出从f(3) 开始的前几项f值依次为:1,2,5,14,42,132,429,1430,4862,16796. 在建立递推式时，经常会用到乘法原理，其核心是分步计数。如果可以把计数分成独立的两个步骤，则总数量等于两步计数之乘积。 另一种思路是考虑V1连出的对角线。对角线V1Vk把凸n边形分成两部分，一部分是k边形，另一部分是n-k+2边形。根据乘法原理，包含对角线V1Vk的凸多边形有f(k)(n-k+2)个，根据对称性，考虑从V2、V3、....出发的对角线也会有同样的结果，因此一共有 n(f(3)f(n-1) + f(4)f(n-2) + ... +f(n-1)f(3))个部分。 但这并不是正确答案，因为同一个剖分被重复计算了多次！不过这次不必取消除重复了，因为这些重复很有规律，每个方案恰好被计算了2n-6次-有n-3条对角线，而考虑每条对角线的每个端点时均计算了一次，这样，得到了f(n)的第2个递推式： f(n)=(f(3)f(n-1) +f(4)(n-2) + ... + f(n-3)(3)) * n/ (2n-6) 它和第一个递推式有几分相似，但又不同。把n+1代入第i个递推式得到： f(n+1) = f(2)f(n) + f(3)f(n-1) + f(4)f(n-2) + ... + f(n-1)f(3) + f(n)(2) 黑 {MOD}部分是相同的！根据第2个递推式，它等于f(n) * （2n-6）/n，把它和f(2)=1一起代入上式得： 这个递推式和前两个相比就简单多了，这个数列称为Catalan数，也是常见的计数数列。 伯努利数是18世纪瑞士数学家伯努利引入的一个数，在数学上，伯努利数是一个有理数序列，在许多领域都有很大的应用。伯努利数在数论中很有用，伯努利数还可用于费马大定理的论证中。 重要应用：求前n项和。 用伯努利数进行求解。