On Some Discrete Statistics of Parking Functions

Ari Cruz, Pamela E. Harris,^{1} Kimberly J. Harry, Jan Kretschmann,

Matt McClinton, Alex Moon, and John O. Museus Department of Mathematical Sciences University of Wisconsin-Milwaukee

Milwaukee, WI 53211

USA

aricruz@arizona.edu
 kjharry@uwm.edu
mcclin33@uwm.edu
jomuseus@uwm.edu
peharris@uwm.edu
kretsc23@uwm.edu
 ajmoon@uwm.edu

Eric Redmon

Department of Mathematics and Statistics Marquette University Milwaukee, WI 53233

USA

eric.redmon@marquette.edu

Abstract

A parking function is a sequence α = (a_{1}, a_{2}, …, a_{n}) ∈ [n]^{n} whose nondecreasing rearrangement β = (b_{1}, b_{2}, …, b_{n}) satisfies b_{i} ≤ i for all 1 ≤ i ≤ n. We study parking functions by their ascents (indices at which a_{i} < a_{i+1}), descents (indices at which a_{i} > a_{i+1}), and ties (indices at which a_{i} = a_{i+1}). By using multiset Eulerian polynomials, we give a generating function for the number of parking functions of length n with i descents. We present a recursive formula for the number of parking functions of length n with descents at a specified subset of [n−1]. We establish the set of parking functions with descent set I and the set of parking functions with descent set J = {n − i : i ∈ I} are in bijection, and hence these sets have the same cardinality. As a special case, we show that the number of parking functions of length n with descents at the first k indices is given by \frac{1}{n} \binom{n}{k}\binom{2n−k}{n−k−1}. We prove this by bijecting to the set of standard Young tableaux of shape ((n − k)^{2}, 1^{k}), which are enumerated by the same formula. We also study peaks and valleys of parking functions, which are indices at which a_{i−1} < a_{i} > a_{i+1} and a_{i−1} > a_{i} < a_{i+1}, respectively. We show that the set of parking functions with no peaks and no ties is enumerated by the Catalan numbers, and the set of parking functions with no valleys and no ties is enumerated by the Fine numbers. We conclude our study by characterizing when a parking function is uniquely determined by its statistic encoding; a word indicating which indices in the parking function are ascents, descents, and ties. We provide open problems throughout.

1P. E. Harris was partially supported by a Karen Uhlenbeck EDGE Fellowship.

1 Introduction

Throughout, we let ℕ = {1, 2, 3, …} and [n] = {1, 2, …, n} for n ∈ ℕ. We define [0] = ∅. Moreover, we let 𝔖_{n} denote the set of permutations of [n] and we use the one-line notation π = π_{1} π_{2} ⋯ π_{n} to denote elements of 𝔖_{n}. If π_{i} > π_{i+1}, then π has a descent at index i; and if π_{i} < π_{i+1}, then π has an ascent at index i. There is a long history of studying and enumerating permutations with certain descents and ascents. This dates back to the work of MacMahon, who established that for a fixed set I, with n ≥ max(I) varying, the number of permutations in S_{n} with descent set I is a polynomial in n [12, Art. 157]. These polynomials are often referred to as descent polynomials, and the coefficients of these polynomials and their roots are studied in the literature [1, 5]. Moreover, there is ample work on generalizing these findings to multipermutations [7, 11, 13]. In the present paper, we are motivated by the work of Schumacher, who enumerated descents, ascents, and ties in parking functions [14].

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \end{matrix}

Figure 1: Graph of the parking function (3, 1, 5, 6, 4, 3, 3, 2, 1) ∈ PF_{9}.

A parking function is a sequence α = (a_{1}, a_{2}, …, a_{n}) ∈ [n]^{n} whose nondecreasing rearrangement β = (b_{1}, b_{2}, …, b_{n}) satisfies b_{i} ≤ i for all 1 ≤ i ≤ n. Parking functions encode the parking preferences for n cars in a queue attempting to park on a one-way street with n parking spots numbered sequentially as follows. For i ∈ [n], car i enters the street and attempts to park in spot a_{i}. If that parking spot is available, car i parks. If the parking spot is occupied, then the car moves forward attempting to park in the first available spot the car encounters. If no such a spot exists, we say the car fails to park. If all cars are able to park under this parking scheme, then α is a parking function.

We let PF_{n} denote the set of parking functions of length n. If α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n}, then α has descents and ascents defined in the analogous way as for permutations, and α has a tie at i if a_{i} = a_{i+1}. In Figure 1, we plot (i, a_{i}) to illustrate the parking function α = (3, 1, 5, 6, 4, 3, 3, 2, 1) ∈ PF_{9} has descents at 1, 4, 5, 7, and 8, ascents at 2 and 3, and a tie at 6. Let des(α) denote the number of descents in α. Schumacher showed that the number of descents among all parking functions of length n is \binom{n}{2}(n + 1)^{n−2} [14, Theorem 10]. Schumacher also showed that the set of parking functions with exactly i ties, denoted PF_{(n,i)}, is enumerated by

|PF_{(n,i)}| = \binom{n − 1}{i}n^{n−1−i}  (1)

[14, Theorem 13] and

∑_{α∈PF_{(n,i)}} des(α) = \frac{n − 1 − i}{2}\binom{n − 1}{i}n^{n−1−i},

[14, Lemma 17]. Let T_{n}(i, j) denote the number of parking functions of length n with i ties and j descents. If i+j ≥ n, then T_{n}(i, j) = 0. Table 2 provides the values of T_{6}(i, j) arranged in a triangular array such that i decreases from top to bottom and j decreases from left to right.^{2} More information on this triangle can be found on the OEIS \underline{A333829}.

For general n, the numbers along the diagonal edges of the triangular array in Figure 2 are the Narayana numbers [14, Theorem 12]

T_{n}(i, 0) = T_{n}(n − 1 − i, i) = \frac{1}{i + 1}\binom{n}{i}\binom{n − 1}{i},

and the row sums are given by (1). General closed formulas for the values of T_{n}(i, j) remain unknown. However, in Section 2, we utilize multiset Eulerian polynomials to give a generating function for the values ∑_{i=0}^{n} T_{n}(i, j). Our first result follows which we prove later in this section.

2Table 2 first appeared in a paper by Schumacher [14, Figure 2], however there was a typographical error for the value T_{6}(3, 1), which should be 260.

j = 0
i = 5  1  j = 1
i = 4  15  15  j = 2
i = 3  50  260  50  j = 3
i = 2  50  1030  1030  50  j = 4
i = 1  15  1240  3970  1240  15  j = 5
i = 0  1  407  3480  3480  407  1

Figure 2: Parking function distribution for n = 6.

Theorem 2. Consider the generating function ∑_{n=1}^{∞} ∑_{j=1}^{n−1} d(n, j)y^{j}x^{n}, where d(n, j) is the number of parking functions in PF_{n} that have j descents, and let PF_{n}^{↑} denote the set of nondecreasing parking functions of length n. Then

∑_{n=1}^{∞} ∑_{α∈PF_{n}} x^{n}y^{des(α)} = ∑_{n=1}^{∞} ∑_{j=1}^{n−1} d(n, j)x^{n}y^{j} = ∑_{n=1}^{∞} ( ∑_{β∈PF_{n}^{↑}} A_{M(β)}(y)) x^{n},

where A_{β}(y) denotes the multiset Eulerian polynomial in y on all multipermutations of β.

Now, we turn our attention to descent sets of parking functions. Given a multiset X of size n with elements in [n], we let W (X) denote the set of multiset permutations of X, written as words w = w_{1} w_{2} ⋯ w_{n}. If I ⊆ [n − 1], then the set of words in W (X) whose descent set is exactly I is denoted

D_{X}(I) = {w ∈ W (X) : Des(w) = I},

where Des(w) = {i ∈ [n − 1] : w_{i} > w_{i+1}}. Let D_{X}(I) = |D_{X}(I)|. Let X be the set of nondecreasing parking functions where each β ∈ PF_{n}^{↑} is considered as a multiset, denoted as M(β). If I ⊆ [n − 1], then define

D(I; n) = {α ∈ PF_{n} : Des(α) = I} = ⨆_{β∈PF_{n}^{↑}} D_{M(β)}(I),

where ⨆ denotes the sets are disjoint. We let d(I; n) = |D(I; n)| = ∑_{β∈PF_{n}^{↑}} d_{M(β)}(I). The set D(∅; n) = PF_{n}^{↑}, and it is known that |PF_{n}^{↑}| = C_{n} = \frac{1}{n+1} \binom{2n}{n}, the nth Catalan number \underline{A000108}. Hence, d(∅; n) = C_{n}.

In Section 3, we consider nonempty descent sets I ⊆ [n − 1] and establish the following results:

• Theorem 16: The set of parking functions with descent set I and the set of parking functions with descent set J = {n − i : i ∈ I} are in bijection, and hence these sets have the same cardinality. Namely, d(I; n) = d(J; n).

• Theorem 18: Let I ⊆ [n − 1] be nonempty, m = max(I), and I^{−} = I \ {m}. Then

d(I; n) = ∑_{β∈PF_{n}^{↑}} ( ∑_{X∈M(β,m)} d_{X}(I^{−})) − d(I^{−}; n),  (2)

where, for β ∈ PF_{n}^{↑}, M(β, m) denotes the collection of multisets consisting of m elements of β.

We remark that Equation (2) is a generalization of Diaz-Lopez, Harris, Insko, Omar, and Sagan’s result [5, Proposition 2.1], which gives a recursion for the number of permutations with a given descent set.

• Proposition 24: Let n ≥ 1 and 0 ≤ k ≤ n − 1. If [k] ⊆ [n − 1], then

d([k]; n) = \frac{1}{n}\binom{n}{k}\binom{2n − k}{n − k − 1}.  (3)

The proof of Proposition 24 is given by a bijection between parking functions of length n with descent set [k] and the set of standard Young tableaux of shape λ = ((n−k)^{2}, 1^{k}). Hence, Equation (3) can be seen as the reindexing d([k]; n) = f(n, n − k − 1).

Other permutation statistics of interest are peaks and valleys. Let π = π_{1} π_{2} ⋯ π_{n} ∈ 𝔖_{n}. Recall that if π_{i−1} < π_{i} and π_{i} > π_{i+1}, then i is a peak of π. Also recall that if π_{i−1} > π_{i} and π_{i} < π_{i+1}, then i is a valley of π. Billey, Burdzy, and Sagan [2] showed that the number of elements in 𝔖_{n} with peaks exactly at I ⊂ [n − 1] is given by p(n)2^{|I|−1}, where p(n) is a polynomial in n whose degree is one less than the maximum of the set I. The polynomial p(n) is called the peak polynomial. It was conjectured that p(n) has a positive integer expansion in a binomial basis centered at the maximum of I and was proven in the affirmative by Diaz-Lopez, Harris, Insko, and Omar [4]. Motivated by these results, we study the set PTPF_{n} consisting of peakless-tieless parking functions of length n, which is the subset of parking functions that have no peaks and no ties.

