Enumeration of tree families and flattened combinatorial structures

Cooperating countries: Kenya, Uganda and Austria

Coordinating institution: Graz University of Technology, Stephan Wagner stephan.wagner@tugraz.at 

Partner institutions: Kibabii University, Maseno University, Mbarara University of Science and Technology

Project duration: 

Budget: EUR 14.800

Abstract: 

This collaborative project in the field of enumerative combinatorics is concerned with different kinds of discrete structures: certain families of trees as well as “flattened” structures. While these objects are interesting in their own right, there are also connections to other areas outside of pure combinatorics.

Our first object of study are variants of noncrossing trees: those are trees whose vertices can be drawn on a circle such that the edges do not cross. We study such trees with various restrictions as well as the family of k-crossing trees, which are trees with a given number k of crossings. Another type of trees that will be of interest to us are k-plane trees, which are labelled plane trees with a specific restriction on the labels. We will generalize this concept further and investigate the resulting tree families. On the other hand, we consider combinatorial structures obtained by a “flattening” operation, whereby blocks are arranged in increasing order of their minima. This includes flattened partitions, parking functions, and Stirling permutations, to name some concrete examples.

Our main goal is of an enumerative nature: to derive counting formulas – exact or asymptotic – for these combinatorial objects, and to determine the distribution of different combinatorial statistics that can be associated with them. Moreover, we will establish bijective relations with other combinatorial classes, and we investigate properties of the generating functions that can be associated with our combinatorial objects. This includes algebraic aspects such as real-rootedness as well as analytic properties required for an asymptotic analysis.