论文部分内容阅读
与上下文无关文法相关的微分算子的概念是由陈永川最先引入的。进一步陈永川提出了运用上下文无关文法生成组合多项式的框架。此后上下文无关文法被广泛用于生成和处理组合多项式。Borcea和Br(a)ndén发展了多元多项式的稳定性理论。在他们工作的基础上Haglund和Visontai提出了一个证明Stirling排列和r-Stirling排列生成函数的稳定性的方法。本文的主要目的是运用上下文无关文法来生成多元组合多项式，并证明多元组合多项式的稳定性。同时，我们将通过恰当的文法标号生成一些组合结构并利用上下文无关文法得到相关的组合恒等式。 论文结构如下。第一章我们主要介绍相关的背景知识，基本概念及常用符号。我们将着重对Haglund和Visontai所做的关于Stirling排列和r-Stirling排列生成函数的稳定性的工作进行介绍。 在第二章中，我们回顾了上下文无关文法的相关背景。在本章节中我们将集中介绍如何使用上下文无关文法刻画组合结构并生成相关的组合多项式，例如:Stirling多项式，Eulerian多项式及二阶Eulerian多项式。其中，我们主要研究了包含多个参数的组合多项式。 第三章，我们主要介绍如何运用上下文无关文法生成多元组合多项式，并证明其稳定性。基于Borcea和Br(a)ndén给出的关于保持多重仿射多项式稳定性的算子的刻画，我们给出运用上下文无关文法证明多元多项式的稳定性的方法。进一步，我们将给出一些通过上下文无关文法生成的多元多项式的稳定性证明。其中我们解决了Haglund和Visontai提出的关于给出Legendre-Stirling排列下降位的生成函数的稳定细化的问题。三项递推关系是组合数学中一类重要的递推关系，在本章结尾我们给出了一个生成特殊三项递推关系的文法。运用这个文法我们得到了一些新的组合恒等式，并且给出一组算子生成满足该三项递推关系序列的生成函数。在此基础上我们得到了此算子保持稳定性的充分必要条件。 在第四章中，我们主要说明了一些可以递归生成的组合结构都是可以由上下文无关文法生成的，例如:递增树，递增二叉树，自反排列，递增圈树及强受限森林。通过上下文无关文法，这些组合结构的性质往往可以被容易的证明。在本章中，我们引入了一种被称之为禁止替换的特殊替换规则，我们将利用含有禁止替换规则的上下文无关文法来生成一些组合结构并证明一些组合恒等式。 在第五章中，我们将上下文无关文法与缸模型相关联。我们利用缸模型对刻画排列中连续的132型及强受限森林中的绝对孤立点的上下文无关文法进行分析，并给出上述统计量的一些分析结果。