Some Enumerations for Parking Functions

Po-Yi Huang, Jun Ma, Jean Yeh

Published 2008-06-03Version 1

In this paper, let $\mathcal{P}_{n,n+k;\leq n+k}$ (resp. $\mathcal{P}_{n;\leq s}$) denote the set of parking functions $\alpha=(a_1,...,a_n)$ of length $n$ with $n+k$ (respe. $n$)parking spaces satisfying $1\leq a_i\leq n+k$ (resp. $1\leq a_i\leq s$) for all $i$. Let $p_{n,n+k;\leq n+k}=|\mathcal{P}_{n,n+k;\leq n+k}|$ and $p_{n;\leq s}=|\mathcal{P}_{n;\leq s}|$. Let $\mathcal{P}_{n;\leq s}^l$ denote the set of parking functions $\alpha=(a_1,...,a_n)\in\mathcal{P}_{n;\leq s}$ such that $a_1=l$ and $p_{n;\leq s}^l=|\mathcal{P}_{n;\leq s}^l|$. We derive some formulas and recurrence relations for the sequences $p_{n,n+k;\leq n+k}$, $p_{n;\leq s}$ and $p_{n;\leq s}^l$ and give the generating functions for these sequences. We also study the asymptotic behavior for these sequences.