Prime parking functions on rooted trees

DOI10.1016/J.JCTA.2019.05.015zbMATH Open1421.05005arXiv1804.01616OpenAlexW2963527093WikidataQ127722565 ScholiaQ127722565MaRDI QIDQ2326324FDOQ2326324

Authors: Westin King, Catherine Yan 

Publication date: 7 October 2019

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: For a labeled, rooted tree with edges oriented towards the root, we consider the vertices as parking spots and the edge orientation as a one-way street. Each driver, starting with her preferred parking spot, searches for and parks in the first unoccupied spot along the directed path to the root. If all $n$ drivers park, the sequence of spot preferences is called a parking function. We consider the sequences, called emph{prime} parking functions, for which each driver parks and each edge in the tree is traversed by some driver after failing to park at her preferred spot. We prove that the total number of prime parking functions on trees with $n$ vertices is $(2n-2)!$. Additionally, we generalize emph{increasing} parking functions, those in which the drivers park with a weakly-increasing order of preference, to trees and prove that the total number of increasing prime parking functions on trees with $n$ vertices is $(n-1)!S_{n-1}$, where ${S_i}_{igeq0}$ are the large Schr"oder numbers.

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

Recommendations

• Parking functions on oriented trees
• Parking function varieties for combinatorial tree models
• Parking functions on directed graphs and some directed trees
• Parking functions
• Parking functions and labeled trees

zbMATH Keywords

treesenumerationparking functionsparking distributions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Title not available (Why is that?)
• Rational parking functions and Catalan numbers
• An Occupancy Discipline and Applications
• Parking functions for mappings
• Trees, parking functions, syzygies, and deformations of monomial ideals
• A refinement of Cayley's formula for trees
• Gončarov polynomials and parking functions
• Parking functions
• Parking functions on oriented trees
• Parking distributions on trees
• On the combinatorics of quadrant marked mesh patterns in 132-avoiding permutations
• Parking Cars of Different Sizes

Cited In (9)

• Brussels sprouts, noncrossing trees, and parking functions
• Parking on the infinite binary tree
• Parking functions on directed graphs and some directed trees
• On increasing and invariant parking sequences
• Parking functions on oriented trees
• Parking distributions on trees
• Parking on Cayley trees and frozen Erdős-Rényi
• Parking function varieties for combinatorial tree models
• Vector parking functions with periodic boundaries and rational parking functions

This page was built for publication: Prime parking functions on rooted trees

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