In Section 4, we prove the following:

• Corollary 31: If n ≥ 1, then |PTPF_{n}| = C_{n}, the nth Catalan number.

• Corollary 32: If PTPF_{n}(i) = {α = (a_{1}, a_{2}, …, a_{n}) ∈ PTPF_{n} : a_{n} = i}, then

|PTPF_{n}(i)| = C_{n,i} ,

where C_{n,i} denotes the ith entry in the nth row of the Catalan triangle \underline{A009766}.

We also prove in Theorem 33 that the number of parking functions of length n with no valleys and no ties is the Fine numbers \underline{A000957}. To those who are used to thinking about permutations, this asymmetry between peaks and valleys may be surprising. It remains an open problem to enumerate all parking functions with a particular peak or valley set.

In Section 5, we study the characterization of parking functions by the locations of their ascents, descents, and ties which we call the statistic encoding of a parking function. We establish the existence of parking functions for every statistic encoding and fully characterize the parking functions that are uniquely identified by their statistic encoding. Remark 1. We present open problems, labeled “Problem n”, throughout the paper.

2 Permutations of multisets

For a multiset M of positive integers, we let m_{i} denote the multiplicity of i in M for all i ∈ [n]. A multipermutation of M is a word π = π_{1} π_{2} ⋯ π_{m} where m = m_{1} + m_{2} + ⋯ + m_{n} and π contains i exactly m_{i} times for all i ∈ [n]. We let 𝔖_{M} denote the set of multipermutations on M. A descent in a multipermutation π is an index j such that π_{j} > π_{j+1}. As before, we let des(π) be the number of descents of π. Then

A_{M}(t) = ∑_{π∈𝔖_{M}} t^{des(π)}  (4)

is the multiset Eulerian polynomial, where 𝔖_{M} is the set of all multipermutations on M. The coefficients of A_{M}(t) count the number of permutations of a given multiset with a certain number of descents and are known as the Simon Newcomb numbers. MacMahon [12, p. 211] showed that A_{M}(t) occurs as the numerator of the following generating function:

\frac{A_{M}(t)}{(1 − t)^{m+1}} = ∑_{ℓ=1}^{∞} ∏_{i=1}^{n} \binom{m_{i} + ℓ}{ℓ}t^{ℓ}.  (5)

Equation (5) allows for the explicit computation of the coefficients as

[t^{k}]A_{M}(t) = |\{π ∈ 𝔖_{M} : des(π) = k\}| = ∑_{ℓ=0}^{k}(−1)^{ℓ}\binom{m + 1}{ℓ} ∏_{i=1}^{n} \binom{m_{i} + k − ℓ}{k − ℓ}, (6)

where [t^{k}]A_{M}(t) denotes the coefficient of t^{k} in A_{M}(t). Using (6), we enumerate descents in parking functions, a superset of permutations, and generalize the results of Schumacher [14].

Now consider the generating function

∑_{n=1}^{∞} ∑_{j=1}^{n−1} d(n, j)x^{n}y^{j},  (7)

where d(n, j) is the number of parking functions in PF_{n} that have j descents. We can now prove Theorem 2 and use it to compute (7). We restate the theorem more succinctly below.

Theorem 2. Let n ∈ ℕ, then the generating function encoding the number of descents throughout all PF_{n} is given by

∑_{n=1}^{∞} ∑_{α∈PF_{n}} x^{n}y^{des(α)} = ∑_{n=1}^{∞} ∑_{j=1}^{n−1} d(n, j)x^{n}y^{j} = ∑_{n=1}^{∞} ( ∑_{β∈PF_{n}^{↑}} A_{M(β)}(y)) x^{n}.

Proof. The result follows from Equation (4). For more details, reference the work by Dillon and Roselle [6, Equation 3.7].

To better understand Theorem 2, we present the case where n = 3.

Example 3. Let n = 3. We have PF_{3}^{↑} = {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3)}. We can partition the set PF_{3} into 𝔖_{3}-orbits of the elements of PF_{3}^{↑}, where 𝔖_{3} acts by permuting preferences:

PF_{3} = 𝔖_{3}(1, 1, 1) ⨆ 𝔖_{3}(1, 1, 2) ⨆ 𝔖_{3}(1, 1, 3) ⨆ 𝔖_{3}(1, 2, 2) ⨆ 𝔖_{3}(1, 2, 3).

We can compute A_{α}(y) for each α ∈ PF_{3}^{↑} using (6). For example, we find

𝔖_{3}(1, 1, 2) = {(1, 1, 2), (1, 2, 1), (2, 1, 1)},

and therefore A_{(1,1,2)}(y) = 2y + 1. Summing over all elements of PF_{3}^{↑}, we retrieve

∑_{α∈PF_{3}^{↑}} A_{α}(y) = y^{2} + 10y + 5.

Similarly, we can recover results from Schumacher [14, Figure 2] (see Figure 2), who provides counts for the numbers of parking functions with i ties and j descents. Setting n = 6, we find

A_{6} = ∑_{α∈PF_{6}^{↑}} A_{α}(y) = y^{5} + 422y^{4} + 4770y^{3} + 8530y^{2} + 2952y + 132.

Each coefficient in A_{6} agrees with the sum of a diagonal of Schumacher’s triangle (from the top left to the bottom right): there is 1 element in PF_{6} with 5 descents, there are 422 elements in PF_{6} with 4 descents, and so on.

Remark 4. Recall that |PF_{n}^{↑}| = C_{n}, where C_{n} is the nth Catalan number. Therefore, partitioning PF_{n} into 𝔖_{n}-orbits means partitioning PF_{n} into C_{n} disjoint subsets. Setting t = 1 in ∑_{α∈PF_{n}^{↑}} A_{α}(t) gives us the known enumeration for parking functions:

(n + 1)^{n−1} = ∑_{α∈PF_{n}^{↑}} A_{α}(1).

Problem 5. Give formulas for T_{n}(i, j) which denotes the number of parking functions of length n with i ties and j descents.

3 Descent sets of parking functions

We now consider parking functions with a specified descent or ascent set. We restate the definition of Des(α) for clarity for the reader and define Asc(α). For α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n}, we let Des(α) = {i ∈ [n − 1] : a_{i} > a_{i−1}} and Asc(α) = {i ∈ [n − 1] : a_{i} < a_{i−1}}. For I ⊆ [n − 1], define

D(I; n) = {α ∈ PF_{n} : Des(α) = I}, and
A(I; n) = {α ∈ PF_{n} : Asc(α) = I},

and denote their cardinalities by d(I; n) = |D(I; n)| and a(I; n) = |A(I; n)|.

Recall that D(∅; n) = PF_{n}^{↑} and that |PF_{n}^{↑}| = C_{n} = \frac{1}{n+1} \binom{2n}{n}, the nth Catalan number \underline{A000108}. Hence, d(∅; n) = C_{n}. For 1 ≤ n ≤ 4, Table 1 provides data on the number of parking functions with a given descent set.

Next, we prove some preliminary results which help establish that the number of parking functions with descents at the indices in I ⊆ [n − 1] is the same as the number of parking functions with descents at indices in J = {n − i : i ∈ I}.

Proposition 6. Let I ⊆ [n − 1] and J = {n − i : i ∈ I}. Then d(I; n) = a(J; n)

Proof. Given α = (α_{1}, α_{2}, …, α_{n}) with Des(α) = I, then (α_{n}, α_{n−1}, …, α_{1}) has Asc(α) = J. This defines a bijection between the sets D(I; n) and A(J; n). Thus, d(I; n) = a(J; n), as claimed.

Next, we define a function used in our subsequent results. To simplify notation, we denote tuples in one-line notation and refer to them as words, i.e., the tuple (w_{1}, w_{2}, …, w_{n}) is written as the word w_{1} w_{2} ⋯ w_{n}.

Definition 7. Let 𝔖_{n}(y) denote the orbit of y ∈ ℕ^{n} under the action of the symmetric group 𝔖_{n} permuting indices. Given x ∈ 𝔖_{n}(y), let arg min(x) denote the set of indices of minimal elements of x and arg max(x) denote the set of indices of maximal elements of x.

Define the map ν : 𝔖_{n}(y) → 𝔖_{n}(y) recursively as follows. For x ∈ 𝔖_{n}(y):

Case 0: If the length of x is 0 or 1, then ν(x) = x.

Case 1: If the length of x is larger than 1 and a ≥ b for all a ∈ arg min(x) and b ∈ arg max(x), then let i = max(arg min(x)) and j = min(arg max(x)). Then

ν(x) = ν(x_{1} x_{2} ⋯ x_{j−1}) x_{i} ν(x_{j+1} ⋯ x_{i−1}) x_{j} ν(x_{i+1} ⋯ x_{n}).

Case 2: If the length of x is larger than 1 and there is some a < b with a ∈ arg min(x) and b ∈ arg max(x), then let i be the greatest element of arg min(x) that is smaller than some element of arg max(x) and let j be the smallest element of arg max(x) greater than i. Then

ν(x) = ν(x_{1} x_{2} ⋯ x_{i−1}) x_{j} ν(x_{i+1} ⋯ x_{j−1}) x_{i} ν(x_{j+1} ⋯ x_{n}).

n I ⊆ [n − 1] d(I, n) D(I, n)
1  ∅  C_{1} = 1 1
2  ∅  C_{2} = 2 11, 12
{1}  1  21
3  ∅  C_{3} = 5 111, 112, 113, 122, 123
{1}  5  211, 311, 212, 213, 312
{2}  5  131, 121, 221, 132, 231
{1, 2}  1  321
4  ∅  C_{4} = 14 {1111, 1112, 1113 1114, 1122, 1123, 1124, 1133, 1134, \atop 1222, 1223, 1224, 1233, 1234}
{1}  21  2111, 3111, 4111, 2112, 2113, 3112, 2114, 4112, 3113, 3114, 4113, 2122, 2123, 3122, 4122, 2133, 3123, 2134, 3124, 4123, 2124
{2}  31  1211, 1311, 1411, 1212, 2211, 1213, 1312, 2311, 1214, 1412, 2411, 1313, 3311, 1314, 1413, 3411, 2212, 1322, 2213, 2312, 1422, 2214, 2412, 1323, 2313, 3312, 1324, 1423, 2314, 2413, 3412
{3}  21  1121, 1131, 1141, 1221, 1132, 1231, 1142, 1241, 1331, 1143, 1341, 2221, 1232, 2231, 1242, 2241, 1332, 2331, 1243, 1342, 2341
{1, 2}  9  3211, 4211, 4311, 3212, 4212, 3213, 3214, 4213, 4312
{1, 3}  19  2121, 2131, 3121, 4121, 3131, 2141, 3141, 4131, 2132, 3221, 2142, 3121, 3231, 4221, 2143, 3142, 3241, 4132, 4231
{2, 3}  9  1321, 1421, 1431, 2421, 3321, 1432, 2431, 2321, 3421
{1, 2, 3}  1  4321

Table 1: Parking functions of length 1 ≤ n ≤ 4 with a given descents set.

We illustrate Definition 7 in the following example.

Example 8. Let y = (1, 1, 1, 1, 2, 3, 3, 4, 4) ∈ ℕ^{9} and consider x = (1, 4, 1, 3, 4, 3, 1, 2, 1) ∈ 𝔖_{n}(y). We write x in one-line notation as: x = 1 4 1 3 4 3 1 2 1. Note Asc(x) = {1, 3, 4, 7}, arg min(x) = {1, 3, 7, 9}, and arg max(x) = {2, 5}. We use Definition 7 to give ν(x).

• Since the length of x is larger than 1 and there exists a ∈ arg min(x) and b ∈ arg max(x) with a < b, we are in Case 2. Then i = 3 and j = 5. Hence,

ν(x) = ν(1 4) \underbrace{4}_{x_{5}} ν(3) \underbrace{1}_{x_{3}} ν(3 1 2 1).  (8)

We now consider ν(1 4), ν(3) and ν(3 1 2 1) independently.

• For the subword 1 4, we are again in Case 2. So, ν(1 4) = 4 1.

• Since 3 has length 1, by Case 0, ν(3) = 3.

• For the subword 3 1 2 1, arg min(3 1 2 1) = {2, 4} and arg max(3 1 2 1) = {1}. Hence by Case 1, ν(3 1 2 1) = 1 ν(1 2) 3. Then by Case 2, ν(1 2) = 2 1.

Substituting these findings into Equation (8) yields

ν(1 4 1 3 4 3 1 2 1) = 4 1 4 3 1 1 2 1 3.

The following remark is helpful and uses wording we implement in subsequent proofs. Remark 9. In Definition 7, Case 1 only considers words x whose minimal value(s) all appear to the right of all of its maximal value(s). Applying ν to x, the result is a word ν(x) that has all maximal value(s) to the right of all minimal value(s). Whenever x has a minimal value to the left of a maximal value, then Case 2 in Definition 7 is applied. Applying ν to x results in ν(x) having a minimal value to the left of a maximal value.

Proposition 10. Fix y ∈ ℕ^{n}. The restriction of the map ν taking the set of elements of 𝔖_{n}(y) with ascent set I to the set of elements of 𝔖(y) with descent set I is a bijection.

Before proving Proposition 10, we need the following lemmas.

Lemma 11. Let y ∈ ℕ^{n} and x ∈ 𝔖_{n}(y). Then Asc(x) = Des(ν(x)) for ν as defined in Definition 7.

Example 12. Continuing Example 8, observe that Asc(x) = Asc(1 4 1 3 4 3 1 2 1) = {1, 3, 4, 7} and Des(ν(x)) = Des(4 1 4 3 1 1 2 1 3) = {1, 3, 4, 7}, thus Asc(x) = Des(ν(x)).

Proof of Lemma 11. Let x and y have length n. For the base case, if n = 0 or n = 1, then by Case 0 of Definition 7, ν(x) = x and Asc(x) = ∅ = Des(ν(x)).

Fix n > 1, y ∈ ℕ^{n}, and x ∈ 𝔖_{n}(y). Assume, for strong induction, that for all k < n, y′ ∈ ℕ^{k}, and x′ ∈ 𝔖_{k}(y′), we have Asc(x′) = Des(ν(x′)). We now consider ν(x) = ν(x_{1} x_{2} ⋯ x_{n}) and proceed via a case-by-case analysis given by the cases in Definition 7.

Case 1: Suppose a ≥ b for all a ∈ arg min(x) and b ∈ arg max(x). Let M = max(x) and let m = min(x). Then

x = x_{1} x_{2} ⋯ x_{j−1} \underbrace{M}_{j} x_{j+1} ⋯ x_{i−1} \underbrace{m}_{i} x_{i+1} ⋯ x_{n}

where j = min(arg max(x)) and i = max(arg min(x)). By Case 1 in Definition 7,

ν(x) = ν(x_{1} x_{2} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{n}).

By the inductive hypothesis, for each

x′ ∈ {x_{1} x_{2} ⋯ x_{j−1}, x_{j+1} x_{j+2} ⋯ x_{i−1}, x_{i+1} x_{i+2} ⋯ x_{n}}

we know Asc(x′) = Des(ν(x′)). Thus, we only need to examine ν(x) at indices j − 1, j, i − 1, and i. We proceed with a case-by-case analysis:

(a) Consider the value at index j − 1: If j = 1, then j − 1 = 0, and hence there is no ascent, descent, or tie in x at index 0. Thus, the ascent and descent sets are empty and ν simply maps the empty set to the empty set. If j > 1, then x has an ascent at position j − 1 because M = max(x) and j = min(arg max(x)). Since arg min(x) ⊆ {j, j + 1, …, i − 1, i}, the element at index j − 1 in ν(x) is larger than m. Since ν places m in position j, ν(x) has a descent at position j − 1.

(b) Consider the values at indices j and i − 1: Note, that x must have a non-ascent at position j because M is a maximal element causing either a tie or descent at j. Likewise, there is a non-ascent in position i because m is a minimal element. Swapping m and M in ν(x) results in the following: First, since m is a minimal element, placing m at position j ensures that at this index we either have an ascent or tie. This means ν(x) has a non-descent at index j. Second, since M is a maximal element, placing M at position i ensures that the index prior is less than or equal to M. This implies that ν(x) has a non-descent at index i − 1.

(c) Consider the value at index i: If i = n, then there is no ascent, descent, or tie at position i in x, and the proposition is vacuously true. If i < n, the reasoning is symmetric to the case for j − 1; x has an ascent at position i and ν(x) has a descent at the same position.

Case 2: Suppose there is some a < b with a ∈ arg min(x) and b ∈ arg max(x). Let i be the greatest element of arg min(x) that is smaller than some element of arg max(x) and let j be the smallest element of arg max(x) greater than i. Furthermore, let M = max(x) and let m = min(x). Then

x = x_{1} x_{2} ⋯ x_{i−1} \underbrace{m}_{i} x_{i+1} ⋯ x_{j−1} \underbrace{M}_{j} x_{j+1} ⋯ x_{n}

and from Case 2 in Definition 7,

ν(x) = ν(x_{1} x_{2} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{n}).

We again only need to examine positions i − 1, i, j − 1, and j. We proceed with a case-by-case analysis:

(a) Consider the value at index i − 1: If i = 1, then i − 1 = 0, and hence there is no ascent, descent, or tie in x at index 0. Thus, the ascent and descent sets are both necessarily empty, so ν simply maps the empty set to the empty set. If i > 1, then in x there is a non-ascent at position i − 1. Then swapping m and M, ensures that there is a non-descent at position i − 1 in ν(x).

(b) Consider the values at positions i and j − 1: There are no minimal or maximal elements in x_{i+1} ⋯ x_{j−1}, but x_{i} = m and x_{j} = M. Therefore, x has ascents in positions i and j − 1. Then for the same reasons, because ν places m in position j and M in position i, ν(x) has descents at positions i and j − 1.

(c) Consider the value at index j: If j = n, then there is no ascent, descent, or tie at position j; and the ascent and descent sets are empty and ν is again mapping the empty set to the empty set. If j < n, the reasoning is symmetric to the case for i − 1; x must have a non-ascent at position j and ν(x) must have a non-descent at the same position.

Therefore, Asc(x) = Des(ν(x)).

Lemma 13. The map ν of Definition 7 is injective.

Proof. We now left-invert ν by inducting on length. In the base case, when the length is zero or one, then ν acts as the identity causing the left-inverse to also be the identity, hence injective. Assume for strong induction, that ν is left-invertible for all inputs of length less than n (i.e., of length 1 < k < n). Now consider ν(x) of length n. We left invert ν(x) by uniquely identifying x. Let m = min(ν(x)) and M = max(ν(x)). By Definition 7, ν does not change the content of the input. Hence, m = min(ν(x)) = min(x) and M = max(ν(x)) = max(x). Given that n > 1, then either:

1. x has the property of either Case 1 of Definition 7 and

ν(x) = ν(x_{1} x_{2} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{n}),

or

2. x is of the from in Case 2 of Definition 7 and

ν(x) = ν(x_{1} x_{2} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{n}),

Thus, i and j are indices determined using Definition 7.

Given ν(x) ∈ ν(𝔖_{n}(y)), if the indices i and j can be uniquely identified by the structure of the word ν(x), then we can inductively construct ν^{−1} by swapping the ith and jth entries of ν(x) and then applying ν^{−1} to each of the subwords of ν(x) with smaller length. This then would uniquely identify the input x, and establish injectivity.

The key to creating the inverse relies on determining whether ν(x) satisfies either:

Case (a): all minimal elements are to the left of all maximal elements, or

Case (b): there exists a minimal element to the right of a maximal element.

We consider each of the above cases independently.

For Case (a) where all minimal elements are to the left of all maximal elements in ν(x), the first step in applying ν to x cannot have arisen from Case 2 in Definition 7, because Case 2 explicitly places a minimal element to the right of a maximal element. Therefore, the first step in applying ν to x arose from Case 1 in Definition 7. This implies that x has all maximal elements to the left of all minimal elements and in the subword x_{j+1} ⋯ x_{i−1}, all instances of M are to the left of all instances of m. Therefore, if x_{j+1} ⋯ x_{i−1} has instances of both M and m, ν acts on x_{j+1} ⋯ x_{i−1} as in Case 1 of Definition 7. Then

ν(x) = ν(x_{1} x_{2} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{n}),

where index j is the smallest index that contains a minimal element and index i is the largest index that contains a maximal element. Therefore, i = max(arg max(ν(x))) and j = min(arg min(ν(x))). Then by induction hypothesis, we have uniquely identified x, which gave rise to ν(x).

