关于后端:卡特兰数

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) $$

矩阵链乘： P=a1×a2×a3×……×an，根据乘法结合律，不扭转其程序，只用括号示意成对的乘积，试问有几种括号化的计划？(h(n)种)

一个栈(无穷大)的进栈序列为1,2,3,…n,有多少个不同的出栈序列?

与问题1解法雷同, 进栈相当于左括号,出栈相当于右括号

另两个相似例子:

　　(1)有2n集体排成一行进入剧场（或者商店买货色）。入场费5元。其中只有n集体有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中办法使得只有有10元的人买票，售票处就有5元的钞票找零？(将持5元者达到视作将5元入栈，持10元者达到视作使栈中某5元出栈)

还是与1相似,5块钱相当于左括号,10块钱相当于右括号

　　(2)在圆上抉择2n个点,将这些点成对连接起来，使得所失去的n条线段不相交的办法数。

（1）一个凸的n边形，用直线连贯他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分计划。

(2)相似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去下班。如果她从不穿梭（但能够碰到）从家到办公室的对角线，那　　么有多少条可能的路线？

(3)相似：在圆上抉择2n个点,将这些点成对连接起来使得所失去的n条线段不相交的办法数?
例如n+2个点的凸多边形，这里n=4，通过卡特兰数的推导能够得出h(4)=14。

给定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 不同的二叉搜寻树

a.在 nn的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？其实向右走相当于进栈，向左走相当于出栈，实质就是n个数出栈秩序的问题，所以答案就是卡特兰数。（利用这个模型，能够解决这个卡特兰问题的变形问题，并顺便给进出栈问题的解法一个几何解释）

b.有n+1个叶子的满二叉树的个数？事实上，向左记为+1，向右记为−1，依照向左优先的准则，从根节点开始遍历．例如第一个图记为+1,+1,+1,−1,−1,−1,于是由卡特兰数的含意可得满二叉树的个数为Cn。

参考:

卡特兰(Catalan)数概念的简要介绍

史上最具体的卡特兰数浅谈

卡特兰数的证实

LeetCode 96之卡特兰数

卡特兰数/概率/蓄水池抽样

本文由mdnice多平台公布