Séminaire Lotharingien de Combinatoire 65 (2011), Article B65e

PARKING FUNCTIONS AND LABELED TREES

ANTÓNIO GUEDES DE OLIVEIRA AND MICHEL LAS VERGNAS

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.

1. 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 [6], 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 [9, Exercise 4], Stanley asks for a direct bijection with this property, unknown until [7], 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 [8]), which was the starting point for our investigation. For the relation between Shin’s bijection and ours, see Remark 3.5.

The structure of the paper is as follows: In Section 2, 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 2.5 plays a rôle (not noted before, we believe) that is central in our construction.

Section 3 deals with rooted forests with n labeled vertices (naturally identified with trees with n + 1 labeled vertices): by using the depth-first search algorithm, it establishes a variant of a well-known bijection between permutations and 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.

2. Parking functions

As usual, we represent, for a natural number n, the set {1, 2, …, 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}.

Definition 2.1. We say that f ∈ F_{n} is a parking function if:

|f^{−1}([i])| ≥ i , i = 1, 2, …, n.

We call n the length of f and denote by PF_{n} the set of all parking functions of length n.

Based on [3] and on a construction of H. O. Pollak referred to therein, let us define, for a function f : [n] → [n + 1], the new function g = P (f) : [n] → [n + 1] recursively as follows:

• g(1) = f(1); • Suppose g(j) is defined for j < i; then define:

k_{0} = min {k ≥ 0: k + f(i) ≢ g(j) (mod n + 1), ∀ j < i}

and

g(i) ≡ k_{0} + f(i) (mod n + 1) (remember that 1 ≤ g(i) ≤ n + 1)

Note that P (f) is injective by definition. Suppose that n + 1 ∉ P (f)([n]) and so, in particular, that n + 1 ∉ f([n]). Then f(i) ≤ P (f)(i) for all i ≤ 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 ∈ S_{n}). More generally, if n+1 ∉ P (f)([n]) then we may write P (f) ∈ S_{n}. We have the following lemma.

Lemma 2.2. A function f ∈ F_{n} is a parking function if and only if n + 1 ∉ P (f)([n]).

Proof. Since P (f) is injective, there exists a unique k ∈ [n + 1] \ P (f)([n]). Suppose k ≤ n. Then P (f) maps injectively f^{−1}([k]) into [k − 1], by definition, and hence f is not a parking function. The converse is similar. □

By this lemma, we view the operator P as a function from PF_{n} to S_{n}. We call Π(f) := P (f)^{−1} the parking scheme of f ∈ PF_{n}. Note that, for f ∈ PF_{n}, P (f)(i) is simply the first k ≥ f(i) that is 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 [5]: 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 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 Π(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, …, n + 1, so that all cars can park in 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.

Lemma 2.3. The number of parking functions of size n is given by

|PF_{n}| = (n + 1)^{n−1}.

Proof. Suppose that f is a function f : [n] → [n + 1]. As in the beginning of the proof of Lemma 2.2, there exists k ≤ n + 1 such that [n + 1] \ P (f)([n]) = {k}. Define f̃: [n] → [n+1] by f̃(i) ≡ f(i)+n+1−k (mod n+1). Then P (f̃)(i) ≡ P (f)(i)+n+1−k (mod n + 1) and so f̃ ∈ PF_{n}. Hence, the number of parking functions of length n is the number (n + 1)^{n} of functions from [n] to [n + 1] divided by n + 1. □

Given σ ∈ S_{n}, the number of parking functions f ∈ PF_{n} such that σ = P (f) can be easily determined from the definition of P. Before establishing this number, we introduce some further notation:

Definition 2.4. For any function f ∈ PF_{n}, define pr(f) to be the vector P (f) − f. The 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} − ∑_{i≤n} f(i).

If σ is a permutation, let, for every i ≤ n, dp_{σ}(i) be the number of elements of σ([i−1]) that are smaller than σ(i) and consecutive to it. That is,

dp_{σ}(i) := σ(i) − min {k ∈ σ([i]): {k, k + 1, …, σ(i)} ⊂ σ([i])},

We define the depth of σ ∈ S_{n} to be

dp(σ) := (dp_{σ}(1), dp_{σ}(2), …, dp_{σ}(n))

and, in general, the depth of f ∈ PF_{n} to be

dp(f) := dp(P (f)) − P (f) + f.

Lemma 2.5. For every σ ∈ S_{n} and for every f ∈ PF_{n},

(2.1)  P (f) = σ holds if and only σ(i) − f(i) ≤ dp_{σ}(i).

