{
  "id": "1504.04972",
  "version": "v1",
  "published": "2015-04-20T08:51:37.000Z",
  "updated": "2015-04-20T08:51:37.000Z",
  "title": "Parking functions for trees and mappings",
  "authors": [
    "Marie-Louise Bruner",
    "Alois Panholzer"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We apply the concept of parking functions to rooted labelled trees and functional digraphs of mappings (i.e., functions $f : [n] \\to [n]$) by considering the nodes as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak about a parking function for the tree or mapping. We transfer well-known characterizations of parking functions to trees and mappings. Especially, this yields bounds and characterizations of the extremal cases for the number of parking functions with $m$ drivers for a given tree $T$ of size $n$. Via analytic combinatorics techniques we study the total number $F_{n,m}$ and $M_{n,m}$ of tree and mapping parking functions, respectively, i.e., the number of pairs $(T,s)$ (or $(f,s)$), with $T$ a size-$n$ tree (or $f : [n] \\to [n]$ an $n$-mapping) and $s \\in [n]^{m}$ a parking function for $T$ (or for $f$) with $m$ drivers, yielding exact and asymptotic results. We describe the phase change behaviour appearing at $m=\\frac{n}{2}$ for $F_{n,m}$ and $M_{n,m}$, respectively, and relate it to previously studied combinatorial contexts. Moreover, we give a bijective proof of the occurring relation $n F_{n,m} = M_{n,m}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-04-20T08:51:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05A16",
      "05A19"
    ],
    "keywords": [
      "parking function",
      "transfer well-known characterizations",
      "analytic combinatorics techniques",
      "phase change behaviour",
      "free parking space"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}