Now consider Case (b) where there exists a minimal element to the right of a maximal element in ν(x). Recall that ν(x) ∈ ν(𝔖_{n}(y)). By induction on the minimum of the number of minimal and maximal elements in y, if ν(x) was the output from Case 1 in Definition 7, then ν(x) would have all minimal elements to the left of all maximal elements. But by assumption ν(x) satisfies Case (b). Therefore, the first step in applying ν to x arose from Case 2 in Definition 7. Then i is the index in x containing the rightmost minimal element that has a maximal element to its right in x, and j is the leftmost maximal element to the right of i. Thus,

x = x_{1} x_{2} ⋯ x_{i−1} \underbrace{m}_{i} x_{i+1} ⋯ x_{j−1} \underbrace{M}_{j} x_{j+1} ⋯ x_{n}.

By the maximality of i, all instances of m must appear to the right of all instances of M in the subword x_{j+1} ⋯ x_{n}. Moreover, by our construction of i and j, there are no instances of m or M in the subword x_{i+1} ⋯ x_{j−1}. Hence,

ν(x) = ν(x_{1} x_{2} ⋯ x_{i−1}) \underbrace{M}_{i} ν(x_{i+1} ⋯ x_{j−1}) \underbrace{m}_{j} ν(x_{j+1} ⋯ x_{n}),

and ν(x_{j+1} ⋯ x_{n}) causes all instances of m to appear to the left of all instances of M according to Case 1 of Definition 7. It follows that i is the index of the rightmost maximal element of ν(x) with a minimal element to its right, and j is the index of the leftmost minimal element to the right of i in ν(x). Then by the induction hypothesis, we have uniquely identified x, which gave rise to ν(x).

Thus, we have shown that whether ν(x) satisfies Case (a) or Case (b), we can uniquely recover x which gives rise to ν(x). This establishes that ν is an injection.

We are now ready to prove Proposition 10.

Proof of Proposition 10. By Lemma 13 and Lemma 11, ν, as constructed in Definition 7, is an injective map 𝔖_{n}(y) → 𝔖_{n}(y) for all y ∈ ℕ^{n} such that Asc(x) = Des(ν(x)). Then since |𝔖(y)| is finite, ν must also be a surjection. Therefore, ν is the desired bijection.

Remark 14. As defined in Proposition 10, ν maps the ascent set to the descent set but does not (and cannot possibly) make additional promises about mapping the descent set to the ascent set. In Example 8, Asc(x) = {1, 3, 4, 7} = Des(ν(x)), but Des(x) = {2, 6, 8} and Asc(ν(x)) = {2, 5, 6, 8}. The map that takes the descent set to the ascent set is ν^{−1}.

Corollary 15. There is a bijection D(I; n) → A(I; n).

Proof. Apply ν from Proposition 10 to a parking function.

Theorem 16. The set of parking functions with descent set I and the set of parking functions with descent set J = {n − i : i ∈ I} are in bijection, and hence d(I; n) = d(J; n).

Proof. This result follows from Proposition 6 and Corollary 15.

In what follows, we say the sets I ⊆ [n − 1] and J = {n − i : i ∈ I} are self-dual if I = J. We now give a formula for the number of self-dual sets.

Our next objective is to give a recursive formula for the number of parking functions of length n with descent set I ⊆ [n − 1]. We begin with some general definitions and notation. Given a multiset X of positive integers with size n, let W (X) denote the set of multipermutations of X. For I ⊆ [n − 1], let

D_{X}(I) = {w ∈ W (X) : Des(w) = I},

and D_{X}(I) = |D_{X}(I)|.

Lemma 17. Given β ∈ PF_{n}^{↑}, let M(β) be the multiset of entries of β. If I ⊆ [n − 1], then

∑_{β∈PF_{n}^{↑}} d_{M(β)}(I) = d(I; n).

Proof. This follows from definitions of D_{X}(I) and D(I; n), and that each parking function is a rearrangement of a unique increasing parking function.

Recall that d(∅; n) = C_{n}, the nth Catalan number. We now give a recursion for the number of parking functions with a nonempty descent set.

Theorem 18. Let I ⊆ [n − 1] be nonempty, m = max(I), and I^{−} = I \ {m}. Then

d(I; n) = ∑_{β∈PF_{n}^{↑}} ( ∑_{X∈M(β;m)} d_{X}(I^{−}; m)) − d(I^{−}; n),

where, for β ∈ PF_{n}^{↑}, M(β, m) denotes the collection of multisets consisting of m elements of β.

Proof. Consider the set P of parking functions α ∈ PF_{n} that can be written as a concatenation α = α′ + α′′ and satisfy

1. that the length of α′ is m and the length of α′′ is n − m and

2. Des(α′) = I^{−} and Des(α′′) = ∅.

We now count the elements of P in two ways.

First, observe that we can write P as the disjoint union of those α where α′_{m} > α′′_{1} and those where α′_{m} ≤ α′′_{1}. Hence,

|P | = d(I^{−}; n) + d(I; n).  (9)

On the other hand, the elements of P can be constructed as follows. Consider every β ∈ PF_{n}^{↑} as a multiset with n elements. For a fixed multiset β ∈ PF_{n}^{↑}, M(β, m) is the collection of multisets of size m with entries in β.

For every X ∈ M(β, m), arrange the elements so that they have descent set I^{−}. This can be done in d_{X}(I^{−}) ways. The remaining n − m values in β \ X are used to construct α′′ by placing those remaining values in nondecreasing order, so as to have no descents. This can be done in a unique way. Thus, the number of elements of P is given by

|P | = ∑_{β∈PF_{n}^{↑}} ( ∑_{X∈M(β,m)} d_{X}(I^{−})) .  (10)

Solving Equation (9) for d(I; n) and substituting the right hand-side of Equation (10) in for |P | yields the desired result.

Example 19. Let I = {1, 3}. Then by Theorem 18,

d(I; 4) = ∑_{β∈PF_{4}^{↑}} ( ∑_{X∈M(β;3)} d_{X}(I^{−})) − d(I^{−}; 4).

To compute the sum, select subsets of size 3 = max(I) for each multiset β ∈ PF_{4}^{↑} and arrange the entries so that they have descents at I^{−} = {1}. Table 2 details the computations establishing

∑_{β∈PF_{4}^{↑}} ( ∑_{X∈M(β,3)} d_{X}(I^{−})) = 40.

Now d(I^{−}; 4) = 21, from which we get d(I; 4) = 40 − 21 = 19 as expected. In fact, Table 1 gives the elements of D(J; 4) for all subsets J ⊆ [3]; and in particular, we list the elements in D(I; 4) confirming that d(I; 4) = 19.

Next, we enumerate parking functions with descents at the first k indices by bijecting onto the set of standard Young tableaux of shape ((n − k)^{2}, 1^{k}), which are known to be enumerated by f(n, n − k − 1) = \frac{1}{n} \binom{n}{k}\binom{2n−k}{n−k−1} (\underline{A033282}).

For natural number n, a partition λ of n is a weakly decreasing tuple (λ_{1}, …, λ_{k}) such that ∑_{i} λ_{i} = n. Whenever λ is a partition of n we write λ ⊢ n.

Definition 20 ([8, p. 1]). Given a partition λ ⊢ n, a Young diagram of shape λ is a leftjustified collection of boxes with λ_{i} boxes in row i and where the top row is row 1. A standard Young tableau of shape λ is a filling of the Young diagram of shape λ with the numbers {1, …, n} such that the rows and columns are strictly increasing left to right and top to bottom.

Definition 21. A Dyck word w of semilength n is a word that contains U’s and D’s where U and D each appear n times such that for all 1 ≤ i ≤ n, the ith D in w appears after the ith U. If U is the ith U in w, then i is the semi-index of the specified U.

\begin{matrix}β ∈ PF_{4}^{↑} & M(β, 3) & ∑_{X∈M(β;3)} d_{X}(I^{−}) \\ \{1, 1, 1, 1\} & \{\{1, 1, 1\}\} & 0 \\ \{1, 1, 1, 2\} & \{\{1, 1, 1\}, \{1, 1, 2\}\} & 0 + 1 = 1 \\ \{1, 1, 1, 3\} & \{\{1, 1, 1\}, \{1, 1, 3\}\} & 0 + 1 = 1 \\ \{1, 1, 1, 4\} & \{\{1, 1, 1\}, \{1, 1, 4\}\} & 0 + 1 = 1 \\ \{1, 1, 2, 2\} & \{\{1, 1, 2\}, \{1, 2, 2\}\} & 1 + 1 = 2 \\ \{1, 1, 2, 3\} & \{\{1, 1, 2\}, \{1, 1, 2\}, \{1, 2, 3\}\} & 1 + 1 + 2 = 4 \\ \{1, 1, 2, 4\} & \{\{1, 1, 2\}, \{1, 1, 4\}, \{1, 2, 4\}\} & 1 + 1 + 2 = 4 \\ \{1, 1, 3, 3\} & \{\{1, 1, 3\}, \{1, 3, 3\}\} & 1 + 1 = 2 \\ \{1, 1, 3, 4\} & \{\{1, 1, 3\}, \{1, 1, 4\}, \{1, 3, 4\}\} & 1 + 1 + 2 = 4 \\ \{1, 2, 2, 2\} & \{\{1, 2, 2\}, \{2, 2, 2\}\} & 1 + 0 = 1 \\ \{1, 2, 2, 3\} & \{\{1, 2, 2\}, \{1, 2, 3\}, \{2, 2, 3\}\} & 1 + 2 + 1 = 4 \\ \{1, 2, 2, 4\} & \{\{1, 2, 2\}, \{1, 2, 4\}, \{2, 2, 4\}\} & 1 + 2 + 1 = 4 \\ \{1, 2, 3, 3\} & \{\{1, 2, 3\}, \{1, 3, 3\}, \{2, 3, 3\}\} & 2 + 1 + 1 = 4 \\ \{1, 2, 3, 4\} & \{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}\} & 2 + 2 + 2 + 2 = 8 \end{matrix}

Table 2: Computations for Example 19.

Lemma 22. [10], Theorem 6. There is a bijection f between Dyck words w of semilength n and standard Young tableaux of shape (n, n) which is given as follows: If w_{i} = U (respectively, D), then i appears in the first (respectively, second) row of f(w).

For more on bijections between Dyck paths and standard Young tableaux, we point the interested reader to Gil, McNamara, Tirrell, and Weiner [9].

Lemma 23. There is a bijection g between Dyck words w of semilength n and nondecreasing parking functions of length n which is given as follows: The ith entry in g(w) is one plus the number of D’s before the ith U in w.

Proof. Because there are strictly less than i D’s before the ith U in w, the ith entry in g(w) never exceeds i. Then the map is well-defined. It is also injective because a Dyck word can be uniquely determined by the data of the number of D’s before the ith U for all i. This fact also yields surjectivity, as g^{−1}(α) is the unique Dyck word that has α_{i} − 1 D’s before the ith U.

