拉马努金与查波顿多项式上的组合学

摘要

本文的主要贡献是拉马努金多项式和查波顿多项式上的组合学。借助于上下文无关文法，我们给出了拉马努金多项式的一个新的组合解释—偏序递增树，并建立了拉马努金多项式的两个组合解释间的一个双射。我们给出了查波顿多项式两个组合解释之间的一个双射，回答了郭和曾二人提出的一个公开问题。进一步，借助于组合对象“分拆排列”，我们给出了平面树上关于统计量年轻孩子数和年长孩子数的生成函数的一个组合解释，建立了分拆排列和平面树的一个基于普吕弗码的双射。据此我们给出了一个凯莱型等式的组合意义，回答了郭和曾的另一公开问题。同时，此双射赋予了格赛尔—西多项式一个关于平面树上统计量的组合解释。利用此双射，一些经典的计数结果能够被重新证明。通过建立分拆排列和半移动树的双射，我们赋予了格赛尔—西多项式关于半移动树上统计量的一个组合解释。
　　在第一章中，我们回顾了拉马努金多项式、查波顿多项式、分拆排列以及上下文无关文法的相关背景知识，并给出了树和排列上一些基础的定义和预备知识。
　　在第二章中，通过建立查波顿多项式Qn,k(x，t)的两个组合解释间的一个双射，我们解决了郭和曾提出的一个公开问题。这两个组合解释分别是平面树上关于统计量“顶点1的年轻孩子数”和“总年长孩子数”的解释以及根为1的平面树上关于统计量“顶点1的年轻孩子数”和“总年长孩子数”的解释。同时，我们构造了多项式rQn-r,k(r，t)的两个组合解释间的双射。
　　在第三章中，我们首先赋予分拆排列多项式一个组合解释。然后通过构造分拆排列与平面树之间的一一映射，我们回答了郭和曾提出的一个公开问题—关于凯莱型等式的组合证明的公开问题。利用此映射，我们能够重新证明平面树及有根树上的部分经典计数结果。最后，通过建立分拆排列与半移动树之间的双射，我们赋予了格赛尔—西多项式新的组合意义。
　　在第四章中，我们建立了由拉马努金文法生成的两个组合结构之间的双射。这两个组合结构分别是有根数和偏序递增树。在该双射下，一个有根树上的非恰当边的个数等于其对应的偏序递增树上标记边的个数。
　　在第五章，我们给出了由斯特林文法生成的三个组合结构之间的两个双射。一个是建立在斯特林排列和限定递增森林上的双射。在该双射下，一个[n]2上含有m个上升位，l个下降位以及k个平行位的斯特林排列被映射为一个含有m非叶子点，l个非根叶子点以及k个根叶子点的n-限定递增森林。另一个是建立在递增平面树和限定递增森林上的双射。

目录

声明

摘要

Abstract

Table of Contents

Chapter 1 Introduction

1．1 Introduction

1．2 Definitions and Preliminaries

1．2．1 Definitions and notations on permutations

1．2．2 Definitions and notations on trees

Chapter 2 On the combinatorics of Chapoton polynomials

2．1 Statistics on plane trees

2．2 Bijections for the interpretations of Qn，k

Chapter 3 Disoosition polynomials and plane trees

3．1 The generating function of dispositions

3．2 A bijection between plane trees and dispositions

3．3 The Gessel-Seo polynomials

3．4 Half-mobile trees

Chapter 4 Ramanujan grammars，rooted trees andpartially ordered increasing trees

4．1 Context-free grammars

4．2 Ramanujan grammars

4．3 Bijection between rooted trees and partially crdered increasing trees

Chapter 5 Stirling grammars，Stirling permutations and increasing trees

5．1 Stirling grammars

5．2 The grammar interpretations of increasing trees

5．3 Bijections

Bibliography

致谢

个人简历 在学期间发表的学术论文与研究成果