快速排序
概率论快速笔记

卡特兰数

scturtle posted @ 2012年3月17日 11:19 in algorithm , 4298 阅读

引子——括号匹配问题

2n 个'('和')'组成的括号序列, 有多少种合法的组合方法?
把括号从 0 到 2n-1 编号, 合法的序列第 0 个一定是 '(' , 假设第 0 个括号与第 k 个括号匹配, 则序列 [1 ... k-1] 和 [k+1 ... 2n-1] 应也是合法的括号序列, 所以 k 必须是奇数, 设 k=2i+1 , 得公式:

如果换种说法, n 对括号的序列, 可得更简单的公式:

进一步证明

如果 '(' 看做是入栈, ')' 看做是出栈, 则 2n 个括号的合法序列, 一一对应于 2n 步合法的入栈出栈序列.
n 步入栈 n 步出栈的序列总数为 . 对于一个不合法的序列, 一定会在某一步(设为 2i+1 )发现此时遇到的出栈符号数多于入栈符号数, 即遇到了 i 个 '(' 和 i+1 个 ')'. 此时后面还有 n-i 个 '(' 和 n-i-1 个 ')', 如果将后面的 '(' ')' 互换则得到 n-1 步入栈 n+1 步出栈的序列, wikipedia 上说, 两者是一一对应的, 即一个不合法的 n 入 n 出序列(我擦我XE了), 一一对应了一个 n-1 入 n+1 出的序列. 所以可得公式:

化简得方便的计算公式:

应用

有一大票的问题可以归约到卡特兰数上, 看书也经常会看到把这个当做公式用在和式相关的证明中. wikipedia 上说某书列了66个可以归约到卡特兰数的问题(orz). 一般问题要么可以归约到括号匹配问题, 要么可以归约到入栈出栈问题, 比如:

  • n+1 个矩阵连乘的括号化方案数, 可以归约到 n 对括号匹配问题, 所以为 Cn
  • 所有在 n×n 格点中不越过对角线的单调对角路径的个数, 可以归约到入栈出栈序列问题, 所以为 Cn
  • 有 n+1 个叶子的二叉树的个数, 括号匹配, Cn
  • 给定 n 个节点,能构成多少种不同的二叉树, 括号匹配, Cn
  • 长度 2n 的dyck word的个数, 入栈出栈序列, Cn
  • 通过连结顶点(连接线不相交)而将 n+2 边的凸多边形分成三角形的方法个数, 括号匹配, Cn
  • n 个长方形填充一个高度为 n 的阶梯状图形的方法个数, 大概是括号匹配, 不明显不好证, Cn
isnowfy 说:
2012年3月17日 14:00

话说你还可以讲讲经典的找钱问题,就是说某件物品50元,有m个人有50元,n个人有100元,m>=n,怎么安排这些人,使得总有零钱可以找


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter