Subset Parking Functions

Sam Spiro Department of Mathematics University of California, San Diego 9500 Gilman Dr. La Jolla, CA 92093 USA

                    sspiro@ucsd.edu

Abstract

A parking function (c_{1}, …, c_{n}) can be viewed as having n cars trying to park on a one-way street with n parking spots from left to right, where car i tries to park in spot c_{i}, and otherwise it parks in the leftmost available spot after c_{i}. Another way to view this is that each car has a set C_{i} of “acceptable” parking spots, namely C_{i} = [c_{i}, n], and that each car tries to park in the leftmost available spot that it finds acceptable.

Motivated by this, we define a subset parking function (C_{1}, …, C_{n}), with each C_{i} a subset of {1, …, n}, by having the ith car try to park in the leftmost available element of C_{i}. We further generalize this idea by restricting our sets to be of size k, intervals, and intervals of length k. In each of these cases we provide formulas for the number of such parking functions.

1 Introduction

Parking functions are well-studied objects in combinatorics, and are often defined in the following way. Imagine that there are n parking spots labeled 1 though n on a one way street. There are n cars, also labeled 1 through n, that wish to park in these spots, and each has a preferred parking spot c_{i}. When it is car i’s turn to park, it goes to its preferred spot c_{i} and parks there if it is empty. Otherwise, it tries to park in the next available spot that is after c_{i}. The tuple (c_{1}, …, c_{n}) is said to be a parking function if every car succeeds in parking.

For example, (2, 2, 2) is not a parking function, as car 1 parks in slot 2; car 2 tries to park in slot 2 but can not and goes to the next available slot 3; and car 3 tries to park in slot 2 but can not, and there are no slots after this that are available. On the other hand, (2, 1, 1) is a parking function as car 1 parks in slot 2; car 2 parks in slot 1; and car 3 tries to park in slot 1 but can not, so it goes to the next available slot 3. We will say that the parking function (2, 1, 1) has outcome 213, which describes how one would see the cars parked if one were to walk from slot 1 to slot 3.

Parking functions have many interesting combinatorial properties. For example, a necessary and sufficient condition for (c_{1}, …, c_{n}) to be a parking function is, after rearranging the c_{i} in increasing order as b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n}, we have b_{i} ≤ i for all i. In particular, this shows that any permutations of the entries of a parking function is also a parking function. One can also prove that the number of parking functions PF(n) satisfies

PF(n) = (n + 1)^{n−1}.  (1)

Parking functions have connections to many other areas of combinatorics, such as hyperplane arrangements [6] and the lattice of non-crossing partitions [7]. We refer the reader to the survey of Yan [9] for an elegant proof of (1) and a more in depth study of parking functions.

Many generalizations and variants of parking functions have been studied, such as xparking functions [8] and G-parking functions [4]. These examples generalize the b_{i} ≤ i characterization of parking functions. One can also generalize the parking analogy. An example of this is to allow cars to park a few spaces before their preferred spot if this is already taken, which has been studied recently [1].

In this paper we also consider a variant of parking function that is obtained by modifying the parking rule. To motivate the idea, we observe that a parking function (c_{1}, …, c_{n}) can be viewed as each car choosing a set C_{i} = [c_{i}, n] of “acceptable” parking spaces, with each car parking in the leftmost available spot which is acceptable to them. One can generalize this idea by allowing each C_{i} to be an arbitrary set.

To this end, let [n] := {1, 2, …, n} and let S_{n} denote the set of permutations of size n written in one line notation. Given n non-empty subsets C_{i} ⊆ [n] and a permutation π ∈ S_{n}, we will say that C = (C_{1}, …, C_{n}) is a subset parking function with outcome π if for all 1 ≤ i ≤ n, having π_{j} = i implies j is the smallest element of C_{i} \ {π_{i′}^{−1} : i′ < i}. That is, if car i ends up in spot j, it must find spot j to be acceptable, all the earlier spots which are acceptable are already taken, and no one has taken spot j yet. We let SPF(n, π) denote the number of subset parking functions with outcome π, and we denote the total number of subset parking functions by SPF(n) := ∑_{π∈S_{n}} SPF(n, π). Technically we should say that SPF(n) counts the number of parking functions of size n, but here and throughout we omit explicitly noting this dependency on n whenever it is clear from context.

For example, ({2}, {2, 3}, {1, 2, 3}) is a subset parking function with outcome 312. However, ({2, 3}, {1, 2, 3}, {2}) is not a subset parking function since we require π_{2} = 1, π_{1} = 2, and then no choice from C_{3} will work. In particular this shows that for subset parking functions the order of the C_{i} sets are important, which is not the case in the classical study of parking functions.

Our first goal is to enumerate subset parking functions. To this end, we recall that the inversion number inv(π) of a permutation π is equal to the number of pairs (i, j) such that i < j and π_{j} < π_{i}.

Theorem 1. For any integer n ≥ 1 and π ∈ S_{n},

SPF(n, π) = 2^{n(n−1)−inv(π)},

SPF(n) = ∏_{i=0}^{n−1}(2^{n} − 2^{i}).

(Classical) parking functions are subset parking functions where each C_{i} is required to be an interval of the form [c_{i}, n]. We can get other interesting variants by restricting the C_{i} sets in other ways. For example, we say that C = (C_{1}, …, C_{n}) is a k-subset parking function if C is a subset parking function and |C_{i}| = k for all i. We let SPF_{k}(n, π) denote the number of k-subset parking functions with outcome π and SPF_{k}(n) the number of k-subset parking functions.

To state our next result, we define the local inversion number inv_{i}(π) to be the number of pairs (i, j) with i < j and π_{j} < π_{i}. Observe that inv(π) = ∑ inv_{i}(π). We adopt the convention that \binom{0}{0} = 1 and \binom{0}{x} = 0 for x > 0.

Theorem 2. For any integer n ≥ 1, π ∈ S_{n}, and 1 ≤ k ≤ n,

SPF_{k}(n, π) = ∏_{i=1}^{n} \binom{n − inv_{i}(π) − 1}{k − 1},

SPF_{k}(n) = ∏_{i=0}^{n−1} (\binom{n}{k} − \binom{i}{k}) .

We next consider the case that each C_{i} is an interval, and we call such parking functions interval parking functions. Let IPF(n) and IPF(n, π) be the total number of interval parking functions and the number of interval parking functions with outcome π, respectively.

To state our full result, given a permutation π we define a_{i}(π) to be the largest j with 1 ≤ j ≤ i such that π_{i} ≥ {π_{i}, π_{i−1}, …, π_{i−j+1}}. For example, a_{i}(π) ≥ 2 if and only if π_{i} > π_{i−1}. As another example, for π = 31524, we have a_{i}(π) equal to 1, 1, 3, 1, 2 as i ranges from 1 to 5. Finally, define PF(n, π) to be the number of (classical) parking functions with outcome π.

Theorem 3. For any n ≥ 1 and π ∈ S_{n},

IPF(n, π) = n! · PF(n, π) = n! ∏_{i=1}^{n} a_{i}(π),

IPF(n) = n! · PF(n) = n! · (n + 1)^{n−1}.

Other properties of interval parking functions are currently being investigated by Christensen, DeMuse, Martin, and Yin [2].

The last variant we consider are k-interval parking functions, which are interval parking functions where each C_{i} is an interval containing k elements. We let IPF_{k}(n) denote the number of k-interval parking functions and IPF_{k}(n, π) the number of those with outcome π. Define S_{n}^{k} to be the set of permutations π of order n with π_{n} > π_{n−1} > ⋯ > π_{n−k+1}.

Theorem 4. Let k and n be integers with 1 ≤ k ≤ n and let π ∈ S_{n}. If π ∉ S_{n}^{k}, then IPF_{k}(n, π) = 0. Otherwise,

IPF_{k}(n, π) = ∏_{i=1}^{n−k} min{a_{i}(π), k} · ∏_{i=n−k+1}^{n} min{n − i − k + a_{i}(π) + 1, n − i + 1}.

This formula is rather complicated, but for certain k it is manageable. For example, when k = 1 each term in the product is 1. We conclude that IPF_{1}(n, π) = 1 for all π, and hence IPF_{1}(n) = n!. When k = n, we have IPF_{n}(n, π) = 1 when π = 12 ⋯ n (since in general a_{1}(π) = 1 and a_{n−i}(π) ≤ n−i), and otherwise IPF_{n}(n, π) = 0, so IPF_{n}(n) = 1. Both of these results can also be verified directly. The formulas for k = n − 1 and k = 2 are also quite nice.

Corollary 5. If n ≥ 2 and π ∈ S_{n}^{n−1} with π_{1} = j, then

IPF_{n−1}(n, π) = \begin{cases}2^{n−j−1}, & if j ≠ n; \\ 1, & if j = n. \end{cases}

Moreover,

IPF_{n−1}(n) = 2^{n−1}.

To state the formula for k = 2, we define the ascent number asc(π) of a permutation π to be the number of i with 2 ≤ i ≤ n and π_{i−1} < π_{i}. Define the Eulerian number \left⟨{n \atop k}\right⟩ to be the number of permutations π ∈ S_{n} with asc(π) = k.

Corollary 6. If n ≥ 2 and π ∈ S_{n}^{2}, then

IPF_{2}(n, π) = 2^{asc(π)−1}.

Moreover,

IPF_{2}(n) = ∑_{k=1}^{n−1}(n − k)\left⟨{n − 1 \atop k − 1}\right⟩2^{k−1}.

2 Subset results

We first prove enumeration results for a generalization of subset parking functions where each car is given a list of allowed subset sizes. To this end, given L = (L_{1}, …, L_{n}) with L_{i} ⊆ [n], we define SPF(n, L) to be the number of subset parking functions where |C_{i}| ∈ L_{i}, and we will call this an L-parking function. Our first goal will be to enumerate SPF(n, L).

To do this, we define the notion of a partial parking function, which intuitively describes where the first m cars have parked. Let S_{m,n} denote the set of strings π = π_{1} ⋯ π_{n} where for all 1 ≤ i ≤ m there exists a unique index j with π_{j} = i and such that every other letter is an auxillary letter ∗. Note that S_{n,n} is simply the set of permutations. For i ≤ m we let π_{i}^{−1} denote the unique index j with π_{j} = i.

We say that (C_{1}, …, C_{m}) with each C_{i} a non-empty subset of [n] is a partial L-parking function with outcome π ∈ S_{m,n} if for all 1 ≤ i ≤ m, |C_{i}| ∈ L_{i} and π_{i}^{−1} = j implies j is the smallest element of C_{i} \ {π_{i′}^{−1} : i′ < i}. Finally, given a permutation π, we write π^{(m)} to denote the string where π_{i}^{(m)} = π_{i} if i ≤ m and π_{i}^{(m)} = ∗ otherwise. Once one unpacks these definitions, the following is immediate.

Lemma 7. Let 1 ≤ m ≤ n and π ∈ S_{n}. C is an L-parking function with outcome π if and only if (C_{1}, …, C_{m}) is a partial L-parking function with outcome π^{(m)} for all m.

The following lemma shows how to extend partial parking functions.

Lemma 8. Let 1 ≤ m ≤ n and π ∈ S_{n}. If (C_{1}, …, C_{m−1}) is a partial L-parking function with outcome π, then (C_{1}, …, C_{m}) is a partial L-parking function if and only if |C_{m}| ∈ L_{m} and C_{m} ⊄ {π_{i}^{−1} : i < m}.

Proof. If C_{m} is such a set, then by assumption |C_{m}| ∈ L_{m} and there exists some minimal j in C_{m} \ {π_{k}^{−1} : k < m}. Thus by defining π′ by π′_{i} = π_{i} for i ≠ j and π′_{j} = m, we see that (C_{1}, …, C_{m}) is a partial L-parking function with outcome π′. Conversely, if (C_{1}, …, C_{m}) is a partial L-parking function, then C_{m} \ {π_{k}^{−1} : k < m} must be non-empty, so C_{m} ⊄ {π_{k}^{−1} : k < m}. We also must have |C_{m}| ∈ L_{m} by definition, proving the result.

Theorem 9. For any n ≥ 1 and L = (L_{1}, …, L_{n}),

SPF(n, L) = ∏_{i=1}^{n} (∑_{ℓ∈L_{i}} \binom{n}{ℓ} − \binom{i − 1}{ℓ}) .

Proof. Consider the following procedure. We start with an empty list (). Recursively, given a partial L-parking function (C_{1}, …, C_{i−1}), we choose a set C_{i} such that (C_{1}, …, C_{i}) is a partial L-parking function. By Lemma 7, every L-parking function is obtained (uniquely) by this procedure. Thus to obtain our result we need only enumerate how many choices we can make at each stage of the procedure.

Assume one has already chosen (C_{1}, …, C_{i−1}) so now we need to choose C_{i}. By Lemma 8, for any ℓ ∈ L_{i}, the number of ways to choose an appropriate C_{i} with |C_{i}| = ℓ is \binom{n}{ℓ} − \binom{i−1}{ℓ}.

Namely, one can choose any ℓ-element subset that is not contained in {π_{j}^{−1} : j < i}. As we allow |C_{i}| to be any element of L_{i}, we conclude that the number of choices for C_{i} is exactly ∑_{ℓ∈L_{i}} \binom{n}{ℓ} − \binom{i−1}{ℓ}. As the number of choices for C_{i} is independent of all of the other C_{j} sets, we conclude that the total number of ways to complete this procedure is the product of all of these sums. This gives the desired result.

We can prove a similar general theorem when the outcome is specified. To this end, define SPF(n, L, π) to be the number of L-parking functions with outcome π. Recall that inv_{i}(π) is defined to be the number of (i, j) with i < j and π_{j} < π_{i}.

Theorem 10. For any n ≥ 1, π ∈ S_{n}, and L = (L_{1}, …, L_{n}),

SPF(n, L, π) = ∏_{i=1}^{n} (∑_{ℓ∈L_{i}} \binom{n − inv_{i}(π) − 1}{ℓ − 1}) .

Proof. Consider the following procedure. We start with an empty list (). Recursively, given a partial L-parking function (C_{1}, …, C_{i−1}) with outcome π^{(i−1)}, we choose a set C_{i} such that (C_{1}, …, C_{i}) is a partial L-parking function with outcome π^{(i)}. By Lemma 7, every L-parking function with outcome π is obtained (uniquely) by this procedure. Thus to obtain our result we need only enumerate how many choices we can make at each stage of the procedure.

Assume (C_{1}, …, C_{i−1}) is a partial L-parking function with outcome π^{(i−1)}. By Lemma 8, if we wish to have |C_{i}| = ℓ ∈ L_{i}, then we must have C_{i} ⊄ {π_{i′}^{−1} : i′ < i}. Moreover, we also must choose this set so that it has outcome π^{(i)}. If j = π_{i}^{−1}, this is equivalent to having C_{i} be any subset with j the minimal element of C_{i} \ {π_{i′}^{−1} : i′ < i}. To summarize, necessary and sufficient conditions for C_{i} to have |C_{i}| = ℓ are

