Ordered Trees Skew Diagrams And Q-catalan Numbers

This project is concerned with the enumeration of a combinatorial object, ordered tree,rnwith respect to different parameters such as, number of edges, vertices, and path lengths.rnA known combinatorial argument is used to prove that among all ordered trees the ratiornof the total number of vertices to leaves is two. A new combinatorial bijection isrnintroduced on the set of these trees to show why this must be so. Ordered trees are thenrnenumerated by number of leaves, total path length, and number of vertices to obtain qanalogsrnof Catalan numbers. The results on ordered trees are then readily transferred byrnthe skew diagrams to help enumerate parallelogram Polyominoes by their area andrnperimeter. Frobenius formula that states “the sum of the squares of the number ofrnStandard Young Tableaux of Ferrers shape _ is n!” is also proved using a combinatorialrnbijection. This bijection is defined from the set of pairs of Standard Young Tableaux ofrnthe same shape into a set of permutations of size n. q-analogs of the Catalan numbersrndefined by rn0,1,2are studied from the view point of Lagrangerninversion: the first due to Stanley satisfies a nice recurrence relation and counts the arearnunder lattice paths. The second due to Carlitz whose recurrence relation coincides withrnthat of Stanley’s and its combinatorial interpretation is counting inversions of Catalanrnwords. The other q-Catalan numbers tracing back to McMahon, arise fromrnKrattenthaler’s and Gessel and Stanton’s q-Lagrange inversion formula, have an explicitrnformula and count the major index of a permutation

Get Full Work

Report copyright infringement or plagiarism