卡特兰

卡特兰数 引入 不妨从找规律开始。 下标从\(0\)开始，卡特兰数的前几项为： 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790… 那么通过认真的瞪眼观察，会发现它 ......

火车进栈 （卡特兰数+位压高精） [题目](130. 火车进出栈问题 - AcWing题库) 思路：车厢进出栈视为\(01\)序列,则每种\(01\)序列对应一种出栈顺序，答案即为：\({\Large \frac{1}{n+1} C_{2n}^{n}}\) 数据范围：\(1{\Large \le } ......

卡特兰数专题（\(Catalan\)） 一、什么是卡特兰数？ 明安图数，又称卡塔兰数，英文名\(Catalan\) \(number\)，是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图 \((1692-1763)\)和比利时的数学家欧仁·查理·卡塔兰 \((1814–1894 ......

卡特兰数 定义： 卡特兰数的计算公式涉及组合计数，它是很多组合问题的数学模型，是一个很常见的数列。 \(\bf{\underline{卡特兰数(Catalan)}}\) 是一个数列，它的一种定义是： \[C_n=\frac{1}{n+1}\binom{2n}{n}，n=0,1,2,... \]卡特兰 ......

卡特兰数 Catalan 数列 引入 有一个无限大的栈，进栈的顺序为 \(1,2,\cdots,n\)，求有多少种不同的出栈序列。 设 \(h[n]\) 为 \(n\) 个数的出栈序列方案数。 可以这样想 \(k\) 是最后一个出栈的数，那么比 \(k\) 早进栈早出栈的有 \(k-1\) 个，方案 ......

引入 有 \(n\) 个元素进栈序列为 \(1,2,3,4\dots n\)。求有多少种出栈序列 我们需要确保最后一次操作后，栈中没有元素。因此，共有 \(2n\) 次操作。（每个元素进栈一次，出栈一次） 对于每次操作，如果我们想出栈，则它一定要有数字可以 pop。如果我们把栈抽象成一条链，若第 \ ......

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 ###1. 动态规划 由于二叉搜索树是有序的，父节点值大于左子树，而小于右子树，所以选定根节点后会将集合划分为两部分 显然，左子树和右子树的构成同样也是个二叉搜索树个数 ......

# 定义 先给一个通项公式 $Cat(n)=\frac{C_{2n}^{n}}{n+1}$。 卡特兰数是一个比较通用的模型，有很多的问题都与其有关，其中比较经典的是括号序列计数和二叉树计数。 # 经典的问题 ## 一些描述 ### 括号序列计数 给定 $n$，求有多少个合法的长度为 $2n$ 的括号 ......

[luogu链接](https://www.luogu.com.cn/problem/CF896D) 题意不再赘述。 优先枚举的应该是$VIP$用户，枚举范围应该是$[0,n-l]$ 之后总客户数为$s=n-i$ 再考虑枚举$100$的总人数为$x$ 则要求$s-2x\in [l,r]$ 这部分方案 ......

## 概念 以下看似毫不相关的问题均属于 Catalan 数列： - $n$ 个节点构成的无标号、区分左右儿子的二叉树数量为 $Cat_n$ - $n$ 个节点构成的无标号、区分儿子的有根树数量为 $Cat_{n - 1}$ - $n$ 个左括号与 $n$ 个右括号组成的合法序列有 $Cat_n$ ......

# 卡特兰数 ## n对括号匹配，n个数入栈出栈 ## 递推：$h(n)=h(n-1)*(4n-2)/(n+1)$ ## 解：$h(n)=C(2n,n)/(n+1)$ ## $h(n)=C(2n,n)-C(2n,n-1)$ ......

# 卡特兰数 - 定义 卡特兰数非常常见，最为典型的就是给定n个1和n个0排列成为一个2n长度的01序列，要求对于任一个$1\le k\le 2n$都有从第一个数到第k个数中0的个数都不少于1的个数。 - 求法及其推导 我们可以把这个01序列抽象成一个具体的问题: 0代表向右走一步，1代表向上走一步 ......

# 斐波那契数列 斐波那契数列是我们较为熟悉的一类数列了，在学习递归和递推的时候我们就已经能求解 $n$ 较小的情况了；斐波那契数列的定义如下： $$ \left\{\begin{matrix} F_{n}=0& n=0\\ F_{n}=1& n=1\\ F_{n}=F_{n-1}+F_{n-2}& ......

已知$n$个数的入栈序列，求一共有多少种出栈序列 这个经典问题有两种解法。 解法一： 设$f(x)$为$x$个数入栈后，再全部出栈的序列数量 假设我们有$4$个数$a,b,c,d$, 我们来看$a$的出栈顺序. 假如$a$第一个出栈，那么后面还有$3$个数没有出栈，因此方法数是$f(3)$. 假设$ ......

引例1、（姐妹洗碗问题） 思考过程： 横坐标表示姐姐洗完的碗的个数，纵坐标表示妹妹摞碗的个数，前提条件为妹妹摞碗的个数不能超过姐姐洗完的碗的个数，要求摞法的方案数实际上是求从坐标（0，0）到坐标（5，5）的所有满足条件的路径数。 引例2、（进出栈问题） 思考过程： 本质上和姐妹洗碗问题一致，都是求方 ......

卡特兰数 问题 给定 $n$ 个 $0$ 和 $n$ 个 $1$，它们将按照某种顺序排成长度为 $2n$ 的序列，它们能排列成的所有序列中，能够满足任意前缀序列中 $0$ 的个数都不少于 $1$ 的个数的序列有多少个？ 转化 我们将上面的问题进行转化： 问：从 $(0, 0)$ 点走到 $(n, n ......