(a) |C_{i}| = ℓ,

(b) C_{i} ⊄ {π_{i′}^{−1} : i′ < i},

(c) j ∈ C_{i}, and

(d) k ∉ C_{i} if k < j and k ∉ {π_{i′}^{−1} : i′ < i}.

Note that (b) is implied by (c), so this is irrelevant. Condition (d) is equivalent to avoiding k with k < j and i < π_{k} (that is, the car that appears in the earlier spot k parks after i). The number of such k is exactly inv_{i}(π), so we conclude that the number of C_{i} satisfying these conditions is exactly \binom{n−1−inv_{i}(π)}{ℓ−1}. Summing this value over all ℓ ∈ L_{i} gives the total number of choices for C_{i}. As this quantity is independent of all the other choices of C_{j}, we can take their product to arrive at the desired count for SPF(n, L, π).

With this we can now prove our results. We start with Theorem 2.

Proof of Theorem 2. Note that k-subset parking functions are precisely L-parking functions where L_{i} = {k} for all i. The result follows from Theorems 9 and 10.

Proof of Theorem 1. Subset parking functions are precisely L-parking functions where L_{i} = [n] \ {0} for all i. By Theorem 9 we have

SPF(n) = ∏_{i=1}^{n} ((2^{n} − 1) − (2^{i−1} − 1)) .

Canceling the 1’s and reindexing the product gives the first result. For the second result, Theorem 10 implies

SPF(n, π) = ∏_{i=1}^{n} 2^{n−inv_{i}(π)−1} = 2^{n(n−1)−inv(π)},

where we used that inv(π) = ∑ inv_{i}(π).

We note that Theorem 1 implies

∑_{π∈S_{n}} 2^{n(n−1)−inv(π)} = ∏_{i=0}^{n−1}(2^{n} − 2^{i}),

which one can verify using the generating function for the inversion statistic. This also provides an alternative way to prove the formula for SPF(n) given the formulas for each SPF(n, π). Similarly Theorem 2 implies

∑_{π∈S_{n}} ∏_{i=1}^{n} \binom{n − inv_{i}(π) − 1}{k − 1} = ∏_{i=1} (\binom{n}{k} − \binom{i − 1}{k}) .

We are not aware of a more direct method to prove this.

Before closing this section, we briefly discuss a variant of subset parking functions. Since subset parking functions allow each car to have any set of positions be acceptable, it also makes sense to allow each car to have their own preference order for these spots insteadof always requiring them to park in the left-most available spot.

To formalize this, we say that a list of subsets C = (C_{1}, …, C_{n}), together with a list of bijections f_{i} : C_{i} → [|C_{i}|], is an ordered parking function with outcome π = π_{1} ⋯ π_{n} if for all 1 ≤ i ≤ n, π_{j} = i implies f_{i}(j) = min_{j′∈D_{i}} f_{i}(j′), where D_{i} := C_{i} \ {π_{i′}^{−1} : i′ < i}. We let OPF(n, π) denote the number of ordered parking functions with outcome π and OPF(n) := ∑ OPF(n, π) the number of ordered parking functions.

If we define L-ordered parking functions analogous to how we defined L-parking functions, then essentially the same proof used to prove Theorem 9 shows that

OPF(n, L) = ∏_{i=1}^{n} (∑_{ℓ∈L_{i}} \binom{n}{ℓ}ℓ! − \binom{i − 1}{ℓ}ℓ!) .

With this established, one can prove a nice analog of Theorem 1. Namely, define O(n) = ∑_{ℓ=0}^{n} \binom{n}{ℓ}ℓ! to be the number of ordered subset of [n]. Then

OPF(n) = ∏_{i=0}^{n−1}(O(n) − O(i)).

In the ordered setting, every π is equally likely to be the outcome of an ordered parking function, so OPF(n, π) = OPF(n)/n! for all π.

3 Interval results

As before we first prove a more general theorem. Let K = (K_{1}, …, K_{n}) be such that K_{i} ⊆ [n]\{0} for all i. We say that (C_{1}, …, C_{n}) is a K-interval parking function if each C_{i} is an interval with |C_{i}| ∈ K_{i}. We define partial K-interval parking functions analogous to how we defined partial L-parking functions in the previous section, and as before we immediately have the following.

Lemma 11. Let 1 ≤ m ≤ n and π ∈ S_{n}. C is a K-interval parking function with outcome π if and only if (C_{1}, …, C_{m}) is a partial K-interval parking function with outcome π^{(m)} for all m.

We also have an analog of Lemma 8. Recall that we define a_{i}(π) to be the largest j ≤ i such that π_{i} ≥ {π_{i}, π_{i−1}, …, π_{i−j+1}}.

