首页 > 其他分享 >【学习笔记】卡特兰数

【学习笔记】卡特兰数

时间:2023-10-28 22:22:25浏览次数:33  
标签:公式 路径 笔记 卡特兰 学习 2n times binom

卡特兰数

定义:

卡特兰数的计算公式涉及组合计数,它是很多组合问题的数学模型,是一个很常见的数列。

\(\bf{\underline{卡特兰数(Catalan)}}\) 是一个数列,它的一种定义是:

\[C_n=\frac{1}{n+1}\binom{2n}{n},n=0,1,2,... \]

卡特兰数有三个计算公式:

公式1

\[C_n=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n}-\binom{2n}{n+1} \]

适用于 \(n\) 较大的情况。

公式2

\[C_n=\sum C_kC_{n-k},C_0=1 \]

适用于 \(n\) 较小的卡特兰数,不需要求逆元,复杂度 \(n^2\)。

公式3

\[C_n=\frac{4n-2}{n+1}C_{n-1},C_0=1 \]

接下来我们通过棋盘问题来推导公式1,通过二叉树问题来推导公式2。

应用

  • \(\bf{\underline{棋盘问题(公式1)}}\)

问题描述:现有一个 \(n\times n\) 的棋盘,从左下角走到右上角,且一直在主对角线下面走,不能穿过主对角线,求路径的方案数。

这个限制等价于走到任意一步 \(k\) 都需要满足向右走的次数大于等于向上走的次数。

首先不考虑主对角线的限制,那么从 \((0,0)\) 走到 \((n,n)\) 的方案数为 \(\binom{2n}{n}\),组合意义为:

每一步我可以选择向上走(记为 \(1\))和向右走(记为 \(2\)),一共走 \(2n\) 步,相当于一个长度为 \(2n\) 的全部为 \(0\) 的序列,我们需要选择其中的 \(n\) 个位置将其填为 \(1\),即 \(2n\) 选 \(n\),为 \(\binom{2n}{n}\)。

那么我们考虑加上这个限制,需要从总方案数上减去不合法方案数,我们看一种不合法情况:

image

如图,我们在对角线上面一格再画一个与其平行的对角线,可以发现只有所以穿过红线的路径(即不合法路径)才和蓝线有交,我们就是要统计这样的路径。
然后我们将这些路径在跨过红线后的部分关于蓝线对称:

image

可以发现这些线的终点都是 \((n-1,n+1)\),也就是 \((n,n)\) 关于蓝线对称后的点,这些路径与原跨过红线的路径都是一一对应的,这部分的方案数同理是 \(\binom{2n}{n-1}\),即不合法的路径数量,所以合法的路径的数量的即为两者相减:

\[\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n} \]

这正好就是卡特兰数的公式1。

  • \(\bf{\underline{括号问题(公式1)}}\)

问题描述:用 \(n\) 个左括号和 \(n\) 个右括号,求能组合出多少种合法的括号序列。

发现问题就是对于该字符串的任意长度前缀,都要满足左括号的数量大于等于右括号的数量,和上面的棋盘问题实际上是一样的,方案数为 \(C_n\)。

  • \(\bf{\underline{出栈序列问题(公式1)}}\)

问题描述:给定一个入栈序列,求有多少种不同的出栈序列?

对于每个数,都是入栈一次,出栈一次,对于每个时刻,只有栈的大小大于等于 \(1\) 才可以出栈,即每时每刻需要满足入栈次数大于等于出栈次数,还是卡特兰数、

  • \(\bf{\underline{二叉树问题(公式2)}}\)

问题描述:\(n\) 个节点构成的二叉树,求有多少种不同的形态?

这个问题其实就是公式2的模型,设 \(f_{x,i}\) 为 \(x\) 子树分配 \(i\) 个点的答案,考虑从叶子节点往上递归。

对于叶子节点,\(f_{x,0}=1\)

对于一个非叶子节点 \(x\),设其左子树节点数量+右子树节点数量 \(=k\),则

\[\begin{aligned} f_{x,k} & = f_{ls,k}\times f_{rs,0}+f_{ls,k-1}\times f_{rs,1}+...+f_{ls,1}\times_{rs,k-1}+f_{ls,0}+f_{rs,k}\\ & = \sum f_{ls,i}\times f_{rs,k-i} \end{aligned} \]

