Enumeration And Application Of A Kind Of Generalized Motzkin Paths

Lattice paths and trees are important structures in combinatorics, and are widely applied in bioinformatics and computer science. Enumerative problems related to these structures have been hot topics among combinatorialists during recent decades. In this paper we study the number of humps in a kind of generalized Motzkin paths (which we call (S, a)-paths in the paper), and give a bijective proof that the total number of humps in all of the generalized Motzkin paths of order n equals the number of free (S, a)-paths whose first non-horizontal step is an up step, and compute the number of humps in all (S,a)-paths of order n. Our bijection solves a problem posed by T. Mansour and M. Shattuck in [12]. Another result of this paper is related to trees. We count the number of branching nodes whose left child is a leaf in m-ary trees with mn+1nodes and general rooted trees with n+1nodes.