Lemma 12. Let 1 ≤ m ≤ n and π ∈ S_{n}. Let (C_{1}, …, C_{m−1}) be a partial K-interval parking function with outcome π^{(m−1)} and let p = π_{m}^{−1}. Then (C_{1}, …, C_{m}) is a partial K-interval parking function with outcome π^{(m)} if and only if C_{m} = [r, r + k − 1] with k ∈ K_{i} and

max{p − a_{p}(π) + 1, p − k + 1} ≤ r ≤ min{p, n − k + 1}.

Proof. Assume (C_{1}, …, C_{m}) is such a partial K-interval parking function with C_{m} = [r, r + k − 1] for some r and k. Because |C_{m}| = k we require k ∈ K_{m}, and because C_{m} ⊆ [n] we must have r + k − 1 ≤ n. We also need p − k + 1 ≤ r ≤ p so that this set contains p. Further, we require every x ∈ [r, p] to satisfy π_{x} < m, otherwise p will not be the smallest element of C_{m} \ {π_{i}^{−1} : i < m}, which would contradict (C_{1}, …, C_{m}) having outcome π^{(m)}. By definition this will not be the case if r < p − a_{p}(π) + 1, so r ≥ p − a_{p}(π) + 1. We conclude that r satisfies the desired inequalities.

Conversely, assume C_{m} = [r, r + k] has r and k satisfying these conditions. Because p − a_{p}(π) + 1 ≥ 1 we have C_{m} ⊆ [n], and we also have |C_{m}| = k ∈ K_{i}. Again by definition of a_{p}(π) these inequalities imply that p is the smallest element of C_{m} \ {π_{i}^{−1} : i < m}, so this gives the desired partial K-interval parking function.

Let IPF(n, K, π) denote the number of K-interval parking functions with outcome π and define

b_{i}(π, k) := \begin{cases}min\{a_{i}(π), k\}, & if i ≤ n − k; \\ 0, & if a_{i}(π) < k + i − n; \\ min\{n − i − k + a_{i}(π) + 1, n − i + 1\}, & otherwise. \end{cases}

Theorem 13. For any n ≥ 1, π ∈ S_{n}, and K = (K_{1}, …, K_{n}),

IPF(n, K, π) = ∏_{i=1}^{n} ( ∑_{k∈K_{π_{i}}} b_{i}(π, k)) .

Proof. We consider the number of ways to iteratively build partial K-interval parking functions with outcomes π^{(m)}. If one has already chosen (C_{1}, …, C_{i−1}) and p = π_{i}^{−1}, then by Lemma 12 the number of ways to choose an appropriate C_{i} with |C_{i}| = k ∈ K_{i} is the number of r in the range

max{p − a_{p}(π) + 1, p − k + 1} ≤ r ≤ min{p, n − k + 1}.

If p ≤ n − k this number is exactly min{a_{p}(π), k}. Otherwise it is

max{0, min{n − k − p + a_{p}(π) + 1, n − p + 1}}.

Because n − p + 1 ≥ 1, this quantity is 0 if and only if a_{p}(π) + 1 ≤ k + p − n. Thus the number of choices for C_{i} with |C_{i}| = k is exactly b_{p}(π, k). Summing this over all k ∈ K_{i} gives a quantity independent of all the other C_{j}, so we can take the product of these values and conclude

IPF(n, K, π) = ∏_{i=1}^{n} ( ∑_{k∈K_{i}} b_{π_{i}^{−1}}(π, k)) .

By reindexing this product, we get the stated result.

Proof of Theorem 4. Recall that we wish to prove

IPF_{k}(n, π) = ∏_{i=1}^{n−k} min{a_{i}(π), k} · ∏_{i=n−k+1}^{n} min{n − i − k + a_{i}(π) + 1, n − i + 1}

whenever π ∈ S_{n}^{k}. That is, whenever π_{n} > ⋯ > π_{n−k+1}. Observe that k-interval parking functions are exactly K-interval parking functions with K_{i} = {k} for all i, so a formula for IPF_{k}(n, π) is given by Theorem 13. It remains to rewrite this formula into the desired form.

If π ∉ S_{n}^{k}, then there exists some i with 0 ≤ i ≤ k − 2 and π_{n−i} < π_{n−i−1}. This implies a_{n−i}(π) = 1 < k − i, and hence b_{n−i}(π, k) = 0. Thus IPF_{k}(n, π) = 0.

From now on we assume π ∈ S_{n}^{k}. This implies a_{n−i}(π) ≥ k − i for all 0 ≤ i ≤ k − 1, and hence for these i we have b_{n−i}(π, k) = min{i − k + a_{n−i}(π) + 1, i + 1}. This gives b_{j}(π, k) for all j ≥ n − k + 1, and otherwise we have b_{j}(π, k) = min{a_{j}(π), k}. Taking the products of these terms gives the desired result.

Proof of Corollary 5. The statement can be verified for n = 2, so assume n ≥ 3. By Theorem 2 we have for π ∈ S_{n}^{n−1} that IPF_{n−1}(n, π) equals

