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

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

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

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

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

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