CODING PARKING FUNCTIONS BY PAIRS OF PERMUTATIONS

YURII BURMAN AND MICHAEL SHAPIRO

Abstract. We introduce a new class of admissible pairs of triangular sequences and prove an bijection between the set of admissible pairs of triangular sequences of length n and the set of parking functions of length n.

1. Introduction

A sequence p = (p_{0}, …, p_{n−1}) is called a parking function if it is majorated by a permutation, that is, there exists a permutation (one-to-one mapping) σ of the set {0, 1, …, n − 1} such that p_{0} ≤ σ(0), …, p_{n−1} ≤ σ(n − 1). The sequence p = (p_{0}, …, p_{n−1}) is a parking function if and only if for every s = 0, …, n − 1 it contains at least s + 1 terms p_{i} satisfying the inequality p_{i} ≤ s. The set of parking functions with n terms will be denoted PF_{n}.

Parking functions are a popular subject in combinatorics. Taking their name from a problem of car parking along a one-way street (see [1]), they attracted attention after the following theorem had been proved:

Theorem 1 (Kreweras, [3], 1977). For every k, 0 ≤ k ≤ n(n − 1)/2, there exists a one-to-one correspondence κ_{n} between the set PF_{n} and the set of T_{n} trees with n + 1 numbered vertices such that if p_{0} + ⋯ + p_{n} = u then the tree D = κ_{n}(p) has exactly n(n − 1)/2 − u inversions. In particular, the total number of parking functions is equal to the total number of trees, that is, (n + 1)^{n−1}.

A tree here means a connected graph without cycles, whose vertices are numbered 0, 1, …, n. We say that a pair of vertices (i, j) forms an inversion if i < j but the path joining the vertex i with the vertex 0 passes through j. The paper [3] contains an explicit construction of the correspondence involved. (Note that Kreweras’s suites majeures differ formally from parking functions we have defined: (q_{0}, …, q_{n−1}) is a suite majeure if (n − q_{0}, …, n − q_{n−1}) is a parking function.)

The permutation group Σ_{n} acts in a natural way on the set PF_{n}. Consider a vector space of dimension (n+1)^{n−1} with the basis e_{p} whose elements are numbered by the parking functions p ∈ PF_{n}. This space carries a natural linear representation of Σ_{n}; denote this representation P_{n}. Define a weight w(p) of the parking function p as w(p) = n(n−1)/2−(p_{0} +⋯+p_{n−1}). The permutation group action preserves the weight, and therefore P_{n} becomes a graded representation.

Another instance of parking functions (and the main inspiration of this paper) is the following theorem conjectured first in [1] and proved later in a series of works by the same author, see [2] and references therein. Consider a natural action of the permutation group Σ_{n} on the direct product V_{n} = (ℂ^{2})^{n}. Let ℂ[V_{n}] be the ring of polynomials on V_{n}, and J_{n} ⊂ ℂ[V_{n}] be the ideal generated by Σ_{n}-invariant polynomials of positive degree. The factor R_{n} = ℂ[V_{n}]/J_{n} is called a module of diagonal harmonics. It is a doubly-graded module: if one denotes arguments of the polynomial f ∈ ℂ[V_{n}] as x_{1}, y_{1}, …, x_{n}, y_{n} (x_{i}, y_{i} being coordinates in the i-th copy of ℂ^{2}) then the gradings are the total degree of f with respect to all x_{i} and its total degree with respect to all y_{i}. Either grading makes R_{n} a graded representation of Σ_{n}.

Theorem 2 (Haiman, [2], 2000). R_{n} is isomorphic, as a graded representation of Σ_{n}, to the representation P_{n} tensored by the sign representation ϵ_{n}.

In particular, the dimension of the homogeneous component of R_{n} of the grading k is equal to the number of parking functions p with p_{0}+⋯+p_{n−1} = n(n−1)/2−k, or to the number of trees with n + 1 numbered vertex having exactly k inversions.

Note that in fact the representation R_{n} is bi-graded, but Theorem 2 ignores the second grading. There are explicit formulas for dimensions of the bihomogeneous components of R_{n} (see [2]) but they have nothing to do with trees and parking functions. Nevertheless, the theorem suggests that the representation P_{n} also can be made doubly graded — that is, the sets of parking functions and trees should carry the second grading, yet unknown, different from the weight defined above.

