卡塔兰数

维基百科,自由的百科全书
跳转至: 导航搜索
明安图《割圜密率捷法》卷三 “卡塔兰数”书影
卡塔兰数

卡塔兰数組合數學中一個常在各種計數問題中出現的數列。以比利時的數學家欧仁·查理·卡塔兰18141894)命名。历史上,清代数学家明安图(1692年-1763年)在其《割圜密率捷法》最早用到“卡塔兰数”,远远早于卡塔兰[1][2][3]。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”[4]

卡塔兰数的一般項公式為 C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}

前100項為(OEIS中的数列A000108):


  *                             C[1] = 1
  *                             C[2] = 1
  *                             C[3] = 2
  *                             C[4] = 5
  *                            C[5] = 14
  *                            C[6] = 42
  *                            C[7] = 132
  *                            C[8] = 429
  *                           C[9] = 1430
  *                           C[10] = 4862
  *                          C[11] = 16796
  *                          C[12] = 58786
  *                          C[13] = 208012
  *                          C[14] = 742900
  *                         C[15] = 2674440
  *                         C[16] = 9694845
  *                         C[17] = 35357670
  *                        C[18] = 129644790
  *                        C[19] = 477638700
  *                        C[20] = 1767263190
  *                        C[21] = 6564120420
  *                       C[22] = 24466267020
  *                       C[23] = 91482563640
  *                       C[24] = 343059613650
  *                      C[25] = 1289904147324
  *                      C[26] = 4861946401452
  *                      C[27] = 18367353072152
  *                      C[28] = 69533550916004
  *                     C[29] = 263747951750360
  *                     C[30] = 1002242216651368
  *                     C[31] = 3814986502092304
  *                    C[32] = 14544636039226909
  *                    C[33] = 55534064877048198
  *                    C[34] = 212336130412243110
  *                    C[35] = 812944042149730764
  *                   C[36] = 3116285494907301262
  *                   C[37] = 11959798385860453492
  *                   C[38] = 45950804324621742364
  *                  C[39] = 176733862787006701400
  *                  C[40] = 680425371729975800390
  *                  C[41] = 2622127042276492108820
  *                 C[42] = 10113918591637898134020
  *                 C[43] = 39044429911904443959240
  *                 C[44] = 150853479205085351660700
  *                 C[45] = 583300119592996693088040
  *                C[46] = 2257117854077248073253720
  *                C[47] = 8740328711533173390046320
  *                C[48] = 33868773757191046886429490
  *               C[49] = 131327898242169365477991900
  *               C[50] = 509552245179617138054608572
  *               C[51] = 1978261657756160653623774456
  *               C[52] = 7684785670514316385230816156
  *              C[53] = 29869166945772625950142417512
  *              C[54] = 116157871455782434250553845880
  *              C[55] = 451959718027953471447609509424
  *             C[56] = 1759414616608818870992479875972
  *             C[57] = 6852456927844873497549658464312
  *             C[58] = 26700952856774851904245220912664
  *            C[59] = 104088460289122304033498318812080
  *            C[60] = 405944995127576985730643443367112
  *            C[61] = 1583850964596120042686772779038896
  *            C[62] = 6182127958584855650487080847216336
  *           C[63] = 24139737743045626825711458546273312
  *           C[64] = 94295850558771979787935384946380125
  *           C[65] = 368479169875816659479009042713546950
  *          C[66] = 1440418573150919668872489894243865350
  *          C[67] = 5632681584560312734993915705849145100
  *          C[68] = 22033725021956517463358552614056949950
  *          C[69] = 86218923998960285726185640663701108500
  *         C[70] = 337485502510215975556783793455058624700
  *         C[71] = 1321422108420282270489942177190229544600
  *         C[72] = 5175569924646105559418940193995065716350
  *        C[73] = 20276890389709399862928998568254641025700
  *        C[74] = 79463489365077377841208237632349268884500
  *        C[75] = 311496878311103321137536291518809134027240
  *       C[76] = 1221395654430378811828760722007962130791020
  *       C[77] = 4790408930363303911328386208394864461024520
  *       C[78] = 18793142726809884575211361279087545193250040
  *       C[79] = 73745243611532458459690151854647329239335600
  *      C[80] = 289450081175264899454283846029490767264392230
  *      C[81] = 1136359577947336271931632877004667456667613940
  *      C[82] = 4462290049988320482463241297506133183499654740
  *     C[83] = 17526585015616776834735140517915655636396234280
  *     C[84] = 68854441132780194707888052034668647142985206100
  *     C[85] = 270557451039395118028642463289168566420671280440
  *    C[86] = 1063353702922273835973036658043476458723103404520
  *    C[87] = 4180080073556524734514695828170907458428751314320
  *    C[88] = 16435314834665426797069144960762886143367590394940
  *    C[89] = 64633260585762914370496637486146181462681535261000
  *   C[90] = 254224158304000796523953440778841647086547372026600
  *   C[91] = 1000134600800354781929399250536541864362461089950800
  *   C[92] = 3935312233584004685417853572763349509774031680023800
  *  C[93] = 15487357822491889407128326963778343232013931127835600
  *  C[94] = 60960876535340415751462563580829648891969728907438000
  *  C[95] = 239993345518077005168915776623476723006280827488229600
  *  C[96] = 944973797977428207852605870454939596837230758234904050
  * C[97] = 3721443204405954385563870541379246659709506697378694300
  * C[98] = 14657929356129575437016877846657032761712954950899755100
  * C[99] = 57743358069601357782187700608042856334020731624756611000
  * C[100] = 227508830794229349661819540395688853956041682601541047340
  * 
  *

