论文部分内容阅读
计数是组合分析的基本内容。在解决各种各样的计数问题中,人们引进了许多方法和工具,比如生成函数。建立计数序列的生成函数是解决计数问题的常用方法之一,它也有许多技巧和方法。DSV方法(Delest-Schutzsnberger-Viennot)就是其中一种。这一方法产生于上世纪六十年代,受计算机语言的启发而提出的。其思想方法是先对计数对象进行编码,使每一个计数对象和它的编码一一对应,从而转化为编码(称为文字)的计数问题,然后构造代数文法,建立形式方程系,再解得计数对象的生成函数,最后得到计数结果。 本文首先概述了DSV方法的发展历史以及它的工作原理和思想方法。然后使用DSV方法系统地研究了两类计数问题:第一、步链为2、3、4时的Dyck路的计数,给出了这三种类型16种情况的二元生成函数;第二、避免多个置换的有禁置换的计数,研究了形如S(312,σ,τ,…)和S(321,σ,τ,…)的置换,得到了其生成函数共12个。研究过程和结果展现了DSV方法的简洁、灵活和有效性。