The aim of our project was to find an elementary approach to the above bigrading. Unfortunatelly we failed to define the second grading. This paper is a description of steps made in this direction, some of them being rigorously proved statements, and some, numerical observations. We start at sections 2 and 3 with a combinatorial construction encoding parking functions by pairs of permutations satisfying some admissibility condition. The last section contains some data shading light on the relation of this construction to Theorem 2 above.

The authors thank Mark Haiman and Ira Gessel for useful discussions. The first author was supported by Gustafsson foundation during his stay at Royal Institute of Technology, where this work started. He also wishes to thank INTAS whose fellowship No YS 2001-1/81 he used in a later stage of the work. The second author wants to express his gratetude to Max Planck Institute in Bonn, where this paper was accomplished.

2. Main definitions

Throughout this paper we use the following conventions:

1. All the numbers mentioned are integers, unless otherwise stated.

2. All sequences are indexed starting from zero; giving numbers to elements of a finite set, we also start from zero.

2.1. Permutations and triangular sequences. We call a sequence a = (a_{0}, …, a_{n−1}) triangular if an inequality 0 ≤ a_{i} ≤ i is satisfied for all i = 0, …, n − 1. Denote A_{n} the set of all triangular sequences of length n. Apparently, the cardinality of A_{n} is n!; this allows to put it into a one-to-one correspondence with the set Σ_{n} of all permutations of the set {0, …, n − 1}.

There are several explicit constructions for this correspondence. We will usually use the correspondence α_{n} : A_{n} → Σ_{n} defined inductively as follows. If n = 1, there is only one triangular sequence, only one permutation, and only one correspondence α_{1} between them. Now let α_{n−1} be defined and let σ′ = (σ′(0), …, σ′(n − 2)) = α_{n−1}(a_{0}, …, a_{n−2}). Take the number n − 1 and insert it into the line (σ′(0), …, σ′(n − 2)) between σ′(n − 2 − a_{n}) and σ′(n − 1 − a_{n}); the resulting sequence will represent the permutation σ = α_{n}(a_{0}, …, a_{n−1}). Formally,

σ(i) = \begin{cases}σ′(i), & if i ≤ n − 2 − a_{n}, \\ n − 1, & if i = n − 1 − a_{n}, \\ σ′(i − 1), & if i ≥ n − a_{n}. \end{cases}

It is easy to see that α_{n} is indeed a one-to-one correspondence. The inverse mapping can be described by the following rule: if a = α_{n}^{−1}(σ) then a_{i} equals the number of j > i such that σ(j) < σ(i). A pair (i, j) such that j > i but σ(j) < σ(i) is called an inversion of the permutation σ; the total number of inversions of the permutation α_{n}(a) is thus equal to a_{0} + ⋯ + a_{n−1}.

2.2. Triangular sequences and parking functions. Consider a pair of triangular sequences k = (k_{0}, …, k_{n−1}), l = (l_{0}, …, l_{n−1}) ∈ A_{n} such that l_{s} ≤ k_{s} for all s = 0, …, n − 1. Define a sequence β_{n}(k, l) = p = (p_{0}, …, p_{n−1}) by induction as follows. Let β_{n−1} be defined, and (p′_{0}, …, p′_{n−1}) = β_{n−1}(k′, l′) where k′ = (k_{0}, …, k_{n−2}), l′ = (l_{0}, …, l_{n−2}) ∈ A_{n−2}. Now take the number k_{n−1} and insert it into the line (p′_{0}, …, p′_{n−1}) between positions number k_{n−1} − l_{n−1} − 1 and k_{n−1} − l_{n−1}; the resulting sequence will be β_{n}(k, l). Formally, if p = β_{n}(k, l) then

p_{i} = \begin{cases}p′_{i}, & if i ≤ k_{n−1} − l_{n−1} − 1, \\ k_{n−1}, & if i = k_{n−1} − l_{n−1}, \\ p′_{i−1}, & if i ≥ k_{n−1} − l_{n−1} + 1. \end{cases}

It is easy to see that β_{n}(k, l) is a parking function for all k, l.

