卡特兰数学习

1，概念

        卡特兰数（英语：Catalan number），又称卡塔兰数，明安图数。是组合数学中一种常出现于各种计数问题中的数列。它在不同的计数问题中频繁出现。

2，公式

       卡特兰数的递推公式为：f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ... + f(n - 1) * f(0)，其中初始值f(0) = f(1) = 1。

        这个数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452...。

3，卡特兰数代码实现

递归

int catalan1(int n)
{
    if (n <= 1) return 1;

    int res = 0;
    for (int i = 1; i <= n - 1; i++)
        res += catalan1(i)*catalan1(n-i);

    return res;
}

非递归

int catalan2(int n)
{
    if (n <= 1) return 1;

    int* h = new int[n];
    h[0] = h[1] = 1;
    for (int i = 2; i < n ; i++)
    {
        h[i] = 0;
        for (int j = 0; j < i; j++)
            h[i] += (h[j] * h[i - 1 - j]); //f[i]=f[0]*f[i-1]+f[1]*f[i-2]+...+f[i-1]*f[0]
    }
    int result = h[n-1];
    delete[] h;
    return result; 

}

4，卡特兰数的应用 

        对于卡特兰数的介绍，我们只知道了它是组合数学中的一种规律，并没有具体意义，是一个常见的数学规律。

        对于卡特兰数的初步理解：有一些操作，这些操作有一定的限制，如一种操作数不能超过另一种操作数，或两种操作数不能有交集，求这些操作的合法数量。

应用1：出栈次序（进出栈问题）

【问题描述】

一个无穷大的栈，进展序列为1，2，3，......，n,问出栈顺序有多少种？

【问题分析】

设f(n)=序列个数为n的出栈序列种数。假定，从开始到栈第一次出空为止，这段过程中第一个出栈的序数是k，如果栈直到整个过程结束时，才为空，那么k=n；首次出空之前，第一个出栈序数k，将1~n的序列划分成两部分。其中一个是1~k-1，一共k-1个数；另一部分是k+1~n，一共n-k个数。

此时，我们把k看作是一个序数，根据乘法原理，f(n)就等价于 序列个数为k-1的出栈序列种树*序列个数为n-k的出栈序列种树。即f(n)=f(k-1)*f(n-k)。而k可以从1选到n，再根据加法原理，将k取不同的值，然后求和，得到总序列种数为：f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。就是卡特兰数的规律，再令f(0)=f(1)=1求解即可。

应用2：括号匹配

【问题描述】

由一对括号，可以组成一种合法序列：（）

由两对括号，可以组成两种合法序列：()()，(())

问:由n对括号组成的合法括号序列一共有多少中？

【问题分析】

        首先，n对括号我们看成是2n个字符，n个左括号，n个右括号。设问题的解为f(2n)。第0个字符肯定为左括号，而第2*i+1个字符肯定为右括号，如果第2*i个字符为右括号，那么0~2*i一共由2*i+1奇数个字符，而奇数个字符是 无法匹配的。

        f(2n)可以转化如下的递推式 f(2n) = f(0)*f(2n-2) + f(2)*f(2n - 4) + ... + f(2n - 4)*f(2) + f(2n-2)*f(0)。f(0)*f(2n-2)表示第0个字符和第1个字符匹配，剩余两部分，一部分0个字符，一部分2n-2个字符。f(2)*f(2n-4)表示 第0个字符和第3个字符匹配，剩余两部分，一部分2个字符，一部分2n-4个字符。以此类推可得出递推式。

        f(0)=1，分别计算出f(1),f(2),f(3),f(4),f(5)，得出f(2n)就是一个卡特兰数的数列。

应用3：二叉树生成问题

【问题描述】

n个节点 构成的二叉数，共有多少情形？

【问题分析】

        设题解为f(n)，T(i,j)表示：一颗二叉树，它的左子树有i个节点，右子树有j个节点。

        根肯定会占用一个节点，那么它的左右子树：T(0,n-1),T(1,n-2),T(2,n-3),...,T(n-1,0)。

        那么f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+...+f(n-1)*f(0)。假设 f(0)=1,那么f(1)=1,f(2)=2,f(3)=5,满足卡特兰数的规律。

应用4：矩阵链乘

【问题描述】

矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

【问题分析】

        首先通过括号化，将P分成两个部分，然后分别对两个部分进行括号化。比如分成(a1)×(a2×a3.....×an)，然后再对(a1)和(a2×a3.....×an)分别括号化；又如分成(a1×a2)×(a3.....×an)，然后再对(a1×a2)和(a3.....×an)括号化。

        设n个矩阵的括号化方案的种数为f(n)，那么问题的解为f(n) = f(1)*f(n-1) + f(2)*f(n-2) + f(3)*f(n-3) + f(n-1)*f(1)。f(1)*f(n-1)表示分成(a1)×(a2×a3.....×an)两部分，然后分别括号化。

        计算开始几项，f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5。结合递归式，满足卡特兰数规律。