min{a_{1}(π), n − 1} · min{a_{2}(π), n − 1} · ∏_{i=3}^{n} min{a_{i}(π) − i + 2, n − i + 1}

= a_{2}(π) · ∏_{i=3}^{n−1} min{a_{i}(π) − i + 2, n − i + 1},

where we used a_{1}(π) ≤ 1 and a_{2}(π) ≤ 2 ≤ n − 1. We claim that this is equal to

∏_{i=2}^{n−1}(a_{i}(π) − i + 2).

Indeed this follows from the fact that a_{i}(π) − i + 2 ≤ 2 ≤ n − i + 1 for all i ≤ n − 1.

Assume π_{1} = j, and recall that π ∈ S_{n}^{n−1} implies that π_{2} < ⋯ < π_{n}. Thus for all i > 1 we have a_{i}(π) = i if π_{i} > j and a_{i}(π) = i−1 otherwise. Thus j = n implies that a_{i}(π) = i−1 for all i ≥ 2, and otherwise there are exactly n − 1 − j different i with 2 ≤ i ≤ n − 1 and a_{i}(π) = i. We conclude the first result. For the second result,

IPF_{n−1}(n) = ∑_{π∈S_{n}^{n−1}} IPF_{n−1}(n, π) = 1 + ∑_{j=1}^{n−1} 2^{n−j−1} = 2^{n−1}.

In principle this same technique can be used to compute IPF_{n−k}(n, π) and IPF_{n−k}(n) for any fixed k, though the case analysis and computations become rather complicated. We note that one can prove IPF_{n−1}(n) = 2^{n−1} more directly by observing that (C_{1}, …, C_{n}) will be an (n − 1)-interval parking function if and only if C_{n} = [2, n] and C_{i} is [1, n − 1] or [2, n] for all other i.

Before proving Corollary 6, we give an enumeration result for permutations in S_{n}^{2} with a given number of ascents. We adopt the convention \left⟨{0 \atop k}\right⟩ = 0 for k > 0, \left⟨{0 \atop 0}\right⟩ = 1, and \left⟨{n \atop −1}\right⟩ = 0.

Lemma 14. For all n and k with n ≥ 1 and 0 ≤ k ≤ n−1, let S_{n,k}^{+} be the set of permutations of size n which have π_{n−1} < π_{n} and which have exactly k ascents. If P (n, k) := |S_{n,k}^{+}|, then

P (n, k) = (n − k)\left⟨{n − 1 \atop k − 1}\right⟩.

We note that this result is implicitly proven in [5], but for completeness we include the full proof here. To prove this, we recall the following recurrence for Eulerian numbers, which is valid for all n, k ≥ 1 [3].

\left⟨{n \atop k}\right⟩ = (k + 1)\left⟨{n − 1 \atop k}\right⟩ + (n − k)\left⟨{n − 1 \atop k − 1}\right⟩.  (2)

Proof. The result is true for k = 0, so assume that we have proven the result up to k ≥ 1. For any fixed k the result is true for n = 1, so assume the result has been proven up to n ≥ 2. To help us prove the result, we define S_{n,k}^{−} to be the set of permutations which have π_{n−1} > π_{n} and which have exactly k ascents. Define M(n, k) := |S_{n,k}^{−}|. By construction we have

P (n, k) + M(n, k) = \left⟨{n \atop k}\right⟩.  (3)

Define the map ϕ : S_{n,k}^{+} → S_{n−1} by sending π ∈ S_{n,k}^{+} to the word obtained by removing the letter 1 from π and then decreasing the value of each letter by 1. For example, ϕ(32514) = 2143. We wish to determine the image of ϕ. Let π be a permutation in S_{n,k}^{+}, and let i denote the position of 1 in π. Note that i ≠ n since π ends with an ascent. If π_{i−1} < π_{i+1} with 1 < i < n, then ϕ(π) will continue to have k ascents and end with an ascent, so ϕ(π) ∈ S_{n−1,k}^{+}. If i = 1 or π_{i−1} > π_{i+1} with 1 < i < n − 1, then ϕ(π) ∈ S_{n−1,k−1}^{+}. If i = n − 1 and π_{n−2} > π_{n}, then ϕ(π) ∈ S_{n−1,k−1}^{−}.

It remains to show how many times each element of the image is mapped to by ϕ. If π ∈ S_{n−1,k}^{+}, then 1 can be inserted into π in k ways to obtain an element of S_{n,k}^{+} (it can be placed between any of the k ascents π_{i} < π_{i+1}). If π ∈ S_{n−1,k−1}^{+}, then 1 can be inserted into π in n − k ways (it can be placed at the beginning of π or between any of the n − 1 − k descents π_{i} > π_{i+1}). If π ∈ S_{n−1,k}^{−}, then 1 must be inserted in between π_{n−1} > π_{n} in order to have the word end with an ascent. With this and the inductive hypothesis, we conclude that

