专栏首页程序编程之旅卡特兰数(Catalan Number) 算法、数论 组合~

卡特兰数(Catalan Number) 算法、数论 组合~

Catalan number,卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡特兰数的前几个数 前20项为(OEIS中的数列A000108):1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

在这里我只详细证明一个例子: (和我后面要写的一个HD题目有关).(HD1133题) 即排队买票问题(出栈次序问题): 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?   有2n个人排成一行进入公园。入场费1元。其中只有n个人有一张1元钞票,另外n人只有2元钞票,剧院无其它钞票,问有多少中方法使得只要有2元的人买票,售票处就有1元的钞票找零?(将持1元者到达视作将1元入栈,持2元者到达视作使栈中某1元出栈)

不难看出,该题求的是左端点为首元素的任意区间内,1的个数大于等于2的个数。

方法一:折现法 可以认为问题是,任意两种操作,持1元者买票是操作一,持2元买票者是操作二。要求每种操作的总次数一样,且进行第k次操作2前必须先进行至少k次操作1。我们假设一个人在原点,操作1是此人沿右上角45°走一个单位(一个单位设为根号2,这样他第一次进行操作1就刚好走到(1,1)点),操作2是此人沿右下角45°走一个单位。第k次操作2前必须先进行至少k次操作1,就是说明所走出来的折线不能跨越x轴走到y=-1这条线上!在进行n次操作1和n此操作2后,此人必将到到达(2n,0)!若无跨越x轴的限制,折线的种数将为C(2n,n),即在2n次操作中选出n次作为操作1的方法数。

现在只要减去跨越了x轴的情况数。对于任意跨越x轴的情况,必有将与y=-1相交。找出第一个与y=-1相交的点k,将k点以右的折线根据y=-1对称(即操作1与操作2互换了)。可以发现终点最终都会从(2n,0)对称到(2n,-2)。由于对称总是能进行的,且是可逆的。我们可以得出所有跨越了x轴的折线总数是与从(0,0)到(2n,-2)的折线总数。而后者的操作2比操作1要多0-(-2)=2次。即操作1为n-1,操作2为n+1。总数为C(2n,n-1)。

这个证明的关键就是最终一定会到达(2n,0)这个点。

对于不满足情况的方案,它一定会越过y=-1,捉住这个特点,我们可将求不合法的方案数这个问题换个说法来:从(0,0)到(2n,-2)一共有多少种走法?这个走法数就是C(2n,n-1)因为走右下角的要多走2步,同时一共只走2n步,那就右下角走n+1步,方案法就是2n选n-1.

合法数=C(2n,n)-C(2n,n-1);

方法二:

还可以等价为求从A点到B点不超过(可接触)红色对角线的最短路径的数量。

如图,易知所有超过红色红色对角先的路径都会碰到绿线。 对A做关于绿线的对称点A’。则A’到B点的路径总数即为非法路径总数。

合法路径数=总路径数-非法路径数=C(2n,n)-C(2n,n-1)。

每個人都是不一樣的,所以需要全排列* n!*n!

可以推广到一般形式,1元的m人,2元的n人。 ( C(m+n,n) - C(m+n,m+1) ) * m! * n!= ( C(m+n,n) - C(m+n,n-1) ) * m! * n!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 卡特兰数

          简介:卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔...

    用户2965768
  • 排队问题

    最近许多人认为我已经工作了,认为我文章应该会天天更新,我在这里再次声明我是学生,这学期课比较多,课后作业也有点多,文章只能周末放假时更新,给大家带来了不便,敬请...

    不可言诉的深渊
  • 一道面试题到卡特兰数及其应用

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

    大黄大黄大黄
  • 卡特兰数问题-LeetCode 96(卡特兰数,BST的构成,圆内连弦)

    卡特兰(Catalan)数来源于卡特兰解决凸n+2边形的剖分时得到的数列Cn,在数学竞赛、信息学竞赛、组合数学、计算机编程等方面都会有其不同侧面的介绍.卡特兰问...

    算法工程师之路
  • 卡特兰数简介原理性质应用参考:

    简介 卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。 卡塔兰数的一般项公式为: ? 卡特兰公式 其前20项为:1, 1, 2, ...

    致Great
  • Catalan数列及其应用

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • 卡特兰数(Catalan)

    卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。个人觉得和斐波那契数列差不多,卡特兰数的地推公式为:pre(n) = pre(0)...

    Ch_Zaqdt
  • 【python刷题】关于一个序列的入栈出栈有多少种方式相关

    剑指offer上有这么一道题目: 题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不...

    西西嘛呦
  • 【编程之美】票买完了,零钱哪去了?

    买票找零 假设有2N个人在排队买票,其中有N个人手持50元的钞票,另外有N个人手持100元的钞票,假设开始售票时,售票处没有零钱,问这2N个人有多少种排队方式...

    程序员互动联盟
  • 11张图带你走过数据可视化的前生今世

    大数据文摘
  • Catalan数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    狼啸风云
  • 堆栈的应用——用JavaScript描述数据结构

    接下来,就是在原型上,对入栈、出栈、清空栈、读取栈顶、读取整个栈数据这几个接口的实现。 Stack类默认以数组头部做栈底,尾部做栈顶。

    我是leon
  • 6段Python代码刻画深度学习历史:从最小二乘法到深度神经网络

    【新智元导读】深度学习为什么会成为今天的样子?让我们用六段代码来刻画深度学习简史,用Python展现深度学习历史上关键的节点和核心要素,包括最小二乘法、梯度下降...

    新智元
  • 卡特兰数入门

    括号的合法匹配方式为:一个左括号对应一个右括号,且左括号必须要在右括号前面出现。为了方便说明,这里将左括号记作 +1,右括号记作 -1,则一个合法序列和一个非法...

    口仆
  • 数据结构(3):栈(上)

    栈(Stack)是一种只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。

    不可言诉的深渊
  • 常用算法整理

    王磊-AI基础
  • 卡特兰数入门

    简介 卡特兰数是组合数学中的一种常见数列 它的前几项为: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58...

    attack
  • NOIP复习内容

    https://www.luogu.org/problemnew/lists?name=GSS&orderitem=pid&tag=&content=0&typ...

    attack
  • 困扰数学界80多年的单位猜想,被一位博士后推翻了

    一个困扰了数学界80多年的单位猜想,被一个博士后研究员证伪了。他在晶体形状的对称性结构中,发现了一个关于乘法逆元基本猜想的反例。

    AI科技评论

扫码关注云+社区

领取腾讯云代金券