\documentclass[12pt,a4paper]{amsart}
\usepackage{amsfonts,amsmath,amsthm,amssymb,stmaryrd} 
%\usepackage[T1]{fontenc}
\usepackage{graphics} \usepackage{pstricks,pst-node}
\usepackage[headings]{fullpage}

\usepackage{rotating}

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}             % the same numbering as theorem
\newtheorem{corolary}[theorem]{Corolary}       % the same numbering as theorem
\newtheorem{definition}[theorem]{Definition}   % the same numbering as theorem
\newtheorem{remark}[theorem]{Remark}   % the same numbering as theorem


\newcommand\Reals{\mathbb{R}}
\newcommand\N{\mathbb{N}}

%Parking functions operators
\newcommand\PF{\mathbf{PF}}
\newcommand\PFR{\mathbf{PF}^0}
\newcommand\df{\mathbf{dp}}
\newcommand\pr{\mathbf{pr}}
\renewcommand\Pr{\mathbf{Pr}}



%Arrangements operators
\newcommand\Shi{\mathcal{S}}
\newcommand\R{\mathcal{R}}
\renewcommand\O{\mathcal{O}}

%Trees operators
\newcommand\pt{\mathsf{p}}
\newcommand\dt{\mathsf{dt}}

\newcommand\desc{\mathrm{desc}\:}
\newcommand\fol{\mathrm{fol}\:}
\newcommand\inv{\mathrm{inv}}