P (n, k) = kP (n − 1, k) + (n − k)P (n − 1, k − 1) + M(n − 1, k − 1)
= k(n − k − 1)\left⟨{n − 2 \atop k − 1}\right⟩ + (n − k)^{2}\left⟨{n − 2 \atop k − 2}\right⟩ + M(n − 1, k − 1).  (4)

By using (3), the inductive hypothesis, and (2); we find

M(n − 1, k − 1) = \left⟨{n − 1 \atop k − 1}\right⟩ − P (n − 1, k − 1)

= \left⟨{n − 1 \atop k − 1}\right⟩ − (n − k)\left⟨{n − 2 \atop k − 2}\right⟩

= k\left⟨{n − 2 \atop k − 1}\right⟩.

Plugging this into (4) and using (2) gives

P (n, k) = (n − k) (k\left⟨{n − 2 \atop k − 1}\right⟩ + (n − k)\left⟨{n − 2 \atop k − 2}\right⟩) = (n − k)\left⟨{n − 1 \atop k − 1}\right⟩,

as desired.

Proof of Corollary 6. By Theorem 2 we have, after evaluating terms which are automatically 1,

IPF_{2}(n, π) = ∏_{i=2}^{n−1} min{a_{i}(π), 2}.

Note that a_{i}(π) ≥ 2 if and only if π_{i−1} < π_{i}. There are exactly asc(π) − 1 different i with 2 ≤ i < n satisfying this, where we subtract 1 since π ∈ S_{n}^{2} implies that there is always an ascent at position n − 1. We conclude the first result.

For the second result, we sum IPF_{2}(n, π) over all π ∈ S_{n}^{2}. Each term contributes 2^{asc(π)−1}, so we conclude the result by Lemma 14 after noting that \left⟨{n−1 \atop −1}\right⟩ = 0.

Corollary 6 shows that, for n ≥ 2, IPF_{2}(n) is equal to \underline{A053525}, the number of connected threshold graphs on n vertices. This can be proven bijectively from essentially the same proof as in [5], but for brevity we omit the details. The formulas for k = 3 \underline{A327761} and k = n − 2 \underline{A327794} seem complicated (though in principle the latter can be put into a closed form).

Before proving our enumeration results for interval parking functions, we first directly enumerate the number of parking functions with a given outcome. In what follows we treat parking functions as subset parking functions (C_{1}, …, C_{n}) where C_{i} = [c_{i}, n] for some 1 ≤ c_{i} ≤ n. Define a partial parking function (C_{1}, …, C_{m}) analogous to how we defined L-partial parking functions. We immediately have the following.

Lemma 15. Let 1 ≤ m ≤ n and π ∈ S_{n}. C is a parking function with outcome π if and only if (C_{1}, …, C_{m}) is a partial interval parking function with outcome π^{(m)} for all m.

We also have an analog of Lemma 12.

Lemma 16. Let 1 ≤ m ≤ n and π ∈ S_{n}. Let (C_{1}, …, C_{m−1}) be a partial parking function with outcome π^{(m−1)} and let p = π_{m}^{−1}. Then (C_{1}, …, C_{m}) is a partial parking function with outcome π^{(m)} if and only if C_{m} = [r, n] with p − a_{p}(π) + 1 ≤ r ≤ p.

Proof. Assume (C_{1}, …, C_{m}) is such a partial parking function with C_{m} = [r, n] for some r. We need r ≤ p so that this set contains j. Further, we require every x ∈ [r, p] to satisfy π_{x} < m, otherwise p will not be the smallest element of C_{m} \ {π_{i}^{−1} : i < m}, which would contradict (C_{1}, …, C_{m}) having outcome π^{(m)}. By definition this will not be the case if r < p − a_{p}(π) + 1, so r ≥ p − a_{p}(π) + 1. We conclude that r satisfies the desired inequalities.

Conversely, assume C_{m} = [r, n] has r satisfying these inequalities. Because p−a_{p}(π)+1 ≥ 1 we have C_{m} ⊆ [n]. Again by definition of a_{p}(π) these inequalities imply that p is the smallest element of C_{m} \ {π_{i}^{−1} : i < m}, so this gives the desired partial parking function.

Proposition 17.

PF(n, π) = ∏_{i=1}^{n} a_{i}(π).

Proof. Assume one has chosen C_{1}, …, C_{i−1} so that (C_{1}, …, C_{i−1}) is a partial parking function with outcome π^{(i−1)}. There are a_{π_{i}^{−1}}(π) choices for C_{i} to make (C_{1}, …, C_{i}) a partial parking function with outcome π^{(i)} by Lemma 16. Every parking is obtained this way by Lemma 15, so taking the product over all these values and reindexing gives the desired result.

We use Theorem 13 to prove Theorem 3, and to do so we require the following lemma.

Lemma 18. For any n ≥ 1 and π ∈ S_{n},

∑_{k=1}^{n} b_{i}(π, k) = a_{i}(π)(n − i + 1).

Proof. Throughout this proof we use that the “otherwise” case in the definition of b_{i}(π, k) can be written as n − i + 1 + a_{i}(π) − max{a_{i}(π), k}.

