Hello World

数据结构笔记

卡特兰数

应用场景

1. 有2n个人排成一行进入剧场，入场费5元，其中n个人有5元钞票，n个人有10元钞票，剧院无多余钞票。问有多少种方法使得只要有10元人买票，售票处就有5元的钞票找零
2. 一个边长为n的正方形，从左下角走到右上角，不穿过对角线，问有几种不同的方法
3. 圆上选择2n个点，问有多少种方法将这些点两两相连，所得到的n条线段两两不相交
4. 对角线不相交的情况下，将凸n边形分成三角形区域的方法数
5. n个元素进栈，问有多少种出栈方法
6. n个节点可以构造多少个不同的二叉树
7. n个1和n个-1构成2n项序列，问从a1开始，部分和始终大于等于0的序列有多少种

公式

$$
\large f(n)=C_n^{2n}-C_{n-1}^{2n}
$$