错排公式

问题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
递推公式为：D(n) = (n - 1) * [D(n - 1) + D(n - 2)]

海伦公式

S = sqrt(p * (p - a) * (p - b) * (p - c))
公式描述：公式中a，b，c分别为三角形三边长，p为半周长，S为三角形的面积。

组合数公式

公式描述：
组合数公式是指从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。

两点之间的距离公式

公式描述：公式中(x1，y1)，(x2，y2)分别为A、B两个点的坐标。

扇形面积

S=1/2×弧长×半径，S扇=（n/360）πR²

卡特兰数

原理：
　　令h(0)=1,h(1)=1,catalan 数满足递归式：

                          　　(其中n>=2)
　　另类递推公式：
　　　　　 　
　　该递推关系的解为：
　　　　　　 　(n=1,2,3,...)

卡特兰数的应用实质上都是递归等式的应用

前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
所有的奇卡塔兰数Cn都满足n = 2^k-1、所有其他的卡塔兰数都是偶数。

应用

1、12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
2、括号化问题。矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
3、将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数?
4、出栈次序问题。一个栈(无穷大)的进栈序列为1、2、3、...、n，有多少个不同的出栈序列?
5、通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。
6、所有在n*n格点中不越过对角线的单调路径的个数。
7、有n+1个叶子的二叉树的个数。

更多的变化不胜枚举，遇到这类规律题建议使用下一节讲的OEIS来解决问题。

掌握本节内容