卡特兰数（catalan number）

青旅半醒 2022-04-14 02:16 241阅读 0赞

### 1.  卡特兰数是什么 ###

**卡塔兰数**是[组合数学][Link 1]中一个常在各种计数问题中出现的[数列][Link 2]。

公式为 ： ![C\_n = \\frac\{1\}\{n+1\}\{2n \\choose n\} = \\frac\{(2n)!\}\{(n+1)!n!\}][C_n _ _frac_1_n_1_2n _choose n_ _ _frac_2n_n_1_n]

前几项为 （n=0,1,2,3,4,5时）:     1, 1, 2, 5, 14, 42

![catalan3.jpg][] n=3时，C 3＝5

### 2. 应用 ###

2.1    一个栈的进栈次序为1、2、3……n。有多少种不同的出栈次序？

当 ![n=3][n_3] 时，有如下5种不同的入出栈顺序

![20181123110826719.jpg][]

2.2   有n个结点，总共能构成几种不同的二叉树？

当 ![n=3][n_3] 时，有如下5种不同的二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70][]

2.3  其它常见问题

1.n对括号有多少种匹配方式？

2.在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？  
      3.求一个凸多边形区域划分成三角形区域的方法数？  
      4.有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？

### 3 .参考 ###

应用例子参见：[https://zhuanlan.zhihu.com/p/31317307][https_zhuanlan.zhihu.com_p_31317307]

[Link 1]: https://zh.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E6%95%B8%E5%AD%B8
[Link 2]: https://zh.wikipedia.org/wiki/%E6%95%B0%E5%88%97
[C_n _ _frac_1_n_1_2n _choose n_ _ _frac_2n_n_1_n]: https://wikimedia.org/api/rest_v1/media/math/render/svg/57de4926a69e67cdcdf999030c5ec3c25d97b0c9
[catalan3.jpg]: /images/20220414/871dac1f5a4f4a4c81d45566fb9f1174.png
[n_3]: /images/20220414/cc6b0c8ec5fc4faf9b14597307665c88.png
[20181123110826719.jpg]: /images/20220414/9cec2e7141d54972bf2f1c6cd95b31ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70]: /images/20220414/36885a06d69848a29ee38261c62669e2.png
[https_zhuanlan.zhihu.com_p_31317307]: https://zhuanlan.zhihu.com/p/31317307