Ordered trees, Skew diagrams and q-Catalan numbers
| dc.contributor.advisor | Zeleke, Melkamu(Professor) | |
| dc.contributor.author | Berhanu, Thomas | |
| dc.date.accessioned | 2018-07-19T06:29:38Z | |
| dc.date.accessioned | 2023-11-04T12:30:43Z | |
| dc.date.available | 2018-07-19T06:29:38Z | |
| dc.date.available | 2023-11-04T12:30:43Z | |
| dc.date.issued | 2011-01 | |
| 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.identifier.uri | http://etd.aau.edu.et/handle/123456789/9316 | |
| 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
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- Thomas Berhanu.pdf
- Size:
- 419.58 KB
- Format:
- Adobe Portable Document Format