上下文無關(guān)文法，多元穩(wěn)定多項式及遞增樹.pdf

1、與上下文無關(guān)文法相關(guān)的微分算子的概念是由陳永川最先引入的。進(jìn)一步陳永川提出了運(yùn)用上下文無關(guān)文法生成組合多項式的框架。此后上下文無關(guān)文法被廣泛用于生成和處理組合多項式。Borcea和Br(a)ndén發(fā)展了多元多項式的穩(wěn)定性理論。在他們工作的基礎(chǔ)上Haglund和Visontai提出了一個證明Stirling排列和r-Stirling排列生成函數(shù)的穩(wěn)定性的方法。本文的主要目的是運(yùn)用上下文無關(guān)文法來生成多元組合多項式，并證明多元組合多項式的

2、穩(wěn)定性。同時，我們將通過恰當(dāng)?shù)奈姆?biāo)號生成一些組合結(jié)構(gòu)并利用上下文無關(guān)文法得到相關(guān)的組合恒等式。
　　論文結(jié)構(gòu)如下。第一章我們主要介紹相關(guān)的背景知識，基本概念及常用符號。我們將著重對Haglund和Visontai所做的關(guān)于Stirling排列和r-Stirling排列生成函數(shù)的穩(wěn)定性的工作進(jìn)行介紹。
　　在第二章中，我們回顧了上下文無關(guān)文法的相關(guān)背景。在本章節(jié)中我們將集中介紹如何使用上下文無關(guān)文法刻畫組合結(jié)構(gòu)并生成相關(guān)的組

3、合多項式，例如:Stirling多項式，Eulerian多項式及二階Eulerian多項式。其中，我們主要研究了包含多個參數(shù)的組合多項式。
　　第三章，我們主要介紹如何運(yùn)用上下文無關(guān)文法生成多元組合多項式，并證明其穩(wěn)定性?；贐orcea和Br(a)ndén給出的關(guān)于保持多重仿射多項式穩(wěn)定性的算子的刻畫，我們給出運(yùn)用上下文無關(guān)文法證明多元多項式的穩(wěn)定性的方法。進(jìn)一步，我們將給出一些通過上下文無關(guān)文法生成的多元多項式的穩(wěn)定性證明。其

4、中我們解決了Haglund和Visontai提出的關(guān)于給出Legendre-Stirling排列下降位的生成函數(shù)的穩(wěn)定細(xì)化的問題。三項遞推關(guān)系是組合數(shù)學(xué)中一類重要的遞推關(guān)系，在本章結(jié)尾我們給出了一個生成特殊三項遞推關(guān)系的文法。運(yùn)用這個文法我們得到了一些新的組合恒等式，并且給出一組算子生成滿足該三項遞推關(guān)系序列的生成函數(shù)。在此基礎(chǔ)上我們得到了此算子保持穩(wěn)定性的充分必要條件。
　　在第四章中，我們主要說明了一些可以遞歸生成的組合結(jié)構(gòu)都

5、是可以由上下文無關(guān)文法生成的，例如:遞增樹，遞增二叉樹，自反排列，遞增圈樹及強(qiáng)受限森林。通過上下文無關(guān)文法，這些組合結(jié)構(gòu)的性質(zhì)往往可以被容易的證明。在本章中，我們引入了一種被稱之為禁止替換的特殊替換規(guī)則，我們將利用含有禁止替換規(guī)則的上下文無關(guān)文法來生成一些組合結(jié)構(gòu)并證明一些組合恒等式。
　　在第五章中，我們將上下文無關(guān)文法與缸模型相關(guān)聯(lián)。我們利用缸模型對刻畫排列中連續(xù)的132型及強(qiáng)受限森林中的絕對孤立點的上下文無關(guān)文法進(jìn)行分析，并