【interview】卡特兰数
涉及卡特兰数的题目列举,也是组合数学中一些例子: 详解链接 https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0 ? 1. n个节点的二叉树有多少种形态? Cn表示有2n+1个节点组成不同构满二叉树(full binary tree)的方案数。 下图中,n等于3,圆形表示内部节点,月牙形表示外部节点。本质同上。 ? ? ? ?? ? 2.?矩阵链乘: P=a1×a2×a3×…×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,有几种括号化的方案?
3. 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列??
? ? ? ?
8.?Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck word:?XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY 证明: 令1表示进栈,0表示出栈,则可转化为求一个2n位、含n个1、n个0的二进制数,满足从左往右扫描到任意一位时,经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有个,下面考虑不满足要求的数目。 考虑一个含n个1、n个0的2n位二进制数,扫描到第2m+1位上时有m+1个0和m个1(容易证明一定存在这样的情况),则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0,则对应一个n+1个0和n-1个1的二进制数。反之亦然(相似的思路证明两者一一对应)。 从而。证毕。 9.
? ? ? 什么是卡特兰数? f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)? ? ? ? 参考博文: https://blog.csdn.net/adminabcd/article/details/46672759 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |