AAU Institutional Repository

Ordered trees, Skew diagrams and q-Catalan numbers

Show simple item record

dc.contributor.advisor Zeleke, Melkamu(Professor)
dc.contributor.author Berhanu, Thomas
dc.date.accessioned 2018-07-19T06:29:38Z
dc.date.available 2018-07-19T06:29:38Z
dc.date.issued 2011-01
dc.identifier.uri http://localhost:80/xmlui/handle/123456789/9316
dc.description.abstract This project is concerned with the enumeration of a combinatorial object, ordered tree, with respect to different parameters such as, number of edges, vertices, and path lengths. A known combinatorial argument is used to prove that among all ordered trees the ratio of the total number of vertices to leaves is two. A new combinatorial bijection is introduced on the set of these trees to show why this must be so. Ordered trees are then enumerated by number of leaves, total path length, and number of vertices to obtain qanalogs of Catalan numbers. The results on ordered trees are then readily transferred by the skew diagrams to help enumerate parallelogram Polyominoes by their area and perimeter. Frobenius formula that states “the sum of the squares of the number of Standard Young Tableaux of Ferrers shape _ is n!” is also proved using a combinatorial bijection. This bijection is defined from the set of pairs of Standard Young Tableaux of the same shape into a set of permutations of size n. q-analogs of the Catalan numbers defined by 0,1,2are studied from the view point of Lagrange inversion: the first due to Stanley satisfies a nice recurrence relation and counts the area under lattice paths. The second due to Carlitz whose recurrence relation coincides with that of Stanley’s and its combinatorial interpretation is counting inversions of Catalan words. The other q-Catalan numbers tracing back to McMahon, arise from Krattenthaler’s and Gessel and Stanton’s q-Lagrange inversion formula, have an explicit formula and count the major index of a permutation en_US
dc.language.iso en en_US
dc.publisher Addis Ababa University en_US
dc.subject Ordered trees en_US
dc.subject Skew diagrams and q-Catalan numbers en_US
dc.title Ordered trees, Skew diagrams and q-Catalan numbers en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search AAU-ETD


My Account