Most Important Formulas

以下部分来自http://lanqi.org/skills/10939/

$C(n)=C_{2n}^n-C_{2n}^{n-1}$

Problem
对于 $\{1,2,..,n\}$ 的进栈序列，有多少合法的出栈序列。

Solution
把进出栈看作事件，进栈记 $1$ ，出栈记 $-1$ ，则一个事件序列的任意前缀和都 $\ge 0$ 首先有 $n$ 个 $1$ ，先不管是否合法，只管总个数，那么序列的数目为 $C_{2n}^n$ 要从中减去不合法的，这样考虑：每个不合法的序列，最先不合法的位置 $i$ ，一定是前缀和为 $-1$ ， $-1$ 比 $1$ 多了一个那么把 $1..i$ 的数字全部取反，整个序列就有 $n+1$ 个 $1$ ， $n-1$ 个 $-1$ 。记不合法的方案集合为 $I$ ，存在 $n+1$ 个 $1$ ， $n-1$ 个 $-1$ 的序列集合为 $S$ ，现在要证明的是 $I$ 中的元素与 $S$ 中的元素构成一一映射。首先， $\forall i \in I$ ，可以转换为唯一的 $s \in S$ 而对于 $\forall s \in S$ ，如果从第二个前缀和为 $1$ 的位置 $j$ 开始取反，那取反后第一个前缀和为 $-1$ 的位置必然不是 $j$ ，那这种不合法方案转化出对应的 $s' \in S \neq s$ ，所以 $\forall s\in S$ 一定唯一对应 $i\in I$ 。即不合法的方案数为 $C_{2n}^{n-1}$

Another Example
(搜到的一个解说三角划分方案数的图，似乎来自一个被封的csdn博客) 这样可以把三角划分转化为划分序列连乘顺序序列连乘顺序可以转化为合法括号序列数目然后就可以解决了

Tips
Catalan数是用映射来解决计数问题的。当有某种属性的方案不好统计的时候，就把这种方案的集合与其它比较容易统计的方案建立一一映射。这种转化思路大概即为其巧妙之处吧。
$C(n+1)=\sum\limits_{i=0}^nC(i)C(n-i),C(0)=1$

Problem
圆周上有 $2n$ 个点，以这些点为端点连互不相交的 $n$ 条弦，求不同连法的总数

Solution
考虑DP。设 $f(i)$ 表示 $i$ 个点时的答案，则 $f(0)=1$ ，答案为 $f(2n)$ 。显然，任意弦的两端点之间的优弧和劣弧上都一定有偶数个点所以， $f(i)=f(0)f(i-2)+f(2)f(i-4)+f(4)f(i-6)+..+f(i-2)f(2)$ 将 $2n$ 代入， $f(2n)=f(0)f(2n-2)+f(2)f(2n-4)+f(4)f(2n-6)+..+f(2n-2)f(0)$ 考虑Catalan数的递推式 $C(n)=C(0)C(n-1)+C(1)C(n-2)+C(2)C(n-3)+...+C(n-1)C(0)$ 可以看出 $f(2n)==C(n)$

Other Examples

$n$ 个顶点的不同二叉树的个数是 $C(n)$ 。
$2n$ 个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，排列方式有 $C(n)$ 种
设 $a_1,a_2,...,a_n$ $a 1 , a 2 , . . ., a n $ 为整数，且满足下列条件:
- $a_1\le 1,a_2\le 2,...,a_n\le n$ 则 $a_1,a_2,...,a_n$ 满足上述条件的序列的个数是 $C(n)$
设 $a_1,a_2,...,a_n$ 与 $b_1,b_2,...,b_n$ 是两个完全不同的序列，则把这两个序列归并组成一个新的序列，恰有 $k$ 个逆序的方案数是 $C(n)$ （一个逆序是指 $a_i$ 排在 $b_i$ 的后面）。（想了很长时间不知道怎么证明）

Most Important Formulas

Problem

Solution

Another Example

Tips

Problem

Solution

Other Examples