组合计数中的DSV方法及应用

来源 :杭州师范大学 | 被引量 : 0次 | 上传用户:ALIMHL
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
计数是组合分析的基本内容。在解决各种各样的计数问题中,人们引进了许多方法和工具,比如生成函数。建立计数序列的生成函数是解决计数问题的常用方法之一,它也有许多技巧和方法。DSV方法(Delest-Schutzsnberger-Viennot)就是其中一种。这一方法产生于上世纪六十年代,受计算机语言的启发而提出的。其思想方法是先对计数对象进行编码,使每一个计数对象和它的编码一一对应,从而转化为编码(称为文字)的计数问题,然后构造代数文法,建立形式方程系,再解得计数对象的生成函数,最后得到计数结果。  本文首先概述了DSV方法的发展历史以及它的工作原理和思想方法。然后使用DSV方法系统地研究了两类计数问题:第一、步链为2、3、4时的Dyck路的计数,给出了这三种类型16种情况的二元生成函数;第二、避免多个置换的有禁置换的计数,研究了形如S(312,σ,τ,…)和S(321,σ,τ,…)的置换,得到了其生成函数共12个。研究过程和结果展现了DSV方法的简洁、灵活和有效性。
其他文献
本文利用Ginzburg-Landau模型,主要研究了超导体在外磁场及通电情况下,正常态的稳定性以及相关问题。Ginzburg-Landau模型在液晶超导理论中占有极其重要的地位,表示如下:该方
我们对Dilcher和Prodinger给出的一些与divisor函数相关的q-级数恒等式进行新的推广,得出以下主要结果(公式略),然后我们给出一些有趣的特例,其中包括Corteel和Lovejoy研究过的
设厂为区域D内的一族全纯函数,k是一正整数,a1(z),a2(z)为区域D内的两个全纯函数,满足|a1(z)|2+|a2(z)|2≠0.若对于厂中的每一个函数f,f的零点重级均大于等于k,且f(z)=0(?)|f(k)(z)|≤M(常数M>0
分圆Temperley-Lieb代数[4],是Temperley-Lieb代数[6]的推广.这类代数既可以用生成元和关系定义,也可以用图来定义.受到J.Eyang[1]关于Temperley-Lieb代数工作的影响,我们将