We first consider the case a_{i}(π) ≤ n−i and split the sum into two parts. For a_{i}(π) < n−i we have

∑_{k=1}^{n−i} b_{i}(π, k) = ∑_{k=1}^{n−i} min(a_{i}(π), k) = ∑_{k=1}^{a_{i}(π)} k + ∑_{k=a_{i}(π)+1}^{n−i} a_{i}(π)

= \binom{a_{i}(π) + 1}{2} + (n − i − a_{i}(π))a_{i}(π).  (5)

If a_{i}(π) = n − i the same formula holds by essentially the same reasoning.

If k > n − i + a_{i}(π) we have b_{i}(π, k) = 0, so the rest of the sum is

∑_{k=n−i+1}^{n−i+a_{i}(π)} b_{i}(π, k) = (n − i + a_{i}(π) + 1)a_{i}(π) − ∑_{k=n−i+1}^{n−i+a_{i}(π)} max{a_{i}(π), k}

= (n − i + a_{i}(π) + 1)a_{i}(π) − ∑_{k=n−i+1}^{n−i+a_{i}(π)} k,  (6)

where we used our assumption a_{i}(π) ≤ n − i < k in this last equality. Using the identity ∑_{k=x+1}^{x+y} k = xy + \binom{y+1}{2}, we conclude that (6) equals

(a_{i}(π) + 1)a_{i}(π) − \binom{a_{i}(π) + 1}{2}.

Adding this to (5) gives the desired result.

Now assume a_{i}(π) ≥ n − i + 1. In this case we have

∑_{k=1}^{n−i} b_{i}(π, k) = ∑_{k=1}^{n−i} min(a_{i}(π), k) = ∑_{k=1}^{n−i} k

= \binom{n − i + 1}{2}.  (7)

The rest of the sum is

∑_{k=n−i+1}^{n−i+a_{i}(π)} b_{i}(π, k) = (n − i + a_{i}(π) + 1)a_{i}(π) − ∑_{k=n−i+1}^{n−i+a_{i}(π)} max{a_{i}(π), k}

= (n − i + a_{i}(π) + 1)a_{i}(π) − a_{i}(π)(a_{i}(π) − n + i) − ∑_{k=1+a_{i}(π)}^{n−i+a_{i}(π)} k

= (2n − 2i + 1)a_{i}(π) − \binom{n − i + 1}{2} − a_{i}(π)(n − i).  (8)

Adding (7) and (8) gives the desired result.

Proof of Theorem 3. Observe that interval parking functions are exactly K-interval parking functions with K_{i} = [n] for all i, so by Theorem 13, Lemma 18, and Proposition 17; we have

IPF(n, π) = ∏_{i=1}^{n} a_{i}(π)(n − i + 1) = n! ∏_{i=1}^{n} a_{i}(π) = n! · PF(n, π).

Using (1), we find

IPF(n) = ∑_{π∈S_{n}} IPF(n, π) = n! ∑_{π∈S_{n}} PF(n, π) = n! · PF(n) = n! · (n + 1)^{n−1}.

4 Acknowledgments

The author was fortunate to have many fruitful discussions about this topic at the Graduate Research Workshop in Combinatorics. In particular we would like to thank Emma Christensen, Ryan DeMuse, Sean English, Jeremy Martin, Puck Rombach, Mike Ross, and Mei Yin.

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1650112. This work was completed in part at the 2019 Graduate Research Workshop in Combinatorics, which was supported in part by NSF grant #1923238, NSA grant #H98230-18-1-0017, a generous award from the Combinatorics Foundation, and Simons Foundation Collaboration Grants #426971 (to M. Ferrara), #316262 (to S. Hartke) and #315347 (to J. Martin).

References

[1] A. Christensen, P. Harris, Z. Jones, M. Loving, A. Rodriguez, J. Rennie, and G. Kirby, A generalization of parking functions allowing backward movement, preprint, 2019,

   https://arxiv.org/abs/1908.07658.

[2] E. Christensen, R. Demuse, J. Martin, and M. Yin. Personal communications, 2019.

[3] R. Graham, D. Knuth, O. Patashnik, and S. Liu, Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley, 1989.

[4] A. Postnikov and B. Shapiro, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356 (2004), 3109–3142.

[5] S. Spiro, Counting threshold graphs with Eulerian numbers, preprint, 2019, https://

   arxiv.org/abs/1909.06518.

[6] R. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. USA 93 (1996), 2620–2625.

[7] R. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4 (1997), #R20.

[8] C. Yan, On the enumeration of generalized parking functions, Congr. Numer. 147 (2000), 201–210.

[9] C. Yan, Parking functions, in Handbook of Enumerative Combinatorics, Chapman and Hall/CRC, 2015, pp. 859–918.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: parking function, subset parking function, threshold graph, permutation.

(Concerned with sequences \underline{A053525}, \underline{A327761}, and \underline{A327794}.)

Received September 26 2019; revised versions received October 12 2019; October 15 2019. Published in Journal of Integer Sequences, October 15 2019.

Return to Journal of Integer Sequences home page.