卡特兰数、真二叉树、出栈序列、n对括号合法表达式

一、本文主要介绍一下几个问题

• 什么是卡特兰数
• n对括号组成的合法表达式个数与卡特兰数的关系
• 真二叉树的形态总数与卡特兰数的关系
• n个互异元素出栈序列数与卡特兰数的关系

1、什么是卡特兰数

        卡特兰数是指满足以下递推关系的数：

h(n)=∑k=0n−1h(k)∗h(n−1−k)" role="presentation">h(n)=∑n−1k=0h(k)∗h(n−1−k)$h(n)=\sum _{k=0}^{n-1}h(k)\ast h(n-1-k)$

这个数跟斐波拉契数列一样是一个递归定义的数，卡特兰数又写作Catalan(n)

2、n对括号组成的合法表达式个数与卡特兰数的关系

        假设n对括号组成的合法字符串种类数为h(n)。
        由组合数计数原理，可以分情况求和，分为n-1种情况。将所有的括号分为三类：

1) 第一个左括号以及其对应的右括号，分别记为A与B
2) AB之间的括号，设有k对括号
3) B右侧的括号，显然有n-1-k对括号

        显然k的取值范围从0到n-1，对应了n种基本情况。

        每种情况的字符串组合数均等于2)中的括号的组合数，与3)中的括号的组合数之积。

        而2)和3）分别对应规模大小为k与n-1-k的子问题，所以相应的组合数分别是h(k)和h(n-1-k)。所以总的字符串组合数＝n种情况的组合数的求和，所以 

h(n)=∑k=0n−1h(k)∗h(n−1−k)" role="presentation">h(n)=∑n−1k=0h(k)∗h(n−1−k)$h(n)=\sum _{k=0}^{n-1}h(k)\ast h(n-1-k)$

 上式中的h(n)是符合卡特兰递推公式的，所以n对括号组成的合法表达式个数=Catalan(n)

3、真二叉树的形态数与卡特兰数的关系

        设真二叉树结点总数为n，根据结点数与边数的数学关系可知，内结点个数m为(n-1)/2，也就是个说，总的节点数确定时，其无论形态如何变化，其内结点个数不变，叶结点个数也不变。

        设内结点数为m的真二叉树形态数为h(m)，其左子树的内结点个数k可以从0变化到m-1，对应了m种情况，右子树内结点个数为m-1-k，所以：

左子树的形态数为h(k)，右子树的形态数为h(m-1-k)

所以有：

h(m)=∑k=0m−1h(k)∗h(m−1−k)" role="presentation">h(m)=∑m−1k=0h(k)∗h(m−1−k)$h(m)=\sum _{k=0}^{m-1}h(k)\ast h(m-1-k)$

 上式中的h(m)是符合卡特兰递推公式的，所以含有m个内节点的真二叉树的形态数h(m)

h(m)=Catalan(m)=Catalan((n-1)/2)

4、n个互异元素出栈序列数与卡特兰数的关系

        设n个互异的元素，依次入栈，随时出栈，可连续出栈，设总序列数为h(n).
        仍然是根据组合数学分类统计原理，分类求和。按第一个元素A在出栈序列中的位置，分为n种情况。设出栈序列中元素A左侧元素个数为k=0,1,2,…,n-1，右侧元素有n-1-k个，这样就变成了两个规模更小的子问题，左边的序列数为h(k)，右边的序列数为h(n-1-k)，于是总的序列数h(n)有：

h(n)=∑k=0n−1h(k)∗h(n−1−k)" role="presentation">h(n)=∑n−1k=0h(k)∗h(n−1−k)$h(n)=\sum _{k=0}^{n-1}h(k)\ast h(n-1-k)$

 上式中的h(n)是符合卡特兰递推公式的，所以n个互异元素出栈序列数=Catalan(n)

5、上述三个问题的联系

        n对括号组成的合法表达式，将左括号看作入栈操作，右括号看作出栈操作，则n对括号组成的合法表达式与n个互异元素的出栈序列是同一个问题。

        含有m个内结点的真二叉树，无论是先序遍历、中序遍历、后序遍历，将从左分支前进看作入栈，从右分支返回父节点看作出栈，由于任意一个内节点既有左孩子又有右孩子，所以出栈入栈是匹配的，还对应于相互匹配的左括号和右括号。