摘要
计数组合学主要研究有限离散对象的计数问题，且与图论、数论、代数拓扑、概率论等数学分支联系密切.计数组合学在其他自然科学中也有重要应用，特别是为离散型概率的计算和计算机科学中的算法设计提供了理论基础. 排列统计量是计数组合学研究的核心对象之一，其近代的研究起源于英国数学家MacMahon的工作.法国组合学家Foata应用双射研究排列统计量的同分布，中科院院士陈永川引进上下文无关文法来形式计算排列统计量.多项式的γ-正性是处理单峰性问题的一个强有力工具，并且蕴含着丰富的组合学性质.本论文主要研究陈氏文法在排列统计量上的简单应用与多重集Eulerian-多项式γ-正性的组合学，其主要内容分为下面两部分. 第一部分研究陈氏文法在排列统计量上的若干应用.首先，介绍了文法的基本定义与性质，展示了文法的思想在证明组合中经典恒等式的应用.接着，利用文法标记法生成了Eulerian-多项式且计算了它的指数型生成函数，进一步应用文法变换法探讨了其γ-正性.最后，研究了排列上三种不同的山峰统计量的文法标记方式并得到对应的递归关系式及Peak-多项式的指数型生成函数. 第二部分研究多重集Eulerian-多项式γ-正性的组合学.首先，给出了一类具有双γ-正性的特殊多重集Eulerian-多项式，并提供了一个代数证明和一个简洁的组合证明.这个工作推广了马世美、马俊和叶永南应用陈氏文法得到的双γ-正性结果.然后，利用弱递增树模型和陈院士关于树上的一般算法，首次给出了p-重集Eulerian-多项式γ-系数的组合解释.这解决了林志聪等学者近期提出的一个公开问题.最后，通过弱递增树的分解和Lagrange-反演公式导出了一般多重集上Eulerian-Narayana数的递归式.
NETL