Runs in labelled trees and mappings

DOI10.1016/J.DISC.2020.111990MaRDI QIDQ776318zbMATH OpenOpenAlexFDO

Authors Marie-Louise Lackner, Alois Panholzer

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(3)

• Embedding small digraphs and permutations in binary trees and split trees
• Consecutive permutation patterns in trees and mappings
• Fishburn 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)