Set $\mathbb{N} := \{0,1,2,\ldots\}$. A *parking function* of length $n$ is a sequence $(\alpha\_1,\ldots,\alpha\_n) \in \mathbb{N}^n$ whose weakly increasing rearrangement $\alpha\_{i\_1} \leq \alpha\_{i\_2} \leq \cdots \leq \alpha\_{i\_n}$ satisfies $\alpha\_{i\_j} \leq j-1$ for all $1 \leq j \leq n$. Let $\mathrm{PF}(n)$ denote the set of parking functions of length $n$. Let $K\_{n}$ denote the complete graph on $n$ vertices. It is very well-known that
$$\#\mathrm{PF}(n) = \#\textrm{ of spanning trees of }K\_{n+1}=(n+1)^{n-1}.$$
(This sequence is <http://oeis.org/A000272>.) Moreover, there are many explicit bijections between parking functions and labeled trees, with interesting properties. I am interested in a bipartite analog of this result. Let $K\_{m,m}$ denote the complete bipartite graph with $m$ vertices in one part and $m$ in the other part. It is not hard to show that
$$ \#\{(\alpha\_1,\ldots,\alpha\_{2m-1}) \in \mathrm{PF}(2m-1)\colon \alpha\_i \textrm{ is even for all }i\} = \#\textrm{ of spanning trees of }K\_{m,m} = m^{2m-2}.$$
(This sequence is <http://oeis.org/A068087>.) I wonder if there is a simple bijective proof of this last equality. This problem is a special case of (3) in Section 5 of <http://arxiv.org/abs/1506.03470>.



Even parking functions and spanning trees of complete bipartite graphs
Let $n=2m$ and let $(\alpha\_1,\dots,\alpha\_{2m-1})$ be an even parking function. Apply Pollak's map: $c=(\alpha\_2-\alpha\_1,\dots,\alpha\_{2m-1}-\alpha\_{2m-2})\mod 2m$.


Thus $c$ is an $(2m-2)$-tuple of even numbers between $0$ and $2m-1$.
Let $a=(c\_1/2,\dots,c\_{m-1}/2)$ and let $b=(c\_m/2+m,\dots,c\_{2m-2}/2+m)$.


Then $(a,b)$ is the 'bipartite' Prüfer code of a spanning tree of $K\_{m,m}$, where the vertices of one block are labelled $0,\ldots,m-1$ and the vertices of the other block are labelled $m,\ldots,2m-1$.