An equivalent description of this algorithm is as follows: let us have, first, n empty positions numbered from 0 to n − 1, left to right. Take k_{n−1} and place it to the position number k_{n−1} − l_{n−1}. Then re-number empty positions using numbers from 0 to n − 2, skipping the occupied position. Then take k_{n−2} and place it to the empty position whose (new) number is k_{n−2} − l_{n−2}. Again, re-number the empty positions using numbers from 0 to n − 3, etc.

3. Admissible pairs of triangular sequences

Let, again, k = (k_{0}, …, k_{n−1}) and l = (l_{0}, …, l_{n−1}) be triangular sequences. We say that a pair of integers (i, j), 0 ≤ i < j ≤ n − 1 forms an irregular position for a pair k, l ∈ A_{n} if l_{i} > l_{j} and k_{j} ≤ i. The pair k, l ∈ A_{n} is called admissible if l_{s} ≤ k_{s} for all s = 0, …, n − 1, and no irregular positions exist. Denote Adm_{n} ⊂ A_{n} × A_{n} the set of all admissible pairs.

The next statement is the main proved result of the paper.

Theorem 3. The mapping β_{n} provides a one-to-one correspondence between the sets Adm_{n} and PF_{n}.

Corollary. There are (n + 1)^{n−1} admissible pairs of triangular sequences.

To prove Theorem 3 we need two lemmas. Let p ∈ PF_{n} be a parking function, and r be a number such that p_{r} is the maximal term of the sequence p; if there are several such terms, take the smallest r possible. Let (k, l) be an admissible pair such that p = β_{n}(k, l), and let s be a number such that k_{s} = p_{r} is sent to position r by the mapping β_{n} (in other words, s = σ_{r} where σ = α_{n}(k − l), cf. Section 2).

Consider the set U of all i, p_{r} ≤ i ≤ n − 1, such that for all j, p_{r} ≤ j ≤ i, the inequality l_{j} ≤ (n − 1 − r) + (p_{r} − i) takes place.

Lemma 1. s = max U.

Proof. By the choice of s, we have k_{j} ≤ k_{s} = p_{r} for every j > s. Now if l_{j} < l_{s} then k_{j} ≤ k_{s} ≤ s, and (s, j) is an irregular position. For an admissible pair (k, l) no such positions exist, and so l_{j} ≥ l_{s} for all j > s. This inequality means that the mapping β_{n} sends every term k_{j}, j > s, to a position left of (less than) r, and therefore r = (n−1−s)+(k_{s}−l_{s}) = (n−1−s)+(p_{r}−l_{s}). So, l_{s} = (n−1−r)+(p_{r}−s).

Now let j be such that p_{r} ≤ j ≤ s − 1. Again, we have l_{j} ≤ l_{s}, because (k, l) is an admissible pair. Therefore, l_{j} ≤ (n − 1 − r) + (p_{r} − s) which means that s ∈ U.

Suppose there exists t ∈ U such that t > s. Then p_{r} ≤ s ≤ t − 1, and there holds the inequality l_{s} = (n − 1 − r) + p_{r} − s ≤ (n − 1 − r) + p_{r} − t — a contradiction.

Now delete the r-th element of the parking function p obtaining a sequence p′. Also, delete the s-th elements from sequences k and l resulting in k′ and l′, respectively.

Lemma 2. 1. The sequence p′ is a parking function: p′ ∈ PF_{n−1}.

2. The sequences k′ and l′ are triangular and form an admissible pair: (k′, l′) ∈ Adm_{n−1}.

3. β_{n}(k′, l′) = p′.

Proof. 1. Let σ be a permutation of the set {0, …, n − 1} majorating the sequence p. Since p_{r} is the maximal term of p, then without loss of generality σ(r) = n − 1. Deleting the r-th term from σ one obtains a permutation σ′ of the set {0, …, n−2} majorating p′.

2. If j < s then k′_{j} = k_{j} ≤ j. As we noticed in the proof of Lemma 1, k_{j} ≤ k_{s} for all j ≥ s, and therefore k′_{j} = k_{j−1} ≤ s ≤ j for such j, too. Thus, the sequence k′ is triangular. The inequalities l′_{i} ≤ k′_{i} imply that the sequence l′ is also triangular. Every irregular position (i, j) for (k′, l′) would be irregular for (k, l), too, and thus (k′, l′) ∈ Adm_{n−1}.

3. Evident.

Proof of Theorem 3. 1. Existence — prove that for every parking function p ∈ PF_{n} there exists an admissible pair (k, l) ∈ Adm_{n} such that p = β_{n}(k, l). Use the induction by n, the base n = 1 being evident. To make the induction step, define the number r and the parking function p′ ∈ PF_{n−1} as described in the beginning of this section. By induction hypothesis, there exists a pair (k′, l′) ∈ Adm_{n−1} such that p′ = β_{n−1}(k′, l′). Let U be the set of all i, 0 ≤ i ≤ n − 1, such that for all j, p_{r} ≤ j ≤ i−1, the inequality l′_{j} ≤ n−1−r+p_{r} −i takes place. Define the number s as the maximal element of U, assuming s = 0 if U = ∅. Now insert the terms k_{s} = p_{r} and l_{s} = (n − 1 − r) + p_{r} − s into k′ and l′ getting k and l, respectively. We are to prove now that (k, l) is an admissible pair of triangular sequences satisfying β_{n}(k, l) = p.

By the choice of s, the inequality k_{s} = p_{r} ≤ s holds, which means that the sequence k is triangular. Prove that l_{s} ≤ k_{s} (triangularity of l would follow). This inequality is equivalent to n − 1 − r ≤ s, so if n − 1 − r ≤ p_{r} then it follows from the previous one.

Suppose n − 1 − r > p_{r}. Then for every j, p_{r} ≤ j ≤ n − 1 − r, one has l′_{j} ≤ k′_{j} < p_{r} + 1 = (n − 1 − r) + p_{r} − (n − 2 − r). This means that the number n − 1 − r belongs to the set U, and therefore, again, n − 1 − r ≤ s. So, l_{s} ≤ k_{s} and l is triangular.

Prove now that β_{n}(k, l) = p. Show first that l_{j} ≥ l_{s} for all j > s. Suppose that l_{j} < l_{s} for some j > s. By the induction hypothesis, (k′, l′) is a admissible pair, and therefore (s, j − 1) is not an irregular position for it. The inequality k′_{j−1} = k_{j} ≥ s + 1 > p_{r} is impossible, so, l_{s+1} = l′_{s} ≤ l′_{j−1} = l_{j}, and therefore l_{s+1} < l_{s} = (n − 1 − r) + p_{r} − s, or l′_{s} ≤ (n − 1 − r) + p_{r} − (s + 1). By the choice of s, the number s + 1 is not an element of the set U. This means that there exists t, p_{r} ≤ t < s, such that l_{t} > l_{s+1}. The inequality k′_{s} ≥ t + 1 > p_{r} is impossible, so in this case (t − 1, s) is an irregular position for (k′, l′) — a contradiction.

So, l_{j} ≥ l_{s} for all j > s. Since k_{s} = p_{r} is the maximal term of the sequence p, we have also k_{j} ≤ k_{s} all j > s. This implies that the mapping β_{n} sends all the k_{j} with j > s to positions left of r, and therefore k_{s} = p_{r} is sent to position r. It follows now from the induction hypothesis (p′ = β_{n−1}(k′, l′)) that p = β_{n}(k, l).

We proved already that the sequences k and l are triangular, and l_{i} ≤ k_{i} for all i = 0, …, n − 1. Prove that there are no irregular positions for k, l and therefore (k, l) ∈ Adm_{n}. Let (u, v) be such a position; consider several cases:

Case 1. u < v < s. Then (u, v) is irregular for (k′, l′), too — a contradiction. The same argument applies to cases u < s < v (the position (u, v − 1)) and s < u < v (the position (u − 1, v − 1)).

Case 2. u = s < v. This is impossible because, as we proved earlier, l_{v} ≤ l_{s}. Case 3. u < v = s. This means that p_{r} ≤ u and thus l′_{u} = l_{u} > l_{s} = (n − 1 −

r) + p_{r} − s, which is impossible by the definition of the set U.

