注:以下我们将记 \(\operatorname{Cat}_i\) 为卡特兰数列的第 \(i\) 项。

公式

\[\large\operatorname{Cat}_n = \frac{\binom{2n}{n}}{n+1} \]

简单推一下,也就是:

\[\large\operatorname{Cat}_n = \binom{2n}{n}-\binom{2n}{n-1} \]

还有递推式:

\[\large \operatorname{Cat}_n = \begin{cases} \sum\limits_{i = 1}^{n} \operatorname{Cat}_{i-1} \times \operatorname{Cat}_{n-i} & n \ge 2\\[1ex] 1 & n = 0 \lor n = 1 \end{cases} \]

这个一般不会用于求解卡特兰数,但是利用这个递推式可以推一些东西和卡特兰数之间的关系。

\[\large\operatorname{Cat}_n = \frac{\operatorname{Cat}_{n-1} \times (4n-2)}{n+1} \]

这个是更为常见的递推式。

推导

不会,先咕

应用

  • oi-wiki

  • 路经统计问题

    • Q1:从 \((0,0)\)\((n,m)\) 的不降路径(最短路径)数量。

      A1:\(\binom{n+m}{m}\)

    • Q2:从 \((0,0)\)\((n,n)\) 不穿过直线 \(y = x\) 的不降路径数量。

      A2:\(\frac{2}{n+1}\binom{2n}{n} = 2\operatorname{Cat}_n\)

      如果我们穿过了直线,那是不是再对称过来就好了?

      于是相当于我们枚举了穿过直线的位置,然后左右两部分贡献做乘积。

      回到了卡特兰数的递推式。

例题

\(\textrm{luogu P2532 [AHOI2012]树屋阶梯}\)

结论先摆一下:答案是 \(\operatorname{Cat}_n\)

为什么?

考虑每次选择一个角,并让它覆盖整个左下部分。

那么它就把一个问题划分成了两个子问题,此时的方案总数为两个子问题方案总数的乘积。

而我们可以枚举每一个角。

于是有了递推式:

\[\large f_n = \begin{cases} \sum\limits_{i = 1}^{n} f_{i-1} \times f_{n-i} & n \ge 2\\[1ex] 1 & n = 0 \lor n = 1 \end{cases} \]

这不就卡特兰嘛!

但是很恶心的是它用了高精度。

原文地址:http://www.cnblogs.com/bikuhiku/p/Catalan.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性