精华内容
下载资源
问答
  • 刚刚接触卡特兰数的时候,对这个结论很蒙,因为左右括号、火车进站很好理解,结果是个2*n的序列,与卡特兰数的证明可以直接对应。但是对于二叉树,我却很难想到怎么构造成2*n个数的数列。 可以把二叉树转换成完全...
  • 卡特兰数

    2020-12-16 21:58:16
    牛牛和网格三角形 先引进一下卡特兰数的概念: 卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,其前...

    Powered by:AB_IN 局外人

    B. 牛牛和网格三角形

    先引进一下卡特兰数的概念:

    卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,其前几项为(从第零项开始) : 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, …

    其实这个题,大佬一眼就能看出来,这个题无非就是卡特兰数通项公式推导的几何呈现

    通项公式

    h [ n ] = 1 n + 1 C 2 n n h[n]=\frac{1}{n+1}C_{2n}^n h[n]=n+11C2nn

    递归公式
    h [ 0 ] = 1 h[0]=1 h[0]=1
    h [ 1 ] = 1 h[1]=1 h[1]=1
    h [ n ] = h [ 0 ] ∗ h [ n − 1 ] + h [ 1 ] ∗ h [ n − 2 ] + . . . + h [ n − 1 ] ∗ h [ 0 ] ( n > = 2 ) h[n]=h[0]∗h[n−1]+h[1]∗h[n−2]+...+h[n−1]∗h[0](n>=2) h[n]=h[0]h[n1]+h[1]h[n2]+...+h[n1]h[0](n>=2)

    递推公式
    h [ n + 1 ] = 4 n + 2 n + 2 h [ n ] h[n+1]=\frac{4n+2}{n+2}h[n] h[n+1]=n+24n+2h[n]
    然后一看,一推导,发现 n + 1 = = 2 k ( k ∈ 0 , 1 , 2 … … ) n+1 == 2 ^ k (k \in 0,1,2……) n+1==2k(k0,1,2) 1 n + 1 C 2 n n \frac{1}{n+1}C_{2n}^n n+11C2nn为奇数的充要条件,然后就判断就行了。

    好的,以上就是大佬的解题方案(与我无瓜)。
    ——————————————————————————————————

    那我们就简单推导一下卡特兰数的通项公式

    首先引进一个经典问题:

    • 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

    看到这个题,脑海里第一个冒出来的限定条件应该是: 出栈的次数不能大于入栈的次数。凭空想象也想不出来怎么约束,那就万能画图法,以 x x x轴作为入栈次数,以 y y y轴作为出栈次数。

    如图:

    • 红线为 y = x y=x y=x,当 n = 4 n = 4 n=4时,假设线段 A B C ABC ABC为一条途径从 ( 0 , 0 ) − > ( 4 , 4 ) (0,0) -> (4,4) (0,0)>(4,4)

    我们前头说了, 出栈的次数不能大于入栈的次数,那么转换成数学公式就是: y < x y < x y<x,换个方式来讲,就是在直线 y = x y = x y=x的下方,即红线下方。
    显然,蓝色的 A B C ABC ABC是符合条件的一条路径,而橙色的 A D C ADC ADC是不符合条件的一条途径。
    看到这,你应该就看出来了,下三角形就是这个题。

    那么,怎么求得 y = x y = x y=x上每个整数点所对应的符合条件的路径条数呢?
    在这里插入图片描述
    比较好想的方法就是,我们可不可以从全部路径中,减去不符合的路径条数?
    显然是可以的。

    那么首先,全部路径怎么求?

    • 当只能往上或往往右走,求从零点到达第一象限的某个整数点的路径条数。 这貌似是一个很经典的 d p dp dp入门题了,核心思想就是: 一 个 点 的 路 径 条 数 = 它 左 边 的 路 径 条 数 + 它 下 面 的 路 径 条 数 一个点的路径条数=它左边的路径条数 + 它下面的路径条数 =+
      如图:

      • 我们所需要的数列就是 1 , 2 , 6 , 20 , 70 … … 1,2,6,20,70…… 1,2,6,20,70

      好了,我们懂了怎么推出来数列,但只是会递推,这没有公式可咋整?在这里插入图片描述
      这时候就可以搬出本篇文章的主角——组合数

      其实你肯定能想到,(挑选 + 没有顺序),这就是组合数的应用条件。怎么到达 ( 4 , 4 ) (4,4) (4,4)这个点,无非就是往上走四步,往右走四步,然后随意组合罢了。那么,这不就是 C 8 4 C_{8}^4 C84嘛?那么宏观来看,公式就是 C 2 n n C_{2n}^n C2nn

    好了,解决完全部路径,就该算不符合的了。

    • 不符合的满足什么条件呢?显而易见就是超出了 y = x y = x y=x这条红线,换种说法,就是 y = x + 1 y = x + 1 y=x+1直线上和直线上面的整数点。

      如图:

      • 橙色线 A B C D ABCD ABCD为不符合途径,黑色线为 y = x + 1 y = x + 1 y=x+1,红色线为 y = x y = x y=x

      在这里插入图片描述
      那我们怎么求这些不符合条件的路径的条数呢?

      这里就用到了一个非常巧妙的方法——转换法

      什么意思呢?就是将这条路线转换成另一条路线,即等效为另一条路线。把第一次碰到该 y = x + 1 y = x + 1 y=x+1以后的部分关于 y = x + 1 y = x + 1 y=x+1对称。 这样这条路线就会到达另一个终点,就可以计算到达这个终点的路径的条数了!(即我们需要求的不符合的路径条数)

      如图:

      • 紫色虚线即为 第一次碰到该 y = x + 1 y = x + 1 y=x+1以后的部分关于 y = x + 1 y = x + 1 y=x+1对称后的部分。
        在这里插入图片描述

      那么很清晰的看到终点G的坐标为 ( 3 , 5 ) (3,5) (3,5),到达 ( 3 , 5 ) (3,5) (3,5)的路径有多少条呢?即 C 8 5 C_{8}^5 C85。那么宏观来看,公式就是 C 2 n n + 1 C_{2n}^{n + 1} C2nn+1。(也可以是 C 2 n n − 1 C_{2n}^{n - 1} C2nn1

    好,我们现在做的,就是相减咯!

    C a t a l a n n = C 2 n n − C 2 n n + 1 = ( 2 n ) ! n ! n ! − ( 2 n ) ! ( n + 1 ) ! ( n − 1 ) ! = 1 n + 1 ( ( 2 n ) ! ( n + 1 ) n ! n ! − ( 2 n ) ! n ! ( n − 1 ) ! ) = 1 n + 1 ( ( 2 n ) ! ( n + 1 ) n ! ∗ n ! − ( 2 n ) ! n n ! n ! ) = 1 n + 1 ( 2 n ) ! ( n + 1 ) − ( 2 n ) ! ∗ n n ! n ! = 1 n + 1 ( 2 n ) ! n ! ∗ n ! = 1 n + 1 C 2 n n \begin{aligned} Catalan_n&=C_{2n}^n-C_{2n}^{n+1}\\ &=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!}\\ &=\frac{1}{n+1}(\frac{(2n)!(n+1)}{n!n!}-\frac{(2n)!}{n!(n-1)!})\\ &=\frac{1}{n+1}(\frac{(2n)!(n+1)}{n!*n!}-\frac{(2n)!n}{n!n!})\\ &=\frac{1}{n+1}\frac{(2n)!(n+1)-(2n)!*n}{n!n!}\\ &=\frac{1}{n+1}\frac{(2n)!}{n!*n!}\\ &=\frac{1}{n+1}C_{2n}^n\\ \end{aligned} Catalann=C2nnC2nn+1=n!n!(2n)!(n+1)!(n1)!(2n)!=n+11(n!n!(2n)!(n+1)n!(n1)!(2n)!)=n+11(n!n!(2n)!(n+1)n!n!(2n)!n)=n+11n!n!(2n)!(n+1)(2n)!n=n+11n!n!(2n)!=n+11C2nn

    求出卡特兰数,一切就迎刃而解了…………然后乱推就可以推出来了。

    怎么 推呢?
    先化简结论吧!
    C a t a l a n n = 1 n + 1 C 2 n n = ( 2 n ) ! n ! n ! × 1 n + 1 = 1 × 2 × 3 × 4 … … × ( 2 n ) n ! n ! × 1 n + 1 = [ 1 × 3 … … × ( 2 n − 1 ) ] × [ 2 × ( 2 ⋅ 2 ) × ( 2 ⋅ 3 ) × … … × ( 2 ⋅ n ) ] n ! n ! × 1 n + 1 = [ 1 × 3 … … × ( 2 n − 1 ) ] × ( 2 n × n ! ) n ! n ! × 1 n + 1 = [ 1 × 3 … … × ( 2 n − 1 ) ] × ( 2 n ) ( n + 1 ) ! \begin{aligned} Catalan_n&=\frac{1}{n+1}C_{2n}^n \\ &= \frac{(2n)!}{n!n!}×\frac{1}{n+1} \\ &= \frac{1×2×3×4……×(2n)}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×[2×(2·2)×(2·3)×……×(2·n)]}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×(2^n×n!)}{n!n!}×\frac{1}{n+1}\\ &=\frac{[1×3……×(2n - 1)] ×(2^n)}{(n+1)!}\\ \end{aligned} Catalann=n+11C2nn=n!n!(2n)!×n+11=n!n!1×2×3×4×(2n)×n+11=n!n![1×3×(2n1)]×[2×(22)×(23)××(2n)]×n+11=n!n![1×3×(2n1)]×(2n×n!)×n+11=(n+1)![1×3×(2n1)]×(2n)
    所以就判断 [ 1 × 3 … … × ( 2 n − 1 ) ] × ( 2 n ) ( n + 1 ) ! \frac{[1×3……×(2n - 1)] ×(2^n)}{(n+1)!} (n+1)![1×3×(2n1)]×(2n)的奇偶即可!

    • 首先观察, 1 × 3 … … × ( 2 n − 1 ) 1×3……×(2n - 1) 1×3×(2n1)一定是奇数,那就看 f ( n ) = 2 n ( n + 1 ) ! f(n) = \frac{2^n} {(n+1)!} f(n)=(n+1)!2n的奇偶。
      如果要 f ( n ) f(n) f(n)为偶数,那么就是问 ( n + 1 ) ! (n+1)! (n+1)!里的 2 2 2的因子个数是否小于 n n n

    问题再一次转化了,首先我们需要会 n ! n! n! 2 2 2的因子个数。(就是将 n ! n! n!素因子分解了,求 2 2 2这一项的指数)

    • 最简单的思路就是按贡献来算, ⌊ n 2 ⌋ \lfloor \frac{n} {2} \rfloor 2n是只贡献了一个 2 2 2的个数,也是 n ! n! n!里有多少个偶数,每个偶数先提供个 2 2 2 ⌊ n 4 ⌋ \lfloor \frac{n} {4} \rfloor 4n是贡献了两个 2 2 2的个数,就是 4 4 4的倍数还可以提供一个 2 2 2……

    • 那么 2 2 2的因子个数为 ⌊ n 2 ⌋ + ⌊ n 4 ⌋ + ⌊ n 8 ⌋ + ⌊ n 16 ⌋ + … … \lfloor \frac{n} {2} \rfloor + \lfloor \frac{n} {4} \rfloor + \lfloor \frac{n} {8} \rfloor + \lfloor \frac{n} {16} \rfloor+ …… 2n+4n+8n+16n+

    • 给出不等式
      ⌊ n 2 ⌋ + ⌊ n 4 ⌋ + ⌊ n 8 ⌋ + ⌊ n 16 ⌋ + … … ≤ n − 1 当 且 仅 当 n 为 2 的 幂 时 , 等 号 成 立 \lfloor \frac{n} {2} \rfloor + \lfloor \frac{n} {4} \rfloor + \lfloor \frac{n} {8} \rfloor + \lfloor \frac{n} {16} \rfloor+ ……\le n-1 \\ 当且仅当n为2的幂时,等号成立 2n+4n+8n+16n+n1n2
      n = 2 n n = 2^n n=2n带进去一看
      2 n − 1 + 2 n − 2 + … … + 4 + 2 + 1 = 2 n − 1 2^{n-1} +2^{n-2} +……+4+2+1=2^n-1 2n1+2n2++4+2+1=2n1
      正好成立!

      • 所以当 n n n 2 2 2的幂的时候, 2 2 2的因子个数为 n − 1 n-1 n1,同时也验证一件事, n ! n! n! 2 2 2的因子个数最大就是 n − 1 n-1 n1
      • 那么当 n n n不是 2 2 2的幂的时候,那么由于向下取整,肯定会有损失,所以是小于。

    回到这个题,我们知道 ( n + 1 ) ! (n+1)! (n+1)!最多有 n n n 2 2 2的因子,只有当且仅当 n + 1 n+1 n+1 2 2 2的幂时。这样就分两种情况了:

    • ( n + 1 ) ! (n+1)! (n+1)! n n n 2 2 2的因子,正好与分子的 2 n 2^n 2n约掉,然后这个式子 2 n ( n + 1 ) ! \frac{2^n} {(n+1)!} (n+1)!2n就为奇数。
    • ( n + 1 ) ! (n+1)! (n+1)!没有 n n n 2 2 2的因子,那就有的 2 2 2约不掉,那这个式子就为偶数。

    我不会乱推怎么办!!!

    当然,打表真香。
    写出卡特兰数公式, 1 − 100 1-100 1100打表!

    class Solution:
        def judge(self , n ):
            # write code here
            n = int(n)
            import math
            ans = math.factorial(2 * n) // (math.factorial(n) * math.factorial(n + 1))
            return ans & 1
    for _ in range(1, 100):
        print(Solution().judge(_), end = " ")
    

    出来结果:

    1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    

    我们提取 T r u e True True,也就是 1 1 1的位置,得到这样一个数列 1 , 3 , 7 , 15 … … 1,3,7,15…… 1,3,7,15,这打眼一看,就是 2 n − 1 2^n - 1 2n1鸭!所以就判断 n + 1 n+1 n+1是不是 2 k 2^k 2k即可。

    不会判断!!

    代码扔给你

    #
    # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    # 
    # @param n string字符串 三角形的长和高
    # @return bool布尔型
    #
    class Solution:
        def judge(self , n ):
            # write code here
            n = int(n)
            import math
            return bin(n + 1)[3:].count("1") == 0
    

    或者

    #
    # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    # 
    # @param n string字符串 三角形的长和高
    # @return bool布尔型
    #
    class Solution:
        def judge(self , n ):
            # write code here
            n = int(n)
            import math
            return n & (n + 1) == 0
    

    你肯定懂的!

    完结。

    展开全文
  • 本篇文章是对卡特兰数及其应用进行了详细的分析介绍,需要的朋友参考下
  • 卡特兰数字

    2014-04-06 11:05:23
    卡特兰数字,用于acm竞赛的卡特兰部分,使用卡特兰数字做间接数据计算题目
  • 卡特兰数(catalan数)总结 (卡特兰大数、卡特兰大数取模、卡特兰数应用)   本文讲解卡特兰数的各种递推公式,以及卡特兰数、卡特兰大数、卡特兰大数取模的代码实现,最后再顺带提一下卡特兰数的几个应用...

    卡特兰数(catalan数)总结 (卡特兰大数、卡特兰大数取模、卡特兰数应用)

     

    本文讲解卡特兰数的各种递推公式,以及卡特兰数、卡特兰大数、卡特兰大数取模的代码实现,最后再顺带提一下卡特兰数的几个应用。

     

    什么是卡特兰数呢?卡特兰数无非是一组有着某种规律的序列。重要的是它的应用。卡特兰数前几项为 : 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, ...

     

    下面给出几个求卡特兰数的公式,用h(n)表示卡特兰数的第n项,其中h(0)=1,h(1)=1

     

    公式一:h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

    公式二: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,...)

     

    下面代码用到的是公式一、公式二和公式四。

     

     

    根据公式一求n<=35以内的卡特兰数,由于卡特兰数很大,超过35就超了long long 型了,所以n<=35时可以用公式一求解:

    void init()
    {
        int i,j;
        LL h[36];
        h[0]=h[1]=1;
        for(i=2;i<36;i++)
        {
      	h[i]=0;
    	for(j=0;j<i;j++)
                h[i]=h[i]+h[j]*h[i-j-1];
        }
    }
    

     

     

    如果n>35时求h(n)%p应该怎么求呢?由于h(n)是大数,这里可以借助Lucas(卢卡斯)定理来解决。

     

    Lucas定理:Lucas定理是用来求 c(n,m) mod p,p为素数的值。Lucas定理的表达式为:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) 有了这个公式,我们直接看Lucas定理的代码:

    //Lucas定理实现C(n,m)%p的代码:
    LL exp_mod(LL a, LL b, LL p) 
    { //快速幂取模
        LL res = 1;
        while(b != 0) 
        {
            if(b&1) res = (res * a) % p;
            a = (a*a) % p;
            b >>= 1;
        }
        return res;
    }
     
    LL Comb(LL a, LL b, LL p) 
    { //求组合数C(a,b)%p
        if(a < b)   return 0;
        if(a == b)  return 1;
        if(b > a - b)   b = a - b;
     
        LL ans = 1, ca = 1, cb = 1;
        for(LL i = 0; i < b; ++i) 
        {
            ca = (ca * (a - i))%p;
            cb = (cb * (b - i))%p;
        }
        ans = (ca*exp_mod(cb, p - 2, p)) % p;
        return ans;
    }
     
    LL Lucas(LL n,LL m,LL p) 
    { //Lucas定理求C(n,m)%p
         LL ans = 1;
     
         while(n&&m&&ans) 
        {
            ans = (ans*Comb(n%p, m%p, p)) % p;
            n /= p;
            m /= p;
         }
         return ans;
    }
    
    


    这样根据公式四:h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...) 就可以利用Lucas定理来求 :

    h(n)%p=(Lucas(2n,n,p)-Lucas(2n,n-1,p)+p)%p。怎么理解呢?对于两个数a,b,(a-b)%p=(a%p-b%p)%p;那括号里为什么还要再加一个p呢?因为取模前前者一定大于后者,相减一定为正,而取模后就不一定了,所以要加一个p,保证是正数。

     

     

    如果是要求卡特兰大数呢?只要顺便实现大数的一些运算就好了。下面直接给出代码:

    int a[101][101],b[101];
     
    void catalan() //求卡特兰数
    {
        int i, j, len, carry, temp;
        a[1][0] = b[1] = 1;
        len = 1;
        for(i = 2; i <= 100; i++)
        {
            for(j = 0; j < len; j++) //乘法
            a[i][j] = a[i-1][j]*(4*(i-1)+2);
            carry = 0;
            for(j = 0; j < len; j++) //处理相乘结果
            {
                temp = a[i][j] + carry;
                a[i][j] = temp % 10;
                carry = temp / 10;
            }
            while(carry) //进位处理
            {
                a[i][len++] = carry % 10;
                carry /= 10;
            }
            carry = 0;
            for(j = len-1; j >= 0; j--) //除法
            {
                temp = carry*10 + a[i][j];
                a[i][j] = temp/(i+1);
                carry = temp%(i+1);
            }
            while(!a[i][len-1]) //高位零处理
            len --;
            b[i] = len;
        }
    }
    

     

     

     

    最后再简单说一下卡特兰数的应用,网上也给出了很多很好的解析,我只是把我觉得重要的整合了一下:

     

    卡特兰数的应用都可以归结到一种情况:有两种操作,分别为操作一和操作二,它们的操作次数相同,都为 N,且在进行第 K 次操作二前必须先进行至少 K 次操作一,问有多少中情况?结果就Catalan(N)。

     

    Catalan数的典型应用:

    1.由n个+1和n个-1组成的排列中,满足前缀和>=0的排列有Catalan(N)种。

    2.括号化问题。左括号和右括号各有n个时,合法的括号表达式的个数有Catalan(N)种。

    3.有n+1个数连乘,乘法顺序有Catalan(N)种,相当于在式子上加括号。

    4.n个数按照特定顺序入栈,出栈顺序随意,可以形成的排列的种类有Catalan(N)种。

    5.给定N个节点,能构成Catalan(N)种种形状不同的二叉树。

    6.n个非叶节点的满二叉树的形态数为Catalan(N)。

    7.对于一个n*n的正方形网格,每次只能向右或者向上移动一格,那么从左下角到右上角的不同种类有Catalan(N)种。

    8.对于在n位的2进制中,有m个0,其余为1的catalan数为:C(n,m)-C(n,m-1)。

    9.对凸n+2边形进行不同的三角形分割(只连接顶点对形成n个三角形)数为Catalan(N)。

    10.将有2n个元素的集合中的元素两两分为n个子集,若任意两个子集都不交叉,那么我们称此划分为一个不交叉划分。此时不交叉的划分数是Catalan(N)。

    11.n层的阶梯切割为n个矩形的切法数也是Catalan(N)。

    12.在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是Catalan(N)。

    展开全文
  • 卡特兰数详讲

    万次阅读 多人点赞 2018-07-18 20:57:04
     卡特兰数是一种经典的组合数,经常出现在各种计算中,其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...

    点击打开参考原博客

      一、关于卡特兰数

           卡特兰数是一种经典的组合数,经常出现在各种计算中,其前几项为 : 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, ...

          二、卡特兰数的一般公式

          卡特兰数满足以下性质:

          令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(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)。这个公式还可以更简单得化为h(n)=C(2n,n)/(n+1)。后一个公式都可以通过前一个公式经过几步简单的演算得来,大家可以拿起笔试试,一两分钟就可以搞定。

          

          三、卡特兰数的应用

          卡特兰数经常出现在OI以及ACM中,在生活中也有广泛的应用。下面举几个例子。

          1、进出栈问题栈是一种先进后出(FILO,First In Last Out)的数据结构.如下图1,1,2,3,4顺序进栈,那么一种可能的进出栈顺序是:1In→2In→2Out→3In→4In→4Out→3Out→1Out, 于是出栈序列为1,3,4,2

                                            

    那么一个足够大的栈的进栈序列为1,2,3,⋯,n时有多少个不同的出栈序列?

                我们可以这样想,假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数,一共有h(k-1)种方案。比k晚进栈且早出栈的有n-k个数,一共有h(n-k)种方案。所以一共有h(k-1)*h(n-k)种方案。显而易见,k取不同值时,产生的出栈序列是相互独立的,所以结果可以累加。k的取值范围为1至n,所以结果就为h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0)。

                出栈入栈问题有许多的变种,比如n个人拿5元、n个人拿10元买物品,物品5元,老板没零钱。问有几种排队方式。熟悉栈的同学很容易就能把这个问题转换为栈。值得注意的是,由于每个拿5元的人排队的次序不是固定的,所以最后求得的答案要*n!。拿10元的人同理,所以还要*n!。所以这种变种的最后答案为h(n)*n!*n!。

           

         2、二叉树构成问题。有n个结点,问总共能构成几种不同的二叉树。

                我们可以假设,如果采用中序遍历的话,根结点第k个被访问到,则根结点的左子树有k-1个点、根结点的右指数有n-k个点。k的取值范围为1到n。讲到这里就很明显看得出是卡特兰数了。这道题出现在2015年腾讯实习生的在线笔试题中。

         3、凸多边形的三角形划分。一个凸的n边形,用直线连接他的两个顶点使之分成多个三角形,每条直线不能相交,问一共有多少种划分方案。

                 这也是非常经典的一道题。我们可以这样来看,选择一个基边,显然这是多边形划分完之后某个三角形的一条边。图中我们假设基边是p1pn,我们就可以用p1、pn和另外一个点假设为pi做一个三角形,并将多边形分成三部分,除了中间的三角形之外,一边是i边形,另一边是n-i+1边形。i的取值范围是2到n-1。所以本题的解c(n)=c(2)*c(n-1)+c(3)*c(n-2)+...c(n-1)*c(2)。令t(i)=c(i+2)。则t(i)=t(0)*t(i-1)+t(1)*t(i-2)...+t(i-1)*t(0)。很明显,这就是一个卡特兰数了。

                

             4、有n+1个叶子的满二叉树的个数?事实上,向左记为+1,向右记为−1,按照向左优先的原则,从根节点开始遍历.例如第一个图记为+1,+1,+1,−1,−1,−1,于是由卡特兰数的含义可得满二叉树的个数为Cn。

             5、在n*n的格子中,只在下三角行走,每次横或竖走一格,有多少中走法?其实向右走相当于进栈,向左走相当于出栈,本质就是n个数出栈次序的问题,所以答案就是卡特兰数。(利用这个模型,我们解决这个卡特兰问题的变形问题,并顺便给进出栈问题的解法一个几何解释.)

    神奇的卡特兰数
             6、将一个凸n+2边形区域分成三角形区域的方法数?(答案卡特兰数)

    神奇的卡特兰数

        先介绍两个关于卡特兰数Cn的小引理,将问题一中的+1和−1分别看成左括号和右括号,我们得到

    引理一    由nn对括号形成的合法括号表达式的个数为C.

    比如n=3时,所有合法的括号表达式有 :((())),(())(),()(()),()()(),(()()),共5个.

    考虑n+1个数相乘,不同的相乘顺序的数目.我们可以给出每一个合法的括号表达式和一种可能的相乘顺序的对应方式.如n=3时,先取44个数a,b,c,d,然后在第一个数下设一个指针,将一个左括号看成是指针右移一格,而将右括号看成是将指针当前指向的数与其左侧的一个数作乘积,并删除左侧的那个数,那么当执行完括号表达式,就得到了一种可能的相乘顺序,如图.

    QQ20151106-2

    这样我们就从引理一出发得到了

    引理二    n+1个数连乘,不同的乘法顺序数为Cn.

        这样也是RPN模式的计算机的工作模式,可以无需括号完成计算,从而节省按键的次数.这种计算器在财务计算中大量使用,如图.

    QQ20151106-3

    接下来解决卡特兰问题,用1,2,3,⋯,n+2标记凸n+2边形的边,从标记为1的边的起点(按逆时针方向)开始按未标记的对角线均为向外标记方向,如图.

    QQ20151105-5(分别标记边和对角线)

     

    进而,逆时针读图,将出的箭头读为左括号,进的箭头读为右括号,就得到了剖分方式与连乘顺序的对应.上图中的两个图对应的连乘顺序表达式分别为 :1((2(34))5)6,(1(23))(45)6,

    抛开6不计,每个连乘顺序表达式实际上就是规定了n+1个数连乘时,不同的乘法顺序,根据引理一,得到剖分方式的总数为Cn。

            7、在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?和凸包切割一个原理。(答案卡特兰数)

    为了解决这个问题,我们重新解释卡特兰数的推导方式.先解决下面的辅助问题:(+1表示向左,-1表示向右)

    圆周上有2n+1个点,其中n+1个点上标“+1”,n个点上标“−1”,如果可以找到某个标有“+1”的点作为起点,当顺时针沿圆周前进时将所遇到的点(包括起点)上标的数相加得到的和始终为正数,就称这种标记法是好标记法.求好标记法的总数(注意考虑圆排列).

    辅助问题的解    对于任何一种标记法,我们将顺时针相邻的“+1”“−1”(指顺时针前进时先遇到“+1”后遇到“−1”)同时抹去,可以证明抹去的前后对标记法的好坏没有影响.不停的重复这一过程,则最后只剩一个标有“+1”的点,显然此时标记法为好的.因此所有的标记法都是好标记法,显然其数目为 (1/2*n+1)C(2*n+1,n)-(1/n+1)C(2n,n)

    问题的解    通过对辅助问题的进一步探索可知,每一种将圆周上2n+1个点标记为n+1个+1点,和n个−1点的方法唯一确定一个顺时针前进的方案(即起点).我们将这个起点删去,剩下的2n个点在顺时针方向上一定为“+1”“−1”“+1”“−1”,…,此时将顺时针相邻的这些“+1”“−1”点用弦连接起来,就得到互不相交的n条弦.这样我们就建立了从好标记法到弦的连法的单射.

    反过来,如果我们有了一种弦的连法,就可以从某条弦的端点出发顺时针前进,对每条弦的两个端点都是先遇到的端点标上“+1”,后遇到的端点标上“−1”,然后在最后回到出发点时添上一个标有“+1”的点.这样我们就建立了从弦的连法到好标记法的单射.

    综上,所求的不同连法数为(1/n+1)C(2n,n).

    7、n个长方形填充一个高度为n的阶梯状图形的方法个数?把包含左上角的矩形去掉,就很容易由递推公式二推得所有填充方法数就是卡特兰数。

    神奇的卡特兰数

    展开全文
  • 什么是卡特兰数

    2020-07-23 17:09:32
    卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。 数列的前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,… 卡特兰数Cn满足以下...

    #简介

    卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。
    数列的前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…

    • 卡特兰数Cn满足以下递推关系:
      • Cn+1 = C0Cn + C1Cn-1 + ··· + CnC0

    ##原理

    • 设h(n)为catalan数的第n+1项,令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) = 11 + 11 = 2
      • h(3) = h(0) * h(2) + h(1) * h(1) + h(2) * h(0) = 12+11+2*1 = 5

    #应用

    实质上都是递推等式的应用
    关于卡特兰数应用实例有很多,有一本书就讲了将近200个“卡特兰数”问题,由于篇幅原因,这里不做过多赘述,有兴趣的同学可以深入研究

    ##进出栈问题

    ###问题描述

    n个元素进栈序列为:1,2,3,4,…,n,则有多少种出栈序列。

    思路

    • 我们将进栈表示为 +1,出栈表示为 -1,则 1 3 2 的出栈序列可以表示为:+1 -1 +1 +1 -1 -1。

    • 根据栈本身的特点,每次出栈的时候,必定之前有元素入栈,即对于每个 -1 前面都有一个 +1 相对应。

    • 因此,出栈序列的 所有前缀和 必然大于等于 0,并且 +1 的数量 等于 -1 的数量。

    • 接下来非法序列怎么求?乍看之下完全没思路啊,如果用暴力解法那未免不要太麻烦,这时候我们采用逆向思维,就会发现这个问题并没有想象的那么难,公式如下:

      合法序列数 = 总序列数 - 非法序列数
    • 所以我们只需要求出总序列数和非法序列数然后相减即可得出合法序列数,总序列数很好求,即 C(n)(2n) ,那么非法序列数怎么求呢?

    • 还是逆向思维,说实话直接求非法序列数同样比较难求,但是我们可以这样:

    求得与非法序列数一一对应的另一种序列数,为了方便描述,这里称非法序列为 A,与 A 相对应的另一种序列为 B,对于B的定义是这样的:由于 A 是一个非法序列,必然存在某个位置的前缀和小于0的情况,那么,从左往右看,可以肯定的是,从某个位置开始,该位置前缀和突然小于0,且必然是-1(因为该位置是第一次前年缀和小于 0 的位置),比如序列:+1 -1 -1 +1 -1 +1,第三个1的前缀和首次小于0,那么我们就将该位置(包含该位置)之前的数字取反就得到了与A相对应的的序列 B:-1 +1 +1 +1 -1 +1,(怎么证明A和B是一一对应的关系呢?这么后面会讲,这里先记着肯定是一一对应的即可),这时候求得序列B的个数,即可得出 A 的个数,那么怎么求 B 的个数呢?
    对于 B,由于其是将A的第一个前缀和小于零的位置(包含该位置)之前的数取反得来的,所以每个 B 都有 (n + 1) 个 +1 以及 (n - 1) 个 -1,那么 B 的数量为 C(n+1)(2n) ,则 A 的数量同为 C(n+1)(2n)

    则合法序列数 = 总序列数 - 非法序列数 = C(n)(2n) - C(n+1)(2n)

    • 还有个问题,那么怎么证明A和B是一一对应的关系呢?

      • 因为每个 A 只有一个"第一个前缀和小于 0 的前缀",所以每个 A 只能产生一个 B。而每个 B 想要还原到 A,就需要找到"第一个前缀和大于 0 的前缀",显然 B 也只能产生一个 A
    • 因此同时满足以下条件即可转化为卡特兰数问题

      • ① +1和-1的个数相同皆为n个(这里+1和-1是虚指,代表两种事物,且只有这两种)
      • ② 序列每个位置的前缀和均大于等于0
        最终,满足该条件的序列数为:C(n)(2n) - C(n+1)(2n),另一种形式则为:C(n)(2n)/(n+1),求和便是Catalan递归式

    ##代码实现

    • Java实现
    import java.math.BigInteger;
    // 打印前 n 个卡特兰数
    int n = 20;
    BigInteger ans = BigInteger.valueOf(1);
    System.out.println("1:" + ans.toString());
    BigInteger four = BigInteger.valueOf(4); 
    BigInteger one = BigInteger.valueOf(1);
    BigInteger two = BigInteger.valueOf(2);
    for (int i = 2; i <= n; i++) {
        BigInteger bi = BigInteger.valueOf(i);
        ans = ans.multiply(four.multiply(bi).subtract(two)).divide(bi.add(one));
        System.out.println(i + ":" + ans.toString());
    }
    
    • Python实现
    # 打印前 n 个卡特兰数
    ans, n = 1, 20
    print("1:" + str(ans))
    for i in range(2, n + 1):
        ans = ans * (4 * i - 2) // (i + 1)
        print(str(i) + ":" + str(ans))
    

    ##其他问题

    1.二叉树

    • n + 1 个叶子节点能够构成多少种形状不同的(国际)满二叉树?
    • (国际)满二叉树定义:如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树。
    • 思路
      • 使用深度优先搜索这个满二叉树,向左扩展时标记为 +1,向右扩展时标记为 -1。

    2. 括号问题

    • n 对括号,则有多少种 “括号匹配” 的括号序列?
    • ( ( )( ) )···
    • 这个完全可直接转化为出入栈问题

    3. 排队问题

    • 8 个高矮不同的人需要排成两队,每队 4 个人。其中,每排都是从低到高排列,且第二排的第 i 个人比第一排中第 i 个人高,则有多少种排队方式?

    #总结

    • 基本上所有的卡特兰数问题经过一定的转换都可以还原成进出栈问题。因此,只要我们能够学会进出栈问题的解法,无论问题再怎么变化,本质还是不变的。
    • 卡特兰数问题中都会存在一种匹配关系,如进出栈匹配,括号匹配等,一旦计数问题中存在这种关系,那我们就需要去考虑这是否是卡特兰数问题。此外,我们还可以记住序列前四项:1, 1, 2, 5,这些将有利于我们联想到卡特兰数。
    展开全文
  • C++卡特兰数

    2019-10-20 16:06:20
    卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。但最早是欧拉在1753年解决凸包划分成三角形问题的时候,推出的...
  • 卡特兰数(Catalan数) 定义: 令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(n) = C(2n,n)/(n+1),n=0,1,2,3,… (其中C(2n,n)表示...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,716
精华内容 3,486
关键字:

卡特兰数