卡特兰数学习笔记

为什么要学卡特兰数?

为了解决一类计数问题

NOIp能考吗:能

以此记录我模拟赛中被强行卡特兰数卡爆的贪心神题


什么是卡特兰数?

卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。--百度百科

用人话来说,就是开头为1,2,5,14,42,132,429,1430,4862....的数列

卡特兰数的公式

卡特兰数的一般公式

k5XalD.png

(只有下标的是卡特兰数,右边那个是组合数)

卡特兰数的递推式

k5XwOH.png
k5Xykt.png


卡特兰数有什么用

此处内容借鉴了:https://blog.csdn.net/wu_tongtong/article/details/78161211

1.括号匹配类计数问题:

  给你n个左括号,n个右括号,问有多少种合法的括号放置方案
  eg. ()()()是合法的方案,)( 是不合法的方案

  能抽象为这类问题的题目,其方案数就是卡特兰数
  例题:luogu P3200 有趣的数列

2.出栈次序问题

  有1-n个元素,依次进栈,问你有多少种合法的出栈方案

  能抽象为这类问题的题目,其方案数也是卡特兰数。

  例子:
    有2n个人去餐厅吃饭,有n个人有10块钱纸币,n个人有5块钱纸币,餐厅的饭卖5块钱一份,问有多少种可行的买饭顺序
    我们可以抽象为:用5块钱买饭就入栈一次,用10块钱买饭就出栈一次

3.二叉树形态数问题

  有n个叶子,问你有多少个形态不同的二叉树

  这种类型的题目方案数就是卡特兰数

  暂无例子( ・´ω`・ )

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注