The number of parking functions with center of a given length

DOI10.1016/J.AAM.2019.02.004MaRDI QIDQ2423404zbMATH OpenOpenAlexWikidataFDO

Authors Rui Duarte, António Guedes de Oliveira

Publication date 21 June 2019

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

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

zbMATH Keywords

depth-first search algorithm

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Let $1leqrleqn$ and suppose that, when the Depth-first Search Algorithm is applied to a given rooted labelled tree on $n+1$ vertices, exactly $r$ vertices are visited before backtracking. Let $R$ be the set of trees with this property. We count the number of elements of $R$. For this purpose, we first consider a bijection, due to Parkinson, Yang and Yu, that maps $R$ onto the set of parking function with center (defined by the authors in a previous article) of size $r$. A second bijection maps this set onto the set of parking functions with run $r$, a property that we introduce here. We then prove that the number of length $n$ parking functions with a given run is the number of length $n$ rook words (defined by Leven, Rhoades and Wilson) with the same run. This is done by counting related lattice paths in a ladder-shaped region. We finally count the number of length $n$ rook words with run $r$, which is the answer to our initial question.

Recommendations

• The convex hull of parking functions of length n
• On the enumeration of generalized parking functions
• Enumeration of \((p,q)\)-parking functions
• On the enumeration of parking functions by leading terms
• Some aspects of (r,k)-parking functions
• Families of parking functions counted by the Schröder and Baxter numbers
• Parking functions and noncrossing partitions
• Combinatorics of \(q\), \(t\)-parking functions
• Parking functions: from combinatorics to probability
• The ``parking problem for segments of different length

Cites work

• G-parking functions and tree inversions
• Affine permutations and rational slope parking functions
• Bijections for the Shi and Ish arrangements
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• Hyperplane arrangements, interval orders, and trees.
• Lattice path enumeration
• Parking functions
• Parking functions and labeled trees
• The q,t-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
• The braid and the Shi arrangements and the Pak-Stanley labelling
• The Shi arrangement and the Ish arrangement
• Une famille de polynômes ayant plusieurs propriétés enumeratives

Cited in

(7)

• Between Shi and Ish
• Hyperplane arrangements between Shi and Ish
• Pak-Stanley labeling of the m-Catalan hyperplane arrangement
• A symmetry on parking functions via Dyck paths
• Two involutions on binary trees and generalizations
• Some equidistributed statistics and applications to hook length formulas
• Symmetric statistics on rational Dyck paths

This page was built for publication: The number of parking functions with center of a given length

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