Proposition 24. Let n ≥ 1 and 0 ≤ k ≤ n − 1. If [k] ⊆ [n − 1], then

d([k]; n) = \frac{1}{n}\binom{n}{k}\binom{2n − k}{n − k − 1}.

Proof. Consider the standard Young tableau

T = ^{a_{1} a_{2} a_{3} … ^{a_{n−k}}} ; ^{b_{1} b_{2} b_{3} … ^{b_{n−k}}} ; c_{1} ; c_{2} ; ⋮ ; c_{k}

whose entries strictly increase along the columns and rows. We construct a bijection τ mapping such a tableau to a parking function of length n with descent set k. Construct a word w = w_{1} w_{2} ⋯ w_{2n−k} for all 1 ≤ i ≤ 2n − k by letting

w_{i} = \begin{cases}U, & if i is in the first row; \\ D, & if i is in the second row; \\ X, & if i is in the third row or beyond. \end{cases}

Because b_{i} > a_{i}, removing all X’s from w would make w a Dyck word. Moreover, inserting a U D into the middle of a Dyck path returns another Dyck path. We construct the word w′ of length 2n by replacing every X in w with a U D. Let I consist of the semi-indices of the inserted U’s. Using Lemma 23, let α be the nondecreasing parking function corresponding to w′. We then construct α′ with descent set [k] from α by moving the entries whose indices are in I to the front of the parking function α in decreasing order. By the construction of α, each such index in I is the last appearance of that index’s values, hence the chosen entries are distinct. Then τ(T) = α′.

In the reverse direction, given a parking function α′ ∈ PF_{n} with descent set [k], record the values in the first k entries in α′ in the set V. Let α be the nondecreasing rearrangement of α′, and let I be the set of indices of the last appearance of each element of V in α. Let w′ be the Dyck word corresponding to α, and the U in w′ with semi-index i has a D immediately to its right for all i ∈ I. Then for each i ∈ I, replace the subword U D, consisting of the ith U and the D immediately to its right, with an X. Then construct the corresponding standard Young tableau T = τ^{−1}(α′) by reversing the process from the Dyck word built from a standard Young tableau, as detailed above.

As τ and τ^{−1} are inverse maps of each other and each is defined on the entire desired domain, τ is the desired bijection.

We illustrate the bijection in the proof of Proposition 24 next.

Example 25. Consider n = 7, k = 3, and the standard Young tableau with shape ((7 − 3)^{2}, 1^{3}) = (4, 4, 1, 1, 1):

T = ^{1 3 7 8} ^{2 5 9 10} 4 6 11 .

The corresponding word is w = U D U X D X U U D D X. For record-keeping, we underline elements instead of using the set I. Replacing X’s with \underline{U D} in w yields

w′ = U D U \underline{U D} D \underline{U D} U U D D \underline{U D}.

The corresponding α ∈ PF_{n}^{↑} is given by α = (1, 2, \underline{2}, \underline{4}, 5, 5, \underline{7}). Move the underlined numbers in α to the front (in decreasing order) to get α′ = (7, 4, 2, 1, 2, 5, 5) which has the desired descent set [3].

For an example of the reverse direction, consider α′ = (5, 3, 2, 1, 1, 2, 2), which has descent set [3]. Underline the first 3 entries and write α′ in nondecreasing order (1, 1, 2, 2, \underline{2}, \underline{3}, \underline{5}). The 2’s are repeated and the right-most 2 is the underlined value. Then construct w′ = U U D U U \underline{U D} \underline{U D} D \underline{U D} D D. Replacing \underline{U D} with X in w′ yields

w = U U D U U X X D X D D.

Then w corresponds to the standard Young tableau

T = ^{1 2 4 5} ^{3 8 10 11} 6 7 9 .

Although we have a recursive formula for the number of parking functions of length n with descent set I ⊆ [n − 1] (Theorem 18), we pose the following problem.

Problem 26. Give non-recursive formulas for the number of parking functions with other interesting descent sets I ⊆ [n − 1]?

4 Peaks of parking functions

The Catalan numbers are one of the most well-studied integer sequences, with 214 different combinatorial explanations in Stanley’s work [15], and many more are found on the OEIS \underline{A000108}. We now establish that the set of parking functions of length n that have no peaks and no ties, i.e., peakless-tieless parking functions, are a new set of Catalan objects.

We begin by setting some needed definitions and notation.

Definition 27. Let α = (a_{1}, a_{2}, …, a_{n}) ∈ [n]^{n}.

• Define the tie set of α as

Tie(α) = {j + 1 ∈ [n] : a_{j} = a_{j+1}}

and order the elements Tie(α) = {t_{1} < t_{2} < ⋯ < t_{j}}, where j = |Tie(α)|.

• Define the value set of α as

Val(α) = {b′_{1}, b′_{2}, …, b′_{k}},

such that set of elements of α are in increasing order 1 = b′_{1} < b′_{2} < ⋯ < b′_{k}, where k is the number of distinct elements of α.

Definition 28. Define the function φ : PF_{n}^{↑} → ℕ^{n} by

φ(α) = (t_{j}, t_{j−1}, …, t_{2}, t_{1}, b_{1}, b_{2}, …, b_{k}),  (11)

where Tie(α) = {t_{j} > t_{j−1} > ⋯ > t_{1} > 1} and Val(α) = {1 = b_{1} < b_{2} < ⋯ < b_{k}} are as in Definition 27.

In fact, we show φ : PF_{n}^{↑} → PTPF_{n} and illustrate these definitions next.

Example 29. Consider the nondecreasing parking function α = (1, 1, 2, 3, 4, 4) ∈ PF_{6}^{↑}. Then Tie(α) = {2, 6} and Val(α) = {1, 2, 3, 4}. Now φ(α) returns the tuple whose first |Tie(α)| elements are the integers in Tie(α) arranged in decreasing order, while the remaining values are the elements of Val(α) listed in increasing order. Namely, φ(α) = (6, 2, 1, 2, 3, 4). The result is a peakless-tieless parking function, as claimed.

Theorem 30. The function φ in Definition 28 is a well-defined bijection φ : PF_{n}^{↑} → PTPF_{n}.

Proof. Let α ∈ PF_{n}^{↑}. In this construction, |Val(α)| = k is the number of values appearing in α and |Tie(α)| = j is the number of ties in α. Because α ∈ PF_{n}^{↑} and a value in α either repeats or appears exactly once, k + j = n. Moreover, the construction in Equation (11) ensures b_{1} = 1 since the letter 1 must appear in PF_{n}^{↑}. Also, the letters before 1 (if they exist) decrease down to 1, and the letters after 1 (if they exist) increase. Hence, φ(α) has no peaks and no ties. Additionally, all cars are still able to park with preferences φ(α). To see this, observe that α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n}^{↑}. The cars park in the order they arrive: car 1 parks in spot 1, car 2 in spot 2, and so on. To show that φ(α) parks, we define γ = (g_{1}, …, g_{n}) from α by replacing each a_{i} where a_{i} = a_{i−1} with i. Because α parks, each unchanged preference satisfies g_{i} ≤ i. If g_{j} is a changed preference, then g_{j} = j ≤ j. Thus, we conclude that γ parks. Now, since γ and φ(α) may be permuted into each other, φ(α) must also park. Thus, φ(α) ∈ PTPF_{n}.

Injectivity: Let α, β ∈ PF_{n}^{↑}, and let φ(α) = φ(β). This implies that Tie(α) = Tie(β) and Val(α) = Val(β). Notice that nondecreasing parking functions x ∈ PF_{n}^{↑} are completely determined by their tie sets, Tie(x), and their value sets, Val(x). When reconstructing α and β from the value set and the tie set, the repeated values in x are the same for both φ(α) and φ(β). Thus, α = β.

Surjectivity: Let β = (t_{j}, t_{j−1}, …, t_{2}, t_{1}, b_{1}, b_{2}, …, b_{k}) ∈ PTPF_{n}, where T = {1 < t_{1} < t_{2} < ⋯ < t_{j−1} < t_{j}} and B = {1 = b_{1} < b_{2} < ⋯ < b_{k}}. It is sufficient to find α ∈ PF_{n}^{↑} with Tie(α) = T and Val(α) = B. Order the elements of X = [n] \ T = {x_{1} < x_{2} < ⋯ < x_{n−j}}. Construct α = (a_{1}, a_{2}, …, a_{n}) as follows.

1. In α, place the elements of B in order 1 = b_{1} < b_{2} < ⋯ < b_{k} at the indices indexed by X in order x_{1} < x_{2} < ⋯ < x_{n−j} = x_{k}. Namely, let a_{x_{i}} = b_{i} for all 1 ≤ i ≤ k.

2. For every j ∈ T, set a_{j} = a_{j−1}.

Since α = (a_{1}, a_{2}, …, a_{n}) is a nondecreasing tuple, α parks if and only if a_{i} ≤ i for all 1 ≤ i ≤ n. If a_{i} = a_{i−1} and a_{i−1} ≤ i − 1, then a_{i} ≤ i. Therefore, it is sufficient to check that a_{x_{i}} = b_{i} ≤ x_{i} for all 1 ≤ i ≤ n − j.

Let P = (p_{1}, p_{2}, …, p_{n}) be β in nondecreasing order. This is a parking function, so p_{i} ≤ i.

1. If there is no duplicate in (a_{1}, …, a_{i}): t_{1} > i. Then in P, t_{1} has index at lest i + 1, implying Val(a_{1}, …, a_{i}) ⊂ Val(p_{1}, …, p_{i}).

2. If there is a duplicate, without loss of generality, we assume a_{i−1} = a_{i}.

Then Val(a_{1}, …, a_{i−1}) ⊂ Val(p_{1}, …, p_{i−1}). Notice then, that since a_{i−1} = a_{i}, we have

Val(a_{1}, …, a_{i}) = Val(a_{1}, …, a_{i−1}) ⊂ Val(p_{1}, …, p_{i−1}) ⊆ Val(p_{1}, …, p_{i}).

Because of this, we satisfy the claim. If we take a_{i} ∈ α, we can find some ℓ_{i} ≤ i such that a_{i} = p_{ℓ_{i}} ≤ ℓ_{i} ≤ i. Then a_{i} ≤ i and α ∈ PF_{n}^{↑}.

The bijection in Theorem 30 immediately implies the following.

Corollary 31. If n ≥ 1, then |PTPF_{n}| = C_{n}, the nth Catalan number.

We now provide a connection between peakless-tieless parking functions and the entries of the Catalan triangle \underline{A009766}, which are defined by

C_{n+1,i} = ∑_{j=0}^{i} C_{n,j}.  (12)

