Noncrossing Trees And Its Applications In Combinatorial Structures

Combinatorics is an important branch of applied mathematics,and combinatorial structure is the core of research on combinatorics.In recent years,as a special combinatorial structure,non-crossing trees has attracted the attention of many experts at home and abroad.This paper focuses on the following two problems about non-crossing trees.1)We discussed the relationship between non-crossing trees and related combinatorial structures.Firstly,using the(l,r)-representation of the non-crossing trees,we establish the bijective between the non-crossing trees and the plane trees.Secondly,using the algorithm given by Hough,we study the correspondence between the non-crossing trees and the connected non-crossing graphs.Then,applying non-crossing trees decomposition algorithm and merging algorithm,we construct the correspondence between the non-crossing trees and the matching.Finally,according to the bijective between the non-crossing trees and the plane trees,we get a rotation correspondence between the non-crossing trees and the ternary trees.2)We study the application of the non-crossing trees on the combinatorial identities.Firstly,we use the correspondence between the non-crossing trees and the connected non-crossing graphs,we get the generating function for descents on non-crossing trees,and the coefficients of the generating function;Secondly,we apply the correspondence between the non-crossing trees and the matching,we get the number of non-crossing trees of size n with k descents,and the number of non-crossing trees of size n with k descents and i leaves are given.Finally,according to the correspondence between the non-crossing trees and the ternary trees,we get a lot of combinatorial identities.