Moreover,

(2.2)  |P^{−1}(σ)| = ∏_{i=1}^{n} (1 + dp_{σ}(i)) .

Proof. By definition of depth,

σ(i) − f(i) ≤ dp_{σ}(i) ⟺ {f(i), f(i) + 1, …, σ(i)} ⊂ σ ([i])
⟺ {f(i), f(i) + 1, …, σ(i) − 1} ⊂ σ ([i − 1]) ,

where the last equivalence holds since σ is injective. This explains (2.1), and (2.2) is an obvious consequence of it. □

As an example, let us consider f = (1, 8, 5, 2, 7, 4, 4, 8, 1) ∈ PF_{9} and evaluate σ = P (f). Since there are no repeated elements in f before i = 7, σ(i) = f(i) for i ≤ 6. Then σ(7) ≥ 4 must be different from 4 and from 5 (these are “spaces already occupied”). Hence, σ(7) = 6. In the same way, σ(8) ≥ 8, σ(8) ≠ 8 and hence σ(8) = 9, and, finally, σ(9) = 2. Therefore, P (f) = σ = (1, 8, 5, 2, 7, 4, 6, 9, 3) and Π(f) = σ^{−1} = (1, 4, 9, 6, 3, 7, 5, 2, 8). Finally, dp(P (f)) = (0, 0, 0, 1, 0, 0, 2, 5, 2) and dp(f) = (0, 0, 0, 1, 0, 0, 0, 4, 0).

3. Rooted labeled forests

A rooted (labeled) forest is a labeled graph where the connected components are trees with a distinguished vertex or 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 [1, Chapter 19], where four very elegant proofs can be found). See Figure 1, below. Here, we consider only labeled trees with vertices 1, 2, …, 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 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 number of inversions of k. In the tree of Figure 1(a), the index of any vertex k is exactly inv_{T} (k). G. Kreweras, in [6], 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^{1}. Our bijection does this as well. Consequently, it can be seen as an answer to [9, Exercise 4], where a direct bijection with this property is asked for.

A tree with no inversions is said to be decreasing. Let, for σ = (a_{1}, …, a_{n}) ∈ S_{n}, \overline{σ} = (a_{1}, …, a_{n}, n + 1), and let T = ϕ(σ) 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{σ}) of a_{i}. Let, for example, σ be (1, 8, 5, 2, 7, 4, 6, 9, 3); then 1 is connected with 4 since 4 > 1 and 2 = σ_{4} and 1 = σ_{1}. Hence, a natural way to represent this graph can be obtained as follows: take α = \overline{σ} ^{−1} ∈ S_{n+1} and, from left to right, just connect each vertex to the next greater vertex (possibly n + 1). In the same example,

α = (1, 4, 9, 6, 3, 7, 5, 2, 8, 10), and T = 1 4 9 6 3 7 5 2 8 10 . We say that T is represented linearly. In Figure 1(b) the same tree is represented as usual. Note that T is decreasing, by definition. It is well known that ϕ is a bijection (cf. for example [10, page 25]). In fact, we will prove it here in Lemma 3.2 below, since we will use an explicit form of the inverse. Note that ϕ is a bijection between S_{n} ⊂ PF_{n}, the set of functions with zero probes, and the set of labeled trees with zero inversions. Our bijection (which we call ϕ as well) extends ϕ in such a way that the images of all elements of P^{−1}(σ) are (special) relabelings of ϕ(σ).

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

Definition 3.1. Given any tree T, consider the depth-first search algorithm that starts with vertex n + 1 and at each step goes to the least adjacent vertex not yet visited, if any, or else it backtracks^{2}. If v_{j} is the j-th vertex visited (for the first time) by the search, define the permutation of T by:

p(T) := (v_{n+1}, v_{n}, …, v_{1} = n + 1).

Hence, the elements of p(T) are in postorder.

We say that a vertex k follows the vertex i in T, k ≠ 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 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 depth of a vertex i in T is the number dt_{T} (i) of descendants of i and the depth of T is the vector dt(T) = (dt_{T} (1), dt_{T} (2), …, dt_{T} (n)).

1In fact, Kreweras works with what he calls “suites majeures de portée n”, that can be seen as the functions g : [n] → [n] such that f(i) = n + 1 − g(i) defines a parking function.

2See [4] for related constructions.

5 ^{0} 8 ^{0} 6 ^{0} 3 ^{2} 2 ^{0}  7 ^{1} 4 ^{0} 9 ^{0} 1 ^{2}  10  ^{1^{10}4^{9} 9^{8} 6^{7} 3^{6} 7^{5} 5^{4} 2^{3}  8^{2}  ^{1}10}

\begin{aligned}(a) & 5 8 6 3 2 7 4 9 1 10 = \\ & ϕ(1, 8, 5, 2, 7, 4, 4, 8, 1) \end{aligned}  \begin{aligned}(b) & 1 4 9 6 3 7 5 2 8 10 = \\ & ϕ(1, 8, 5, 2, 7, 4, 6, 9, 3) \end{aligned}

Figure 1. The number of inversions of each vertex appears as an index in (a), whereas in (b) the indices show the order in which depth-first search on the tree visits the vertices.

In the tree T of Figure 1(a), for example, after starting with 10, 1 is visited, then 9, then 4, 7, 2, 3, 6, 8 and finally 5. Hence p(T) = (5, 8, 6, 3, 2, 7, 4, 9, 1, 10) and, for example, fol_{T} (3) = {6, 8}, whereas desc_{T} (3) = ∅. In the same tree, dt(T) = (0, 0, 0, 0, 0, 0, 4, 0, 1).