Table 3 provides some of the initial values in the Catalan triangle. The sum along the nth row of the Catalan triangle is given by C_{n}.

n \ k 1 2 3 4 5 6 7
1 1
2 1 1
3 1 2 2
4 1 3 5 5
5 1 4 9 14 14
6 1 5 14 28 42 42
7 1 6 20 48 90 132 132

Table 3: The entries of the Catalan triangle for 1 ≤ n, i ≤ 7.

Corollary 32. If PTPF_{n}(i) = {α = (a_{1}, a_{2}, …, a_{n}) ∈ PTPF_{n} : a_{n} = i}, then |PTPF_{n}(i)| = C_{n,i}.

Proof. We proceed by induction on n and i ∈ [n]. When n = 1, the set |PTPF_{1}(1)| = |{(1)}| = 1 = C_{1,1}. When n = 2, the set |PTPF_{2}(1)| = |{(2, 1)}| = 1 = C_{2,1} and |PTPF_{2}(2)| = |{(1, 2)}| = 1 = C_{2,2}.

Assume for induction that for all n ≤ k and i ≤ n, |PTPF_{n}(i)| = C_{n,i}. Let β = (b_{1}, b_{2}, …, b_{n−1}, i) ∈ PTPF_{n}(i). Prepending n + 1 to β yields (n + 1, b_{1}, b_{2}, …, b_{n−1}, i) ∈ PTPF_{n+1}(i). By induction, we construct C_{n,i} many elements of PTPF_{n+1}(i). For every element γ = (b_{1}, b_{2}, …, b_{n−1}, j) ∈ PTPF_{n}(j) with 1 ≤ j ≤ i − 1, appending i to γ yields (b_{1}, b_{2}, …, b_{n−1}, j, i) ∈ PTPF_{n+1}(i), and we construct ∑_{j=1}^{i−1} C_{n,j} elements. These constructions yield distinct elements of PTPF_{n+1}(i) since the construction creates tuples beginning with n + 1, while the second begins with b_{1} ∈ [n]. As these are the only possible values with which the tuple may begin, applying the induction hypothesis yields

|PTPF_{n+1}(i)| = C_{n,i} + ∑_{j=1}^{i−1} C_{n,j} = ∑_{j=1}^{i} C_{n,j} = C_{n+1,i}

where the last equality holds by Equation (12).

4.1 Valleys of parking functions

In permutations, the map i → n − i + 1 gives a bijection on permutations, which sends peaks to valleys. This establishes that the number of permutations with k peaks is the same as the number of permutations with k valleys. However, this map is not well-defined for parking functions. For example, (1, 1, 1) goes to (3, 3, 3) which is not even a parking function. Moreover, the number of parking functions with k peaks is not the same as the number with k valleys. For example, when n = 3, there are four parking functions with one peak:

(1, 2, 1), (1, 3, 1), (1, 3, 2), (2, 3, 1).

Whereas, there are three parking functions with one valley:

(2, 1, 2), (2, 1, 3), (3, 1, 2).

We now consider the set of valleyless-tieless parking functions; parking functions for which there is no index 1 ≤ i ≤ n − 1 such that a_{i} = a_{i+1} nor index 2 ≤ i ≤ n − 1 such that a_{i−1} > a_{i} < a_{i+1}. We let VTPF_{n} denote the set of valleyless-tieless parking functions of length n. Our main result is as follows.

Theorem 33. Valleyless-tieless parking functions of length n are enumerated by |VTPF_{n}| = F_{n+2}, where F_{n} is the nth Fine number (as defined by Deutsch and Shapiro [3]) with the first ten values of the sequence being (1 ≤ n ≤ 10):

1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724.

To prove Theorem 33, in Subsection 4.2, we establish a bijection between the set of valleyless-tieless parking functions and certain types of peakless-tieless parking functions. In Subsection 4.3, we show that the special set of peakless-tieless parking functions are counted by the Fine numbers (\underline{A000957}). This result implies Theorem 33.

4.2 Bijective maps

We let VTPF_{n+1}(a_{1} = 1, a_{n+1} > 1) be the set of valleyless-tieless parking functions of length n + 1 in which the first value is one and the last is larger than one. A more formal definition of peakless-tieless parking functions of length n + 1 is the set of parking functions of length n + 1 for which there is no index i ∈ [n] such that a_{i} = a_{i+1} or a_{i−1} < a_{i} > a_{i+1}.

We let PTPF_{n+1}(a_{1} > a_{n+1}) be the set of peakless-tieless parking functions of length n + 1 in which the first value is larger than the last.

Lemma 34. The function ψ : VTPF_{n} → VTPF_{n+1}(a_{1} = 1, a_{n+1} > 1) defined by

(a_{1}, a_{2}, …, a_{n}) → (1, a_{1} + 1, a_{2} + 1, …, a_{n} + 1)

is a bijection.

Proof. First, we show injectivity. If α = (a_{1}, a_{2}, …, a_{n}), β = (b_{1}, b_{2}, …, b_{n}) ∈ VTPF_{n}, and ψ(α) = ψ(β), then a_{i} + 1 = b_{i} + 1 for all i ∈ [n]. Then a_{i} = b_{i} for all i ∈ [n], so α = β.

For surjectivity, suppose α = (1, a_{2}, …, a_{n}) ∈ VTPF_{n+1}(a_{1} = 1, a_{n+1} > 1). We wish to show that β = (a_{1} − 1, a_{2} − 1, …, a_{n} − 1) ∈ VTPF_{n}. For i ∈ [n], a_{i} > 1 and in general an element of VTPF_{n} can only have a 1 in the first and/or last position. If an instance of 1 has a neighbor both to its left and right and there are no ties, then both of 1’s neighbors are greater than 1, creating a valley and giving rise to a contradiction. Recall α satisfies a_{n} > 1, so a_{i} > 1 for all i ∈ [n]. Moreover, a_{i} − 1 ≤ n for all i ∈ [n]. Hence, β ∈ [n]^{n}.

Next, we show that β is a parking function. Let α^{↑} = (1, x_{1}, x_{2}, …, x_{n}) be the nondecreasing rearrangement of α. Since α is a parking function, we know that 1 < x_{i} ≤ i + 1 for all i ∈ [n]. Then the nondecreasing rearrangement β^{↑} of β is (x_{1}−1, x_{2}−1, …, x_{n}−1), which satisfies 0 < x_{n} − 1 ≤ i, so β parks. Removing the first element of a parking function, in particular of α, does not create a valley or a tie that was not there before. This ensures that β also does not have ties nor valleys. This then establishes that β ∈ VTPF_{n} and satisfies ψ(β) = α.

Remark 35. In a valleyless-tieless parking function there is a unique maximal entry. If this were not the case and the maximum value k appeared twice. Then either they are consecutive entries in the tuple, creating a tie (a contradiction), or they are nonadjacent entries in the tuple and thus the value(s) between them would either be larger or create a valley, giving a contradiction.

In the following, we reverse parts of a tuple. To this end, we define the following.

Definition 36. Let (x_{1}, x_{2}, …, x_{n}) ∈ [n]^{n}. For i ∈ [n − 1] let

flick_{i}(x) = (x_{i}, x_{i−1}, …, x_{1}, x_{n}, x_{n−1}, …, x_{i+1})

and

flick_{n}(x) = (x_{n}, x_{n−1}, …, x_{2}, x_{1}).

For example, if x = (1, 2, 1, 3, 5, 6, 3, 2), then flick_{4}(x) = (3, 1, 2, 1, 2, 3, 6, 5) and flick_{6}(x) = (6, 5, 3, 1, 2, 1, 2, 3).

Proposition 37. Define the map φ : VTPF_{n+1}(a_{1} = 1, a_{n+1} > 1) → PTPF_{n+1}(a_{1} > a_{n+1}) as follows: If v = (v_{1}, v_{2}, …, v_{n+1}) ∈ VTPF_{n+1}(a_{1} = 1, a_{i+1} > 1) and i ∈ [n + 1] is the unique index containing the maximal entry of v, then

φ(v) = flick_{i}(v).

The map φ is a bijection.

Proof. By definition, flick_{i} is an involution that, as a rearrangement, maps parking functions to parking functions. Let α = (a_{1}, a_{2}, …, a_{n+1}) ∈ PTPF_{n+1}(a_{1} > a_{n+1}) with i being the index of the unique instance of 1 ∈ α. Then it is sufficient to show that β = (b_{1}, b_{2}, …, b_{n+1}) = flick_{i}(α) is an element of VTPF_{n+1}(a_{1} = 1, a_{n+1} > 1). Recall that since α ∈ PTPF_{n+1}(a_{1} > a_{n+1}), we have that

a_{1} > a_{2} > ⋯ > a_{i−1} > a_{i} < a_{i+1} < ⋯ < a_{n+1}  (13)

and a_{1} > a_{n+1}. Then by definition of flick_{i}(α) and the inequalities in Expression (13), we have that

1 = a_{i} < a_{i−1} < ⋯ < a_{2} < a_{1} > a_{n+1} > a_{n} > ⋯ > a_{i+1}.

So β = (b_{1}, b_{2}, …, b_{n+1}) = flick_{i}(α) ensures that

1 = b_{1} < b_{2} < ⋯ < b_{i−1} < b_{i} > b_{i+1} > b_{i+2} > ⋯ > b_{n+1}  (14)

with b_{1} = 1 and b_{n+1} > b_{1} = 1. The inequalities in Expression (14) imply that β ∈ VTPF_{n+1}(b_{1} = 1, b_{n+1} > 1).

Then flick_{i} is a well-defined involution between the desired domains. Therefore, we get the bijection as desired.

4.3 Valleyless-tieless parking functions and the Fine numbers

We now define a set partition which is useful in proving Theorem 33.

Definition 38. For n ≥ 0, we partition the set PTPF_{n+1} as follows:

• 𝒢_{n+1} = {α ∈ PTPF_{n+1} : a_{1} > a_{n+1}},

• ℰ_{n+1} = {α ∈ PTPF_{n+1} : a_{1} = a_{n}}, and

• ℒ_{n+1} = {α ∈ PTPF_{n+1} : a_{1} < a_{n+1}}.

For convenience 𝒢_{1} = ℒ_{1} = ∅ and ℰ_{1} = {(1)}. Let G_{n+1} = |𝒢_{n+1}|, E_{n+1} = |ℰ_{n+1}|, and L_{n+1} = |ℒ_{n+1}|.

As expected,

G_{n+1} + E_{n+1} + L_{n+1} = |PTPF_{n+1}| = C_{n+1},  (15)

the (n + 1)th Catalan number, and where the last equality holds by Corollary 31.

