Enumeration Of Generalized Motzkin Paths And Motzkin Trees

Motzkin paths and Motzkin trees are two kinds of important combination objects in combinatorial mathematics.A Motzkin path of length n is a lattice path from(0,0)to(n,0)with up step U=(1,1),down step D=(1,-1)and horizontal step H=(1,0)such that the path never goes below the x-axis.A Motzkin tree is an ordered tree in which the degree of each vertex is 0,1 or 2.Firstly,we generalize the definition of Motzkin paths,and introduce the concept of generalized Motzkin paths.Then a relationship between generalized Motzkin numbers and generalized Riordan numbers is proved by using symbolic method and bijection.Furthermore,we also study the counting problem of partial generalized Motzkin paths by using Riordan matrix and Lagrange inversion formula.Finally,we study the counting problem of statistics such as the total number of leaves,the total number of vertices with degree 1,the total number of vertices with degree 2,the total number of vertices on Motzkin trees with n edge.By using symbolic method,the relationship between these statistics and the number of free Motzkin paths with length n are established.Explicit formulas as well as the bijection proofs are given.Using the previous bijection proof,we also obtain some results of full binary trees,Dyck paths and Motzkin paths.