为卡特兰数递推式。

\[C_n=\sum C_i\times C_{n-i},C_0=1 \]

没了。

标签:公式,路径,笔记,卡特兰,学习,2n,times,binom
From: https://www.cnblogs.com/cccomfy/p/17794780.html

相关文章

  • 学习笔记7
    第四章并发编程这一章主要介绍了并发编程的相关内容,包括并行计算、顺序算法与并行算法以及并行性和并发性;解释了线程的原理机器相对于进程的优势,同时还进行了线程管理、并发编程的实际操作,让我们更加深刻地了解多任务处理、线程同步和并发编程的原理及方法。并行计算基于分治......
  • 第九周Linux学习笔记
    本周的学习内容属实有点多(差点跟不上,浅浅吐槽一下),学习了第五章进程管理以及第六章I/O重定向。具体命令及其作用在下面一一列举。第五章:进程管理进程小tips:每个进程都有唯一的进程表示PID;进程有就绪态、阻塞态和运行态三个状态;进程有的是密集型有的是疏散型。1、“psaux”命令,......
  • 关于学习Mybatis-plus的认识
    1.实体类的类名和属性尽量一致,如果不一致需要用注解进行指定。2.mybatis-plus是把实体类的类名直接转换成小写到数据库查找,所以需要@TableName(value="表名")来指定表的名字进行查询@TableName("sys_user")publicclassUser{privateLongid;privateStringn......
  • 现代企业管理的部分复习笔记
    因为不是专业课学的比较随意,大概会分成四个部分,三个内容一个部分题,最近就要考试了,共勉格式问题显示不好  用word写的,链接如下我用夸克网盘分享了「现代企业管理.docx」,点击链接即可保存。打开「夸克APP」在线查看,支持多种文档格式转换。链接:https://pan.quark.cn/s/aacef986......
  • 《信息安全与设计》第四章学习笔记
    《信息安全与设计》第四章学习笔记第四章并发编程并行计算导论顺序算法与并行算法顺序算法:所有步骤通过单个任务依次执行,每次执行一个步骤,当所有步骤执行完成时,算法结束。并行算法:cobegin-coend代码块来指定独立任务,所有任务都是并行执行的,紧接着代码块的下一个步骤将只在......
  • 学习笔记7
    目录知识点归纳第4章并行计算并行性和并发性线程线程同步苏格拉底挑战问题与解决方案实践过程知识点归纳第4章并行计算并行性和并发性并行算法只识别可并行执行的任务。CPU系统中,并发性是通过多任务处理来实现的。通常,并行算法只识别可并行执行的任务,但是它没有规定如何将......
  • AJAX学习(四)-(axios核心的原理)
    一、Promise1.定义Promise对象用于表示一个异步操作的最终完成(或失败)及其结果值我们用一张图来清晰的看Promise位于哪里2.好处1.逻辑更清晰2.了解axios函数内部运作机制3.能解决回调函数地狱问题3.使用语法及步骤示例代码如下:<!DOCTYPEhtml><htmllang="en"><head><metacha......
  • 大数据的机器学习应用
    当谈到大数据时,机器学习扮演了至关重要的角色。它不仅能够处理庞大的数据集,还能从中提取有价值的信息,并为企业和组织提供深刻的洞察。本文将探讨大数据中机器学习的应用,以及如何使用Python实现一些基本的机器学习算法。什么是大数据的机器学习应用?大数据的机器学习应用是利用机器......
  • 20231327 司宏林《计算机基础与程序设计》第5周学习总结
    学期(2023-2024-1)学号(20231327)《计算机基础与程序设计》第5周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2023-2024-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2023-2024-1计算机基础与程序设计第5周作业)这个作业的目标<关于机器语......
  • 第八周Linux教材第四章学习笔记——并发编程
     第四章 并发编程4.1并行计算导论在早期,大多数计算机只有一个处理组件,称为处理器或中央处理器(CPU)。受这种硬件条件的限制,计算机程序通常是为串行计算编写的。要求解某个问题,先要设计一种算法,描述如何一步步地解决问题,然后用计算机程序以串行指令流的形式实现该算法。在只有......