组合计数中的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
文章首先探讨了公共危机信息准备的内涵,然后将公共危机信息准备核心能力归纳为规划、态势感知、信息资源管理、执行四个大类共十七种具体能力,最后结合危机准备周期理论论述
The Hoek-Brown criterion was introduced in 1980 to provide input for the design of underground ex-cavations in rock. The criterion now incorporates both intact
Excavation damage under high in situ stress depends largely upon the potential block size associated with any violent ejection. The size and shape of the dynami
改革开放以来,我省外商投资企业迅猛发展,规模不断壮大,到2002年底,全省已开业、投产的外商投资企业达2.8万家,中方从业人员390多万人。近年来,我省各级党委和外商投资企业党
薛毅1923年出生于河北完县(今顺平县)城区一个贫民家庭。15岁投身到抗日战争的洪流,16岁加入中国共产党。他虽只求学至高小毕业,但勤奋好学,在战争年代就已写出不少生动的宣
分圆Temperley-Lieb代数[4],是Temperley-Lieb代数[6]的推广.这类代数既可以用生成元和关系定义,也可以用图来定义.受到J.Eyang[1]关于Temperley-Lieb代数工作的影响,我们将
Rock mechanics plays a critical role in the design and construction of hydroelectric projects including large cavs under high in situ stress, deep tunnels with