Figure 1(b) gives us an example that will be generalized in Lemma 3.2 below: if σ = (1, 8, 5, 2, 7, 4, 6, 9, 3) ∈ S_{9}, then (1, 4, 9, 6, 3, 7, 5, 2, 8) = σ^{−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 σ (cf. Definition 2.4) and 2 is the ninth component. More precisely, whereas {6, 3, 7, 5, 2} = desc_{T} (8), σ({6, 3, 7, 5, 2}) = {4, 5, 6, 7, 8}, σ(8) = 9 and {4, 5, 6, 7, 8, 9} is the interval of form {k, k +1, …, 9} contained in σ([8]) that is maximal for this property, which means dp_{σ}(8) = 5.

In fact, this idea is the crux of our construction. It is implicit in [7], but we believe it was unobserved before. We formalize it in Lemma 3.3. Before, we recall some properties of this construction.

Let α := p(T) =: (a_{1}, a_{2}, …, a_{n+1} = n + 1).

• Suppose i = a_{j}. By definition, either fol_{T} (i) = ∅ or there exists k < j such that fol_{T} (i) = {a_{k}, a_{k+1}, …, a_{j−1}}. The subgraph induced by this set of vertices is also a tree.

• Given any vertex i = a_{j}, there is a unique k > j such that i is connected to a_{k}. In other words, in α, any vertex is connected to a unique vertex in its right-hand side. The vertex a_{k} is the leftmost (i.e., the last visited) ancestor of i.

• 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 p. Note that, by Lemma 3.2 below, if T = ϕ(σ) for some σ ∈ S_{n} this is the linear representation already described.

• If fol _{T} (i) = {a_{l}, a_{l+1}, …, a_{j−1}} and l > 1, then a_{l−1} is precisely the rightmost element connected with some a_{p} with p > j.

• Passing from a vertex to its neighbor on the right in α, 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, …, n + 1. In particular, a tree is decreasing if and only if every vertex that follows a given vertex i is its descendant.

It is now easy to prove Lemma 3.2. Note that S_{n} is the set of parking functions with zero probes, whereas the decreasing trees are the labeled trees with zero inversions.

Lemma 3.2. The map ϕ as defined before maps S_{n} bijectively onto the set of decreasing trees with labels [n + 1]. More precisely,

(3.3)  p (ϕ(σ)) = \overline{σ} ^{−1}  for every σ ∈ S_{n};
(3.4)  T = ϕ (p(T)^{−1})  for every decreasing tree T.

Proof. We prove that ϕ is injective; surjectivity is a consequence of (3.4). We assume that σ ≠ σ′ are two bijections with associated trees T and T′. We assume also that σ(i) ≠ σ′(i) but σ(j) = σ′(j) for i < j < n + 1. Let a = σ(i) and b = σ′(i), and suppose without loss of generality that a < b. Then, in T there exists an edge e = a \overline{σ}(k) with i < k ≤ n + 1. Note that we must have a = σ(l) for some l < i, but since b > a the edge e cannot belong to T′. Hence T ≠ T′.

Statement (3.3) is a consequence of this fact and of (3.4).

For the proof of (3.4), let again α = p(T) = (a_{1}, a_{2}, …, a_{n+1} = n + 1) and i ≤ n + 1 with i = a_{j}. In order to prove the first statement, we prove that the leftmost (in α) 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 ≤ x and y is on the left of m and on the right of i, contrary to the definition of m. □

Lemma 3.3. For every permutation σ ∈ S_{n},

dp(σ) = dt(ϕ(σ)).

Proof. Define, for 1 ≤ i ≤ n, m_{i} := min {k ∈ σ([i]): {k, k + 1, …, σ(i)} ⊂ σ([i])}, and suppose m_{i} > 1. In other words, m_{i} is defined by σ^{−1}(m_{i} − 1) > i and σ^{−1}(k) < i for every m_{i} ≤ k < σ(i). Hence, the set of descendants of i in T = ϕ(σ) is σ^{−1}({m_{i}, m_{i} + 1, …, σ(i)}) \ {i}. □

1^{4}^{9}_{6}_{3}^{7}^{5}^{2} ^{8} ^{10} →  _{6}_{3}^{7}^{5}^{2} ^{8}_{1}^{9}^{4} ^{10}  →  _{6}_{3}^{7}^{5}^{2} ^{8}_{4}^{9}^{1} ^{10}  →  _{7}_{3}^{6}^{5}^{2} ^{8}_{4}^{9}^{1} ^{10}  →  ^{5}_{7}_{6}^{3}^{2} ^{8}_{4}^{9}^{1} ^{10}  →  ^{5}_{8}_{6}^{3}^{2} ^{7}_{4}^{9}^{1} ^{10}

ϕ(1,8,5,2,7,4,6,9,3) ϕ(1,8,5,2,7,4,6,9,2) ϕ(1,8,5,2,7,4,6,9,1) ϕ(1,8,5,2,7,4,5,9,1) ϕ(1,8,5,2,7,4,4,9,1) ϕ(1,8,5,2,7,4,4,8,1)

Figure 2. Rewriting process

Let us now proceed to the definition of ϕ. Let T be a labeled tree and i and k be two vertices such that k ∈ desc_{T} (i), (and hence, k < i). Similar to [2], define π(T; i, k) as the labeled tree that is obtained from T by replacing each label l by π(l), where:

π(l) = \begin{cases}min \{m ∈ desc_{T} (i) ∪ \{i\}: m > l\} & if k ≤ l < i and l ∈ desc_{T} (i); \\ k & if l = i; \\ l & if l ∉ desc_{T} (i) or l < k or l > i. \end{cases}

It is convenient to define also T = π(T; i, i) for every i ∈ [n].

Now, given the parking function f ∈ PF_{n}, let σ = P (f), α = \overline{σ} ^{−1}, T = ϕ(σ) and T_{0} = T. For each i ≤ n, let desc _{T} (i) = {a_{1}^{i} > ⋯ > a_{dp_{σ}(i)}^{i}} be written in decreasing order, and a_{0}^{i} = i. Finally, define recursively

T_{i} = π (T_{i−1}; i, a_{σ(i)−f(i)}^{i}) , 1 ≤ i ≤ n,

and ϕ(f) = T_{n}.

Note that if p_{i} := σ(i) − f(i) > 0 then the permutation that changes the labels of T_{i−1} into the labels of T_{i} is the cycle γ_{i} = (a_{p_{i}}^{i} a_{p_{i}−1}^{i} ⋯ a_{2}^{i} a_{1}^{i} i) = (a_{p_{i}}^{i} a_{p_{i}−1}^{i}) ⋯ (a_{2}^{i} a_{1}^{i}) (a_{1}^{i} i). Let once more π be their product, ordered according to i. For example, in Figure 1, the initial T (that is, ϕ(σ)) is the tree represented in (b). The vertices of T are relabeled in ϕ(f) by π = γ_{9} ∘ γ_{8} ∘ γ_{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 1(b) is relabeled 4 in the tree of Figure 1(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 ϕ(f) is the total number of probes of f, Pr(f). More precisely, if this construction is combined with Lemma 3.3, the following result is implied.

Theorem 3.4. For every f ∈ PF_{n},

dp(f) = dt(ϕ(f)) ∘ π.

Remark 3.5. Suppose the tree T′ = Φ(f) is given and T′ is the relabeling by π ∈ S_{n}, also given, of T = Φ(P (f)), as in Figure 3.5 (see Lemma 3.6, below). Then, the easiest way to recover f is as follows: for every i ∈ [n], f(i) = P (f)(i) − inv_{T′}(π(i)) and the P (f)(i)’s are in postorder. Hence, in Figure 3.5, we obtain f(i) by reading the blue index near to the vertex labeled i in (b) and subtracting from it the red index near to the corresponding position in (a).

In fact, by Lemma 3.2, the blue index near to i is P (f)(i). In order to see that

pr(f) = inv_{T′} ∘ π,

5 8 6 3 ^{2} 2  7 ^{1} 491 ^{2}  10  {π \atop ⟵} ^{5^{7} 6^{4} 3^{5} 7^{6} 2^{8}  8^{9} 1^{1}4^{2}9^{3}  10}
(a) T′ = ϕ(1, 8, 5, 2, 7, 4, 4, 8, 1)  (b) T = ϕ(1, 8, 5, 2, 7, 4, 6, 9, 3)

Figure 3. In (b) the indices show postorder.

note that pr(f) = dp(P (f))−dp(f) is equal to dt(ϕ(P (f)))−dt(ϕ(f))∘π by Theorem 3.4, and so is the difference between the number of followers and descendants of π(i) in T′.

If we replace our tree T′ = π(T) by the tree T of [7], then our T is Shin’s D, the red labels in (a) form Shin’s tree I and the blue labels in (b) form C. Proceeding as indicated above, we would then obtain Shin’s related parking function instead of f. On the other hand, our construction of T′ = Φ(f) and Shin’s corresponding construction are both based on T = Φ(P (f)), and both proceed by relabeling T, although by two different processes.

Note that, in the previous example, we have as well π = γ_{8} ∘ γ_{7} ∘ γ_{9} (cf. Figure 2), since desc_{T} (9) ∩ desc_{T} (8) = ∅ and desc_{T} (7) ⊂ 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 ∈ fol_{T} (w), and then fol _{T} (v) ⊂ fol _{T} (w). In other words, we may take the sets of followers of the vertices ordered reversely to any depth-first search, independently of the way siblings (adjacent vertices following the same vertex) are ordered. We will use this in the proof of Lemma 3.6 below, where we assume, for the purpose of recovering the order of the transpositions in π, that p(f) = π ∘ p(σ).

We may write f = σ − e_{k_{1}} − ⋯ − e_{k_{Pr(f)}}, where e_{k} = (0, …, 0, 1, 0, …, 0) as usual (i.e., 1 is the k-th coordinate) and k_{1} ≤ ⋯ ≤ k_{Pr(f)}^{3}. The sequence of trees obtained by changing the labels transposition by transposition is then clearly ϕ(σ−e_{k_{1}}), ϕ(σ−e_{k_{1}}−e_{k_{2}}), etc. (which, in particular, by Lemma 2.5, are images by ϕ 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}) in a certain intermediate tree, but not necessarily in the final one. As an example, note that in Figure 1 the transposition (6 7) in (b) gives rise to the inversion (8, 3) in (a), and not to (7, 6). Let us have a closer look at this.

3The order may be different according to the last paragraph. Both ideas are illustrated in Figure 2.

Lemma 3.6. Let f ∈ PF_{n}, p = Pr(f), σ = P (f), T = ϕ(σ), T′ = ϕ(f) be the relabeling of the vertices of T by π ∈ S_{n} and β = p(T′). Suppose that the inversions of T′, of the form (β(a_{k}), β(b_{k})) say, are defined such that

b_{k} > b_{k+1} or
b_{k} = b_{k+1} and β(a_{k}) < β(a_{k+1}).

Then

π^{−1} = (β(a_{1}) β(b_{1})) (β(a_{2}) β(b_{2})) ⋯ (β(a_{p}) β(b_{p})).

Proof. The permutation π has been defined as a product of transpositions, say

π = (c_{1} d_{1}) (c_{2} d_{2}) ⋯ (c_{p} d_{p}) (c_{k} < d_{k} , k ≤ p).

According to the previous remarks, we have p(f) = π ∘ p(σ). We generalize π by considering, for 1 ≤ k ≤ p, π_{k} = (c_{1} d_{1}) (c_{2} d_{2}) ⋯ (c_{k} d_{k}). Note that, in ϕ(f), to the transposition (c_{k} d_{k}) there corresponds the inversion (π_{k}(c_{k}), π_{k}(d_{k})), and note that

(3.5)  (π_{k}(c_{k}) π_{k}(d_{k})) = π_{k} (c_{k} d_{k}) π_{k}^{−1}.

Finally, note that, if γ_{i} = (c_{j} d_{j}) ⋯ (c_{k} d_{k}) for some j < k, then, by definition: • d_{k} = i and c_{l}, d_{l} ≠ i for l > k. Hence, π_{k}(i) = π(i).

• d_{l} = c_{l+1} for j ≤ l < k. Hence, π_{k}(d_{k}) = π_{k−1}(c_{k}) = π_{k−1}(d_{k−1}). Continuing in this way, we obtain that π_{l}(d_{l}) = π(i) for every j ≤ l ≤ k.

• c_{l−1} < c_{l} for every j < l ≤ k; γ_{i}(c_{i−1}) = c_{i} < d_{i} = γ_{i}(c_{i}) and every γ_{m} with m > i

either increases d_{i} or both c_{i} and d_{i}, keeping its order. In short, we have proved that:

β(a_{l}) = π_{l}(c_{l}) and β(b_{l}) = π_{l}(d_{l}) , for 1 ≤ l ≤ p;

hence, by (3.5),

(β(a_{1}) β(b_{1})) ⋯ (β(a_{p}) β(b_{p})) = π_{1}(c_{1} d_{1})π_{1}^{−1}π_{2}(c_{2} d_{2})π_{2}^{−1}π_{3}(c_{3} d_{3})π_{3}^{−1} ⋯ π_{p}(c_{p} d_{p})π_{p}^{−1}
= π_{1}^{−1}π_{2}(c_{2} d_{2})π_{2}^{−1}π_{3}(c_{3} d_{3})π_{3}^{−1} ⋯ π_{p}(c_{p} d_{p})π_{p}^{−1}
= π_{2}^{−1}π_{3}(c_{3} d_{3})π_{3}^{−1} ⋯ π_{p}(c_{p} d_{p})π_{p}^{−1}
= π_{p}^{−1}
= π^{−1}.
□

As an example, note that in the tree of Figure 1(a), since β = (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 π^{−1} = (4 1) (9 1) (8 7) (6 3) (8 3) = (9, 2, 7, 1, 5, 3, 8, 6, 4).

Put together, Lemma 2.3 and Lemma 3.6 imply that ϕ is a bijection. In fact, suppose ϕ(f) = ϕ(g) for two parking functions f and g of size n. By Lemma 3.6, we then get ϕ(P (f)) = ϕ(P (g)) and hence P (f) = P (g). But, by definition of ϕ, we must have P (f) − f = P (g) − g, and hence f = g.

4. Acknowledgements

We thank the referee for slightly changing our definition of inversion, which has led to Remark 3.5. The work of the first author was supported, in part, by Fundação para a Ciência e a Tecnologia (FCT) through the Centro de Matemática da Universidade do Porto (CMUP).

References

[1] M. Aigner and G. Ziegler, Proofs from THE BOOK (2nd ed.). Berlin, New York: Springer-Verlag (2002) (4-th edition in 2009).

[2] J. S. Beissinger, “On external activity and inversions in trees”, J. Combin. Theory Ser. B 33 (1982), 87–92.

[3] D. Foata and J. Riordan, “Mappings of acyclic and parking functions”, Aequationes Math. 10 (1974), 10–22.

[4] I. Gessel and D. L. Wang, “Depth-first search as a combinatorial correspondence”, J. Combinatorial Theory Ser. A 26 (1979), 308–313.

[5] A. G. Konheim and B. Weiss, “An occupancy discipline and applications”, SIAM J. Appl. Math. 14 (1966), 1266–1274.

[6] G. Kreweras, “Une famille de polynômes ayant plusieurs propriétés énumeratives”, Per. Math. Hung. 11 (1980), 309–320.

[7] H. Shin, “A new bijection between forests and parking functions”, arχiv: 0810.0427v2 [math.CO].

See also: www.emis.de/journals/SLC/wpapers/s61vortrag/shin.pdf

[8] H. Shin and J. Zeng, “A further correspondence between (b c; \overline{b})-parking functions and (b c; \overline{b})- forests”, DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 793–804.

[9] R. P. Stanley, “An introduction to Hyperplane Arrangements”, in Geometric Combinatorics (E. Miller, V. Reiner, and B. Sturmfels, eds.), IAS/Park City Mathematics Series, vol.13, American Mathematical Society, Providence, RI (2007), 389–496.

[10] R. P. Stanley, “Enumerative Combinatorics,” vol. I, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, New York, 7th printing, (2006).

CMUP and Departamento de Matemática, Fac. de Ciências, Universidade do Porto

E-mail address: agoliv@fc.up.pt

Combinatoire et Optimisation, CNRS and Université Pierre et Marie Curie (Paris 6)

E-mail address: mlv@math.jussieu.fr