Enumeration on Set Partitions and（k,m）-ary Trees

摘要

本文主要研究了几类带限制的集合分拆以及(k，m)-叉树的计数。首先我们给出了集合[n]={1，2，…，n}上的m正则分拆的一个约简算法。该算法将集合[n]上的m正则分拆转化为集合[n-1]上的(m-1)-正则分拆。我们还证明了分拆的不交性质在这种约简算法下保持不变，从而给出了Simion-Ullman以及Klazar的一个组合恒等式的简单证明。利用该恒等式我们还给出了一种广义RNA二级结构的计数公式。对于一般的不交分拆，利用该算法，我们可以将其转化为一个只包含单点、独立边及自环的图，从而得到一个将Narayana数用Catalan数表示的恒等式。 然后我们介绍了Dyck路和2-Mozkin路上的标号规则。对于任意一个3长的排列τ，我们都给出了一种Dyck路上的标号规则，通过这种标号可以建立长为2n的Dyck路与集合[n]上避免τ的有禁排列之间的双射。这些双射还将排列上的一些统计量转化为Dyck路上的统计量。对于2-Mozkin路，我们给出了两种标号规则：最远标号规则与最近标号规则。我们可以利用这些标号规则来研究多种带限制的集合分拆的计数等问题。作为这些标号规则的一个应用，我们还给出了集合[n]上二正则不嵌套分拆(避免abba的二正则分拆)和长为n-2的2-Mozkin路之间的对应。 接下来我们开始研究3不交匹配和3不交分拆。关于3不交匹配的计数是近两年由Klazar提出的问题.该问题的更广义的形式是关于k不交分拆的计数。我们在本文中指出有三类禁止长度为6的子序列的[2n]上的有禁匹配均和长为2n的不交Dyck路对的集合之间存在一一对应。这三类有禁匹配分别是3不交匹配(避免123123的匹配)、3不嵌套匹配(避免123321的匹配)以及非双嵌套匹配(避免123312的匹配)。我们还给出了这三类有禁匹配的计数公式。 本文中关于集合分拆的最重要的结果是引进了一种新的工具：“犹豫杨表”，并通过它来研究匹配以及分拆上的交叉数与嵌套数。利用集合分拆与犹豫杨表之间的一个双射，我们证明了如果给定分拆的每个块中的最大和最小元素，这些分拆的交叉数与嵌套数有对称的交集分布。因此对所有的集合[n]上的分拆以及集合[n]=[2m]上的匹配，交叉数与嵌套数也是对称交集分布的。该结论的一个推论就是：k不交分拆(匹配)与k不嵌套分拆(匹配)的个数相等。 在本文的最后我们定义并研究了(k，m)-Catalan数Ck,m(n)=1/mn+1(mn+1)kn)，它是传统意义的Catalan数C(n)=1/n+1(2nn)的一个推广。我们还给出了(k，m)-Catalan数的两种组合解释：含有n个关键点的(k，m)-叉树以及(mn+1)×k的“停车表”. 利用(k，m)-Catalan数的这两种组合解释我们给出了它的一些递归关系。利用这些递归关系我们证明了关于m叉树以及平面森林的hook长度多项式的一些公式。作为在这些公式的推论，我们还得到了关于m叉树以及平面森林上的计数的几个恒等式。

目录

文摘

英文文摘

南开大学学位论文版权使用授权书和原创性声明

Introduction

Chapter 1 Definitions and Preliminaries

1.1 Permutations and Partitions

1.2 Matchings

1.3 Lattice Paths

1.4 The RSK Algorithm

1.5 Noncrossing Partitions and RNA Secondary Structures

1.6 Nonnesting Partitions and Shi Arrangement

1.7 Catalan Number and Binary Trees

Chapter 2 Reduction of m-Regular Noncrossing Partitions

2.1 Introduction

2.2 The Reduction Algorithm

2.3 Reduction of Noncrossing Partitions

Chapter 3 Labelling Schemes for Dyck paths and 2-Motzkin paths

3.1 Introduction and Notations

3.2 Labelling Schemes for Dyck paths

3.2.1 321-Avoiding Labelling Scheme for Dyck Paths

3.2.2 312-Avoiding Labelling Scheme for Dyck Paths

3.2.3 Other Labelling Schemes for Dyck Paths

3.3 Labelling Schemes for 2-Motzkin paths

3.4 2-Regular Nonnesting (abba-Free) Partitions

Chapter 4 Matchings and Pairs of Noncrossing Dyck Paths

4.1 Introduction

4.2 3-Noncrossing Matchings

4.3 3-Nonnesting Matchings

4.4 Non-double-nesting Matchings

4.5 Concluding Remarks

Chapter 5 Crossings and Nestings of Matchings and Partitions

5.1 Introduction

5.2 A Bijection between Set Partitions and Vacillating Tableaux

5.3 Crossings and Nestings of Partitions

5.4 A Variant: Partitions and Hesitating Tableaux

5.5 Enumeration of k-Noncrossing Matchings

Chapter 6 (k, m)-Catalan Numbers and Hook Length Polynomials for Trees

6.1 Introduction

6.2 (k, m)-Parking Tables and (k, m)-ary Trees

6.3 Hook Length Polynomials for m-ary Trees

6.4 Hook Length Polynomials for Plane Forests

Bibliography

Acknowledgements