查看“︁卡塔兰数”︁的源代码

[[File:Mingantu's Catalan numbers.JPG|thumb|400px|[[明安圖|明安图]]《割圜密率捷法》卷三 “卡塔兰数”书影]]
[[File:Catalan number.png|thumb|400px|卡塔兰数]]
'''卡塔兰数'''（{{lang-en|Catalan number}}）是[[組合數學]]中一個常在各種計數問題中出現的[[數列]]，以[[比利時]]數學家[[欧仁·夏尔·卡塔兰]]命名。历史上，[[清朝]]数学家[[明安图]]在其《[[割圜密率捷法]]》中最先发明这种计数方式，早于卡塔兰<ref>吴文俊主编 《[[中国数学史大系]]》第7卷 474-475页</ref><ref>{{Cite web |url=http://en.cnki.com.cn/Article_en/CJFDTOTAL-NMGX198802004.htm |title=明安图第发明卡塔兰数之第一人 |access-date=2014-06-24 |archive-date=2020-01-31 |archive-url=https://web.archive.org/web/20200131101929/http://en.cnki.com.cn/Article_en/CJFDTOTAL-NMGX198802004.htm |dead-url=no }}</ref><ref>{{Cite web |url=http://www.math.ucla.edu/~pak/lectures/Cat/Larcombe-The_18th_century_Chinese_discovery_of_the_Catalan_numbers.pdf |title=中国人在18世纪发现卡塔兰数 |access-date=2014-06-24 |archive-date=2021-02-24 |archive-url=https://web.archive.org/web/20210224043753/https://www.math.ucla.edu/~pak/lectures/Cat/Larcombe-The_18th_century_Chinese_discovery_of_the_Catalan_numbers.pdf |dead-url=no }}</ref>。有中国学者建议将此数命名为“'''明安图数'''”或“'''明安图-卡塔兰数'''”<ref>[[吴文俊]]主编 《中国数学史大系》 第七卷 476页</ref>。

卡塔兰数的一般項公式為

<math>C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}</math>

第0項到第19項的卡塔兰数為：{{數列|$, |0|19|binomial(2*x,x)/(x+1)}}...{{OEIS|id=A000108}}

== 性质 ==

''C''<sub>''n''</sub>的另一个表达形式为

<math>C_n = {2n\choose n} - {2n\choose n+1} \quad\mbox{ for }n\ge 1</math>，

所以，''C''<sub>''n''</sub>是一个[[自然数]]；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。

[[递推关系]]：<ref>{{Cite journal|title=Counting symmetry classes of dissections of a convex regular polygon|url=https://linkinghub.elsevier.com/retrieve/pii/S0196885814000219|last=Bowman|first=Douglas|last2=Regev|first2=Alon|date=2014-05|journal=Advances in Applied Mathematics|doi=10.1016/j.aam.2014.01.004|volume=56|pages=35–55|language=en|access-date=2020-02-23|archive-date=2020-02-23|archive-url=https://web.archive.org/web/20200223015810/https://linkinghub.elsevier.com/retrieve/pii/S0196885814000219|dead-url=no}}</ref>

:<math>C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\mbox{for }n\ge 0.</math>

它也满足
:<math>C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,</math>
这提供了一个更快速的方法来计算卡塔兰数。

卡塔兰数的渐近增长为
:<math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}</math>
它的含义是当''n''&nbsp;→&nbsp;∞时，左式除以右式的商[[极限|趋向于]]1。（这可以用''n''!的[[斯特灵公式]]来证明。）

所有的奇卡塔兰数''C''<sub>''n''</sub>都满足<math>n=2^k-1</math>。所有其他的卡塔兰数都是偶数。

而且

<math>C_n = \int_0^4 x^n \frac{1}{2\pi} \sqrt{4/x - 1} \mathrm{d}x</math>

== 母函数 ==
{{Main|母函数}}
若'''卡塔兰数'''的[[母函数]]是

<math>M(z) = \sum C_n z^n</math>

则<ref>{{Cite mathworld|title=Catalan Number|urlname=CatalanNumber|accessdate=2020-02-23|language=en|archive-date=2019-06-18|archive-url=https://web.archive.org/web/20190618193524/http://mathworld.wolfram.com/CatalanNumber.html|dead-url=no}}</ref>

<math>M(z) = 1 + zM(z)^2</math>

解是

<math>M(z) = \frac{1-\sqrt{1-4z}}{2z}</math>

== 应用 ==

[[组合数学]]中有非常多的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。以下用n=3和n=4举若干例：

* ''C''<sub>''n''</sub>表示长度''2n''的{{Internal link helper/en|dyck word|Dyck word}}<ref>{{Cite web|title=DyckPaths|url=http://www.findstat.org/DyckPaths|accessdate=2020-02-23|author=|date=|format=|work=www.findstat.org|publisher=|language=|archive-date=2020-12-03|archive-url=https://web.archive.org/web/20201203194735/https://www.findstat.org/DyckPaths|dead-url=no}}</ref>的个数。Dyck词是一个有''n''个X和''n''个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
<center>XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY</center>

* 将上例的X换成左括号，Y换成右括号，''C''<sub>''n''</sub>表示所有包含''n''组括号的合法运算式的个数：
<center>((())) ()(()) ()()() (())() (()())</center>

* ''C''<sub>''n''</sub>表示有''n''个节点组成不同构[[二叉树]]的方案数。下图中，''n''等于''3''，圆形表示节点，月牙形表示什么都没有。

* ''C''<sub>''n''</sub>表示有''2n+1''个节点组成不同构满[[二叉树]]的方案数。下图中，''n''等于''3''，圆形表示内部节点，月牙形表示外部节点。本质同上。
[[File:Catalan_number_binary_tree_example.png|center]]

'''证明'''''：''令1表示进栈，0表示出栈，则可转化为求一个''2n''位、含''n''个1、''n''个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含''n''个1、''n''个0的''2n''位二进制数共有<math>{2n \choose n}</math>个，下面考虑不满足要求的数目。

考虑一个含''n''个1、''n''个0的2n位二进制数，扫描到第''2m+1''位上时有''m+1''个0和''m''个1（容易证明一定存在这样的情况），则后面的0-1排列中必有''n-m''个1和''n-m-1''个0。将''2m+2''及其以后的部分0变成1、1变成0，则对应一个''n+1''个0和''n-1''个1的二进制数。反之亦然（相似的思路证明两者一一对应）。

从而<math>C_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n+1}{2n \choose n}</math>。证毕。

* ''C''<sub>''n''</sub>表示所有在''n'' × ''n''格点中不越过对角线的'''单调路径'''的个数。一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数：X代表“向右”，Y代表“向上”。下图为''n'' = 4的情况：
[[File:Catalan number 4x4 grid example.svg|450px|center]]

* ''C''<sub>''n''</sub>表示通过连结顶点而将''n''&nbsp;+&nbsp;2边的[[凸多边形]]分成[[三角形]]的方法个数。下图中为''n'' = 4的情况：
[[File:Catalan-Hexagons-example.svg|400px|center]]

* ''C''<sub>''n''</sub>表示对{1, ..., ''n''}依序进出[[栈]]的[[置换]]个数。一个置换''w''是依序进出栈的当''S''(''w'') = (1, ..., ''n''),其中''S''（''w''）递归定义如下：令''w'' = ''unv''，其中''n''为''w''的最大元素，''u''和''v''为更短的数列；再令''S''(''w'') = ''S''(''u'')''S''(''v'')''n''，其中''S''为所有含一个元素的数列的单位元。

* ''C''<sub>''n''</sub>表示集合{1, ..., ''n''}的{{Internal link helper/en|不交叉划分|Noncrossing partition}}的个数。那么, ''C''<sub>''n''</sub>永远不大于第''n''项[[贝尔数]]. ''C''<sub>''n''</sub>也表示集合{1, ..., 2''n''}的[[不交叉划分]]的个数，其中每个段落的长度为2。综合这两个结论，可以用[[数学归纳法]]证明：在 [[魏格纳半圆分布定律]] 中度数大于2的情形下，所有 ''自由的'' [[累积量]]s 为零。 该定律在{{Internal link helper/en|自由概率论|Free probability theory}}和[[随机矩阵]]理论中非常重要。

* ''C''<sub>''n''</sub>表示用''n''个长方形填充一个高度为''n''的阶梯状图形的方法个数。下图为''n''&nbsp;=&nbsp;4的情况：
[[File:Catalan stairsteps 4.svg|400px|center]]

* ''C''<sub>''n''</sub>表示表为2×''n''的矩阵的标准[[杨氏矩阵]]的数量。 也就是说，它是数字 1,&nbsp;2,&nbsp;...,&nbsp;2''n'' 被放置在一个2×''n''的矩形中并保证每行每列的数字升序排列的方案数。同样的，该式可由[[杨氏矩阵|勾长公式]]的一个特殊情形推导得出。

* ''C''<sub>''n''</sub>表示''n''个无标号物品的[[半序]]的个数。

== 汉克尔矩阵 ==

无论''n''的取值为多少，''n''×''n''的[[汉克尔矩阵]]:<math>A_{i,j} = C_{i + j - 2}.\ </math>的[[行列式]]为1。例如，''n'' = 4 时我们有
:<math>\det\begin{bmatrix}1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132\end{bmatrix} = 1</math>。

进一步，无论''n''的取值为多少，如果矩阵被移动成<math>A_{i,j} = C_{i + j - 1}.\ </math>，它的行列式仍然为1。例如，''n'' = 4 时我们有
:<math>\det\begin{bmatrix}1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \\ 14 & 42 & 132 & 429 \end{bmatrix} = 1</math>。

同时，这两种情形合在一起唯一定义了卡塔兰数。

==参考文献==
<references/>

[[Category:整数数列|K]]
[[Category:阶乘与二项式主题]]
[[Category:置换]]
[[Category:随机矩阵]]