Remark 39. Let α = (a_{1}, a_{2}, …, a_{n}) be a peakless-tieless parking function of length n ≥ 2. If a_{i} = n for some index i, then i = 1 or i = n, but not both. This is because if both a_{1} = n and a_{n} = n, then α is not a parking function. If a_{i} = n for i ∈ [2, n − 1], then either α has a peak at i or there is a tie in position i − 1 or i, contradicting that α is peakless and tieless.

Lemma 40. If n ≥ 1, then E_{n+1} = L_{n}, and if n ≥ 0, then G_{n+1} = L_{n+1}.

Proof. For the first equality, we establish a bijection between ℰ_{n+1} and ℒ_{n}, from which the result follows.

Let e = (e_{1}, e_{2}, …, e_{n+1}) ∈ ℰ_{n+1}, so that e_{1} = e_{n+1}. Notice that e is peakless-tieless. Since e_{1} = e_{n+1} and e_{2} < e_{1}, then we have that e_{2} < e_{n+1}. Furthermore, removing e_{1} from e does not create a peak, nor a tie. By Remark 39, the largest possible value in e is n − 1 and would occur at the endpoints. This implies that e_{1} = e_{n+1} ≤ n − 1. Hence, the tuple (e_{2}, e_{3}, …, e_{n+1}) would allow the cars to park. Thus, (e_{2}, e_{3}, …, e_{n+1}) ∈ ℒ_{n}.

In the reverse direction, if ℓ = (ℓ_{1}, ℓ_{2}, …, ℓ_{n}) ∈ ℒ_{n}, then the tuple ℓ′ = (ℓ_{n}, ℓ_{1}, ℓ_{2}, …, ℓ_{n}) has no peaks and no ties as ℓ_{n} > ℓ_{1}. Moreover, we know ℓ_{n} ≤ n. Hence, the largest value in ℓ′ is n, and all n + 1 cars can park. Therefore, we get ℓ′ ∈ ℰ_{n+1}.

If α = (a_{1}, a_{2}, …, a_{n+1}) ∈ 𝒢_{n+1}, the map flick_{n}(α) = (a_{n+1}, a_{n}, …, a_{1}) gives a bijection from 𝒢_{n+1} to ℒ_{n+1}. Hence, G_{n+1} = L_{n+1}.

Theorem 41. If n ≥ 0, then |PTPF_{n+1}(a_{1} < a_{n+1})| = F_{n+1}, the (n + 1)th Fine number.

Proof. Note, that PTPF_{n+1} = 𝒞_{n+1} ⨆ ℰ_{n+1} ⨆ ℒ_{n+1}, so by Equation (15), we have that

C_{n+1} = G_{n+1} + E_{n+1} + L_{n+1}.

By Lemma 40, E_{n+1} = L_{n} and G_{n+1} = L_{n+1}, implying

C_{n+1} = 2L_{n+1} + L_{n}.

The initial values are L_{1} = 0; and since ℒ_{2} = {(1, 2)}, we have L_{2} = 1. Deutsch and Shapiro [3, p. 8] proved the following identity relating the Fine numbers to the Catalan numbers

C_{n+1} = 2F_{n+2} + F_{n+1}

where F_{1} = 0 and F_{2} = 1. Together, this implies that L_{n+1} = F_{n+2}.

The bijections in Lemma 34 and Proposition 37, along with the the enumerative result of Theorem 41 together imply Theorem 33, establishing that the number of valleyless-tieless parking functions is given by a Fine number.

4.4 Open problems

There are many open problems remaining when considering the set of parking functions of length n with j peaks and k ties, which we denote by PF_{n}(j, k). Table 4 provides the cardinality of the set PF_{n}(0, k) for small values of n and k. The column corresponding to k = 0 gives the Catalan numbers, which we prove in Corollary 31.

We prove the following two results related to the value of PF_{n}(0, k) with k = n − 2, n − 1.

Lemma 42. If n ≥ 1, then |PF_{n}(0, n − 1)| = 1.

\begin{matrix}n \ k ties & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ 3 & 5 & 6 & 1 & 0 & 0 & 0 \\ 4 & 14 & 32 & 12 & 1 & 0 & 0 \\ 5 & 42 & 178 & 110 & 20 & 1 & 0 \\ 6 & 132 & 1078 & 978 & 280 & 30 & 1 \end{matrix}

Table 4: Number of parking functions of length n with 0 peaks and k ties.

Proof. A tuple in [n]^{n} with n − 1 ties must have the same value at every entry. The only such parking functions is the all ones tuple.

Lemma 43. If n ≥ 1, then |PF_{n}(0, n − 2)| = n(n + 1), the nth Oblong number \underline{A002378}.

Proof. Such a tuple has exactly one non-tie. If there is exactly one ascent, the tuple begins with 1 ≤ i ≤ n many ones, followed by n − i many repeated values k where 2 ≤ k ≤ i + 1. So the number of possibilities is given by ∑_{i=1}^{n} i = n(n + 1)/2. We can reverse the tuple to account for the case where it has exactly one descent. This yields a total of n(n + 1), as claimed.

A general open problem follows.

Problem 44. For n, j, k ∈ ℕ, give recursive or closed formulas for the value of |PF_{n}(j, k)|.

One could also consider parking functions of length n with j peaks. This set is given by

PF_{n}^{j} = ⋃_{k=0}^{n−1−2j} PF_{n}(j, k).

Table 5 gives the cardinality of |PF_{n}^{j}| for 0 ≤ j ≤ n ≤ 6. The first column corresponding to j = 0 peaks is also given by the row sums in Table 4. We can now pose another open problem.

Problem 45. Characterize and enumerate the set PF_{n}^{k} for general values of n and k.

5 Statistic encoding

We now study a collection of parking functions with a prescribed pattern at every index.

\begin{matrix}n \ j peaks & 0 & 1 & 2 & 3 \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 3 & 0 & 0 & 0 \\ 3 & 12 & 4 & 0 & 0 \\ 4 & 59 & 66 & 0 & 0 \\ 5 & 351 & 825 & 120 & 0 \\ 6 & 2499 & 9704 & 4604 & 0 \\ 7 & 20823 & 115892 & 115959 & 9470 \\ 8 & 197565 & 145478 & 2479110 & 651816 \end{matrix}

Table 5: Number of parking functions of length n with j peaks.

Definition 46. Every α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n} gives rise to a word w = w_{1} w_{2} ⋯ w_{n−1} ∈ {A, D, T}^{n−1}, where for each i ∈ [n − 1] we let

w_{i} = \begin{cases}A, & if a_{i} < a_{i+1}; \\ D, & if a_{i} > a_{i+1}; \\ T, & if a_{i} = a_{i+1}. \end{cases}

We call w the statistic encoding of α and denote it as stat(α).

In defining a statistic encoding, we use the letter A to denote an ascent, D to denote a descent, and T to denote a tie. The vast majority of statistic encodings are non-unique. For example, α = (1, 1, 2, 3, 4) and β = (1, 1, 3, 4, 5) both have w = TAAA as their statistic encoding.

In this section, we answer the following questions:

1. Does there exist a parking function with statistic encoding w for arbitrary w?

2. When is a statistic encoding determined by a unique parking function?

To begin, we set the following notation. Let W_{n−1} denote the set of all statistic encodings of length n − 1, which implies W_{n−1} = {A, D, T}^{n−1}. Our first result establishes that every word of length n − 1 in the letters A, D, T arises as a statistic encoding for some parking function. Before proving the result, we illustrate this notation with an example.

Example 47. To construct a parking function for the word DATA, we begin with a parking function whose statistic encoding is DAT, such as α = (3, 1, 2, 2). To account for the added ascent at the end of the word DATA, we simply append 5 to α and obtain (3, 1, 2, 2, 5) ∈ PF_{5}. Notice that (3, 1, 2, 2, 5) is not the only parking function with statistic encoding DATA as we could have also appended 3 or 4.

If instead we want to construct a parking function with statistic encoding ATADD, we begin with the parking function β = (1, 2, 2, 3, 1) with a corresponding statistic encoding ATAD. To construct a parking function with statistic encoding ATADD, we must create a new descent at the end of β. To do this, we begin by incrementing every entry in β by one, resulting in the tuple (2, 3, 3, 4, 2). Then append 1 to the end of that tuple creating (2, 3, 3, 4, 2, 1), which is an element of PF_{6} and has the desired statistic encoding ATADD.

We are now ready to settle Question (1).

Theorem 48. If w ∈ W_{n−1}, then there exists α ∈ PF_{n} which has w as its statistic encoding.

Proof. We proceed by induction on n, the length of the parking function. We begin with the base case where n = 1 and observe that the empty statistic encoding arises from the parking function (1).

Assume for induction that for n > 1 and for every w ∈ {A, D, T}^{n−1} there is a parking function α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n} with statistic encoding w.

Now consider a word w ∈ W_{n} = {A, D, T}^{n} such that w = w′x where w′ ∈ {A, D, T}^{n−1} and x ∈ {A, D, T}. By the inductive step, we can find some P′ = (p′_{1}, p′_{2}, …, p′_{n}) ∈ PF_{n} whose statistic encoding is w′. To obtain a parking function α ∈ PF_{n+1} with statistic encoding w = w′x, we append a new preference to P′ ∈ PF_{n} based on the letter x by the following criteria:

C1: If x = T, we append p′_{n} to P′ constructing

α = (p′_{1}, p′_{2}, …, p′_{n}, p′_{n}).

Note, α is a parking function of length n + 1 as P′ is a parking function of length n, and appending the value p′_{n} ensures that car n + 1 parks in spot n + 1. Moreover, this ensures that the parking function ends with a tie.

C2: If x = A, we append n + 1 to P′ to get

α = (p′_{1}, p′_{2}, …, p′_{n}, n + 1).

Note, α is a parking function of length n + 1 and P′ is a parking function of length n. Appending the value n + 1 to α ensures that car n + 1 parks in spot n + 1. Moreover, this ensures that the parking function ends with an ascent.

C3: If x = D, we modify P′ by incrementing each p′_{i} by one and then appending the value 1 at the end of P′ to get

α = (p′_{1} + 1, p′_{2} + 1, …, p′_{n} + 1, 1).

Note, P′ is a parking function of length n, and by incrementing its values by one, the cars 1 through n in α park in spots 2 through n + 1. Then car n + 1 with preference 1 parks in spot 1. Thus, α is a parking function of length n + 1. Moreover, this ensures that the parking function ends with a descent.

In the next result, we use the notation A^{∗} T^{∗} to describe a word with some nonnegative integer number of A’s followed by a nonnegative integer number of T’s. When we specify that A^{∗} T^{∗} ∈ W_{n−1}, then the total number of A’s and T’s must be equal to n − 1. Whenever we want to specify the full set of such words, we write {A^{∗} T^{∗}}. Likewise for T^{∗}D^{∗} and {T^{∗}D^{∗}}.

