Catalan数（卡特兰数）
实际问题
- 有 $2n$ 个人排成一行进入剧场。入场费 $5$ 元。其中只有 $n$ 个人有一张 $5$ 元钞票，另外 $n$ 人只有 $10$ 元钞票，剧院无其它钞票，问有多少种方法使得只要有 $10$ 元的人买票，售票处就有 $5$ 元的钞票找零？
- 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
- 在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
- 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
- 一个栈（无穷大）的进栈序列为 $1,2,3,\cdots,n$ 有多少个不同的出栈序列？
- $n$ 个结点可构造多少个不同的二叉树？
- $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2,a_3,\cdots ,a_n$，其部分和满足 $a_1+a_2+\cdots+a_k \le 0(k=1,2,3,\cdots ,2n)$ 对与 $n$ 该数列为？
公式及其推导
$h_n$ 表示Catalan数列的第 $n$ 项。
递推公式：
$$\displaystyle \begin{align}h_n & = h_{0}h_{n-1}+h_{1}h_{n-2}+ \cdots +h_{n-1}h_0 \\ & =\sum^{n-1}_{k=0}h_k*{h_n-1-k} \\ & =\frac{4n−2}{n+1}h_{n−1} \\ & (h_0=1,h_1=1)\end{align}$$
通项公式：
$$\displaystyle \begin{align} h_n & =\frac{1}{n+1}\mathrm{C}_{2n}^n \\ &=\mathrm{C}_{2n}^n-\mathrm{C}_{2n}^{n-1} \\ & =\sum^{n-1}_{i=0}h_ih_{n-i-1} \\ & (h_0=1,h_1=1) \end{align}$$
其前几项为（从第 $0$ 项开始）：$1,1,2,5,14,42\cdots$
这里我们以实际问题4为例：当 $n=4$ 时，凸多边形为凸六边形时，能够画出 $3$ 条不相交的对角线，能够找出 $4$ 种不同的画法。
每次在连接完一条不相交的对角线时，可以看到这条对角线将一个空间分割成了两部分，我们设其中的一个部分有 $k+2$ 条边，那么这一部分就可以使用对角线分割成 $k$ 个三角形，另一块就有 $n+1-k$ 条边，就可以分割成 $n-1-k$ 个三角形，根据乘法原理，这样的分割方案数是 $h_k*h_{n-1-k}$ ，因为 $k$ 可以从 $0$ 一直变化到 $n-1$ ，所以得到了上述递推公式。
但是对于通项问题，该案例需要使用生成函数的知识，为降低知识难度，我们更换案例分析。
现在以实际问题7为例：我们规定，如果 $n$ 个 $+1$ 和 $n$ 个 $-1$ 的序列满足部分和都不小于等于 $0$ ，那么我们称其为可接受的，否则为不可接受的。令$\mathrm{A}_n$为$ n$ 个 $+1$ 和 $n$ 个 $-1$ 形成的可接受序列的个数，令$\mathrm{U}_n$为不可接受的序列个数，我们尝试计算出$\mathrm{A}_n+\mathrm{U}_n$的值和$\mathrm{U}_n$的值以得到$\mathrm{A}_n$的值。其中：
$$\mathrm{A}_n+\mathrm{U}_n=\mathrm{C}^n_{2n}$$
该处符号$\mathrm{C}$表示组合数。
对于任意一个不可接受的数列中一定存在一个最小的 $k$ ，使得 $a_1+a_2+a_3+\cdots +a_k \lt 0$ ，于是我们可以得出结论： $k$ 是一个奇数，否则上述和只能等于零或更小的负数，矛盾； $a_k$ 一定是 $-1$ ，否则 $k$ 不满足最小的要求；前 $k-1$ 个数中 $+1$ 和 $-1$ 的个数恰好各占一半。我们将这 $k$ 个数取相反数，后面的数字不变，由此得到了一个有 $n+1$ 个 $+1$ 和 $n-1$ 个 $-1$ 的数列，我们只需要找到最小的 $k'$ ，满足 $a_1+a_2+a_3+\cdots +a_{k'} \gt 0$ ，然后将前 $k$ 个数取反即可得到原数列，所以不可接受的序列和有 $n+1$ 个 $+1$ 和 $n-1$ 个 $-1$ 的数列是一一对应的，故：
$$\displaystyle \begin{align}\mathrm{U}_n & = \mathrm{C}_{2n}^{n+1} \\ & = \frac{n}{n+1}\mathrm{C}_{2n}^n \end{align}$$
最终得到通项公式。
第二类Stirling数（第二类斯特林数）
第一类和第二类Stirling数都是基于对查分数列的研究，但第一类Stirling数对信息学竞赛中几乎没有用处，故略去。
实际问题
- 把 $n$ 个不同的数划分为 $m$ 个集合的方案数，要求不能为空集。其中，所有集合完全相同，互不区分。
公式及其推导
第二类Stirling数记作$\begin{Bmatrix} n \\ k \end{Bmatrix}$，或 $\mathrm{S}(n,k)$ ，表示 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。
递推公式：
$$\begin{align} \mathrm{S}(n,k) & =k \times \mathrm{S}(n-1,k)+\mathrm{S}(n-1,k-1) \\ \mathrm{S}(n,1) & =1 , n \ge 1 \\ \mathrm{S}(n,n) & =1 \end{align}$$
通项公式：
$$\displaystyle \mathrm{S} (n,k)=\sum^m_{i=0} \frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
假设现在有 $n$ 个元素的集合，对于第 $n$ 个元素，我们有两种处理方法，第一是将第 $n$个元素单独拿出来划分成一个集合的方法数是 $\mathrm{S}(n-1,k-1)$ ，第二是将剩下 $n-1$ 个元素划分好后，将元素 $n$ 放入其中一个分好的集合中，方法数是 $k \times \mathrm{S}(n-1,k)$ 。故得到递推公式
对于通项公式的证明，需要二项式反演的知识基础，未来会补充。