2. Uniqueness. Again, use induction by n, the base n = 1 being evident. Let β_{n}(k^{(1)}, l^{(1)}) = β_{n}(k^{(2)}, l^{(2)}) = p ∈ PF_{n} where (k^{(1)}, l^{(1)}) and (k^{(2)}, l^{(2)}) are admissible pairs. Choose the number r as above, and let s_{1}, s_{2} be numbers such that the mapping β_{n} applied to pairs (k^{(1)}, l^{(1)}) and (k^{(2)}, l^{(2)}) sends k_{s_{1}}^{(1)} and k_{s_{2}}^{(2)}, respectively, to position r. Let k̃^{(1)} and l̃^{(1)} be sequences obtained by deletion of the s_{1}-th term from k^{(1)} and l^{(1)}, and similarly k̃^{(2)} and l̃^{(2)}. By Lemma 2, β_{n−1}(k^{(1)}, l^{(1)}) = β_{n−1}(k^{(2)}, l^{(2)}), and by the induction hypothesis, k̃^{(1)} = k̃^{(2)}, l̃^{(1)} = l̃^{(2)}.

The pair (k^{(1)}, l^{(1)}) is admissible, and k_{i}^{(1)} ≤ k_{s_{1}}^{(1)} for all i. It implies that l_{j}^{(1)} ≥ l_{s_{1}}^{(1)} for all j > s_{1} and l_{j}^{(1)} ≤ l_{s_{1}}^{(1)} for all j, p_{r} ≤ j ≤ s_{1} − 1. The same is true for l^{(2)}. As we know, the sequences l^{(1)} and l^{(2)} become the same after deletion of the s_{1}-th and the s_{2}-th terms, respectively. Hence, if l_{s_{1}}^{(1)} > l_{s_{2}}^{(2)} then s_{1} > s_{2}, and vice versa.

On the other hand, the mapping β_{n} sends all the k_{j}^{(1)} with j > s_{1} to positions left of r, and therefore r = (n − 1 − s_{1}) + (p_{r} − l_{s_{1}}^{(1)}). A similar equation is true for l^{(2)}, hence, l_{s_{1}}^{(1)} + s_{1} = l_{s_{2}}^{(2)} + s_{2}. So, s_{1} = s_{2} and l_{s_{1}}^{(1)} = l_{s_{2}}^{(2)} — uniqueness is proved.

4. Admissible pairs and diagonal harmonics

Here we present some relation between the construction of Theorem 3 and the module R_{n} of diagonal harmonics described in Section 1. Let H_{u,v} be the bihomogeneous component of the module R_{n} of bi-degree (u, v); denote h_{u,v} its dimension.

Define now the four sets Y_{0}, Y_{1}, Y_{2}, Y_{3} ⊂ A_{n} of triangular sequences as follows.

0. The set Y_{0} consists of only one sequence, namely (0, 0, …, 0).

1. The set Y_{1} consists of sequences (l_{0}, …, l_{n−1}) such that l_{0} = ⋯ = l_{n−2} = 0 and l_{n−1} ≥ 1.

2. The set Y_{2} consists of sequences (l_{0}, …, l_{n−1}) such that l_{0} = ⋯ = l_{n−3} = 0 and l_{n−1} ≥ l_{n−2} ≥ 1.

3. Y_{3} is a union of two sets, Y′_{3} and Y′′_{3}. The set Y′_{3} consists of sequences (l_{0}, …, l_{n−1}) such that l_{0} = ⋯ = l_{n−3} = 0 and 1 ≤ l_{n−2} > l_{n−1}. The set Y′′_{3} consists of sequences (l_{0}, …, l_{n−1}) such that l_{0} = ⋯ = l_{n−4} = 0 and 1 ≤ l_{n−3} ≤ l_{n−2} ≤ l_{n−1} ≤ n − 2 (note an additional inequality at the end; triangularity requires only l_{n−1} ≤ n − 1).

Numerical computations made for all n ≤ 7 (using tables of h_{u,v} taken from [1]) give the following observation:

For all u and v = 0, 1, 2, 3 and all n ≤ 7 the dimension h_{u,v} is equal to the number of admissible pairs (k, l) such that k_{0} + ⋯ + k_{n−1} = n(n − 1)/2 − u and l ∈ Y_{v}.

Thus it can be conjectured that there exists a splitting of the set A_{n} into a disjoint union: A_{n} = ⨆_{v=0}^{n(n−1)/2} Y_{v} such that the statement above holds for all u, v (and all n). The authors, though, know neither a construction of Y_{v} nor a proof of the conjecture above for small v.