性质[编辑]

Cn的另一个表达形式为C_n = {2n\choose n} - {2n\choose n+1} \quad\mbox{ for }n\ge 1 所以,Cn是一个自然数;这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。)

递推关系

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.

它也满足

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

这提供了一个更快速的方法来计算卡塔兰数。

卡塔兰数的渐近增长为

C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}

它的含义是左式除以右式的商趋向于1当n → ∞。(这可以用n!的斯特灵公式来证明。)

所有的奇卡塔兰数Cn都满足n=2^k-1。所有其他的卡塔兰数都是偶数。

应用[编辑]

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

  • Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
  • 将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
  • Cn表示有n个节点组成不同构二叉树的方案数。下图中,n等于3,圆形表示节点,月牙形表示什么都没有。
  • Cn表示有2n+1个节点组成不同构满二叉树(full binary tree)的方案数。下图中,n等于3,圆形表示内部节点,月牙形表示外部节点。本质同上。
Catalan number binary tree example.png

证明:

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

考虑一个含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的二进制数。反之亦然(相似的思路证明两者一一对应)。

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

  • Cn表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数:X代表“向右”,Y代表“向上”。下图为n = 4的情况:
Catalan number 4x4 grid example.svg
  • Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况:
Catalan-Hexagons-example.svg
  • Cn表示对{1, ..., n}依序进出置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n),其中Sw)递归定义如下:令w = unv,其中nw的最大元素,uv为更短的数列;再令S(w) = S(u)S(v)n,其中S为所有含一个元素的数列的单位元。
  • Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为n = 4的情况:
Catalan stairsteps 4.svg
  • Cn表示表为2×n的矩阵的标准杨氏矩阵的数量。 也就是说,它是数字 1, 2, ..., 2n 被放置在一个2×n的矩形中并保证每行每列的数字升序排列的方案数。同样的,该式可由勾长公式的一个特殊情形推导得出。
  • Cn表示n个无标号物品的半序的个数。

汉克尔矩阵[编辑]

无论n的取值为多少,n×n汉克尔矩阵:A_{i,j} = C_{i + j - 2}.\ 行列式为1。例如,n = 4 时我们有

\det\begin{bmatrix}1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132\end{bmatrix} = 1

进一步,无论n的取值为多少,如果矩阵被移动成A_{i,j} = C_{i + j - 1}.\ ,它的行列式仍然为1。 例如,n = 4 时我们有

\det\begin{bmatrix}1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \\ 14 & 42 & 132 & 429 \end{bmatrix} = 1

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

参考文献[编辑]

  1. ^ 吴文俊主编 《中国数学史大系》第7卷 474-475页
  2. ^ 明安图第发明卡塔兰数之第一人
  3. ^ 中国人在18世纪发现卡塔兰数
  4. ^ 吴文俊主编 《中国数学史大系》 第七卷 476页