Combinatorics of complete non-ambiguous trees: Thomas Selig
ICE-TCS seminar
ICE-TCS seminar #322
Date and time: Tuesday, 20 November 2018, 12:10-13:00
Location: Room V1.04
Speaker: Thomas Selig (University of Iceland)
Title: Combinatorics of complete non-ambiguous trees
Abstract: Non-ambiguous trees are fillings of an m x n grid with 0s and 1s which satisfy certain conditions. These conditions ensure the existence of an underlying binary tree, from which these objects derive their name. A non-ambiguous tree is complete if this underlying binary tree is complete. Aval et al showed that complete non-ambiguous binary trees (CNATs) provide a combinatorial explanation for the coefficients of the Bessel function. In this talk, we associate to a CNAT a certain permutation, and show that the number of CNATs with a given permutation is in 1-1 correspondence with certain spanning trees of the associated permutation graph. We study in more detail the case where the permutation is the decreasing permutation n(n-1)...1. In this case, we exhibit a bijection from the set of CNATs to the set of (n-1)-permutations, which preserves certain statistics of the CNAT.
