pith. sign in

arxiv: 1611.03707 · v2 · pith:ITY6LPPXnew · submitted 2016-11-11 · 🧮 math.CO

The number of parking functions with center of a given length

classification 🧮 math.CO
keywords numberlengthparkingfunctionsgivenbijectioncentercount
0
0 comments X
read the original abstract

Let $1\leq r\leq n$ 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.