Ordered trees, Skew diagrams and q-Catalan numbers
No Thumbnail Available
Date
2011-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
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
Description
Keywords
Ordered trees, Skew diagrams and q-Catalan numbers