K-Trees and Catalan Identities
No Thumbnail Available
Date
2011-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
Ordered trees are trees with a distinguished vertex called the root where the children of each internal vertex are linearly ordered. K-trees generalize ordered trees in the sense that ordered trees are 2-trees in which edges between nodes are drawn as double edges. A class of numbers are introduced which unify many well-known counting coefficients, such as the Catalan numbers, the Fine numbers and the Central Binomial numbers and also their generating functions are computed. The Generalized Catalan numbers count the number of homogeneous ordered k-trees consisting of n k-cycles. We can prove the 17 most useful Catalan generating function identities by simple algebraic manipulations. In this project also we use ordered trees and k-trees to obtain generating function identities involving generalizations of Catalan numbers, Central Binomial numbers, and Fine numbers. We give some examples to show possible applications of these identities, like the Fibonacci polynomials, which is the generalization of Fibonacci numbers, the higher derivative of Central Binomial numbers, enumerating edges of odd degree and odd out degree and also show that the ratio of generalized Fine numbers to Catalan numbers is asymptotic
Description
Keywords
K-Trees and Catalan Identities