Parking function varieties for combinatorial tree models

DOI10.1016/J.AAM.2021.102191zbMATH Open1467.05016arXiv2007.14676OpenAlexW3139269871MaRDI QIDQ2035991FDOQ2035991

Alois Panholzer

Publication date: 28 June 2021

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We study the enumeration problem for different kind of tree parking functions introduced recently, called tree parking functions, tree parking distributions, prime tree parking functions, and prime tree parking distributions, for rooted labelled trees of important combinatorial tree families including labelled ordered, unordered and binary trees. Using combinatorial decompositions of the underlying structures yields, after solving the resulting equations, implicit characterizations of suitable generating functions of the total number of such tree parking functions for trees of size $n$ and $n$ successful drivers, from which we obtain exact and asymptotic enumeration results. The approach can be extended to the general situation of tree parking functions for trees of size $n$ and $m<n$ drivers for which we are also able to characterize the generating functions solutions, which allow, by applying analytic combinatorics techniques, a study of the asymptotic behaviour of the total number of tree parking functions and distributions for $noinfty$ depending on the load factor $0<alpha=fracmn<1$.

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

zbMATH Keywords

generating functionsexact enumerationasymptotic enumerationparking functionsparking distributionstree families

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Occupancy Discipline and Applications
• Counting defective parking functions
• Parking functions for mappings
• Level of nodes in increasing trees revisited
• Cutting down very simple trees
• Parking functions on directed graphs and some directed trees
• Parking on a random rooted plane tree
• Parking distributions on trees
• Parking on a Random Tree
• Prime parking functions on rooted trees

Cited In (10)

• Brussels sprouts, noncrossing trees, and parking functions
• Combinatorial aspects of Parker's model
• Multilayer parking with screening on a random tree
• Parking functions on directed graphs and some directed trees
• A combinatorial approach for discrete car parking on random labelled trees
• Parking on Cayley trees and frozen Erdős-Rényi
• Title not available (Why is that?)
• Generalized tree inversions and \(k\)-parking functions
• Symmetries in trees and parking functions
• Title not available (Why is that?)

Uses Software

• OEIS

This page was built for publication: Parking function varieties for combinatorial tree models

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