电子商务网站建设主题,可以做网站的软件上传歌曲,宁波网站建设销售,青岛南丰网站建设公司卡特兰数
从格点(0,0)(0,0)(0,0)走到格点(n,n)(n,n)(n,n)#xff0c;只能向右或向上走#xff0c;不能穿过对角线#xff0c;的路径的条数#xff0c;称为卡特兰数HnH_nHn。 则有H01H_01H01。
通项公式#xff1a; Hn(2nn)−(2nn−1)H_n\begin{pmatrix} 2n\\ n \en…卡特兰数
从格点(0,0)(0,0)(0,0)走到格点(n,n)(n,n)(n,n)只能向右或向上走不能穿过对角线的路径的条数称为卡特兰数HnH_nHn。 则有H01H_01H01。
通项公式
Hn(2nn)−(2nn−1)H_n\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} 2n\\ n-1 \end{pmatrix}Hn(2nn)−(2nn−1)Hn(2nn)n1H_n\frac {\begin{pmatrix} 2n\\ n \end{pmatrix}}{n1}Hnn1(2nn)Hn4n−2n1Hn−1H_n\frac{4n-2}{n1}H_{n-1}Hnn14n−2Hn−1
折线法
证明一下卡特兰数的公式。
先证明公式1 如果没有限制那么路径总数是从2n2n2n步移动之中选出nnn步向上走另外nnn步向右走的方案数(2nn)\begin{pmatrix} 2n\\ n \end{pmatrix}(2nn)。
如果有限制我们画出yx1yx1yx1的函数图像碰到这条线意味着不合法。 把所有不合法的路径沿着这条图像对折过来其终点必然是(n−1,n1)(n-1,n1)(n−1,n1)。 换句话说所有到达(n−1,n1)(n-1,n1)(n−1,n1)的路径都对应着到达(n,n)(n,n)(n,n)的一条不合法路径。因此答案就是(2nn)−(n1n−1n−1)\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} n1n-1\\ n-1 \end{pmatrix}(2nn)−(n1n−1n−1)
QED.
证明一下公式2 (2nn)−(2nn−1)\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} 2n\\ n-1 \end{pmatrix}(2nn)−(2nn−1) (2n)!n!n!−(2n)!(n1)!(n−1)!\frac{(2n)!}{n!n!}-\frac {(2n)!}{(n1)!(n-1)!}n!n!(2n)!−(n1)!(n−1)!(2n)! (2n)!n!(n−1)!n−(2n)!n!(n−1)!(n1)\frac{(2n)!}{n!(n-1)!n}-\frac {(2n)!}{n!(n-1)!(n1)}n!(n−1)!n(2n)!−n!(n−1)!(n1)(2n)! (2n)!n!(n−1)!⋅(1n−1n1)\frac{(2n)!}{n!(n-1)!}\cdot\left(\frac{1}{n}-\frac 1{n1}\right)n!(n−1)!(2n)!⋅(n1−n11) (2n)!n!(n−1)!n−(2n)!n!(n−1)!(n1)\frac{(2n)!}{n!(n-1)!n}-\frac {(2n)!}{n!(n-1)!(n1)}n!(n−1)!n(2n)!−n!(n−1)!(n1)(2n)! (2n)!n!(n−1)!⋅(1n−1n1)\frac{(2n)!}{n!(n-1)!}\cdot\left(\frac{1}{n}-\frac 1{n1}\right)n!(n−1)!(2n)!⋅(n1−n11) (2n)!n!(n−1)!⋅1n(n1)\frac{(2n)!}{n!(n-1)!}\cdot\frac {1}{n(n1)}n!(n−1)!(2n)!⋅n(n1)1 (2n)!n!n!⋅1n1\frac{(2n)!}{n!n!}\cdot\frac {1}{n1}n!n!(2n)!⋅n11 (2nn)⋅1n1\begin{pmatrix} 2n\\ n \end{pmatrix}\cdot\frac {1}{n1}(2nn)⋅n11
QED.
证明一下公式3 留作习题读者自证不难。
常见情况
特点一种操作不能超过另一种操作或操作之间不能有交集。
例如
一个由nnn个000nnn个111组成的长度为2n2n2n的字符串满足所有前缀中111的个数不能超过000的个数这样的子串数量。包含nnn组括号的合法表达式的数量。 想要括号序列合法必须保证所有前缀中左括号的数量大于等于右括号的数量一个栈的进栈序列为1,2,...,n1,2,...,n1,2,...,n则出栈序列的可能数量。 必须保证出栈数量小于等于进栈数量在圆上选择2n2n2n个点连接起来形成nnn条不相交的弦的方案数。 把nnn条不相交的弦映射为括号序列把弦的左端映射为左括号右端映射为右括号通过连接顶点将n2n2n2条边的正多边形分为nnn个三角形的方案数三角剖分。 想要保证分为nnn个三角形必须保证连接的线不相交nnn个节点可以构造多少颗不同的二叉树 考虑对n2n2n2条边的多边形三角剖分把剖分得出的三角形抽象为一个节点对它相邻的三角形连边最后得出必定是一颗二叉树。一段连乘积有多少种运算次序 相当于给连乘积加括号
公式法
事实上有 Hn∑i0n−1HiHn−i−1H_n\overset{n-1}{\underset{i0}\sum}H_iH_{n-i-1}Hni0∑n−1HiHn−i−1
可以从两个方面来证明一下
出栈序列 考虑iii是最后一个出栈的数则[1,i−1][1,i-1][1,i−1]在iii进栈之前就出栈了情况数有Hi−1H_{i-1}Hi−1种而iii后面的n−in-in−i个数则必然在iii出栈前就出栈了情况数有Hn−iH_{n-i}Hn−i种枚举这个iii得到 Hn∑i1nHi−1Hn−i∑i0n−1HiHn−i−1H_n\overset{n}{\underset{i1}\sum}H_{i-1}H_{n-i}\overset{n-1}{\underset{i0}\sum}H_iH_{n-i-1}Hni1∑nHi−1Hn−ii0∑n−1HiHn−i−1格点计数 我们知道在格点卡特兰数的要求中路径不能越过对角线。我们可知在走到终点之前的一步一定是向上走的 红色表示最后一步。
显然碰到对角线之后一定是向右走的我们枚举对角线上的一个点使得走完向右走的那一步之后不能越过新的对角线统计的路径条数 绿色枚举的位置。 红色最后一步。 蓝色新的对角线。
此时我们发现从底下走到绿色圆圈不能越过对角线。与从绿色箭头走到红色圆圈不能越过蓝线是两个更小的卡特兰数问题因此可以用乘法原理计数。
我们注意到我们枚举的一种新的情况在我们枚举的更旧的情况中都属于不合法情况不会被重复统计。
QED.
用公式同样可以解释各种卡特兰数的情况。
一个由nnn个000nnn个111组成的长度为2n2n2n的字符串满足所有前缀中111的个数不能超过000的个数这样的子串数量。 注意到最后一个字符一定是111枚举一个位置的000使得这个000与末尾的那个111匹配转化为格点计数的情况。包含nnn组括号的合法表达式的数量。 同理。一个栈的进栈序列为1,2,...,n1,2,...,n1,2,...,n则出栈序列的可能数量。 同理。在圆上选择2n2n2n个点连接起来形成nnn条不相交的弦的方案数。 同理枚举一个点与最后那个点任意指定一个固定的点为最后的点连接成弦。通过连接顶点将n2n2n2条边的正多边形分为nnn个三角形的方案数三角剖分。 同理4。nnn个节点可以构造多少颗不同的二叉树 枚举根节点有iii个左子树则就会有n−i−1n-i-1n−i−1个右子树显然。
斯特林数
第一类斯特林数
定义[nm]\begin{bmatrix}n\\ m\end{bmatrix}[nm]表示nnn元集合划分为mmm个非空环排列的方案数即无符号第一类斯特林数或简称为第一类斯特林数斯特林轮换数。
第一类斯特林数有递推式 [nm][n−1m−1](n−1)[n−1m]\begin{bmatrix} n\\ m \end{bmatrix}\begin{bmatrix} n-1\\ m-1 \end{bmatrix}(n-1)\begin{bmatrix} n-1\\ m \end{bmatrix}[nm][n−1m−1](n−1)[n−1m]
递推式容易证明留作习题。
第二类斯特林数
定义{nm}\begin{Bmatrix} n\\ m \end{Bmatrix}{nm}表示将nnn元集合划分为mmm个非空子集的方案数即第二类斯特林数或斯特林子集数。
第二类斯特林数有递推式 {nm}{n−1m−1}m{n−1m}\begin{Bmatrix} n\\ m \end{Bmatrix}\begin{Bmatrix} n-1\\ m-1 \end{Bmatrix}m\begin{Bmatrix} n-1\\ m \end{Bmatrix}{nm}{n−1m−1}m{n−1m}
递推式容易证明留作习题。
其他
两类斯特林数的边界条件都是s[0][0]1s[0][0]1s[0][0]1。从递推式可以看出斯特林数增长比组合数还要快。斯特林数用于解决组合计数问题以及用于斯特林反演。这些问题较复杂单独讨论。
后记
于是皆大欢喜。
