The Motzkin Numbers and their Combinatorial Interpretations
No Thumbnail Available
Date
2011-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
This project paper is divided into four sections. we discuss the origin of Motzkin numbers using the division of finite number of points on a circle by non-intersecting chords. The idea of division of finite number of points on a circle which leads us to the origin of Motzkin numbers after getting the Catalan numbers is raised by Th. Motzkin in his paper “Relations between Hyper Surface Cross ratios and the Combinatorial formula for partitions of a polygon…” .
In addition to this the relation between the Motzkin and Catalan numbers are proved. Here we have the two important relations which are given by
1. Cn+1=Σ , and
2.=0 , where is the nth Motzkin number and +1 is the
(+1)ℎ Catalan number.
Combinatorial settings which are enumerated by the Motzkin numbers are stated and proved using diagrams for different values of n. The Combinatorial objects through which the sequence of Motzkin numbers can be constructed are the division of points on the circle with non- intersecting chords, the Motzkin paths, the Dyck paths etc.
In this paper we also showed that the Generating Function of the sequence of Motzkin numbers can be constructed from the enumeration of ordered- trees and the recursion formula is found by using Wen- jin Woan’s general idea of lattice paths. Using the recursion formula one can easily show that the asymptotic property of the regular Motzkin sequence which says the ratio between two consecutive terms of the Motzkin numbers approaches 3 for large values of n.
Finally the generalization of Motzkin numbers using k- trees which is the main purpose of this project is explained. Here k- tree is the generalization of ordered trees which are counted by the Catalan numbers. The general Motzkin numbers (k- Motzkin numbers) for k >2 are defined using k- trees and we show that these numbers agree with Baxter’s generalization of the Temperley – Lieb operators for k=3. As M. Jani and Melkamu Zeleke showed in [3] there is a one to one correspondence between the permissible modes of connections of X2n and the 3-Motzkin numbers
Description
Keywords
The Motzkin Numbers and their Combinatorial