liweiguo_10加特兰数.ppt_第1页
liweiguo_10加特兰数.ppt_第2页
liweiguo_10加特兰数.ppt_第3页
liweiguo_10加特兰数.ppt_第4页
liweiguo_10加特兰数.ppt_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1 加特兰( Catalan )数,一、加特兰数的定义,第八章 特殊计数序列,n+1条边组成的凸多边形,被n-2条不相交的对角线分成 n-1个三角形区域。,二、加特兰数的背景1,n=4 时,K是由n+1条边组成的凸多边形,n-2条不相交的 对角线把 K 分成n-1个三角形。,问有多少种不同的分法？,加两条辅助线：,n+2条边组成的凸多边形,被分成 n个三角形区域的分法总数。,加特兰数,三、加特兰数的背景2,由n个1和n个-1组成排列：,证明：,不允许： ,1,-1,1,-1,-1,-1,1,-1,1,变 换： -,-1,1,-1,1,1,1,1,-1,1,前7个元素变号，后三个元素不动。 此时

2、1增加1个，-1 减少一个：有n+1个1，n-1个-1,第7个位置首先不满足！ 前6个元素之和=0，第7个元素必为-1。,每个不允许排列可对应 有n+1个1和n-1个-1的一个排列。,变为不允许排列： ,1,-1,1,-1,-1,-1,1,-1,1,给定排列： -,-1,1,-1,1,1,1,1,-1,1,前7个元素变号，后三个元素不动。 此时-1增加1个，1 减少一个：有n个1，n个-1 而且一定是不允许排列。,前7项和首先大于0。 前6个元素之和=0，第7个元素必为1。,反之， 每个有n+1个1和n-1个-1的排列 也可对应一个不允许排列。,所有n+1个1和n-1个-1的排列 与所有不允许

3、排列一一对应。,例1 （零钱问题）,解,有2n个人排队买电影票，0.50元/张。 若售票处没有准备零钱，问总有零钱找的排队方法有多少种？,四、应用问题,用零钱买票的人1，用整币买票的人为-1,满足前k项和大于等于0的排队方法即为所求。,所以，能顺利找零的排队数就是加特兰数,如果认为人有区别，则还应考虑1和-1的排列。,例2 （上班路径问题）,解：,我家与办公室南北相隔n个街区，东西也相隔n个街区。若不穿过对角线，有多少种走法？,向右为1，向上走-1，,当1的个数大于等于-1的个数时，路径在对角线下方。,由对称性，对角线上方的路径数与之相同。所以,怎样加括号？,例3 乘法结合律,例3 乘法结合律,用二分树表示：,例3 结合率

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论