卡塔兰数

✍ dations ◷ 2025-09-16 09:36:05 #整数数列,阶乘与二项式主题,置换,随机矩阵

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。

卡塔兰数的一般项公式为

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!n!}}$ 的另一个表达形式为

$C_{n}={2n \choose n}-{2n \choose n+1}\quad {\mbox{ for }}n\geq 1$ 是一个自然数；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。（见https://en.wikipedia.org/wiki/Catalan_number#Second_proof。）

递推关系：

它也满足

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

卡塔兰数的渐近增长为

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

所有的奇卡塔兰数都满足 $n=2^{k}-1$ 令1表示进栈，0表示出栈，则可转化为求一个位、含个1、个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含个1、个0的位二进制数共有 ${2n \choose n}$ 个1、个0的2n位二进制数，扫描到第位上时有个0和个1（容易证明一定存在这样的情况），则后面的0-1排列中必有个1和个0。将及其以后的部分0变成1、1变成0，则对应一个个0和个1的二进制数。反之亦然（相似的思路证明两者一一对应）。

从而 $C_{n}={2n \choose n}-{2n \choose n+1}={\frac {1}{n+1}}{2n \choose n}$ 的取值为多少，×的汉克尔矩阵: $A_{i,j}=C_{i+j-2}.\$ = 4 时我们有

进一步，无论的取值为多少，如果矩阵被移动成 $A_{i,j}=C_{i+j-1}.\$ = 4 时我们有

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

相关

大成蓝大成蓝，又称大成蓝布，是一个中国土布的品牌。得名于在清末嘉庆、道光年间创立于上海，后来发展到浙江、广州等地的林大成布庄。其出产的染色土布因质地坚固，耐洗耐晒而畅销全国以
弗朗索瓦一世弗朗索瓦一世，可能为以下历史人物：
己烷己烷，化学式C6H14，是烷烃中的第六个成员。己烷是常用的非极性具汽油味的有机溶剂，被广泛应用于色谱法中。正己烷作为良好的有机溶剂，被广泛使用在化工有机合成，机械设备表面清洗
望远镜放大倍数光学望远镜的放大倍数是指被观测物体的张角，在经过望远镜的光学系统后被扩大多少倍。比如1000米外一个1米大小的物体，肉眼直接观测时，其张角约为0.001弧度；用放大倍数为10倍的望
俄罗斯形式主义俄罗斯形式主义，是指二十世纪10年代到30年代时期，在俄国盛行的一个有影响的文艺评论流派。它包含了许多颇具影响的俄国和苏联学者的作品，例如维克托·什克洛夫斯基、提尼雅诺夫
皇帝新脑《皇帝新脑——有关电脑、人脑及物理定律》（英语：）是数学物理学家罗杰·潘洛斯1989年出版的一本关于人工智能科普读物。
博茨瓦纳经济博茨瓦纳经济在1966至1999年间每年平均增长9%左右，私人机构就业人数每年平均增长约10%。21世纪初，经济陷入停滞，直到2010年代初国内生产总值增长率才恢复到6-7％。博茨瓦纳是世界
杰森杰森（Jason）可以指：
轰炸鲁尔水坝记《轰炸鲁尔水坝记》（英语：The Dam Busters，又译《敌后大爆破》）是于1955年上映的英国战争片，本片根据真实故事改编，由于本片故事是一连串军事机密的秘密作战，所以并没有很详细，公元2
米格尔·穆诺兹米基尔·穆诺兹·莫桑（西班牙语：Miguel Muñoz Mozún，1922年1月19日－1990年7月16日），出生于马德里，逝世亦在马德里。是一名西班牙足球运动员及教练。他职业身涯大部分时间都在皇家