Besides the numerical observations for n ≤ 7 there are some more facts supporting the conjecture.

1. Let S ⊂ ℂ[x_{1}, …, x_{n}] be the ideal generated by symmetrical polynomials of positive degree. Apparently, ℂ[x_{1}, …, x_{n}]/S is a graded module isomorphic to ⨁_{u} H_{u,0}. As it is well known, the dimension h_{u,0} of its component of gradung u is equal to the number of permutations having exactly u inversions. On the other hand, for v = 0 we have l = (0, 0, …, 0), and the admissibility condition does not impose any limitations on k. The results of Section 2 now imply that the observation above is true for v = 0 and all n.

2. Apparently, h_{u,v} = h_{v,u}, and therefore the dimension h_{0,v} is equal to the number of permutations with v inversions. The conjecture above implies that h_{0,v} equals to the number of admissible pairs (k, l) such that k_{0}+⋯+k_{n−1} = n(n−1)/2 and l ∈ Y_{v}. The first equation holds only if k_{i} = i for all i = 0, …, n − 1. For such k and the pair (k, l) is admissible for every l ∈ A_{n}. This implies that the number of elements in Y_{v} should be equal to the number of permutations with v inversions. It is easy to check that this is true for v = 0, 1, 2, 3 (and all n).

3. It can be easily checked that the answer for h_{u,v} given by the conjecture satisfies the condition h_{u,v} = h_{v,u} for all n and all u, v ≤ 3 (that is, in all cases when the conjectural values of both h_{u,v} and h_{v,u} are known).

4. From Theorem 2 we know that ∑_{u} h_{u,v} equals to the number T_{v} of trees with v inversions. The conjecture implies then that the total number of admissible pairs (k, l) with l ∈ Y_{v} should be equal to T_{v}, too. A direct computation (see [3] for a formula for T_{v}) shows that this is true for v = 0, 1, 2, 3 (and all n).

The splitting A_{n} = ⨆_{v=0}^{n(n−1)/2} Y_{v}, if known, would provide the second grading on the sets of admissible pairs. The one-to-one correspondences β_{n} and κ_{n} mentioned in Section 1 would allow then to define the grading on the set of parking functions and on the set of trees. (Recall that the first grading for an admissible pair (k, l) equals n(n − 1)/2 − (k_{0} + ⋯ + k_{n−1}), for a parking function p = β_{n}(k, l) it is w(p) = n(n − 1)/2 − (p_{0} + ⋯ + p_{n−1}) = n(n − 1)/2 − (k_{0} + ⋯ + k_{n−1}), and for a tree D = κ_{n}(p) it is equal, by Theorem 1, to the number of inversions). Thus, by now we are able to describe conjecturally the sets of parking functions and trees of

Figure 1. Such trees probably have grading 1: c ≥ b

grading 0, 1, 2 and 3 using explicit constructions of β_{n} (see Section 2) and κ_{n} (see [3]). To exemplify what happens we give here the answers for gradings 0 and 1:

0. Parking functions of grading zero are triangular sequences: p_{s} ≤ s for all s = 0, 1, …, n − 1. Trees of grading zero are “linear” trees with one branch only.

1. A parking function of grading 1 has exactly one term p_{s} such that p_{s} > s. After deletion of this term the remaining sequence is triangular (i.e. a parking function of grading 0). A tree of grading 1 has exactly one “branching point”

— a vertex A having two children, B and C (all the other non-terminal vertices have one child only). The vertex B is terminal and carries the number b which is less or equal to the length of path joining A with the other terminal vertex (see Figure 1).

References

[1] Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, Journal of Algebraic Combinatorics, 3 (1994), pp. 17–76.

[2] Mark D. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, to appear in Invent. Math.; http://www.arXiv.org:math.AG/0201148.

[3] G. Kreweras, Une famille de polynômes ayant plusieurs propriétés énumeratives, Periodica Mathematica Hungarica, 3, Vol. 11 (1980), pp. 309–320.

(Yu.Burman) Independent University of Moscow, 121002, 11, B.Vlassievsky per., Moscow, Russia

E-mail address: burman@mccme.ru

(M.Shapiro) Michigan State University and Royal Institute of Technology, Stockholm

E-mail address: mshapiro@math.msu.edu