组合数学——卡特兰数
我们以一道题为例来介绍卡特兰数:
题目链接:满足条件的01序列
给定
n ">n个0 ">0和n ">n个1 ">1,它们将按照某种顺序排成长度为2 n ">2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0 ">0的个数都不少于1 ">1的个数的序列有多少个。输出的答案对
10 9 + 7 ">109+7取模。
10 9 + 7 ">给定一个n*n的矩阵,每一步只能往右走或者往上走,求从左下角顶点走到右上角顶点所有方案中,往右走的步数不少于往上走的步数的方案的数量,并且对109+7取模。
10 9 + 7 ">合法路径数 = 总路径数 - 非法路径数
卡特兰数:
以下内容参考百度百科:卡特兰数
卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。
原理:
设h(n)为catalan数的第n项,令h(0)=1,h(1)=1,catalan数满足递推式:
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另类递推式:
h(n)=h(n-1)*(4*n-2)/(n+1);
递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)
卡特兰数的常见应用:
一、出栈次序
一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
二、括号化
矩阵连乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
三、凸多边形三角划分
四、给定节点组成二叉搜索树在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。比如当n=6时,f(6)=14。
五、n对括号正确匹配数目给定N个节点,能构成多少种不同的二叉搜索树?(能构成h(n)个)
给定n对括号,求括号正确配对的字符串数。