AAU Institutional Repository

# The Motzkin Numbers and their Combinatorial Interpretations

 dc.contributor.advisor Zeleke, Melkamu(Professor) dc.contributor.author Ararsa, Shibru dc.date.accessioned 2018-07-18T06:03:55Z dc.date.available 2018-07-18T06:03:55Z dc.date.issued 2011-01 dc.identifier.uri http://localhost:80/xmlui/handle/123456789/9089 dc.description.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…” . en_US 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  there is a one to one correspondence between the permissible modes of connections of X2n and the 3-Motzkin numbers dc.language.iso en en_US dc.publisher Addis Ababa University en_US dc.subject The Motzkin Numbers and their Combinatorial en_US dc.title The Motzkin Numbers and their Combinatorial Interpretations en_US dc.type Thesis en_US
﻿