Processing math: 100%

嘘~ 正在从服务器偷取页面 . . .

浅谈_


浅谈卡特兰数 (Catalan数)

卡特兰数的定义

卡特兰数是组合数学中一个常在各种计数问题中出现的数列。

卡特兰数的一般项公式为

Cn=1n+1(2nn)=(2n)!n!(n+1)!(nN)

还有以下常见公式 (nN)

C0=1, C1=1Cn=ni=1Ci1Cni,n2Cn=(4n2)Cn1n+1Cn=(2nn)(2nn1)

OEIS A000108

这张表很重要。因为有时候想不出来可以手推前几项猜卡特兰数。

n 0 1 2 3 4 5 6
Cn 1 1 2 5 14 42 132

我们可以用如下代码计算卡特兰数的第 n 项(改不了C++行末分号的习惯了

python
n = int(input()); 
if(n == 0 or n == 1): print(1); exit(0); 
fac = [0 for i in range(2*n+5)]; fac[0]=1; 
for i in range(1, 2*n+1): fac[i] = fac[i-1] * i; 
print(fac[2*n] // (fac[n] * fac[n+1]))

卡特兰数的应用

有好多,这里就列举几个常见的。

1. 合法括号序列(Dyck word)

Cn 表示长度为 2n合法括号序列的个数。

注:a Dyck word is a balanced string of square brackets [ and ].

Dyck word是一个有 nXnY 组成的字串,且所有的前缀字串皆满足 X 的个数大于等于 Y 的个数。

以下为长度为 6 的 Dyck words

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY


2. n×n 的格点中不越过对角线的单调路径

Cn 表示所有 n×n 的格点中不越过对角线的单调路径的个数。

一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右。

计算这种路径的个数等价于计算Dyck word的个数:X代表“向右”,Y代表“向上”。

以下为 n=4 的情况


3. n 个结点的不同构二叉树

Cn 表示 n 个结点的不同构有根二叉树(无标号)的个数。

以下为 n=3 时的情况:


Cn 也能表示 2n+1 个结点的不同构有根满二叉树(无标号)的个数。

以下为 n=3 时的情况。

这里的满二叉树采用国外的定义

国外定义:树上任何结点,如果不是叶子结点,则一定有 2 个儿子。

国内定义:2k1 个结点,第 i(i1) 层有 2i1 个结点。


4. 分割凸多边形

Cn 表示通过连结顶点而将 n+2 条边的凸多边形分成三角形的方法个数

下图为 n=4 的情况


5. 高度为 n 的阶梯状图

Cn 表示用 n 个长方形填充一个高度为 n 的阶梯状图形的方法个数

P2532 [AHOI2012]树屋阶梯

下图为 n=4 的情况


参考文献

[1] https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

[2] https://en.wikipedia.org/wiki/Dyck_language

[3] https://en.wikipedia.org/wiki/Catalan_number

[4] https://oi-wiki.org/math/combinatorics/catalan/

[5] https://oi-wiki.org/topic/bracket/


文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3