共计 1522 个字符，预计需要花费 4 分钟才能阅读完成。
title: 卡特兰数
date: 2021-02-28 16:27:10
tags: 算法
概念
卡特兰数 的通项公式为
$$f \left(n \right) = \frac{1}{n+1} C_{2n}^{n}$$
又依据 组合数的计算公式:
可得:
$$f \left(n \right) = \frac{1}{n+1} \frac{(2n)!}{n!\cdot n!} = \frac{(2n)!}{(n+1)!\cdot n!} $$
同时满足递推关系式:
$$f \left(0 \right) = 1, f \left(n+1 \right) = \frac{2(2n+1)}{n+2} \cdot f \left(n \right) $$
利用
<font color=”#008B8B”>1. 括号化问题（或者 01 的个数问题）</font>
矩阵链乘：P=a1×a2×a3×……×an，根据乘法结合律，不扭转其程序，只用括号示意成对的乘积，试问有几种括号化的计划？(h(n)种)
<font color=”#008B8B”>2. 出栈秩序问题 </font>
一个栈 (无穷大) 的进栈序列为 1,2,3,…n, 有多少个不同的出栈序列?
与 问题 1 解法雷同, 进栈相当于左括号, 出栈相当于右括号
另两个相似例子:
(1)有 2n 集体排成一行进入剧场（或者商店买货色）。入场费 5 元。其中只有 n 集体有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少中办法使得只有有 10 元的人买票，售票处就有 5 元的钞票找零？(将持 5 元者达到视作将 5 元入栈，持 10 元者达到视作使栈中某 5 元出栈)
还是与 1 相似,5 块钱相当于左括号,10 块钱相当于右括号
(2)在圆上抉择 2n 个点, 将这些点成对连接起来，使得所失去的 n 条线段不相交的办法数。
<font color=”#008B8B”>3. 凸多边形问题 </font>
（1）一个凸的 n 边形，用直线连贯他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分计划。
(2)相似：一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去下班。如果她从不穿梭（但能够碰到）从家到办公室的对角线，那 么有多少条可能的路线？
(3)相似：在圆上抉择 2n 个点, 将这些点成对连接起来使得所失去的 n 条线段不相交的办法数?
例如 n + 2 个点的凸多边形，这里 n =4，通过卡特兰数的推导能够得出 h(4)=14。
<font color=”#008B8B”>4. 给定节点组成二叉树的问题 </font>
给定 N 个节点，能形成多少种形态不同的二叉树？
先取一个点作为顶点, 而后右边顺次能够取 0 至 N - 1 个, 绝对应的, 左边是 N - 1 到 0 个, 两两配对相乘, 就是 h(0)*h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)（能形成 h(N)个）
leetcode-96 不同的二叉搜寻树
<font color=”#008B8B”>5.n* n 棋盘从左下角走到右上角而不穿过主对角线的走法 </font>
a. 在 nn 的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？其实向右走相当于进栈，向左走相当于出栈，实质就是 n 个数出栈秩序的问题，所以答案就是卡特兰数。（利用这个模型，能够解决这个卡特兰问题的变形问题，并顺便给进出栈问题的解法一个几何解释）
b. 有 n + 1 个叶子的满二叉树的个数？事实上，向左记为 +1，向右记为−1，依照向左优先的准则，从根节点开始遍历．例如第一个图记为 +1,+1,+1,−1,−1,−1, 于是由卡特兰数的含意可得满二叉树的个数为 Cn。
参考:
卡特兰 (Catalan) 数概念的简要介绍
史上最具体的卡特兰数浅谈
卡特兰数的证实
LeetCode 96 之卡特兰数
卡特兰数 / 概率 / 蓄水池抽样
本文由 mdnice 多平台公布
