关于推广的Catalan数与类Fibonacci数的若干研究

摘要

Catalan序列Cn=1/n+1(2nn)在组合数学中出现非常频繁。人们已经发现了差不多100种结构可以由这些数来计数,并且新的能由Catalan数计数的组合结构的发现也从未停止。另外,关于Catalan数的数字特征及性质的研究也广泛存在于文献资料中。比如,它们之间的各种递推关系,模关系以及因子等等。 在这篇论文紧接着介绍部分的头两章,我们将对推广的Catalan数Ck,r(n)=r/kn+r(kn+rn)以及其向量形式的推广做一些研究。我们首先直接从Lagrange反演定理推导出一个Catalan数向量推广形式满足的卷积并给予应用。接着,我们给出一个染色k叉树上的对合,并且从这个对合我们证明了一组符号交替变化的含有推广的Catalan数及其向量推广形式的恒等式。最后,根据得到的恒等式和Riordan阵列理论,我们重新提炼出k叉树的计数公式和非常漂亮且重要的Gould-Vandermonde卷积公式Fibonacci序列Fn是满足条件Fn=Fn-1+Fn-2和F0=0,F1=1的序列,它是组合数学中另一个极为重要的序列。人们发现这些数和自然界有着密切的联系。在本文最后一章,我们研究一组类Fibonacci序列Gn,它们满足递推关系:Gn=(d+2)Gn-1-Gn-2。注意当d=1和适当初始条件,我们分别得到Cn=F2n,n＞1和Gn=F2n+1,n＞0.对这一类序列及其相关性质,我们将用-类有序树给出组合描述解释。同时,我们还将给出与这类序列相关的组合结构之间的双射以及研究与其相关的其他序列。

目录

文摘

英文文摘

声明

Chapter 1 Introduction

1.1 Generalized Catalan Sequences

1.2 Fibonacci-like Sequences

Chapter 2 Convolution (1.2) and Counting Ordered Trees

2.1 Notations and Lagrange Inversion Formula

2.2 Deduction of (1.2) from Lagrange Inversion Formula

2.3 Enumeration of κ-ary Trees and Chen's Bijective Algorithm

Chapter 3 κ-ary Trees and the Gould-Vandermonde's Convolution

3.1 Combinatorial Sums Involving the Generalized Catalan Numbers

3.2 An Involution on Colored Trees

3.3 Refinement of Cβγ(n) and the Gould-Vandermonde's Convolution

3.4 Congruence Results of the Generalized Catalan Numbers

Chapter 4 Skinny Trees and Fibonacci-like Sequences

4.1 A Short Introduction

4.2 Sequences with Go = 1, G1 = 1

4.3 Sequences with Go = 1, G1 =d

4.4 Average Height of Skinny Trees

Bibliography

Acknowledge

Resume