With this notation in mind, we now settle Question (2).

Lemma 49. Let w ∈ W_{n−1}. If there is a unique α ∈ PF_{n} such that stat(α) = w, then for all indices i ∈ [n−1], |α_{i+1} −α_{i}| ≤ 1. Moreover, if m_{p}(α) > 0, then m_{q}(α) > 0 for all q < p.

Proof. Let w ∈ W_{n−1}. Assume towards a contradiction that α is a parking function with an index i such that |α_{i+1} − α_{i}| > 1. Without loss of generality, suppose p = α_{i+1} > α_{i}. Let j be the first index after i such that α_{j} ≠ α_{j+1}. In other words, let α have the following structure:

(α_{1}, …, α_{i}, \underbrace{p}_{i+1}, p, …, \underbrace{p}_{j}, α_{j+1}, …, α_{n}),

where α_{i}, α_{j+1} ≠ p. Then the tuple

α′ = (α_{1}, …, α_{i}, \underbrace{p − 1}_{i+1}, p − 1, …, \underbrace{p − 1}_{j}, α_{j+1}, …, α_{n})

has the same statistic encoding as α. We know that α′ is a parking function because reducing the value of an element in a parking function always yields a parking function. Then stat(α′) = w, yielding a contradiction. Thus, α is not the unique parking function such that stat(α) = w.

The second part of the lemma results from induction on the maximal value p in α. First, observe that 1 appears at least once in every parking function. Then if p = 1 or p = 2 the proposition is straightforward. Now assume the inductive hypothesis on a parking function α with maximum value p. Let i be the first index such that exactly one of α_{i} and α_{i+1} is equal to p. Without loss of generality, assume α_{i} = p and α_{i+1} ≠ p. Then by the first part of the lemma, α_{i+1} = p−1. Then m_{p−1}(α) > 0, so by m_{q}(α) > 0 for all q < p by induction.

Lemma 50. Let w ∈ W_{n−1}. If there is a unique α ∈ PF_{n} with stat(α) = w, then the statistic encoding of the nondecreasing rearrangement β of α is of the form A^{∗} T^{∗}.

Proof. For the sake of contradiction, suppose that α is the unique parking function with stat(α) = w but the statistic encoding of the nondecreasing rearrangement β of α is not of the form A^{∗} T^{∗}. Then let i be the index of the first A in stat(β) that comes after a T. Then α_{i} < i. By Lemma 49, α_{j+1} ≤ α_{j} + 1 for all j ∈ [n − 1]. Then using induction, α_{j} < j for all j > i. Now let p be the maximal value of α. In β, all instances of p are strictly less than their index. Then let α′ be the tuple obtained by increment all instances of p in α. Then α′ is still a parking function and has the same statistic encoding of α. This contradicts α being the unique parking function with statistic encoding w.

Lemma 51. Let w ∈ W_{n−1} with unique α ∈ PF_{n} such that stat(α) = w. If there exist indices 1 ≤ i ≤ j ≤ n such that α_{i−1} > α_{i} = α_{i+1} = ⋯ = α_{j} < α_{j+1} where α_{i−1} and α_{j+1} exist, then α_{i} = ⋯ = α_{j} = 1.

Proof. Let w ∈ W_{n−1} with unique α ∈ PF_{n} such that stat(α) = w. For the sake of contrapositive, let the indices satisfy 1 ≤ i < j ≤ n such that α_{i−1} > α_{i} = α_{i+1} = ⋯ = α_{j} < α_{j+1} with α_{i} > 1. The parking function α′ obtained by replacing α_{i}, …, α_{j} with 1, …, 1 has the same statistic encoding as α. Thus, α is not the unique parking function with stat(α) = w.

In other words, if α is the unique parking function with statistic encoding w, then the local minimum in α has value 1.

Theorem 52. Let w ∈ W_{n−1}. Then there is a unique α ∈ PF_{n} with statistic encoding w if and only if w ∈ {A^{∗} T^{∗}} ∪ {T^{∗}D^{∗}}.

Proof. (⇒) First we show that if w contains both A and D, then there are multiple parking functions α with stat(α) = w. Suppose w contains both A and D. Then there is some n ≥ 0 such that either AT^{n}D or DT^{n} A is a contiguous subword of w.

• Suppose v = AT^{n}D is a contiguous subword of w. Where v first appears in w, let i be the index A and let j be the index of D. Let p be the minimum value in α with index weakly less than i and let q be the minimum value in α with index strictly greater than j. By Lemma 51, p = q = 1. Then the nondecreasing rearrangement β of α starts with two 1’s, but is not itself all ones. This contradicts Lemma 50.

• Suppose v = DT^{n} A is a contiguous subword of w. For the sake of contradiction, suppose α is the unique parking function with stat(α) = w. By the previous bullet point, there is no A that comes before D in w. Then α can be broken into a nonincreasing part α^{∗}, some amount of 1’s, and a nondecreasing part α^{∗∗}. We choose α^{∗} and α^{∗∗} such that neither contain 1’s. By Lemma 49, α^{∗} ends with a 2 and α^{∗∗} begins with a 2. Then the nondecreasing rearrangement β of α is of the form (1, …, 1, 2, 2, …). By Lemma 50, β contains only one instance of the value 1 and has no ascents after the first position. Then α is of the form (2, …, 2, 1, 2, …, 2). However, the parking function α′ = (3, …, 3, 1, 2, …, 2) has the same statistic encoding as α, contradicting α being the unique parking function with statistic encoding w.

Now we consider the case where w does not have both A and D.

• Suppose that w does not contain D. If stat(α) = w, α is nondecreasing. By Lemma 50, w is of the form A^{∗} T^{∗}.

• Suppose that w does not contain A. If stat(α) = w, α is nonincreasing. The nondecreasing rearrangement β of α is exactly the reverse of α. The statistic encoding of β is of the form A^{∗} T^{∗}, so the statistic encoding of α is of the form T^{∗}D^{∗}.

(⇐) Let w ∈ {A^{∗} T^{∗}} ∪ {T^{∗}D^{∗}}. We consider the case where w ∈ {A^{∗} T^{∗}} and w ∈ {T^{∗}D^{∗}}, separately and show that α with statistic encoding w is unique.

• If w = A^{i} T^{n−1−i} for some i ∈ [n − 1], then a_{1} = 1. We claim a_{j} = j for all 2 ≤ j ≤ i. For the sake of contraction, suppose that there exists 1 < j′ ≤ i such that a_{j′} ≠ j′. Then the number j′ does not appear in α as its statistic encoding is w = A^{i} T^{n−1−i}. This would imply that no car parks in spot j and hence α is not a parking function giving us a contradiction. Thus, a_{j} = j for all 1 ≤ j ≤ i. Since w = A^{i} T^{n−1−i}, we now have that a_{i+1} = a_{i+2} = ⋯ = a_{n} = i. Thus, if w = A^{i} T^{n−1−i}, then α is unique and has the form

α = (1, 2, …, i − 1, i, i + 1, i + 1, …, i + 1) ∈ PF_{n}.  (16)

• If w = T^{n−1−i}D^{i} for some i ∈ [n − 1], then a_{n} = 1. By a similar argument in the bullet above, we can show w is a unique parking function. We can reverse the parking function α given in Equation (16) to create

α^{∗} = (i + 1, i + 1, …, i + 1, i, i − 1, …, 3, 2, 1),

which is a parking function and has w as its statistic encoding. As α was unique, so is α^{∗}.

We conclude by posing the following open problems.

Problem 53. Fix a statistic encoding w ∈ W_{n−1}. Characterize and enumerate the subset of parking functions of length n which have w as their statistic encoding.

Problem 54. For which statistic encoding w ∈ W_{n−1} is the subset of parking functions of length n which have w as their statistic encoding the largest?

6 Acknowledgments

The authors thank the anonymous referee for an exceptionally detailed review process. We appreciate their feedback and care.

References

[1] F. Bencs, Some coefficient sequences related to the descent polynomial, European J. Combin. 98 (2021), 103396.

[2] S. Billey, K. Burdzy, and B. Sagan, Permutations with given peak set, J. Integer Sequences 16 (2012), Article 13.6.1.

[3] E. Deutsch and L. W. Shapiro, A survey of the Fine numbers, Discrete Math. 241 (2001), 241–265.

[4] A. Diaz-Lopez, P. E. Harris, E. Insko, and M. Omar, A proof of the peak polynomial positivity conjecture, J. Combin. Theory Ser. A 149 (2017), 21–29.

[5] A. Diaz-Lopez, P. E. Harris, E. Insko, M. Omar, and B. E. Sagan, Descent polynomials, Discrete Math. 342 (2019), 1674–1686.

[6] J. F. Dillon and D. P. Roselle, Simon Newcomb’s problem, SIAM J. App. Math. 17 (1969), 1086–1093.

[7] S. Elizalde, Descents on quasi-Stirling permutations, J. Combin. Theory Ser. A 180 (2021), 105429.

[8] W. Fulton, Young Tableaux, Cambridge University Press, 1997.

[9] J. B. Gil, P. R. W. McNamara, J. O. Tirrell, and M. D Weiner, From Dyck paths to standard Young tableaux, Ann. Comb. 24 (2020), 69–93.

[10] Hilmar Gudmundsson, Dyck paths, standard Young tableaux, and pattern avoiding permutations, ArXiv preprint arXiv:0912.4747 [math.CO], December 23 2009. Available

at https://arxiv.org/abs/0912.4747.

[11] P. Jiradilok and T. McConville, Roots of descent polynomials and an algebraic inequality on hook lengths, Elect. J. Combinatorics 30 (2003), P4.41. Available at https://www.

combinatorics.org/ojs/index.php/eljc/article/view/v30i4p41.

[12] P. A. MacMahon, Combinatory Analysis, Chelsea Publishing Co., 1960.

[13] Angel Raychev, A generalization of descent polynomials, Discrete Math. 346 (2023), 113105.

[14] P. R. F. Schumacher, Descents in parking functions, J. Integer Sequences 21 (2018), Article 18.2.3.

[15] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: parking function, descent, ascent, tie, multiset, Eulerian polynomial, Catalan number, Fine number.

(Concerned with sequences \underline{A000108}, \underline{A000957}, \underline{A002378}, \underline{A009766}, \underline{A033282}, and \underline{A333829}.)

Received December 28 2023; revised versions received May 11 2024; October 31 2024; November 28 2024; November 29 2024. Published in Journal of Integer Sequences, November 30 2024.

Return to Journal of Integer Sequences home page.