注:以下我们将记 \(\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} \]
这个是更为常见的递推式。
推导
不会,先咕
应用
-
路经统计问题
-
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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性