\newcommand\lig[2]{\overarc{$#1\,#2$}}

\newcommand\K{\tilde{K}}
\renewcommand\Im{\mathrm{Im}}

\newcommand\pequl[2]{$\rlap{\red $#1-#2=1$}$}
\newcommand\pequr[2]{$\llap{\red $#1-#2=1$}$}
\newcommand\peqzl[2]{$\rlap{\red $#1-#2=0$}$}
\newcommand\peqzr[2]{$\llap{\red $#1-#2=0$}$}


\newcommand\peqd[2]{\rlap{\red\scriptsize$\ [#1-#2=0]\ $}}
\newcommand\peqld[2]{\rlap{\red\scriptsize$\ [#1-#2=1]\ $}}
\newcommand\peqe[2]{\llap{\red\scriptsize$\ [#1-#2=0]\ $}}
\newcommand\peqle[2]{\llap{\red\scriptsize$\ [#1-#2=1]\ $}}
\newcommand\sesp[1]{\vbox to0pt{\vss\hbox to0pt{\hss#1\hss}\vss}}

\newcommand\sr[2]{\begin{rotate}{#2}#1\end{rotate}}




\begin{document}

\title{Parking functions and labeled trees} 
\author[A. Guedes de Oliveira]{Ant\'onio Guedes
  de Oliveira} 
\address{CMUP and Departamento de Matem\'atica, Fac. de
  Ci\^encias, Universidade do Porto} \email{agoliv@fc.up.pt}


\author[M. Las Vergnas]{Michel Las~Vergnas}
\address{Combinatoire et Optimisation, CNRS and
Universit\'e Pierre et Marie Curie (Paris 6)}
\email{mlv@math.jussieu.fr}

\begin{abstract}
  We define a bijection between the set of parking functions of
  size $n$ and the set of rooted (labeled) forests with $n$ vertices
  for which the number of ``probes'' of the function is the number of
  inversions of the tree. This definition is not recursive.
\end{abstract}

\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8

\markright{\its S{\'e}minaire Lotharingien de
Combinatoire \bfs 65 \rms (2011), Article~B65e\hfill}
\def\thepage{}

\section{Introduction}
It is well-known that the set of parking functions of size $n$ and the
set of rooted (labeled) forests with $n$ vertices are in bijection.
In fact, G.~Kreweras, in \cite{kreweras}, after finding a common
enumerator of parking functions by the total number of probes and of
rooted forests by the number of inversions, even constructs a
bijection that sends parking functions with $k$ probes to forests with
$k$ inversions. However, his definition is recursive, and, in
\cite[Exercise 4]{stan1}, Stanley asks for a direct bijection with
this property, unknown until \cite{shin}, where a bijection with the
required property was given. The present article gives a second answer to the
problem and may be seen as an alternative to the work of Shin (see also
\cite{shin2}), which was the starting point for our investigation. For
the relation between Shin's bijection and ours, see Remark \ref{rem}.

The structure of the paper is as follows: In Section~\ref{pf}, we
introduce the notions related with parking functions that will be used
afterwards, and we collect some well-known results.  It will be seen
that Lemma~\ref{pproperties} plays a r\^ole (not noted before, we
believe) that is central in our construction.

Section~\ref{rlf} deals with rooted forests with $n$ labeled vertices
(naturally identified with trees with $n+1$ labeled vertices): by
using the \emph{depth-first search} algorithm, it establishes a
variant of a well-known bijection between \emph{permutations} and
\emph{decreasing trees}, which will be extended to parking functions,
on the one hand, and to general labeled trees, on the other hand. The
depth-first search algorithm is also used to find the inverse
of the bijection.

\section{Parking functions}\label{pf}

As usual, we represent, for a natural number $n$, the set
$\{1,2,\dotsc,n\}$ by $[n]$ and denote by $S_n$ the set of permutations of
$[n]$; the set of all autofunctions of $[n]$ is denoted $F_n$.

\begin{definition}
We say that $f\in F_n$ is a \emph{parking function} if:
\begin{equation*}
\left|f^{-1}\big([i]\big)\right|\geq i\ , \qquad i=1,2,\dotsc,n.
\end{equation*}
We call $n$ the \emph{length} of $f$ and denote by $\PF_n$ the set of
all parking functions of length $n$.
\end{definition}


Based on \cite{foatariordan} and on a construction of H.~O.~Pollak
referred to therein, let us define, for a function $f:[n]\to[n+1]$, the
new function $g=P(f):[n]\to[n+1]$ recursively as follows:
\begin{itemize}
\item $g(1)=f(1)$;
\item Suppose $g(j)$ is defined for $j<i$; then define:
\begin{align*}
  k_0&=\min\big\{k\geq 0 \colon k+f(i)\not\equiv g(j) \pmod{n+1},
  \  \forall\ j<i\big\}\\
\intertext{and}
  g(i)&\equiv k_0+f(i) \pmod{n+1}\quad(\text{remember that }1\leq g(i)\leq n+1)
\end{align*}
\end{itemize}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL A. GUEDES DE OLIVEIRA AND M. LAS VERGNAS}{\SMALL PARKING FUNCTIONS AND LABELED TREES}
%
%

Note that $P(f)$ is injective by definition.  Suppose that $n+1\notin
P(f)([n])$ and so, in particular, that $n+1\notin f([n])$.  Then
$f(i)\leq P(f)(i)$ for all $i\leq n$ and $P(f)=f$ if and only if $f$
is itself injective (in short, we may say the equality holds if and
only if $f\in S_n$).  More generally, if $n+1\notin P(f)([n])$ then we
may write $P(f)\in S_n$.  We have the following lemma.
\begin{lemma}\label{defpf}
  A function $f\in F_n$ is a parking function if and only if
  $n+1\notin P(f)([n])$.
\end{lemma}
\begin{proof}
  Since $P(f)$ is injective, there exists a unique $k\in
  [n+1]\setminus P(f)([n])$.  Suppose $k\leq n$.  Then $P(f)$ maps
  injectively $f^{-1}\big([k]\big)$ into $[k-1]$, by definition, and
  hence $f$ is not a parking function. The converse is similar.
\end{proof}
\noindent By this lemma, we view the operator $P$ as a function from
$\PF_n$ to $S_n$. We call $\Pi(f):=P(f)^{-1}$ the \emph{parking
  scheme} of $f\in\PF_n$. Note that, for $f\in\PF_n$, $P(f)(i)$ is
simply the first $k\geq f(i)$ that is \emph{different} from every
$P(f)(j)$ with $j<i$, in the recursion above.

The lemma also explains the name ``parking function'', apparently
coined by A.\!~G.\!~Konheim and B.~Weiss in \cite{kohneim}: suppose
the drivers of $n$ cars want to park on a one-way street with $n$
parking spaces, where each driver has a special preference for a
space, say, the $i$-th driver that enters the street wants to park in
space $f(i)$. The driver does so if the space is free, or else
(s)he \emph{probes} the next space, and so on, and parks in the next
free space, if there is still one available. Then $f$ is a parking
function exactly when all drivers can park their cars in the street.
Clearly, if $f$ is a parking function then $\Pi(f)(i)$ is the number
of the car that, at the end, is parked in space $i$.

Keeping the colorful setting, the definition of $P(f)$ rests in the
following idea:
just imagine that instead of a one-way street we have a one-way
roundabout with parking spaces labeled $1,2,\dotsc,n+1$, so that
\emph{all} cars can park in \emph{all} cases --- and there will still
be an empty space at the end. Clearly, the parking functions are those
functions for which the empty space at the end is the space numbered
$n+1$.
This is an idea of Pollak, used to easily count the number of parking
functions. It is  a matter of fact that there are as many functions with this
particular empty space as with any other empty space. To justify this,
just imagine that we rotate the labels of the spaces in the
roundabout, and the values given by the functions accordingly.  More
precisely, we have the following lemma.

\begin{lemma}\label{lemmanum}
The number of parking functions of size $n$ is given by
\begin{equation*}
\left|\PF_n\right|\;=\;(n+1)^{n-1}.
\end{equation*}
\end{lemma}
\begin{proof}
  Suppose that $f$ is a function $f:[n]\to[n+1]$.
As in the beginning of the proof of Lemma~\ref{defpf}, there exists
$k\leq n+1$ such that $[n+1]\setminus P(f)([n])=\{k\}$.
Define $\tilde{f}:[n]\to[n+1]$ by
  $\tilde{f}(i)\equiv f(i)+n+1-k \pmod{n+1}$. Then
  $P(\tilde{f})(i)\equiv P(f)(i)+n+1-k \pmod{n+1}$ and so
  $\tilde{f}\in\PF_n$. Hence, the number of parking functions of
  length $n$ is the number $(n+1)^n$ of functions from $[n]$ to
  $[n+1]$ \emph{divided by} $n+1$.
\end{proof}

\medskip
Given $\sigma\in S_n$, the number of parking functions $f\in\PF_n$
such that $\sigma=P(f)$ can be easily determined from the definition of $P$.
Before establishing this number, we introduce some further notation:


\begin{definition} \label{def2.4}
  For any function $f\in\PF_n$, define $\pr(f)$ to be the vector $P(f)-f$.
The \emph{total number of probes} of $f$, denoted by $\Pr(f)$, is
  the sum of the coordinates of $\pr(f)$. In symbols,
$$\Pr(f)=\binom{n+1}{2}-\sum_{i\leq n}f(i).$$ 

If
  \emph{$\sigma$ is a permutation}, let, for every $i\leq n$,
  $\df_\sigma(i)$ be the number of elements of $\sigma([i-1])$ that
  are \emph{smaller} than $\sigma(i)$ and \emph{consecutive} to
  it. That is,
\begin{align*}
  \df_\sigma(i)&:=\sigma(i)-\min\big\{k\in \sigma([i])\colon
  \{k,k+1,\dotsc, \sigma(i)\}\subset\sigma([i])\big\}, \intertext{We define the
    \emph{depth of $\sigma\in S_n$} to be}
  \df(\sigma)&:=\big(\df_\sigma(1),\df_\sigma(2),\dotsc,\df_\sigma(n)\big)\\
  \intertext{and, in general, the \emph{depth of $f\in\PF_n$} to be}
  \df(f)&:=\df(P(f))-P(f)+f.
\end{align*}
\end{definition}


\begin{lemma}\label{pproperties}
For every $\sigma\in S_n$ and for every $f\in\PF_n$,
\begin{equation}
\text{$P(f)=\sigma$ holds if and only  }
\sigma(i)-f(i)\;\leq\;\df_\sigma(i).\label{aqui1}
\end{equation}
Moreover,
\begin{equation}
\left|P^{-1}(\sigma)\right|\;=\;\prod_{i=1}^n
\left(1+\df_\sigma(i)\right).\label{aqui2}
\end{equation}
\end{lemma}
\begin{proof}
  By definition of depth,
\begin{align*}
\sigma(i)-f(i)\;\leq\;\df_\sigma(i)
\iff &\{f(i),f(i)+1,\dotsc,\sigma(i)\}\subset\sigma\left([i]\right)\\
\iff &\{f(i),f(i)+1,\dotsc,\sigma(i)-1\}\subset\sigma\left([i-1]\right),
\end{align*}
where the last equivalence holds since $\sigma$ is injective.  This explains
\eqref{aqui1}, and \eqref{aqui2} is an obvious consequence of it.
\end{proof}

As an example, let us consider $f=(1,8,5,2,7,4,4,8,1)\in\PF_9$ and
evaluate $\sigma=P(f)$.  Since there are no repeated elements in $f$
before $i=7$, $\sigma(i)=f(i)$ for $i\leq 6$.  Then $\sigma(7)\geq 4$
must be different from $4$ and from $5$ (these are ``spaces already
occupied''). Hence, $\sigma(7)=6$. In the same way, $\sigma(8)\geq 8$,
$\sigma(8)\neq 8$ and hence $\sigma(8)=9$, and, finally,
$\sigma(9)=2$. Therefore, $P(f)=\sigma=(1,8,5,2,7,4,6,9,3)$ and
$\Pi(f)=\sigma^{-1}=(1,4,9,6,3,7,5,2,8)$.  Finally,
$\df(P(f))=(0,0,0,1,0,0,2,5,2)$ and $\df(f)=(0,0,0,1,0,0,0,4,0)$.

\section{Rooted labeled forests}\label{rlf}
A \emph{rooted (labeled) forest} 
%, also said sometimes a \emph{planted forest}, 
is a labeled graph where the connected components are trees
with a distinguished vertex or \emph{root}.  By joining to the graph a
new vertex connected with the roots of all trees, we construct a
bijection between the set of rooted forests with $n$ vertices and the
set of trees with $n+1$ vertices, known to have $(n+1)^{n-1}$ elements
by Cayley's Theorem (for a proof, see \cite[Chapter 19]{book}, where
four very elegant proofs can be found). See Figure~\ref{fig1}, below.
Here, we consider only labeled trees with vertices $1,2,\dotsc,
n+1$ for a given $n$.


One of the goals of this paper is to establish a new, direct
(i.e., non-recursive) bijection from the set of parking functions of a
given length and the set of rooted labeled forests with the same number
of vertices. Moreover, we want the bijection to fulfil some extra conditions.

In a labeled tree, an \emph{inversion (of $k$)} is a pair $(i,k)$ of
vertices such that $k<i$ and $k$ belongs to the (unique) path
connecting $i$ to the vertex $n+1$.  We denote by $\inv_T(k)$ the
\emph{number of inversions} of $k$.  In the tree of
Figure~\ref{fig1}\textrm{(a)}, the index of any vertex $k$ is exactly
$\inv_T(k)$. G.~Kreweras, in \cite{kreweras}, after finding a common
generating function for parking functions enumerated by the total
number of probes and for rooted forests enumerated by the number of
inversions, constructs recursively a bijection that sends functions
with $k$ probes to forests with $k$ inversions\footnote{In fact,
  Kreweras works with what he calls ``suites majeures de port\'ee
  $n$'', that can be seen as the functions $g:[n]\to[n]$ such that
  $f(i)=n+1-g(i)$ defines a parking function.}. Our bijection does
this as well. Consequently, it can be seen as an answer to
\cite[Exercise 4]{stan1}, where a direct bijection with this property
is asked for.


A tree with no inversions is said to be \emph{decreasing}.  Let, for
$\sigma=(a_1,\dotsc,a_n)\in S_n$,
$\overline{\sigma}=(a_1,\dotsc,a_n,n+1)$, and let $T=\phi(\sigma)$ be
the tree with labels $[n+1]$ constructed as follows: a vertex $i$ is connected
with $k$, if $i<k$, and if $a_k$ is the smallest element greater than and on
the right (in $\overline{\sigma}$) of $a_i$.  Let, for example, 
$\sigma$ be $(1,8,5,2,7,4,6,9,3)$; then $1$ is connected with $4$ since
$4>1$ and $2=\sigma_4$ and $1=\sigma_1$.  Hence, a natural way to
represent this graph can be obtained as follows: take
$\alpha={\overline{\sigma}}\;^{-1}\in S_{n+1}$ and, from left to
right, just connect each vertex to the next greater vertex (possibly
$n+1$).  In the same example, $\alpha=(1,4,9,6,3,7,5,2,8,10)$, and
$\vbox to20pt{\vfill} T=\rnode{aa}{1}\, \rnode{ab}{4}\,
\rnode{ac}{9}\, \rnode{ad}{6}\, \rnode{ae}{3}\, \rnode{af}{7}\,
\rnode{ag}{5}\, \rnode{ah}{2}\, \rnode{ai}{8}\, \rnode{aj}{10}\,
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{aa}{ab}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{ah}{ai}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{ae}{af}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{ab}{ac}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{ag}{ai}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{ad}{af}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{af}{ai}
\nccurve[nodesep=.05,linecolor=red,ncurv=0.75,angleB=90,angleA=90]{-}{ai}{aj}
\nccurve[nodesep=.05,linecolor=red,ncurv=0.5,angleB=90,angleA=90]{-}{ac}{aj}
$.  We say that $T$ is represented \emph{linearly}.  In 
Figure~\ref{fig1}\textbf{(b)} the same tree is represented as usual.  Note
that $T$ is decreasing, by definition.  It is well known that $\phi$
%possibly under a slightly disguised form, 
is a bijection (cf.\ for example \cite[page 25]{stanenum}).  In fact,
we will prove it here in Lemma~\ref{permtree} below, since we will use
an explicit form of the inverse.  Note that $\phi$ is a bijection
between $S_n\subset \PF_n$, the set of functions with zero probes, and
the set of labeled trees with zero inversions.  Our bijection (which
we call $\phi$ as well) extends $\phi$ in such a way that the
  images of all elements of $P^{-1}(\sigma)$ are (special) relabelings
  of $\phi(\sigma)$.

% \cite{shin} (see Remark~\ref{rem}).


% Finally, this bijection (the new $\phi$) has also the interesting
% property that the images of all elements of $P^{-1}(\sigma)$ are
% (special) relabelings of $\phi(\sigma)$.  For example, in 
% Figure~\ref{fig1}\textbf{(a)}, $\phi(1,8,5,2,7,4,4,8,1)$ is a relabeling of
% $\phi(\sigma)$ for $\sigma=(1,8,5,2,7,4,6,9,3)$, in 
% Figure~\ref{fig1}\textbf{(b)}, and we have seen that
% $\sigma=P(1,8,5,2,7,4,4,8,1)$.


% All these properties are fulfilled by the bijection of Heesung Shin in
% \cite{shin} (see Remark~\ref{rem}).
% , that inspired very much of our work.  Yet, Shin's and our
% bijections do not coincide. We will point out later some relation
% that exists between both bijections.

\begin{figure}[tbp]
\hrule
\setlength{\unitlength}{1.25cm}
\strut\hfill\begin{picture}(4.5,4.5)(0,-4.5)
\psset{unit=1.25cm}
\cnodeput(4.,-3.){b5}{5}
\rput(4.25,-3.35){\red\scriptsize 0}
\cnodeput(3.,-4.){b8}{8}
\rput(3.25,-4.35){\red\scriptsize 0}
\cnodeput(2.,-4.){b6}{6}
\rput(2.25,-4.35){\red\scriptsize 0}
\cnodeput(2.5,-3.){b3}{3}
\rput(2.85,-3.35){\red\scriptsize 2}
\cnodeput(1.,-3.){b2}{2}
\rput(1.25,-3.35){\red\scriptsize 0}
\cnodeput(2.5,-2.){b7}{7}
\rput(2.75,-2.35){\red\scriptsize 1}
\cnodeput(0.,-4.){b4}{4}
\rput(0.25,-4.35){\red\scriptsize 0}
\cnodeput(0.,-3.){b9}{9}
\rput(0.25,-3.35){\red\scriptsize 0}
\cnodeput(0.,-2.){b1}{1}
\rput(0.25,-2.35){\red\scriptsize 2}
\cnodeput[linecolor=red](1.25,-0.75){b10}{\red 10}
\ncline{-}{b1}{b9}
\ncline[linecolor=red]{-}{b1}{b10}
\ncline{-}{b2}{b7}
\ncline{-}{b3}{b6}
\ncline{-}{b3}{b7}
\ncline{-}{b3}{b8}
\ncline{-}{b4}{b9}
\ncline{-}{b5}{b7}
\ncline[linecolor=red]{-}{b7}{b10}
%\end{minipage}
\end{picture}\hfill
\begin{picture}(4.5,4.5)(0,-4.5)
\psset{unit=1.25cm}
\cnodeput(4.,-4.){a1}{1}
\rput(3.75,-4.35){\red\scriptsize 10}
\cnodeput(4.,-3.){a4}{4}
\rput(3.75,-3.35){\red\scriptsize 9}
\cnodeput(4.,-2.){a9}{9}
\rput(3.75,-2.35){\red\scriptsize 8}
\cnodeput(3.,-4.){a6}{6}
\rput(2.75,-4.35){\red\scriptsize 7}
\cnodeput(2.,-4.){a3}{3}
\rput(1.75,-4.35){\red\scriptsize 6}
\cnodeput(2.5,-3.){a7}{7}
\rput(2.15,-3.25){\red\scriptsize 5}
\cnodeput(1.,-3.){a5}{5}
\rput(0.75,-3.35){\red\scriptsize 4}
\cnodeput(0.,-3.){a2}{2}
\rput(-0.25,-3.35){\red\scriptsize 3}
\cnodeput(1.16667,-2.){a8}{8}
\rput(0.92,-2.375){\red\scriptsize 2}
\rput(2.33333,-1.1){\red\scriptsize 1}
\cnodeput[linecolor=red](2.58333,-0.75){a10}{\red 10}
\ncline{-}{a1}{a4}
\ncline{-}{a2}{a8}
\ncline{-}{a3}{a7}
\ncline{-}{a4}{a9}
\ncline{-}{a5}{a8}
\ncline{-}{a6}{a7}
\ncline{-}{a7}{a8}
\ncline[linecolor=red]{-}{a8}{a10}
\ncline[linecolor=red]{-}{a9}{a10}
\end{picture}\hfill\strut
%\vspace{.25cm}
\bigskip

\noindent
\strut\hfill
\begin{minipage}[h]{5.125cm}
%$$\mathbf{(a)}\quad%&=
%\rnode{d5}{5}\;\rnode{d8}{8}\;\rnode{d6}{6}\;\rnode{d3}{3}\;\rnode{d2}{2}\;
%\rnode{d7}{7}\;\rnode{d4}{4}\;\rnode{d9}{9}\;\rnode{d1}{1}\;\rnode{d10}{10}$$
\begin{align*}
\mathbf{(a)}\quad &
\rnode{d5}{5}\;\rnode{d8}{8}\;\rnode{d6}{6}\;\rnode{d3}{3}\;\rnode{d2}{2}\;
\rnode{d7}{7}\;\rnode{d4}{4}\;\rnode{d9}{9}\;\rnode{d1}{1}\;\rnode{d10}{10}\,=\\
&\phi(1,8,5,2,7,4,4,8,1)
\end{align*}
\end{minipage}\hfill
\begin{minipage}[h]{5.125cm}
%$$\mathbf{(b)}\quad%&=
%\rnode{c1}{1}\;\rnode{c4}{4}\;\rnode{c9}{9}\;\rnode{c6}{6}\;\rnode{c3}{3}\;
%\rnode{c7}{7}\;\rnode{c5}{5}\;\rnode{c2}{2}\;\rnode{c8}{8}\;\rnode{c10}{10}=$$
\begin{align*}
\mathbf{(b)}\quad &
\rnode{c1}{1}\;\rnode{c4}{4}\;\rnode{c9}{9}\;\rnode{c6}{6}\;\rnode{c3}{3}\;
\rnode{c7}{7}\;\rnode{c5}{5}\;\rnode{c2}{2}\;\rnode{c8}{8}\;\rnode{c10}{10}\,=\\
&\phi(1,8,5,2,7,4,6,9,3)
\end{align*}
\end{minipage}\hfill\strut
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d1}{d9}
\nccurve[nodesep=.05,ncurv=0.75,linecolor=red,angleB=90,angleA=90]{-}{d1}{d10}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d2}{d7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d6}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d4}{d9}
\nccurve[nodesep=.05,ncurv=0.625,angleB=90,angleA=90]{-}{d5}{d7}
\nccurve[nodesep=.05,ncurv=0.625,linecolor=red,angleB=90,angleA=90]{-}{d7}{d10}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c1}{c4}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c2}{c8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c3}{c7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c4}{c9}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c5}{c8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c6}{c7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c7}{c8}
\nccurve[nodesep=.05,ncurv=0.75,linecolor=red,angleB=90,angleA=90]{-}{c8}{c10}
\nccurve[nodesep=.05,ncurv=0.5,linecolor=red,angleB=90,angleA=90]{-}{c9}{c10}
\caption{The number of inversions of each vertex appears as an index in
  \textbf{(a)}, whereas in \textbf{(b)} the indices show the order
  in which \emph{depth-first search} on the tree visits the vertices.}
\label{fig1}
\bigskip
\hrule
\end{figure}

Before proceeding to the definition of (the extended) $\phi$, let us
introduce some new concepts that will be necessary in the sequel.

\begin{definition}
  Given any tree $T$, consider the \emph{depth-first search algorithm}
  that starts with vertex $n+1$ and at each step goes to the
  \emph{least} adjacent vertex not yet visited, if any, or else it
  backtracks\footnote{See \cite{gessel} for related
    constructions.}. If $v_j$ is the $j$-th vertex visited (for the
  first time) by the search, define the \emph{permutation of $T$} by:
$$\pt(T):=(v_{n+1},v_n,\dotsc,v_1=n+1).$$
Hence, the elements of $\pt(T)$ are in \emph{postorder}.

We say that a vertex $k$ \emph{follows the vertex $i$ in $T$}, $k\ne
i$, if it is visited for the first time between the first and the last
visit to $i$.  We denote the set of vertices that follow a vertex $i$
in $T$ by $\fol_T(i)$.

A \emph{descendant of a vertex $i$ in $T$} is a vertex $k< i$
that follows $i$. These vertices form a set denoted by $\desc_T(i)$.
 The \emph{depth of a vertex $i$ in $T$} is the
number $\dt_T(i)$ of descendants of $i$ and the \emph{depth of $T$} is
the vector $\quad \dt(T)=\big(\dt_T(1),\dt_T(2),\dotsc,\dt_T(n)\big)$.
\end{definition}

\noindent
In the tree $T$ of Figure~\ref{fig1}\textbf{(a)}, for example, after
starting with $10$, $1$ is visited, then $9$, then $4$, $7$, $2$, $3$,
$6$, $8$ and finally $5$. Hence $\pt(T)=(5,8,6,3,2,7,4,9,1,10)$ and,
for example, $\fol_T(3)=\{6,8\}$, whereas $\desc_T(3)=\emptyset$.
  In the same tree, $\dt(T)=(0,0,0,0,0,0,4,0,1)$.

  Figure~\ref{fig1}\textbf{(b)} gives us an example that will be
  generalized in Lemma~\ref{permtree} below: if
  $\sigma=(1,8,5,2,7,4,6,9,3)\in S_9$, then $(1,4,9,6,3,7,5,2,8)=
  \sigma^{-1}$.  Let $T$ be the tree in this figure; we have
  $\dt_T(8)=5$ and $\dt_T(9)= 2$.  Note that $5$ is also the eighth
component of the depth of $\sigma$ (cf.\ Definition~\ref{def2.4}) and
${2}$ is the ninth component.  More precisely, whereas
$\{6,3,7,5,2\}=\desc_T(8)$,
$\sigma\big(\{6,3,7,5,2\}\big)=\{4,5,6,7,8\}$, $\sigma(8)=9$ and
$\{4,5,6,7,8,9\}$ is the interval of form $\{k,k+1,\dotsc, 9\}$
contained in $\sigma([8])$ that is maximal for this property, which
means $\df_\sigma(8)=5$.

In fact, this idea  is the crux of our
construction. It is implicit in \cite{shin}, but we believe it was
unobserved before.  We formalize it in Lemma~\ref{crux}.
Before, we recall some properties of this construction.
\medskip
 
Let $\alpha:=\pt(T)=:(a_1,a_2,\dotsc,a_{n+1}=n+1)$.
\begin{itemize}
\item Suppose $i=a_j$.  By definition, either $\fol_T(i)=\emptyset$
  or there exists $k<j$ such that
  $\fol_T(i)=\{a_{k},a_{k+1},\dotsc,a_{j-1}\}$.  The subgraph induced
  by this set of vertices is also a tree.
\item Given any vertex $i=a_j$, there is a unique $k>j$ such that $i$
  is connected to $a_k$. In other words, in $\alpha$, any vertex is
  connected to a unique vertex \emph{in its right-hand side}. The
  vertex $a_k$ is the leftmost (i.e., the last visited) ancestor of
  $i$.
\item Hence, if $j<p<l$ and $a_j$ is connected to $a_l$, then $a_p$
  must be connected to some $a_q$ with $p<q<l$. Therefore, there
  exists a planar representation of the tree $T$ where all vertices
  are in a line --- ordered according to $\pt$.  Note that, by
    Lemma~\ref{permtree} below, if $T=\phi(\sigma)$ for some
  $\sigma\in S_n$ this is the \emph{linear representation} already
  described.
\item If $\fol_T(i)=\{a_{l},a_{l+1},\dotsc,a_{j-1}\}$ and $l>1$, then
  $a_{l-1}$ is precisely the rightmost element connected with some
  $a_p$ with $p>j$.
\item Passing from a vertex to its neighbor on the right in $\alpha$,
  we obtain a path between any vertex and $n+1$.  Since $T$ is a tree,
  thus, a vertex $v$ follows a vertex $i$ in $T$ if and only if $i$
  belongs to the path that connects $v$ to $n+1$.  Hence,
  $\inv_T(i)=|\fol_T(i)|-\dt_T(i)$ for every $i=1,\dotsc,n+1$.  In
  particular, a tree is decreasing if and only if every vertex that
  follows a given vertex $i$ is its descendant.
\end{itemize}


It is now easy to prove Lemma~\ref{permtree}. Note that $S_n$ is the
set of parking functions with zero probes, whereas the decreasing
trees are the labeled trees with zero inversions.


\begin{lemma}\label{permtree} 
The map $\phi$ as defined before maps $S_n$ bijectively onto the
    set of decreasing trees with labels $[n+1]$. More precisely,
\begin{align}
  &\pt\left(\phi(\sigma)\right)\;=\;\overline{\sigma}\;^{-1}&%\hspace{-2cm}
&\text{for
    every $\sigma\in S_n$;}\label{dois}\\[5pt]
  &T\;=\;\phi\left(\pt(T)^{-1}\right)&%\hspace{-2cm}
&\text{for every decreasing tree $T$.}\label{um}
\end{align}
\end{lemma}
\begin{proof}
  We prove that $\phi$ is injective; surjectivity is a consequence of
  \eqref{um}. We assume that $\sigma\neq\sigma'$ are two bijections with
  associated trees $T$ and $T'$. We assume also that
  $\sigma(i)\neq\sigma'(i)$ but $\sigma(j)=\sigma'(j)$ for
  $i<j<n+1$. Let $a=\sigma(i)$ and $b=\sigma'(i)$, and suppose without
  loss of generality that $a<b$. Then, in $T$ there exists an edge
  $e=a\,\overline{\sigma}(k)$ with $i<k\leq n+1$. Note that we must have
  $a=\sigma(l)$ for some $l<i$, but since $b>a$ the edge $e$ cannot
  belong to $T'$. Hence $T\neq T'$.

  Statement \eqref{dois} is a consequence of this fact and of \eqref{um}.

  For the proof of \eqref{um}, let again
  $\alpha=\pt(T)=(a_1,a_2,\dotsc,a_{n+1}=n+1)$ and $i\leq n+1$ with
  $i=a_j$.  In order to prove the first statement, we prove that the
  leftmost (in $\alpha$) ancestor of $i$, $k$, is also the leftmost
  element greater than $i$. We already know that $k>i$ since $T$ is
  decreasing. Suppose that $k=a_l$ and there exists $m=a_p>i$ with
  $j<p<l$; we may and will assume that $p$ is minimal for this
  property. Then $m$ is a descendant of $k$ but $i$ is not a
  descendant of $m$, and so there is a first common ancestor of $i$
  and $m$ that is either $k$ or a descendant of $k$. Finally, there
  exist $x$ and $y$ adjacent to this ancestor and in the path
  connecting $m$ and $i$ to it, respectively. Note that $x<y$, $m\leq
  x$ and $y$ is on the left of $m$ and on the right of $i$, contrary
  to the definition of $m$.
\end{proof}

\begin{lemma}\label{crux}
For every permutation $\sigma\in S_n$,
\begin{equation*}
\df(\sigma)\;=\;\dt(\phi(\sigma)).
\end{equation*}
\end{lemma}
\begin{proof}
  Define, for $1\leq i\leq n$, $m_i:=\min\big\{k\in \sigma([i])\colon
  \{k,k+1,\dotsc,\sigma(i)\}\subset\sigma([i])\big\}$, and suppose
  $m_i>1$.  In other words, $m_i$ is defined by
  $\sigma^{-1}(m_i-1)>i$ and $\sigma^{-1}(k)<i$ for every $m_i\leq
  k<\sigma(i)$.  Hence, the set of descendants of $i$ in
  $T=\phi(\sigma)$ is
  $\sigma^{-1}\big(\{m_i,m_i+1,\dotsc,\sigma(i)\}\big)\setminus\{i\}$.
\end{proof}

\begin{figure}[tbp]
\hrule
\bigskip

\vspace{-.5cm}
\noindent
{\setlength{\unitlength}{.5cm}
\strut\hfill
\begin{picture}(5.25,5.)(0.,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](4.,-4.){a1}{\scriptsize 1}
\cnodeput[framesep=1pt](4.,-3.){a4}{\scriptsize 4}
\cnodeput[framesep=1pt](4.,-2.){a9}{\scriptsize 9}
\cnodeput[framesep=1pt](3.,-4.){a6}{\scriptsize 6}
\cnodeput[framesep=1pt](2.,-4.){a3}{\scriptsize 3}
\cnodeput[framesep=1pt](2.5,-3.){a7}{\scriptsize 7}
\cnodeput[framesep=1pt](1.,-3.){a5}{\scriptsize 5}
\cnodeput[framesep=1pt](0.,-3.){a2}{\scriptsize 2}
\cnodeput[framesep=1pt](1.167,-2.){a8}{\scriptsize 8}
\cnodeput[framesep=1pt,linecolor=red](2.583,-0.75){a10}{\red\scriptsize 10}
\ncline{-}{a1}{a4}
\ncline{-}{a2}{a8}
\ncline{-}{a3}{a7}
\ncline{-}{a4}{a9}
\ncline{-}{a5}{a8}
\ncline{-}{a6}{a7}
\ncline{-}{a7}{a8}
\ncline[linecolor=red]{-}{a8}{a10}
\ncline[linecolor=red]{-}{a9}{a10}
\end{picture}\llap{$\to\ $}
\begin{picture}(5.25,5.)(4.5,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](9.,-4.){b6}{\scriptsize 6}
\cnodeput[framesep=1pt](8.,-4.){b3}{\scriptsize 3}
\cnodeput[framesep=1pt](8.5,-3.){b7}{\scriptsize 7}
\cnodeput[framesep=1pt](7.,-3.){b5}{\scriptsize 5}
\cnodeput[framesep=1pt](6.,-3.){b2}{\scriptsize 2}
\cnodeput[framesep=1pt](7.167,-2.){b8}{\scriptsize 8}
\cnodeput[framesep=1pt](5.,-4.){b1}{\scriptsize 1}
\cnodeput[framesep=1pt](5.,-3.){b9}{\scriptsize 9}
\cnodeput[framesep=1pt](5.,-2.){b4}{\scriptsize 4}
\cnodeput[framesep=1pt,linecolor=red](6.083,-0.75){b10}{\red\scriptsize 10}
\ncline{-}{b1}{b9}
\ncline{-}{b2}{b8}
\ncline{-}{b3}{b7}
\ncline{-}{b4}{b9}
\ncline[linecolor=red]{-}{b4}{b10}
\ncline{-}{b5}{b8}
\ncline{-}{b6}{b7}
\ncline{-}{b7}{b8}
\ncline[linecolor=red]{-}{b8}{b10}
\end{picture}\llap{$\to\ $}
\begin{picture}(5.25,5.)(9.,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](14.,-4.){c6}{\scriptsize 6}
\cnodeput[framesep=1pt](13.,-4.){c3}{\scriptsize 3}
\cnodeput[framesep=1pt](13.5,-3.){c7}{\scriptsize 7}
\cnodeput[framesep=1pt](12.,-3.){c5}{\scriptsize 5}
\cnodeput[framesep=1pt](11.,-3.){c2}{\scriptsize 2}
\cnodeput[framesep=1pt](12.167,-2.){c8}{\scriptsize 8}
\cnodeput[framesep=1pt](10.,-4.){c4}{\scriptsize 4}
\cnodeput[framesep=1pt](10.,-3.){c9}{\scriptsize 9}
\cnodeput[framesep=1pt](10.,-2.){c1}{\scriptsize 1}
\cnodeput[framesep=1pt,linecolor=red](11.0833,-0.75){c10}{\red\scriptsize 10}
\ncline{-}{c1}{c9}
\ncline{-}{c2}{c8}
\ncline{-}{c3}{c7}
\ncline{-}{c4}{c9}
\ncline{-}{c5}{c8}
\ncline{-}{c6}{c7}
\ncline{-}{c7}{c8}
\ncline[linecolor=red]{-}{c8}{c10}
\ncline[linecolor=red]{-}{c1}{c10}
\end{picture}\llap{$\to\ $}
\begin{picture}(5.25,5.)(13.5,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](19.,-4.){d7}{\scriptsize 7}
\cnodeput[framesep=1pt](18.,-4.){d3}{\scriptsize 3}
\cnodeput[framesep=1pt](18.5,-3.){d6}{\scriptsize 6}
\cnodeput[framesep=1pt](17.,-3.){d5}{\scriptsize 5}
\cnodeput[framesep=1pt](16.,-3.){d2}{\scriptsize 2}
\cnodeput[framesep=1pt](17.167,-2.){d8}{\scriptsize 8}
\cnodeput[framesep=1pt](15.,-4.){d4}{\scriptsize 4}
\cnodeput[framesep=1pt](15.,-3.){d9}{\scriptsize 9}
\cnodeput[framesep=1pt](15.,-2.){d1}{\scriptsize 1}
\cnodeput[framesep=1pt,linecolor=red](16.083,-0.75){d10}{\red\scriptsize 10}
\ncline{-}{d1}{d9}
\ncline[linecolor=red]{-}{d1}{d10}
\ncline{-}{d2}{d8}
\ncline{-}{d3}{d6}
\ncline{-}{d4}{d9}
\ncline{-}{d5}{d8}
\ncline{-}{d6}{d7}
\ncline{-}{d6}{d8}
\ncline[linecolor=red]{-}{d8}{d10}
\end{picture}\llap{$\to\ $}
\begin{picture}(5.25,5.)(18.,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](24.,-3.){e5}{\scriptsize 5}
\cnodeput[framesep=1pt](23.,-4.){e7}{\scriptsize 7}
\cnodeput[framesep=1pt](22.,-4.){e6}{\scriptsize 6}
\cnodeput[framesep=1pt](22.5,-3.){e3}{\scriptsize 3}
\cnodeput[framesep=1pt](21.,-3.){e2}{\scriptsize 2}
\cnodeput[framesep=1pt](22.5,-2.){e8}{\scriptsize 8}
\cnodeput[framesep=1pt](20.,-4.){e4}{\scriptsize 4}
\cnodeput[framesep=1pt](20.,-3.){e9}{\scriptsize 9}
\cnodeput[framesep=1pt](20.,-2.){e1}{\scriptsize 1}
\cnodeput[framesep=1pt,linecolor=red](21.25,-0.75){e10}{\red\scriptsize 10}
\ncline{-}{e1}{e9}
\ncline[linecolor=red]{-}{e1}{e10}
\ncline{-}{e2}{e8}
\ncline{-}{e3}{e6}
\ncline{-}{e3}{e7}
\ncline{-}{e3}{e8}
\ncline{-}{e4}{e9}
\ncline{-}{e5}{e8}
\ncline[linecolor=red]{-}{e8}{e10}
\end{picture}\llap{$\to\ $}
\begin{picture}(4.,5.)(22.5,-3.35)
\psset{unit=.45cm}
\cnodeput[framesep=1pt](29.,-3.){f5}{\scriptsize 5}
\cnodeput[framesep=1pt](28.,-4.){f8}{\scriptsize 8}
\cnodeput[framesep=1pt](27.,-4.){f6}{\scriptsize 6}
\cnodeput[framesep=1pt](27.5,-3.){f3}{\scriptsize 3}
\cnodeput[framesep=1pt](26.,-3.){f2}{\scriptsize 2}
\cnodeput[framesep=1pt](27.5,-2.){f7}{\scriptsize 7}
\cnodeput[framesep=1pt](25.,-4.){f4}{\scriptsize 4}
\cnodeput[framesep=1pt](25.,-3.){f9}{\scriptsize 9}
\cnodeput[framesep=1pt](25.,-2.){f1}{\scriptsize 1}
\cnodeput[framesep=1pt,linecolor=red](26.25,-0.75){f10}{\red\scriptsize 10}
\ncline{-}{f1}{f9}
\ncline[linecolor=red]{-}{f1}{f10}
\ncline{-}{f2}{f7}
\ncline{-}{f3}{f6}
\ncline{-}{f3}{f7}
\ncline{-}{f3}{f8}
\ncline{-}{f4}{f9}
\ncline{-}{f5}{f7}
\ncline[linecolor=red]{-}{f7}{f10}
\end{picture}
\hfill\strut

\noindent\strut$\scriptstyle
\phi( 1, 8, 5, 2, 7, 4, 6, 9, 3)\hfill
\phi(1, 8, 5, 2, 7, 4, 6, 9, 2)\hfill
\phi(1, 8, 5, 2, 7, 4, 6, 9, 1)\hfill
\phi(1, 8, 5, 2, 7, 4, 5, 9, 1)\hfill
\phi(1, 8, 5, 2, 7, 4, 4, 9, 1)\hfill
\phi(1, 8, 5, 2, 7, 4, 4, 8, 1)$\strut
}

\caption{Rewriting process}
\bigskip
\hrule
\label{fig2}
\end{figure}

\newpage

Let us now proceed to the definition of $\phi$. Let $T$ be a labeled
tree and $i$ and $k$ be two vertices such that $k\in\desc_T(i)$,
(and hence, $k<i$). Similar to \cite{beissinger}, define $\pi(T;i,k)$ as the labeled
tree that is obtained from $T$ by replacing each label $l$ by $\pi(l)$,
where:
\begin{equation*}
\pi(l)\;=\;
\begin{cases}
  \min\left\{m\in\desc_T(i)\cup\{i\}\colon m>l\right\}&
  \text{if $k\leq l<i$ and $l\in\desc_T(i)$;}\\
  k&\text{if $l=i$;}\\
  l&\text{if $l\notin\desc_T(i)$ or $l<k$ or $l>i$.}
\end{cases}
\end{equation*}
It is  convenient to define also $T=\pi(T;i,i)$ for every $i\in[n]$.


Now, given the parking function $f\in\PF_n$, let $\sigma=P(f)$,
$\alpha=\overline{\sigma}\;^{-1}$, $T=\phi(\sigma)$ and $T_0=T$.  For
each $i\leq n$, let
$\desc_T(i)=\big\{a_1^i>\dotsb>a_{\df_\sigma(i)}^i\big\}$ be written
in decreasing order, and $a_0^i=i$.  Finally, define recursively
$$T_i=\pi\left(T_{i-1};i,a_{\sigma(i)-f(i)}^i\right)\ ,\quad
1\leq i\leq n,$$
and $\phi(f)=T_n$.


Note that if $p_i:=\sigma(i)-f(i)>0$ then the permutation that changes
the labels of $T_{i-1}$ into the labels of $T_i$ is the cycle
$\gamma_i=(a_{p_i}^i\;a_{p_i-1}^i\;\dotsb\;a_2^i\;a_1^i\;i)
=(a_{p_i}^i\;a_{p_i-1}^i)\dotsb (a_2^i\;a_1^i)\,(a_1^i\;i)$.  Let once
more $\pi$ be their product, ordered according to $i$.  For
  example, in Figure~\ref{fig1}, the initial $T$ (that is,
  $\phi(\sigma)$) is the tree represented in \textbf{(b)}.  The
vertices of $T$ are relabeled in $\phi(f)$ by $\pi=\gamma_9\circ
\gamma_8\circ \gamma_7=(1\,4)(4\,9)(7\,8)(3\,6)(6\,7)=
(4,2,6,9,5,8,3,7,1)$: vertex $1$ of the tree in
  Figure~\ref{fig1}(\textbf{b}) is relabeled $4$ in the tree of
  Figure~\ref{fig1}(\textbf{a}), the label of $2$ is kept, and so
  on, $3$ is relabeled $6$, etc.

  It follows immediately from the previous definition that the number
  of inversions of $\phi(f)$ is the total number of probes of $f$,
  $\Pr(f)$.  More precisely, if this construction is combined with
  Lemma~\ref{crux}, the following result is implied.


\begin{theorem}\label{depthsthm}
For every $f\in \PF_n$,
\begin{equation*}
{\df(f)\;=\;\dt(\phi(f))
\circ\pi}.
\end{equation*}
\end{theorem}


\begin{remark}\label{rem}
\emph{
\begin{figure}[tbp]
\hrule
{\setlength{\unitlength}{1.25cm}
\strut\hfill\begin{picture}(4.5,4.5)(0,-4.5)
\psset{unit=1.25cm}
\cnodeput(4.,-3.){b5}{5}
%\rput(4.25,-3.35){\red\scriptsize 0}
\cnodeput(3.,-4.){b8}{8}
%\rput(3.25,-4.35){\red\scriptsize 0}
\cnodeput(2.,-4.){b6}{6}
%\rput(2.25,-4.35){\red\scriptsize 0}
\cnodeput(2.5,-3.){b3}{3}
\rput(2.85,-3.35){\red\scriptsize 2}
\cnodeput(1.,-3.){b2}{2}
%\rput(1.25,-3.35){\red\scriptsize 0}
\cnodeput(2.5,-2.){b7}{7}
\rput(2.75,-2.35){\red\scriptsize 1}
\cnodeput(0.,-4.){b4}{4}
%\rput(0.25,-4.35){\red\scriptsize 0}
\cnodeput(0.,-3.){b9}{9}
%\rput(0.25,-3.35){\red\scriptsize 0}
\cnodeput(0.,-2.){b1}{1}
\rput(0.25,-2.35){\red\scriptsize 2}
\cnodeput[linecolor=red](1.25,-0.75){b10}{\red 10}
\ncline{-}{b1}{b9}
\ncline[linecolor=red]{-}{b1}{b10}
\ncline{-}{b2}{b7}
\ncline{-}{b3}{b6}
\ncline{-}{b3}{b7}
\ncline{-}{b3}{b8}
\ncline{-}{b4}{b9}
\ncline{-}{b5}{b7}
\ncline[linecolor=red]{-}{b7}{b10}
\end{picture}%\hfill
\quad\!\raisebox{2.8cm}{$\stackrel{\displaystyle\pi}{\longmapsfrom}$}\qquad
\begin{picture}(4.5,4.5)(0,-4.5)
\psset{unit=1.25cm}
\cnodeput(4.,-3.){b5}{5}
\rput(3.85,-3.35){\blue\scriptsize 7}
\cnodeput(3.,-4.){b8}{6}
\rput(2.85,-4.35){\blue\scriptsize 4}
\cnodeput(2.,-4.){b6}{3}
\rput(1.85,-4.35){\blue\scriptsize 5}
\cnodeput(2.5,-3.){b3}{7}
\rput(2.15,-3.25){\blue\scriptsize 6}
\cnodeput(1.,-3.){b2}{2}
\rput(0.85,-3.35){\blue\scriptsize 8}
\cnodeput(2.5,-2.){b7}{8}
\rput(2.35,-2.35){\blue\scriptsize 9}
\cnodeput(0.,-4.){b4}{1}
\rput(-0.15,-4.35){\blue\scriptsize 1}
\cnodeput(0.,-3.){b9}{4}
\rput(-0.15,-3.35){\blue\scriptsize 2}
\cnodeput(0.,-2.){b1}{9}
\rput(-0.15,-2.35){\blue\scriptsize 3}
\cnodeput[linecolor=red](1.25,-0.75){b10}{\red 10}
\ncline{-}{b1}{b9}
\ncline[linecolor=red]{-}{b1}{b10}
\ncline{-}{b2}{b7}
\ncline{-}{b3}{b6}
\ncline{-}{b3}{b7}
\ncline{-}{b3}{b8}
\ncline{-}{b4}{b9}
\ncline{-}{b5}{b7}
\ncline[linecolor=red]{-}{b7}{b10}
\end{picture}\hfill\strut
\bigskip
%
\noindent
\strut\hfill
\begin{minipage}[h]{5.525cm}
$\mathbf{(a)}\ T'=\phi(1,8,5,2,7,4,4,8,1)$
\end{minipage}\hfill
\begin{minipage}[h]{5.525cm}
$\mathbf{(b)}\ T=\phi(1,8,5,2,7,4,6,9,3)$
\end{minipage}\hfill\strut
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d1}{d9}
\nccurve[nodesep=.05,ncurv=0.75,linecolor=red,angleB=90,angleA=90]{-}{d1}{d10}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d2}{d7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d6}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d3}{d8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{d4}{d9}
\nccurve[nodesep=.05,ncurv=0.625,angleB=90,angleA=90]{-}{d5}{d7}
\nccurve[nodesep=.05,ncurv=0.625,linecolor=red,angleB=90,angleA=90]{-}{d7}{d10}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c1}{c4}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c2}{c8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c3}{c7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c4}{c9}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c5}{c8}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c6}{c7}
\nccurve[nodesep=.05,ncurv=0.75,angleB=90,angleA=90]{-}{c7}{c8}
\nccurve[nodesep=.05,ncurv=0.75,linecolor=red,angleB=90,angleA=90]{-}{c8}{c10}
\nccurve[nodesep=.05,ncurv=0.5,linecolor=red,angleB=90,angleA=90]{-}{c9}{c10}%}
\caption{In \textbf{(b)} the indices show \emph{postorder}.}
}
\label{fig3}
\bigskip
\hrule
\end{figure}} \emph{Suppose the tree $T'=\Phi(f)$ is given and $T'$ is
the relabeling by $\pi\in S_n$, also given, of $T=\Phi(P(f))$, as in
Figure~\ref{fig3} (see Lemma~\ref{inversetree}, below).  Then, the
easiest way to recover $f$ is as follows: for every $i\in[n]$,
$f(i)=P(f)(i)-\inv_{T'}(\pi(i))$ and the $P(f)(i)$'s are in
  % reversed depth-first search order
postorder. Hence, in Figure~\ref{fig3}, we obtain $f(i)$ by
reading the blue index near to the vertex labeled $i$ in \textbf{(b)}
and subtracting from it the red index near
to the corresponding position in \textbf{(a)}.\\
\indent In fact, by Lemma~\ref{permtree}, the blue index near to $i$
is $P(f)(i)$.  In order to see that
$$\pr(f)=\inv_{T'}\circ\pi,$$
note that $\pr(f)=\df(P(f))-\df(f)$ is equal to
$\dt(\phi(P(f)))-\dt(\phi(f))\circ\pi$ by Theorem~\ref{depthsthm}, and
so is the difference between the number of \emph{followers} and
\emph{descendants} of $\pi(i)$ in $T'$.\\} \indent \emph{If we
  replace our tree $T'=\pi(T)$ by the tree $T$ of \cite{shin}, then
  our $T$ is Shin's $D$, the red labels in \textbf{(a)} form Shin's
tree $I$ and the blue labels in \textbf{(b)} form $C$. 
Proceeding as indicated above, we would then obtain Shin's related parking function
instead of  $f$.
% what we have seen, under this assumption our bijection and Shin's
% bijection, $\sigma$, say, would coincide (see \cite{shin}).
%In fact, 
On the other hand, our construction of $T'=\Phi(f)$ and 
Shin's corresponding construction are both based on $T=\Phi(P(f))$, and 
both proceed by relabeling $T$, although by two different processes.}
% Although the two processes are different, 
%Hence, from this point of view, Shin's bijection and ours differ
%  essentially by the fact that}
%, if inversions are marked as in
%Figure~\ref{fig3}\textbf{.(a)}, since 
%  Shin's concept of \emph{inversion} is our concept of
%  \emph{descendant}}.
\end{remark}


Note that, in the previous example, we have as well $\pi=\gamma_8\circ
\gamma_7\circ \gamma_9$ (cf.\ Figure~\ref{fig2}), since
$\desc_T(9)\cap\desc_T(8)=\emptyset$ and
$\desc_T(7)\subset\desc_T(8)$.  In general, given two vertices $v$ and
$w$ of a tree $T$, either neither of the vertices follows the other
one and then there exists no vertex following both vertices, or one of
the vertices follows the other, say $v\in\fol_T(w)$, and then
$\fol_T(v)\subset\fol_T(w)$.  In other words, we may take the sets of
followers of the vertices ordered \emph{reversely} to \textbf{any}
depth-first search, independently of the way \emph{siblings} (adjacent
vertices following the same vertex) are ordered. We will use this in
the proof of Lemma~\ref{inversetree} below, where we assume, for the
purpose of recovering the order of the transpositions in $\pi$, that
$\pt(f)=\pi\circ\pt(\sigma)$.

We may write $f=\sigma-e_{k_1}-\,\dotsb\,-e_{k_{\Pr(f)}}$, where
$e_k=(0,\dotsc,0,1,0,\dotsc,0)$ as usual (i.e., 1 is the $k$-th
coordinate) and $k_1\leq\dotsm\leq k_{\Pr(f)}$\footnote{The order may
  be different according to the last paragraph. Both ideas are
  illustrated in Figure~\ref{fig2}.}.  The sequence of trees obtained
by changing the labels \emph{transposition by transposition} is then
clearly $\phi(\sigma-e_{k_1})$, $\phi(\sigma-e_{k_1}-e_{k_2})$,
etc. (which, in particular, by Lemma~\ref{pproperties}, are images by
$\phi$ of parking functions with the same parking scheme).  By
definition, the number of probes increases in each step by one.  But
note that also the number of inversions increases by one, since the
labels we switch in each step are consecutive within the set of
descendants of some vertex (including possibly the vertex itself).

On the other hand, note that the inversion corresponding to the
transposition $(a_{j+1}^i\;a_j^i)$ is $(a_j^i,a_{j+1}^i)$ \emph{in a
  certain intermediate tree}, but not necessarily in the final one.
As an example, note that in Figure~\ref{fig1} the transposition
$(6\;7)$ in \textbf{(b)} gives rise to the inversion $(8,3)$ in
\textbf{(a)}, and \emph{not} to $(7,6)$.  Let us have a closer look at
this.

\begin{lemma}\label{inversetree}
  Let $f\in\PF_n$, $p=\Pr(f)$, $\sigma=P(f)$, $T=\phi(\sigma)$,
  $T'=\phi(f)$ be the relabeling of the vertices of $T$ by $\pi\in
  S_n$ and $\beta=\pt(T')$. Suppose that the inversions of $T'$, of
  the form $(\beta(a_k),\beta(b_k))$ say, are defined such that
\begin{align*}
  &b_k>b_{k+1}\ \text{or}\\
  &b_k=b_{k+1}\ \text {and}\ \beta(a_k)<\beta(a_{k+1}).
  \intertext{Then}
  &\pi^{-1}=(\beta(a_1)\;\beta(b_1))\,(\beta(a_2)\;\beta(b_2))\,\dotsb\,
  (\beta(a_p)\;\beta(b_p)).
\end{align*}
\end{lemma}
\begin{proof}
%According to the previous remarks, we consider that
%$\pt(f)=\pi\circ\pt(\sigma)$ where $\pi$ has been defined as a
%product of transpositions that we write, simplifying:
The permutation $\pi$ has been defined as a product of transpositions,
say
  \begin{equation*}
    \pi=(c_1\;d_1)\,(c_2\;d_2)\,\dotsm\,(c_p\;d_p)\qquad
    (c_k<d_k\ ,\quad k\leq p).
  \end{equation*}
According to the previous remarks, we have
  $\pt(f)=\pi\circ\pt(\sigma)$.
  We generalize $\pi$ by considering, for $1\leq k\leq p$,
  $\pi_k=(c_1\;d_1)\,(c_2\;d_2)\,\dotsm\,(c_k\;d_k)$. Note that, in
  $\phi(f)$, to the transposition $(c_k\;d_k)$ there corresponds the
  inversion $\left(\pi_k(c_k),\pi_k(d_k)\right)$, and note that
\begin{equation}\label{interm}
\big(\pi_k(c_k)\;\pi_k(d_k)\big)\;=\;\pi_k\,(c_k\;d_k)\,{\pi_k}^{-1}.
\end{equation}
Finally, note that, if $\gamma_i=(c_j\;d_j)\,\dotsm\,(c_k\;d_k)$ for
some $j<k$, then, by definition:
\begin{itemize}
\item $d_k=i$ and $c_l,d_l\neq i$ for $l>k$. Hence, $\pi_k(i)=\pi(i)$.
\item $d_l=c_{l+1}$ for $j\leq l<k$. Hence, 
  $\pi_k(d_k)=\pi_{k-1}(c_k)= \pi_{k-1}(d_{k-1})$. Continuing in this
  way, we obtain that $\pi_l(d_l)=\pi(i)$ for every $j\leq l\leq k$.
\item $c_{l-1}<c_l$ for every $j<l\leq k$;
  $\gamma_i(c_{i-1})=c_i<d_i=\gamma_i(c_i)$ and every $\gamma_m$ with
  $m>i$ either increases $d_i$ or both $c_i$ and $d_i$, keeping its
  order.
\end{itemize}
In short, we have proved that:
$$\beta(a_l)=\pi_l(c_l)\quad\text{and}\quad\beta(b_l)=\pi_l(d_l)\,,
\quad\text{for $1\leq l\leq p$};$$
hence, by \eqref{interm},
\begin{align*}
(\beta(a_1)\;\beta(b_1))\,\dotsb\,(\beta(a_p)\;\beta(b_p))
&=\pi_1(c_1\,d_1){\pi_1}^{-1}\pi_2(c_2\,d_2){\pi_2}^{-1}\pi_3 (c_3\,d_3){\pi_3}^{-1}
\dotsm \pi_p(c_p\,d_p){\pi_p}^{-1}\\
&={\pi_1}^{-1}\pi_2(c_2\,d_2){\pi_2}^{-1}\pi_3 (c_3\,d_3){\pi_3}^{-1}
\dotsm \pi_p(c_p\,d_p){\pi_p}^{-1}\\
&={\pi_2}^{-1}\pi_3 (c_3\,d_3){\pi_3}^{-1}
\dotsm \pi_p(c_p\,d_p){\pi_p}^{-1}\\
&={\pi_p}^{-1}\\
&={\pi}^{-1}.
\end{align*}
\end{proof}

As an example, note that in the tree of Figure~\ref{fig1}\textbf{(a)},
since $\beta=(5,8,6,3,2,7,4,9,1,10)$, the ordered set of inversions is
$\{(4,1),(9,1),(8,7),(6,3),(8,3)\}$; hence $\pi^{-1}=(4\,1)$\,$(9\,1)$
$(8\,7)$\,$(6\,3)$\,$(8\,3) =(9,2,7,1,5,3,8,6,4)$.

Put together, Lemma~\ref{lemmanum} and Lemma~\ref{inversetree} imply
that $\phi$ is a bijection. In fact, suppose $\phi(f)=\phi(g)$ for two
parking functions $f$ and $g$ of size $n$. By Lemma~\ref{inversetree},
we then get $\phi(P(f))=\phi(P(g))$ and hence $P(f)=P(g)$. But, by
definition of $\phi$, we must have $P(f)-f=P(g)-g$, and hence $f=g$.

\section{Acknowledgements} { We thank the referee for slightly
  changing our definition of inversion, which has led to 
Remark~\ref{rem}.  The work of the first author was supported, in part, by
  Funda\c{c}\~ao para a Ci\^encia e a Tecnologia (FCT) through the
  Centro de Matem\'atica da Universidade do Porto (CMUP).}


\begin{thebibliography}{99}
\bibitem{book} M.~Aigner and G.~Ziegler, \textit{Proofs from THE BOOK}
  (2nd ed.). Berlin, New York: Springer-Verlag (2002) (4-th
  edition in 2009).
\bibitem{beissinger} J.~S.~Beissinger, ``On external activity and
  inversions in trees'', \textit{J. Combin. Theory Ser. B} \textbf{33}
  (1982), 87--92.
\bibitem{foatariordan} D. Foata and J. Riordan, ``Mappings of acyclic
  and parking functions'', \textit{Aequationes Math.} \textbf{10}
  (1974), 10--22.
\bibitem{gessel} I. Gessel and D. L. Wang, 
``Depth-first search as a combinatorial correspondence'',
\textit{J. Combinatorial Theory Ser.~A} \textbf{26} (1979), 308--313.
\bibitem{kohneim} A.~G.~Konheim and B.~Weiss, ``An occupancy
  discipline and applications'', \textit{SIAM J. Appl. Math.}
  \textbf{14} (1966), 1266--1274.
\bibitem{kreweras} G.~Kreweras, ``Une famille de polyn\^omes ayant
  plusieurs propri\'et\'es \'enumeratives'', \textit{Per. Math. Hung.}
  \textbf{11} (1980), 309--320.
\bibitem{shin} H.~Shin, ``A new bijection between forests and parking
  functions'', ar$\chi$iv: {\tt 0810.0427v2 [math.CO]}. See also:
  \texttt{www.emis.de/journals/SLC/wpapers/s61vortrag/shin.pdf}
\bibitem{shin2} H.~Shin and J.~Zeng, ``A further correspondence
  between $\left(b\,c;\overline{b}\right)$-parking functions and
  $\left(b\,c;\overline{b}\right)$-forests'', \textit{DMTCS Proceedings}, 21st
  International Conference on Formal Power Series and Algebraic
  Combinatorics (FPSAC 2009), 793--804.
\bibitem{stan1} R.~P.~Stanley, ``An introduction to Hyperplane
  Arrangements'', in \textit{Geometric Combinatorics} (E. Miller,
  V. Reiner, and B. Sturmfels, eds.), IAS/Park City Mathematics
  Series, vol.\textbf{13}, American Mathematical Society, Providence,
  RI (2007), 389--496.
\bibitem{stanenum} R.~P.~Stanley, ``Enumerative Combinatorics,'' vol.~I, 
Cambridge Studies in Advanced Mathematics \textbf{49},
  Cambridge University Press, Cambridge, New York, 7th printing,
  (2006).

\end{thebibliography}

\end{document}