組合計(jì)數(shù)中的DSV方法及應(yīng)用.pdf

1、計(jì)數(shù)是組合分析的基本內(nèi)容。在解決各種各樣的計(jì)數(shù)問(wèn)題中，人們引進(jìn)了許多方法和工具，比如生成函數(shù)。建立計(jì)數(shù)序列的生成函數(shù)是解決計(jì)數(shù)問(wèn)題的常用方法之一，它也有許多技巧和方法。DSV方法（Delest-Schutzsnberger-Viennot）就是其中一種。這一方法產(chǎn)生于上世紀(jì)六十年代，受計(jì)算機(jī)語(yǔ)言的啟發(fā)而提出的。其思想方法是先對(duì)計(jì)數(shù)對(duì)象進(jìn)行編碼，使每一個(gè)計(jì)數(shù)對(duì)象和它的編碼一一對(duì)應(yīng)，從而轉(zhuǎn)化為編碼（稱為文字）的計(jì)數(shù)問(wèn)題，然后構(gòu)造代數(shù)文法，建

2、立形式方程系，再解得計(jì)數(shù)對(duì)象的生成函數(shù)，最后得到計(jì)數(shù)結(jié)果。
　　本文首先概述了DSV方法的發(fā)展歷史以及它的工作原理和思想方法。然后使用DSV方法系統(tǒng)地研究了兩類計(jì)數(shù)問(wèn)題：第一、步鏈為2、3、4時(shí)的Dyck路的計(jì)數(shù)，給出了這三種類型16種情況的二元生成函數(shù)；第二、避免多個(gè)置換的有禁置換的計(jì)數(shù)，研究了形如S(312，σ，τ，…)和S(321，σ，τ，…)的置換，得到了其生成函數(shù)共12個(gè)。研究過(guò)程和結(jié)果展現(xiàn)了DSV方法的簡(jiǎn)潔、靈活和有效