Runs in labelled trees and mappings

DOI10.1016/J.DISC.2020.111990zbMATH Open1443.05166arXiv1507.05484OpenAlexW3026676104MaRDI QIDQ776318FDOQ776318

Authors: Marie-Louise Lackner, Alois Panholzer 

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We generalize the concept of ascending and descending runs from permutations to rooted labelled trees and mappings, i.e., functions from the set $1,dots,n$ into itself. A combinatorial decomposition of the corresponding functional digraph together with a generating functions approach allows us to perform a joint study of ascending and descending runs in labelled trees and mappings, respectively. From the given characterization of the respective generating functions we can deduce bivariate central limit theorems for these quantities. Furthermore, for ascending runs (or descending runs) we gain explicit enumeration formulae showing a connection to Stirling numbers of the second kind. We also give a bijective proof establishing this relation, and further state a bijection between mappings and labelled trees connecting the quantities in both structures.

Full work available at URL: https://arxiv.org/abs/1507.05484

Recommendations

• Ascents and descents in random trees
• Consecutive permutation patterns in trees and mappings
• Limiting distributions for the number of inversions in labelled tree families
• Limit theorems for sizes of trees in the unlabelled graph of a random mapping
• scientific article; zbMATH DE number 1159039

zbMATH Keywords

exact enumerationbijectionslimiting distributionsrunsrandom mappingslabelled trees

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Bell and Stirling numbers (11B73) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Analytic combinatorics
• On the Lambert \(w\) function
• On convergence rates in the central limit theorems for combinatorial structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new proof of Cayley's formula for counting labeled trees
• Parking functions for mappings
• Enumeration results for alternating tree families
• Bijections for Cayley trees, spanning trees, and their q-analogues
• A refinement of Cayley's formula for trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the enumeration of rooted trees with fixed size of maximal decreasing trees
• Random mappings with constraints on coalescence and number of origins
• Asymptotic properties of eulerian numbers
• Hwang's Quasi-Power-Theorem in Dimension Two
• Rooted forests that avoid sets of permutations
• Symmetries in trees and parking functions
• Counting forests by descents and leaves
• Alternating mapping functions
• Ascents and descents in random trees

Cited In (3)

• Consecutive permutation patterns in trees and mappings
• Fishburn trees
• Embedding small digraphs and permutations in binary trees and split trees

This page was built for publication: Runs in labelled trees and mappings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776318)