避免双3长Vincular模式排列的计数研究.pdf
《避免双3长Vincular模式排列的计数研究.pdf》由会员分享,可在线阅读,更多相关《避免双3长Vincular模式排列的计数研究.pdf(8页珍藏版)》请在咨信网上搜索。
1、Pure Mathematics 理论数学理论数学,2023,13(10),3111-3118 Published Online October 2023 in Hans.https:/www.hanspub.org/journal/pm https:/doi.org/10.12677/pm.2023.1310322 文章引用文章引用:赵沨,朱泉龙,李晓清.避免双 3 长 Vincular 模式排列的计数研究J.理论数学,2023,13(10):3111-3118.DOI:10.12677/pm.2023.1310322 避免双避免双3长长Vincular模式排列的计数研究模式排列的计数研究
2、赵赵 沨沨1,朱泉龙朱泉龙2,李晓清李晓清2*1河北师范大学数学科学学院,河北省数学与交叉科学国际联合研究中心,河北省数学研究中心,河北省计算数学与应用重点实验室,河北 石家庄 2中国石油大学理学院,北京 收稿日期:2023年9月23日;录用日期:2023年10月24日;发布日期:2023年10月31日 摘摘 要要 本文首先介绍有禁排列相关的基本定义,对避免双本文首先介绍有禁排列相关的基本定义,对避免双3长长vincular模式排列的计数结果进行整理,将计数结模式排列的计数结果进行整理,将计数结果相同的模式用表格的形式进行分类。随后我们使用特殊元素分析与位置分析这两种方法,给出果相同的模式用表
3、格的形式进行分类。随后我们使用特殊元素分析与位置分析这两种方法,给出()321,312nS、()123,312nS等等8个避免双个避免双3长长vincular模式排列计数结果的代数证明。模式排列计数结果的代数证明。关键词关键词 排列,有禁模式,组合计数排列,有禁模式,组合计数 Enumeration of Permutations Avoiding Double Vincular Patterns of Length 3 Feng Zhao1,Quanlong Zhu2,Xiaoqing Li2*1Hebei Key Laboratory of Computational Mathematic
4、al and Applications,Hebei Mathematical Research Center,Heibei International Joint Research Center of Mathematics and Interscience,School of Mathematical Science,Heibei Normal University,Shijiazhuang Hebei 2College of Sciences,China University of Petroleum,Beijing Received:Sep.23rd,2023;accepted:Oct.
5、24th,2023;published:Oct.31st,2023 Abstract This article first introduces the basic definitions related to forbidden permutations,and summarizes the counting results of bivincular patterns of length 3.We classify patterns with the same counting results and present them intabular form.Additionally,we
6、also provides algebraic proofs for the counting results of eight bivincular patterns of length 3,including()321,312nS and()123,312nS,赵沨 等 DOI:10.12677/pm.2023.1310322 3112 理论数学 using two mainmethods:analysis of special elements and analysis of positions.Keywords Permutation,Pattern Avoidance,Combina
7、torial Enumeration Copyright 2023 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 排列是一种重要的离散结构,在组合数学中具有其重要的研究意义1,其中有禁排列的计数理论是近些年来较为热门的研究方向。在上世纪 60 年代末,Knuth 2研究计算机的排序算法时
8、发现了有禁排列在其领域的首个明确应用,他发现有禁模式与堆栈的分类有关,这次发现使得越来越多的学者开始关注并深入研究有禁排列这个领域。在 1985 年,Simion 和 Schmidt 3首次对有禁排列进行了系统研究,他们的相关成果不仅丰富了排列与其他组合结构之间的对应关系4,还促进了有禁排列之间 Wilf-等价关系的研究5。至此以后,对有禁排列的研究开始逐步形成体系,学者们也对有禁模式的研究逐渐拓宽限制6。在1981年,Rotem 7对避免双3长普通模式的排列进行了研究,得到()231,312nS的计数结果是12n。1995 年,Julian West 8提出了生成树应用于()132,231n
9、S的计数问题。1997 年,Mikls Bna 9首次解决了 Sn避免单个 4 长模式的排列计数问题,得到()1342nS的生成函数,并证明了()1342nS的计数结果等于n 个顶点上某种类型的标记平面数。到了 2000 年,Babson 和 Steingrmsson 10提出了 vincular 模式,其要求模式中需存在相连的部分,拓宽了对有禁排列的研究道路,因此有更加丰富多样的有禁模式问题等待着人们的探究。此外,Claesson 11研究了避免单一 3 长 vincular 模式和避免双 3 长 vincular 模式排列的计数结果,并建立了()123,132nS与 Motzkin 路之间
10、的双射11。这个研究打开了 Motzkin 数与 Catalan 数之间的研究方向,此后更多计数结果为 Motzkin 数与 Catalan 数的有禁排列在此基础上被深入研究。在 2003 年,Kitaev 利用归纳法得到了()213,312nS的计数结果是12n 12。自此学者们开始对避免双 vincular 模式排列的计数问题与其他组合结构之间建立双射进行研究。此后不久,Elizalde 和 Mansour 在 2005 年通过与 Motzkin 路之间建立双射得到()123,132nS的计数结果是第 n 个 Motzkin 数13。在 2010 年,Barnabei、Bonetti 和
11、Silimbani 14也通过与 Motzkin 路之间建立双射得到()213,312nS的计数结果是第 n 个 Motzkin 数。在上述学者研究的基础上,本文中我们给出了部分避免双 3 长 vincular 模式排列的部分计数结果,并使用特殊元素法和位置分析法提供了代数证明。2.有禁排列的基本理论有禁排列的基本理论 记 Sn表示 1,2,nn=的排列集合。我们可以将每个排列nS表示为12n,其中i表示排列从左往右第 i 个位置上的数。对1,2,1in=,我们称i与1i+左邻接,元素1i+与i右邻接。如果对每一个指标 i,满足11ii+=+(或11ii+=),则称排列是连续递增(或递减)的。
12、定义定义 1 一个排列的前缀是一个对于某个正整数 p,取连续的初始子序列12p。定义定义 2 给定一个排列nS,如果()()1ii+,则称位置1in是的下降。类似地,如果Open AccessOpen Access赵沨 等 DOI:10.12677/pm.2023.1310322 3113 理论数学 1ii+,则称位置1in是的上升。定义定义 3 给定一个排列nS,如果存在指标1kcc v。由此令1n在第()2,3i inn=位,记排列为()1lrn,显然()1321,312ilS,()321,312n irS,这时仅对于1n的位置的排列结果为 223nin ina a。同理,当我们固定1n的
13、位置讨论2n时发现,对于2n同样只有,2,1u nn与2,1nu n两种排列方式。这时对于2n的位置的排列结果为 425nin ina a。由此,因为3n,我们可以归纳出当 n 在倒数第二位时的数量为 220nin ia a。综合上述两种情况,可得:()21203nnnin iaaa an=+。赵沨 等 DOI:10.12677/pm.2023.1310322 3115 理论数学 将递推关系式与nM的递推关系式对比,并结合初值可证()3nnaMn=。证毕。定理定理 3 对于2n,用()1321,312nS表示()321,312nS中首位上升的排列组成的集合,记()1321,312nnbS=,则
14、有1nnnbbM+=。证明证明 对于()1321,312nS中任一排列,记LRn=,由于避免321模式且避免 312 模式,显然n 不可能出现在首位。当 n 不在首位时。上文已证()321,312nnSM=,用()2321,312nS表示()321,312nS中首位下降的排列组成的集合。对任取的()2321,312nS,由于避免321模式,则12,32。为了保证该排列避免 312 模式,必须满足121=+。去掉1,对于34n 中大于2的数都减 1,操作后得到的排列()11321,312nS。反之,任取一排列()11 211321,312nnS=,在中第一个位置前面插入11+,其后比1大的数都加
15、 1,得到的排列()2321,312nS。因此,综合上述两种情况,可得()()1111321,312321,312nnnnnMSSbb+=+。证毕。定理定理 4 对于1n,有()()123,312112nn nS=+。证明证明 对于()123,312nS中任一排列,记LRn=,则 n 在排列中的位置可分为两种情况:1)当 n 在首位时。此时排列L为空且排列R中任一元素均小于 n,显然R满足避免 123 模式。又R避免 312 模式,则R首位21n=,否则一定存在1in=,3in,使得2in 构成 312 模式。同理我们得到R的第二位32n=,第三位43n=,故R是一个单调递减的排列。所以该情况
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 避免 Vincular 模式 排列 计数 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。