{
  "id": "1611.03707",
  "version": "v1",
  "published": "2016-11-11T14:06:20.000Z",
  "updated": "2016-11-11T14:06:20.000Z",
  "title": "The number of parking functions with center of a given length",
  "authors": [
    "Rui Duarte",
    "António Guedes de Oliveira"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-11T14:06:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A19"
    ],
    "keywords": [
      "parking function",
      "rook words",
      "depth-first search algorithm",
      "second bijection maps",
      "initial question"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}