---

卡特兰数

卡特兰数的推导：
卡特兰数（Catalan）

应用场景

1. 假设有n个左括号和n个右括号，他们有多少种合法的组合。
   一共有C(2n,n)种组合，假设这些组合为A集合。
   对于不合法的组合，一定有一个前缀，其右括号数量比左括号数量多1个，比如())(()中前缀())，而后缀一定是右括号比左括号少1一个(()，我们将后缀反转（左括号变右括号，右括号变左括号），这样就变成了整个组合中右括号为n+1，左括号为n-1。反转后一共有C(2n,n-1)种组合，假设他们为B集合。
   A中不合法的组合可以通过反转推出B集合中所有的情况，而B集合也可以通过反转推出A中不合法的组合。因此A中不合法的数量就等于C(2n,n-1)。
   综上，合法的组合一共有C(2n,n)-C(2n,n-1)种。

2. n个数有多少种合法的进出栈方式。
   任何一个前缀出栈数量一定是少于进栈数量，因此这个问题就转化成了上面的括号问题。其组合方式也是C(2n,n)-C(2n,n-1)种。

3. 一共有n个节点，有多少种组成二叉树的方式。
   有0个节点，方式为空树，组成二叉树的方式1种。
   有1个节点，树为它自己，1种。
   有2个节点，根+左或者根+右，2种。
   有n个节点，选一个节点为头节点；头节点左边0个节点，右边n-1个节点；头结点左边1个节点，右边n-2个节点；头结点左边2个节点，右边n-3个节点。。。 可以推出k(n)=k(0)*k(n-1)+k(1)*k(n-2)+....+k(n-2)*k(1)+k(n-1)*k(0)，也就是卡特兰数C(2n,n)-C(2n,n-1)种组合方式。