Research Of Bicoloured Ordered Trees And The Application In Computation Of Molecular Biology

Trees are the simplest combinatorial structures that arise naturally in diverse applications. This thesis concerns the enumeration of bicoloured ordered trees and that of ordered trees, and studies the intrinsic relation between them and noncrossing partitions, Motzkin paths and other combinatorial structures. Enumeration of RNA secondary structures is one of the most important branches in the computation of molecular biology. Using bicoloured ordered trees, this thesis concerns the enumeration of RNA secondary structures. The main work and the creative achievements in this thesis are as follows.1. The enumeration of labelled bicoloured ordered trees and unlabelled bicoloured ordered trees are concerned, and lots of explicit formulae are derived, which will be used directly in the computation of RNA secondary structures. The enumeration of multi-coloured ordered trees are concerned also and many formulae are derived.2. A decomposing algorithm for labelled ordered trees specified with four parameters is derived and the enumeration is discussed directly. By the decomposing algorithm, involutions on a kind of labelled ordered trees where leaves can be exchanged between two different types are introduced, which give combinatorial proofs to a enumerating result.3. A 2-depth decomposition on unlabelled bicoloured ordered trees and a left-lateral decomposition on unlabelled ordered trees are introduced. A bijection between unlabelled bicoloured ordered trees and unlabelled ordered trees which are specified with four parameters respectively is established the first time, which gives directly a combinatorial proof to their equality. Due to the fact that the parameters discussed here correspond to some ones in the Dyck paths, the above bijection is actually one between two different kinds of Dyck paths specified with four parameters repectively, which seems to appear the first time and solves firstly part of the open problem given by Clark in 1997.4. A notion (i.e., block run) and two different algorithms to assign labels for the edges in an unlabelled bicoloured ordered tree are proposed. Two bijections between unlabelled bicoloured ordered trees and non-crossing partitions are established the first time to reveal their relation. From the first bijection, several new enumerative results of non-crossing partitions specified with some new parameters are derived.5. A left-chain decomposition on unlabelled bicoloured ordered trees and an 1-depth decomposition on Motzkin paths are proposed, and bijections between unlabelled bicoloured ordered trees and Riordan paths, Motzkin paths, 2-Motzkin paths are established respectively the first time to reveal their relation.6. For the enumeration of RNA secondary structures, lots of recursive results and asymptotics and few of explicit formulae have been given. A maximum substructure decomposition on RNA secondary structures is proposed. A bijection between unlabelled bicoloured ordered trees and RNA secondary structures is established the first time, which reveals the correspondence between their lots of parameters, and a new method to study the enumeration of RNA secondary structures is presented. From the bijection here and the various enumerative results of unlabelled bicoloured ordered trees, lots of new explicit formulae for the number of RNA secondary structures specified with some parameters are derived.