WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
卡特兰数 - 数学
## Catalan 数列 以下问题属于 Catalan 数列: 1. 有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票,另外 $n$ 人只有 10 元钞票,剧院无其它钞票,问有多少中方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零? 2. 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 3. 在圆上选择 $2n$ 个点,将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数? 4. 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数? 5. 一个栈(无穷大)的进栈序列为 $1,2,3, \cdots ,n$ 有多少个不同的出栈序列? 6. $n$ 个结点可构造多少个不同的二叉树? 7. $n$ 个不同的数依次进栈,求不同的出栈结果的种数? 8. $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2, \cdots ,a_{2n}$ ,其部分和满足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 对与 $n$ 该数列为? 其对应的序列为: | $H_0$ | $H_1$ | $H_2$ | $H_3$ | $H_4$ | $H_5$ | $H_6$ | ... | | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | :-: | | 1 | 1 | 2 | 5 | 14 | 42 | 132 | ... | (Catalan 数列) ## 递推式 该递推关系的解为: $$ H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}}) $$ 关于 Catalan 数的常见公式: $$ H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\\\ 1 & n = 0, 1 \end{cases} $$ $$ H_n = \frac{H_{n-1} (4n-2)}{n+1} $$ $$ H_n = \binom{2n}{n} - \binom{2n}{n-1} $$ ### " 例题[洛谷 P1044 栈](https://www.luogu.com.cn/problem/P1044)" > 题目大意:入栈顺序为 $1,2,\ldots ,n$ ,求所有可能的出栈顺序的总数。 ```cpp #include
using namespace std; int n; long long f[25]; int main() { f[0] = 1; cin >> n; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1); // 这里用的是常见公式2 cout << f[n] << endl; return 0; } ``` ## 路径计数问题 非降路径是指只能向上或向右走的路径。 1. 从 $(0,0)$ 到 $(m,n)$ 的非降路径数等于 $m$ 个 $x$ 和 $n$ 个 $y$ 的排列数,即 $\dbinom{n + m}{m}$ 。 2. 从 $(0,0)$ 到 $(n,n)$ 的除端点外不接触直线 $y=x$ 的非降路径数: 先考虑 $y=x$ 下方的路径,都是从 $(0, 0)$ 出发,经过 $(1, 0)$ 及 $(n, n-1)$ 到 $(n,n)$ ,可以看做是 $(1,0)$ 到 $(n,n-1)$ 不接触 $y=x$ 的非降路径数。 所有的的非降路径有 $\dbinom{2n-2}{n-1}$ 条。对于这里面任意一条接触了 $y=x$ 的路径,可以把它最后离开这条线的点到 $(1,0)$ 之间的部分关于 $y=x$ 对称变换,就得到从 $(0,1)$ 到 $(n,n-1)$ 的一条非降路径。反之也成立。从而 $y=x$ 下方的非降路径数是 $\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}$ 。根据对称性可知所求答案为 $2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}$ 。 3. 从 $(0,0)$ 到 $(n,n)$ 的除端点外不穿过直线 $y=x$ 的非降路径数: 用类似的方法可以得到: $\dfrac{2}{n+1}\dbinom{2n}{n}$