On Flattened Parking Functions

Jennifer Elder

Department of Computer Science

Mathematics and Physics Missouri Western State University

4525 Downs Drive St. Joseph, MO 64507

USA

flattenedparkingfunctions@outlook.com

Pamela E. Harris Department of Mathematical Sciences University of Wisconsin-Milwaukee 3200 N. Cramer Street Milwaukee, WI 53211 USA

                                   peharris@uwm.edu

Zoe Markman Department of Mathematics and

Statistics Swarthmore College 500 College Avenue Swarthmore, PA 19081

USA

zmarkma1@swarthmore.edu

Izah Tahir School of Mathematics Georgia Institute of Technology 686 Cherry Street Atlanta, GA 30332 USA

                                  itahir3@gatech.edu

Amanda Verga Department of Mathematics Trinity College 300 Summit Street Hartford, CT 06106 USA

            amanda.verga@trincoll.edu

Abstract

A permutation of length n is called a flattened partition if the leading terms of maximal chains of ascents (called runs) are in increasing order. We analogously define flattened parking functions: a subset of parking functions for which the leading terms of maximal chains of weak ascents (also called runs) are in weakly increasing order. For n ≤ 8, where there are at most four runs, we give data for the number of flattened parking functions, and it remains an open problem to give formulas for their enumeration in general. We then specialize to a subset of flattened parking functions that we call S-insertion flattened parking functions. These are obtained by inserting all numbers of a multiset S whose elements are in [n] = {1, 2, …, n}, into a permutation of [n] and checking that the result is flattened. We provide bijections between S-insertion flattened parking functions and S′-insertion flattened parking functions, where S and S′ have certain relations. We then further specialize to the case S = 1_{r}, the multiset with r ones, and we establish a bijection between 1_{r}-insertion flattened parking functions and set partitions of [n + r] with the first r integers in different subsets.

1 Introduction

Let n ∈ ℕ := {1, 2, 3, …} and let 𝔖_{n} denote the set of permutations of [n] := {1, 2, …, n}. Recall that a permutation σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ 𝔖_{n} has a descent (an ascent) at index i if σ_{i} > σ_{i+1} (if σ_{i} < σ_{i+1}). Ascents and descents are often referred to as a permutation statistic. The study of permutation statistics is a robust area of research in combinatorics and has gathered much interest as its connections to other areas of math are plentiful [3, 4, 7, 11, 13].

Another statistic of interest is the number of runs of a permutation. We recall that a run of length p + 1 in σ ∈ 𝔖_{n} is a subword σ_{i}σ_{i+1} ⋯ σ_{i+p−1}σ_{i+p} where i, i + 1, …, i + p − 1 are consecutive ascents, and σ_{i+p} > σ_{i+p+1}, or i + p = n. Given σ ∈ 𝔖_{n}, we let run(σ) denote the number of runs. Zhuang [13] counted permutations by runs and their work provided a generalization of a theorem of Gessel, which gave a reciprocity formula for noncommutative symmetric functions. Gessel [5] also enumerated permutations having certain restrictions on their run lengths. Related work considered permutations whose runs satisfy the condition that the leading terms form an increasing sequence; we define this formally next.

A permutation σ is said to be a flattened partition if it consists of runs arranged from left to right such that their leading values are in increasing order. For example, the permutation σ = 1423 is flattened, as its runs are 14 and 23, and 1 ≤ 2. However, the permutation τ = 4321 is not flattened, as each element is in its own run, and these elements form a decreasing sequence. The research teams of Nabawanda, Rakotondrajao, Bamunoba [8] and Beyene, Mantaci [2] studied the distribution of runs for flattened partitions. Nabawanda et al. establish a new combinatorial interpretation for the number of flattened partitions with k runs along with a bijection between this combinatorial family of objects and set partitions of [n − 1].

In the current work, we extend the definition of flattened partitions to parking functions by allowing ascents to be weak ascents, i.e., a word a_{1}a_{2} ⋯ a_{n} has a weak ascent at index i if a_{i} ≤ a_{i+1}. We begin by recalling that parking functions are tuples in [n]^{n} describing the parking preferences of n cars (denoted c_{1}, c_{2}, …, c_{n}) entering a one-way street (in sequential order) with a preference for a parking spot among n spots on the street. If α = (a_{1}, a_{2}, …, a_{n}) ∈ [n]^{n} is such that a_{i} denotes the parking preference of car c_{i}, then c_{i} drives to a_{i} and parks there if the spot is not previously occupied by an earlier car c_{j}, with 1 ≤ j < i. If such a car has already parked in spot a_{i}, then c_{i} drives down the street parking in the first available spot. Given the parking preferences in α, if the n cars are able to park in the n spots on the street, then we say that α is a parking function. We let PF_{n} denote the set of all parking functions of length n and recall from Konheim and Weiss [6] that |PF_{n}| = (n + 1)^{n−1}. Of course, if every entry of α is distinct (i.e., α is a permutation of n), then all of the cars can park. Thus the set of permutations on n letters is a subset of PF_{n}.

There is much known about parking functions, including their enumeration, their characterization in terms of inequalities, and statistics such as ascents and descents from Schumacher [9], not to mention their numerous generalizations, such as the work done by Yan [12]. However, there is little to nothing known about the set of flattened parking functions of length n:

flat(PF_{n}) := {α ∈ PF_{n} : the leading values in the runs of α are in weakly increasing order},

or of the set of all flattened parking functions of length n with k runs:

flat_{k}(PF_{n}) := {α ∈ flat(PF_{n}) : α has k runs}.

Given a parking function α, we say α is flattened whenever α ∈ flat(PF_{n}) and k-flattened whenever α ∈ flat_{k}(PF_{n}). Moreover, we abuse notation and let run(α) denote the number of runs of α. Thus, the goal of this paper is to extend the study of run distributions of flattened partitions to parking functions.

Our preliminary results establish that the set flat_{1}(PF_{n}) is enumerated by the Catalan numbers, \underline{A000108}, (Theorem 2), and we show that the maximum number of runs in a flattened parking function of length n is at most ⌈\frac{n}{2}⌉, see (Theorem 3). In Table 1, we provide data on the number of flattened parking functions of length n, which we then aggregate by k, the number of runs. We note that the sequence (flat(PF_{n}))_{n≥1} does not appear as a known sequence in the Online Encyclopedia of Integer Sequences (OEIS) [10]. In fact, it remains an open problem to provide a recursive formula for this sequence. Given this challenge, we restrict our study by considering a specific subset of parking functions that are created from permutations and (through an insertion process) made into parking functions.

n |flat(PF_{n})| |flat_{1}(PF_{n})| |flat_{2}(PF_{n})| |flat_{3}(PF_{n})| |flat_{4}(PF_{n})|
1 1  1  0  0  0
2 2  2  0  0  0
3 8  5  3  0  0
4 46  14  32  0  0
5 336  42  245  49  0
6 2937  132  1656  1149  0
7 29629  429  10563  17008  1629
8 336732  1430  65472  204815  65015

Table 1: Total flattened parking functions of length n, aggregated by k, the number of runs.

Let S be a multiset whose elements are in [n + 1] and let |S| denote the cardinality of S with multiplicity. Given a permutation π ∈ 𝔖_{n}, let I(S, π) be the set of words of length n + |S| constructed by inserting the elements of S into the permutation π in all possible ways. For example, if S = {1, 1} and π = 12, then I(S, π) = {1112, 1121, 1211}. Then, we define the set of S-insertion parking functions as the set

PF_{n}(S) := ⋃_{π∈𝔖_{n}} I(S, π).

We show in (Lemma 3) that for all multisets S with elements in [n + 1], the set PF_{n}(S) is a subset of PF_{n+|S|}. A parking function α ∈ PF_{n}(S) is said to be a S-insertion flattened parking function if it satisfies the properties of a flattened parking function; we let

flat(PF_{n}(S)) := {α ∈ PF_{n}(S) : α is flattened}

denote the set of S-insertion flattened parking functions and we let

flat_{k}(PF_{n}(S)) := {α ∈ PF_{n}(S) : α is flattened with k runs}

denote the set of S-insertion flattened parking functions with exactly k runs. For ease of notation, henceforth we let |flat(PF_{n}(S))| = f(S; n) and |flat_{k}(PF_{n}(S))| = f(S; n, k).

Given these definitions, in Section 3, we provide bijections between sets flat(PF_{n}(S)) and flat(PF_{n}(S′)) with S and S′ having certain relations. In Section 4, we focus on flattened 1_{r}-insertion flattened parking functions, where 1_{r} := {1, …, 1} with |1_{r}| = r. When r = 1, our results generalize many of the results provided by [8] from flattened partitions to {1}- insertion flattened parking functions. We then extend our study to r ≥ 2, in Theorem 37 we give a bijection between the elements of flat_{k+1}(PF_{n+1}(1_{r})) and set of set partitions of [n + r] satisfying the following conditions:

1. the first r numbers are in different subsets, and

2. there are exactly k blocks with at least two elements.

We define the (r, k)-Bell numbers, denoted B_{k}(n, r), as the cardinality of the set partitions described above, which generalize the sequence found in \underline{A124324} for r > 1. We remark that in our work we establish that the statistic k, which accounts for k +1 runs in the 1_{r}-insertion flattened parking functions and the k blocks of size at least 2 in the set partitions is preserved by our bijections. While Nabawanda et al. noted that the bijection was statistic preserving, they did not note that f_{n,k} is enumerated by \underline{A124234}.

With those results at hand, in Section 5, we attempted to generalize the work of Nabawanda et al. and study the exponential generating function of the numbers |flat_{k}(PF_{n}(1_{r}))| = f(1_{r}; n, k):

F (x, y, z) = ∑_{n≥0} ∑_{k≥0} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{y^{n}}{n!} \frac{z^{r}}{r!} = ∑_{n≥0} ∑_{r≥1} ∑_{α∈flat(PF_{n}(1_{r}))} x^{run(α)} \frac{y^{n}}{n!} \frac{z^{r}}{r!} .

However, we identify an error in the computation for the closed differential form provided in [8, p. 8]. We provide the details of this error, which we were unable to resolve. We leave it as an open problem to find or prove that no closed differential form exists, as well as then consider the corresponding generating function for our generalizations.

Section 6 provides our final set of results, where we generalize the results in Nabawanda et al. [2, 8] to 1_{r}-insertion flattened parking functions whose first s integers belong to different runs. In particular, we provide a generalization which involves compositions of r delineating the position of ones among the k runs. To conclude, we provide a variety of directions for future work.

2 Flattened parking functions

Throughout this paper, we work with both permutations and parking functions. For this reason, we abuse notation slightly in the following way: for α = (a_{1}, a_{2}, …, a_{n}) ∈ PF_{n}, we write α = a_{1}a_{2} ⋯ a_{n}. This way of writing the parking function as a word allows us to more easily go back and forth between parking functions and permutations, whose one line notation is written in this form.

As with permutations, the set of all parking functions of length n grows rapidly. This is why we study new classes of parking functions with particular properties.

Recall we generalized the notion of a run from permutations to parking functions by allowing weak ascents. This allows us to define the following class of parking functions.

Definition 1. A parking function π is said to be a flattened parking function if it consists of runs arranged from left to right such that their leading values are in weakly increasing order.

For example, note that the parking function 112233456 has a single run and is flattened and the parking function 14224222 is also flattened and has three runs. However, the parking function 7654321 is not flattened. We denote the set of all flattened parking functions of length n as flat(PF_{n}), and the set of flattened parking functions of length n with k runs as flat_{k}(PF_{n}). Table 1 provides data on the cardinalities of these sets for 1 ≤ k ≤ 4 and 1 ≤ n ≤ 8. Our first result connects these sets with the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}.

Theorem 2. If n ≥ 1, then |flat_{1}(PF_{n})| = C_{n}.

Proof. Flattened parking functions with one run are the same set as all weakly increasing parking functions, as a descent would mark the start of a new run. Armstrong, Loehr, and Warrington [1] proved that weakly increasing parking functions are in bijection with the Catalan numbers.

Theorem 3. The maximal number of runs for a flattened parking function of length n is ⌈\frac{n}{2}⌉.

Proof. Note that there cannot be a run of length one in the middle of a flattened parking function; if there is a run of length one aside from the last run, the leading value must be greater than the subsequent leading value. Hence the leading values would not fulfill the conditions for being flattened. So, every run besides the last run must have length at least two.

We now consider the parity of n. First, if n is odd, then there can only be one run of length one, and all other runs must be of length at least two. So, the maximal number of runs is given by

\frac{n − 1}{2} + 1 = ⌈\frac{n}{2}⌉ .

In the case where n is even, there can only be one run of length one. However, if there is one run of odd length, there must be a second run of odd length: in which case we have either one run of length one and one run of length three or more, or no runs of length one. Observe that having one run of length one and one run of length three does not yield a greater number of runs than the flattened parking function with all runs of length two. Thus, we can split n into runs of length two to get a maximal number of runs which is given by \frac{n}{2}. This is equivalent to ⌈\frac{n}{2}⌉.

With these initial results at hand we are now able to begin our study of S-insertion flattened parking functions.

3 S-insertion flattened parking functions

Similarly to how we restricted our focus from parking functions to flattened parking functions, we restrict further to a smaller subclass. First, we define a process by which we can construct parking functions from permutations.

Let 𝔖_{n} denote the set of permutations on [n] and let S be a multiset whose elements are in [n + 1] and let |S| denote the cardinality of S with multiplicity.

Definition 4. For a multiset S whose elements are in [n + 1], let I(S, π) be the set of words of length n + |S| constructed by inserting the elements of S into the permutation π ∈ 𝔖_{n} in all possible ways. Denote the set of S-insertion parking functions as the set PF_{n}(S) := ⋃_{π∈𝔖_{n}} I(S, π).

Remark 5. One might believe that the S-insertion procedure would yield all of the parking functions of length n + |S|. However, this is not true. For example, the parking function 111111119 of length 9 cannot be created from a permutation in 𝔖_{8}, as the smallest possible permutation in this list is the identity element on one letter, namely π = 1 ∈ 𝔖_{1}. Moreover, our insertion process would only allow S to contain the elements one and two, thereby never being able to insert the number 9.

We now show that all of the words created through the S-insertion process in Definition 4 produce parking functions.

Theorem 6. The set PF_{n}(S) := ⋃_{π∈𝔖_{n}} I(S, π) is a subset of PF_{n+|S|}.

Proof. Recall the well-known fact that a list of numbers x_{1}x_{2} ⋯ x_{n} with entries in [n] is a parking function if and only if its weakly increasing rearrangement x′_{1}x′_{2} ⋯ x′_{n} satisfies x′_{i} ≤ i for all i ∈ [n]. Now notice that if a = a_{1}a_{2} ⋯ a_{n} is a permutation in 𝔖_{n}, then in the extreme case where we insert S = {n + 1, n + 1, …, n + 1}, with |S| = m, into a yields a word whose weakly increasing rearrangement a′ satisfies a′_{i} ≤ i for all i ∈ [n + m]. Thus, inserting S into a would result in a parking function of length n + m = n + |S|, as desired. We conclude by noting that all other multisets S would result in the same inequalities being satisfied.

We now extend the definition of “flattened” to the set PF_{n}(S).

Definition 7. Let S be a multiset whose elements are in [n + 1] and let |S| denote the cardinality of S with multiplicity. A S-insertion flattened parking function is defined as a S-insertion parking function that is flattened. These S-insertion flattened parking functions are contained in the subset flat(PF_{n}(S)) ⊂ PF_{n}(S). Let flat_{k}(PF_{n}(S)) denote the subset of flat(PF_{n}(S)) where each parking function has exactly k runs.

By Theorem 3 we have shown that PF_{n}(S) ⊂ PF_{n+|S|}, and hence flat(PF_{n}(S)) ⊂ flat(PF_{n+|S|}).

Although our main focus in subsequent sections is on S-insertion flattened parking functions for the multiset S consisting of all ones, the following results provide interesting bijections between certain sets of S-insertion flattened parking functions.

Theorem 8. Let S be a multiset with elements in [n]\{1} and let S′ = {s−1 : s ∈ S}∪{1}. Then, the sets flat(PF_{n}(S)) and flat(PF_{n−1}(S′)) are in bijection.

Proof. Let |S| = m and note that |S′| = m + 1. Let a = a_{1}a_{2} ⋯ a_{n+m} ∈ flat(PF_{n}(S)). Define the map ψ : flat(PF_{n}(S)) → flat(PF_{n−1}(S′)), by ψ(a) = b_{1}b_{2} ⋯ b_{n+m}, where

b_{i} = \begin{cases}a_{1}, & if i = 1; \\ a_{i} − 1, & if 1 < i ≤ n + m. \end{cases}

We note that the function is well defined, as ψ(a) maps to a unique parking function. We also note that our function definition preserves flattenedness, since descents a_{i} ≥ a_{i+1} implies that b_{i} ≥ b_{i+1} is also a descent.

To show the map ψ is onto, let b = b_{1}b_{2} ⋯ b_{n+m} ∈ flat(PF_{n−1}(S′)). Observe that b is a parking function built from a permutation on [n − 1], with all m + 1 elements of S′ inserted into the permutation. Let b′ = b′_{1}b′_{2} ⋯ b′_{n+m} be such that

b′_{i} = \begin{cases}b_{1}, & if i = 1; \\ b_{i} + 1, & if 1 < i ≤ n + m. \end{cases}

Note that this new parking function, b′, contains only one one, namely b_{1} = b′_{i}. By construction of S′, and the fact that we now have at least one instance of all the numbers of [n], b′ is an element of flat(PF_{n}(S)). Now note that ψ(b′) = b, as desired.

To show the map ψ is one-to-one suppose that ψ(a) = ψ(c) = b_{1}b_{2} ⋯ b_{n+m}, for a = a_{1}a_{2} ⋯ a_{n+m} and c = c_{1}c_{2} ⋯ c_{n+m} in flat(PF_{n}(S)). By definition of ψ this means that b_{1} = a_{1} = c_{1} and for all 1 < i ≤ n + m, b_{i} = a_{i} − 1 = c_{i} − 1, which implies that a_{i} = c_{i}. Thus a_{i} = c_{i} for all 1 ≤ i ≤ n + m, establishing that a = c, as desired.

Therefore, we have shown that ψ is a bijection between the sets flat(PF_{n}(S)) and flat(PF_{n−1}(S′)), as claimed.

Theorem 9. Let S be a multiset with elements in [n − 2]. Then the sets flat(PF_{n}(S ∪ {n})) and flat(PF_{n}(S ∪ {n − 1})) are in bijection.

Proof. Let |S| = m, where s ∈ [n − 2] for all s ∈ S. Let a = a_{1}a_{2} ⋯ a_{n+m+1} ∈ flat(PF_{n}(S ∪ {n − 1})). Note that a contains the value n − 1 exactly twice, and our approach is to replace one of these with the value n. To do this we define the map ψ : flat(PF_{n}(S ∪ {n − 1})) → flat(PF_{n}(S ∪ {n})) with ψ(a) = b_{1}b_{2} ⋯ b_{n+m+1} where if 1 ≤ i < j < k ≤ n + m + 1 and

1. a_{i} = n − 1, a_{j} = n − 1, and a_{k} = n, then b_{s} = a_{s} for all s ≠ j, and b_{j} = n,

2. a_{i} = n − 1, a_{j} = n, and a_{k} = n − 1, then b_{s} = a_{s} for all s ≠ i, and b_{i} = n,

3. a_{i} = n, a_{j} = n − 1, and a_{k} = n − 1, then b_{s} = a_{s} for all s ≠ k, and b_{k} = n.

To show that the map ψ is well defined, first note that the entries in ψ(a) are those in the multiset [n] ∪ S ∪ {n}. In ψ(a) we replaced a single instance of n − 1 in a with the value n. This process keeps all weak ascents (and descents) in a as weak ascents (and descents) in ψ(a). This process also keeps the relative order of the leading value of the runs. Thus ensuring that ψ(a) is in flat(PF_{n}(S ∪ {n})).

We now construct the inverse. Let b ∈ flat(PF_{n}(S ∪ {n})). Note that b contains two instances of the value n and one instance of the value n−1. Define the map ϕ : flat(PF_{n}(S ∪ {n})) → flat(PF_{n}(S ∪ {n − 1})) with ϕ(b) = a_{1}a_{2} ⋯ a_{n+m+1} where if 1 ≤ i < j < k ≤ n + m + 1 and

Case 1. b_{i} = n − 1, b_{j} = n, and b_{k} = n, then a_{s} = b_{s} for all s ≠ j, and a_{j} = n − 1,

Case 2. b_{i} = n, b_{j} = n, and b_{k} = n − 1, then a_{s} = b_{s} for all s ≠ i, and a_{i} = n − 1,

Case 3. b_{i} = n, b_{j} = n − 1, and b_{k} = n, then a_{s} = b_{s} for all s ≠ k, and a_{k} = n − 1.

To show that the map ϕ is well defined, first note that the entries in ϕ(b) are those in the multiset [n] ∪ S ∪ {n − 1}. In ϕ(b) we replaced a single instance of n in b with the value n−1. This process keeps all weak ascents (and descents) in b as weak ascents (and descents) in ϕ(b). This process also keeps the relative order of the leading value of the runs. Thus ensuring that ϕ(b) is in flat(PF_{n}(S ∪ {n − 1})).

To conclude, note that ϕ is the inverse of ψ. This holds because for all 1 ≤ x ≤ 3, if b is as in Case x, then ϕ(b) = a gives a defined as in (x) above, and ψ(a) returns b, as desired.

In general, we can use the reasoning in Theorem 9 to produce the following bijection when there are only two runs.

Theorem 10. If 2 ≤ ℓ ≤ n, then the sets flat_{2}(PF_{n}({ℓ − 1})) and flat_{2}(PF_{n}({ℓ})) are in bijection.

Proof. Let a = a_{1}a_{2} ⋯ a_{n+1} ∈ flat_{2}(PF_{n}({ℓ − 1})) for some 2 ≤ ℓ ≤ n. Note that a contains the value ℓ − 1 exactly twice, and our approach is to replace one of these with the value ℓ. To do this we define the map ψ : flat_{2}(PF_{n}({ℓ − 1})) → flat_{2}(PF_{n}({ℓ})) with ψ(a) = b_{1}b_{2} ⋯ b_{n+1} where if 1 ≤ i < j < k ≤ n + 1 and

1. a_{i} = ℓ − 1, a_{j} = ℓ − 1, and a_{k} = ℓ, then b_{s} = a_{s} for all s ≠ j, and b_{j} = ℓ,

2. a_{i} = ℓ − 1, a_{j} = ℓ, and a_{k} = ℓ − 1, then b_{s} = a_{s} for all s ≠ i, and b_{i} = ℓ,

3. a_{i} = ℓ, a_{j} = ℓ − 1, and a_{k} = ℓ − 1, then b_{s} = a_{s} for all s ≠ k, and b_{k} = ℓ.

To show that the map ψ is well-defined, first note that the entries in ψ(a) are those in the multiset [n] ∪ {ℓ}. In ψ(a) we replaced a single instance of ℓ − 1 in a with the value ℓ. By construction we know that the resulting list ψ(a) is unique. We now claim that ψ(a) has exactly two runs. We argue based on which case a satisfies.

In item 1: replacing a_{j} = ℓ − 1 with the value ℓ means that, if a_{j} ended a run, then so does b_{j} = ℓ. If a_{j} did not end a run, that means that a_{j} = ℓ − 1 < a_{j+1} and a_{j+1} ≥ ℓ, which implies that replacing a_{j} = ℓ − 1 with ℓ also does not end the run. Thus, in case 1, the number of runs remains the same.

In item 2: we are replacing a_{i} = ℓ − 1 with the value ℓ. Note that a begins with two runs. If a_{i} = ℓ − 1 and a_{j} = ℓ are not in the same run, then we currently have at least two runs. However, a_{k} = ℓ − 1 and k > j implies that a_{k} would not be in the same run as a_{j}. Hence, a would have a minimum of three distinct runs, a contradiction. Thus, a_{i} = ℓ − 1 and a_{j} = ℓ must be in the same run, which implies they must be consecutive. That is, we know j = i + 1. In this case, replacing the subword (ℓ − 1)ℓ with ℓℓ keeps the number of runs at two runs, as desired.

In item 3: we are replacing a_{k} = ℓ − 1 with the value ℓ. Note that to begin a had two runs. This means that a_{i} = ℓ is in the first run, while both instances of ℓ − 1, in this case a_{j} and a_{k} are in the same run, and the only way for this to be true is for them to be consecutive. Moreover, a_{k+1} ≥ ℓ as the opposite inequality would imply there are at least three runs. Moreover, a_{k+1} > ℓ as the only instance of ℓ in a appeared at index i. Hence in a we replace the subword (ℓ − 1)(ℓ − 1) with (ℓ − 1)ℓ, which would not introduce a new run.

Therefore, under all assumptions, ψ(a) results in a unique element in flat_{2}(PF_{n}({ℓ})). Therefore, this process keeps all weak ascents (and descents) in a as weak ascents (and

descents) in ψ(a). This process also keeps the relative order of the leading value of the runs, ensuring that ψ(a) is in flat_{2}(PF_{n}({ℓ})).

We now construct the inverse. Let b be in flat_{2}(PF_{n}({ℓ})). Note that b contains two instances of the value ℓ and one instance of the value ℓ − 1. Define the map ϕ : flat_{2}(PF_{n}({ℓ})) → flat_{2}(PF_{n}({ℓ − 1})) with ϕ(b) = a_{1}a_{2} ⋯ a_{n+1} where if 1 ≤ i < j < k ≤ n + 1 and

Case 1. b_{i} = ℓ − 1, b_{j} = ℓ, and b_{k} = ℓ, then a_{s} = b_{s} for all s ≠ j, and a_{j} = ℓ − 1,

Case 2. b_{i} = ℓ, b_{j} = ℓ, and b_{k} = ℓ − 1, then a_{s} = b_{s} for all s ≠ i, and a_{i} = ℓ − 1,

Case 3. b_{i} = ℓ, b_{j} = ℓ − 1, and b_{k} = ℓ, then a_{s} = b_{s} for all s ≠ k, and a_{k} = ℓ − 1.

To show that the map ϕ is well-defined, first note that the entries in ϕ(b) are those in the multiset [n] ∪ {ℓ − 1}. In ϕ(b) we replaced a single instance of ℓ in b with the value ℓ − 1. As before, by construction, we know that ϕ(b) is unique. We now claim that ϕ(b) has exactly two runs. We argue based on which case b satisfies.

In Case 1: suppose first that b_{j} = ℓ ends the first run. Then since (ℓ − 1) is to the right, we must have the subword (ℓ − 1)ℓ b_{j+1}, where b_{j+1} < (ℓ − 1), as there is only one instance of ℓ − 1 in b. This subword maps to (ℓ − 1)(ℓ − 1) b_{j+1}, which preserves the run, and the descent in position y. Now suppose that b_{j} is in the middle of a run. Then we have the subword ℓ b_{j+1}, where b_{j+1} ≥ ℓ. This subword maps to (ℓ − 1)b_{j+1}, which also preserves the run. Thus, in case 1, the number of runs remains the same.

In Case 2: we are replacing b_{i} = ℓ with the value ℓ − 1. Note that b has two runs. As before, if b_{i} and b_{j} = ℓ are in separate runs, then we must have at least three runs in b. Thus, b_{i} and b_{j} must be in the same run, which implies that they are consecutive. That is, j = i + 1. Furthermore, b_{i−1} < ℓ − 1, as the only occurrence of ℓ − 1 appears to the right of b_{j}. In this case, the subword b_{i−1}ℓℓ maps to b_{i−1}(ℓ − 1)ℓ, which preserves the run.

In Case 3: we are replacing b_{k} = ℓ with the value ℓ − 1. Note that b has two runs. This means that b_{j} = ℓ − 1 and b_{k} must be in the second run, while b_{i} is in the first run. Because b_{j} = ℓ − 1 and b_{k} = ℓ are in the same run, we have k = j + 1. Moreover, b_{k+1} > ℓ, as the only other instance of ℓ appears to the left of b_{k}. Hence the subword (ℓ − 1)ℓb_{k+1} maps to (ℓ − 1)(ℓ − 1)b_{k+1}, which preserves the run.

This process keeps all weak ascents (and descents) in b as weak ascents (and descents) in ϕ(b). This process also keeps the relative order of the leading value of the runs, ensuring that ϕ(b) is in flat(PF_{n}({ℓ − 1})).

To conclude note that ϕ is the inverse of ψ. This holds as for all 1 ≤ x ≤ 3, if b is as in Case x, then ϕ(b) = a gives a defined as in (x) above, and ψ(a) returns b, as desired.

We remark that Theorem 10 is not true for all 2 ≤ ℓ ≤ n if the number of runs is not exactly two. For example, if n = 4 and ℓ = 3, then there are two elements in flat_{3}(PF_{4}({2})): 14232 and 13242. Using the map defined in the proof of Theorem 10, we have ψ(14232) = 14332, which is not flattened. By restricting our map to only two runs, we know exactly where the values ℓ−1 and ℓ are with respect to each other, and our map preserves the number of runs. In Theorem 9, we did not have to worry about this restriction to the number of runs, as the values n − 1 and n were extreme values that allowed us to preserve all ascents and descents we started with.

We now present the following enumerative result.

Theorem 11. If n ≥ 3 and ℓ ≥ 2, then |flat_{2}(PF_{n}({ℓ}))| = ∑_{i=0}^{n−3} 2^{i}(n − 1 − i).

The proof of Theorem 11 follows from the bijection in Theorem 10 and the following technical results, which provide a connection to tableaux enumerations.

Lemma 12 (\underline{A077802}). The sum of products of parts increased by one in hook partitions is

∑_{i=0}^{m−1} 2^{i}(m + 1 − i).

Proof. A hook partition on m boxes has i rows of exactly one box, such that 0 ≤ i ≤ m − 1, and one row of length m − i. In increasing each part by one, we add one box to each row, to get i rows of length two and a single row of length m − i + 1. Then, the product of the lengths of the rows is given by 2^{i}(m − i + 1). Finally, we sum the products over all possible hook partitions of size m. Note that each hook partition corresponds to exactly one value of i, giving the sum: ∑_{i=0}^{m−1} 2^{i}(m + 1 − i).

Lemma 13. If n ≥ 3, then |flat_{2}(PF_{n}({2}))| = ∑_{i=0}^{n−3} 2^{i}(n − 1 − i).

Proof. We prove this by induction on m = n − 2. If m = 1, then

∑_{i=0}^{m−1} 2^{i}(m + 1 − i) = 2.

We note that the set flat(PF_{3}({2})) = {1223, 1232, 1322} is formed by inserting a 2 into a permutation of 𝔖_{3}, and then only selecting the flattened parking functions. We are only interested in the subset flat_{2}(PF_{3}({2})), with two runs. In this case, there are two such elements: 1232 and 1322. So indeed, |flat_{2}(PF_{3}({2}))| = 2.

Suppose that ∑_{i=0}^{m−1} 2^{i}(m + 1 − i) = |flat_{2}(PF_{n}({2}))|, where n = m + 2. We now establish that the result hold for m + 1. Note that we can get some of the elements in flat_{2}(PF_{n+1}({2})) by inserting n + 1 into the elements in flat_{2}(PF_{n}({2})). Since we have two runs, we can insert n + 1 to the end of the first run or to the end of the second run. By induction, this gives 2 ∑_{i=0}^{m−1} 2^{i}(m + 1 − i) parking functions. We can also get elements of |flat_{n+1}(PF_{n} ({2}))| by inserting n + 1 into an element of flat_{(}PF_{n}({2})) with a single run, which increases the number of runs by one. Note that we only have one element with a single run, namely, when all elements are in weakly increasing order. In this case, we can insert n + 1 into any spot other than the end in order to increase the number of runs, as a descent always occurs after the inserted n + 1. Note that we have n = m + 2 such spots in which to insert the value n + 1, hence we have constructed m + 2 + 2 ∑_{i=0}^{m−1} 2^{i}(m + 1 − i) elements in flat_{2}(PF_{n+1}({2})). Now note that

m + 2 + 2 ∑_{i=0}^{m−1} 2^{i}(m + 1 − i) = m + 2 + ∑_{i=0}^{m−1} 2^{i+1}(m + 2 − (i + 1))

= m + 2 + ∑_{i=1}^{m} 2^{i}(m + 2 − i)

= ∑_{i=0}^{m} 2^{i}(m + 2 − i).

Thus, |flat_{2}(PF_{n}({2}))| = ∑_{i=0}^{m−1} 2^{i}(m + 1 − i).

We can now proceed to our main object of study, S-insertion flattened parking functions in the special case of S being the multiset consisting of all ones.

4 1_{r}-insertion flattened parking functions

In this section, we let S := 1_{r} = {1, …, 1} be the multiset containing r ≥ 1 ones. We then study families of flat(PF_{n}(1_{r})) for r ≥ 1. To highlight how our results generalize the work of Nabawanda, Rakotondrajao and Bamunoba in [8], we begin with Subsection 4.1 which contains the results in the special case of r = 1. We then further generalize to r ≥ 2 in Subsection 4.2.

4.1 The case of r = 1

In this section, we study the set flat(PF_{n}({1})), which is the case of flat(PF_{n}(1_{r})), with r = 1. Henceforth, we call this family of parking functions 1-insertion flattened parking functions.

Our work is motivated by the results of Nabawanda, Rakotondrajao and Bamunoba in [8]. In their work, they study F_{n,k}, which is the set of flattened partitions with k runs. They denote the cardinality of this set as f_{n,k}. In what follows we recall their recursions for f_{n,k}, and provide our generalizations thereafter.

4.1.1 Recursions for flat(PF_{n}({1}))

For sets of S-insertion flattened parking functions, we let f(S; n) denote the cardinality of flat(PF_{n}(S)), and f(S; n, k) denote the cardinality of flat_{k}(PF_{n}(S)). We begin by recalling the recurrence for the cardinality of flattened partitions of length n with k runs as given by Nabawanda et al. [8, Thm. 1, p. 4].

Theorem 14. For all integers n, k such that 2 ≤ k < n, the numbers f_{n,k} of flattened partitions of length n with k runs satisfy the following recurrence relation:

f_{n,k} = ∑_{m=1}^{n−2} (\binom{n − 1}{m} − 1) f_{m,k−1}.

The following result constructs elements of flat_{k}(PF_{n}({1})) using a similar argument as that in the proof of Theorem 14.

Theorem 15. For all integers n and k such that 2 ≤ k < n, the numbers f({1}; n, k) of 1-insertion flattened parking functions with k runs satisfy the following recurrence relation:

f(\{1\}; n, k) = ∑_{m=1}^{n−1} (\binom{n}{m} − 1) · f_{m,k−1}.  (1)

Proof. We begin constructing our 1-insertion flattened parking function γ by building the first run. Recall that every flattened parking function starts with a one and let γ = 1αβ where 1α denotes the first run and β contains the remaining k − 1 runs of γ. Note that αβ is a permutation of length n, and since k ≥ 2, we know that β cannot be empty.

Assume that α is of length m, where m satisfies 1 ≤ m ≤ n − 1. This ensures β is not empty. For a given m, there are \binom{n}{m} − 1 options for the elements in the first run, namely the entries in α. Note that the “-1” in our count comes from the fact that if α = 123 ⋯ m, then 1α would not be the entirety of the first run as the number beginning β would be larger than m and hence would be a part of the run 1α, contradicting the assumption that α has length m. Moreover, all other choices for the entries in α result in a unique first run where those elements appear in increasing order. Thus, there are \binom{n}{m} − 1 options for constructing the first run 1α.

Given the same value of m as before, we then construct the remaining k − 1 runs of γ, which are the entries in β. We know β must be flattened for the sequence 1αβ to be flattened, must contain k − 1 runs, and has length n − m. We claim that there are f_{n−m,k−1} choices for β. To see this, note that for each flattened partition with k − 1 runs, we simply replace the set {1, 2, 3, …, n−m} with the set of n−m numbers making up β and put them in the same relative order so as to create k − 1 runs that are flattened. Hence, each flattened partition of length n − m with k − 1 runs gives a unique possible β.

Finally, observe that our first run has minimum length 2 and maximum length n, in order to guarantee that we have at least two runs. So, this process holds for 1 ≤ m ≤ n − 1, giving us our final summation of f(\{1\}; n, k) = ∑_{m=1}^{n−1} (\binom{n}{m} − 1) f_{n−m,k−1}. To conclude, we note that

f(\{1\}; n, k) = ∑_{m=1}^{n−1} (\binom{n}{m} − 1) f_{n−m,k−1}

= ∑_{m=1}^{n−1} (\binom{n}{n − m} − 1) f_{n−m,k−1}

= ∑_{m=1}^{n−1} (\binom{n}{m} − 1) f_{m,k−1},

where the last equality follows from reindexing the sum.

Nabawanda et al. [8, Thm. 10, p. 6], constructed the following two term recursion.

Theorem 16. For all integers n, k such that 1 ≤ k < n, the number of flattened partitions of length n with k runs satisfies the following recursion:

f_{n,k} = kf_{n−1,k} + (n − 2)f_{n−2,k−1}.

The following is a generalization of Theorem 16 from flattened partitions to the set flat_{k}(PF_{n}({1})). This result allows us to consider the patterns present in a parking function that contain the largest letter n + 1.

Theorem 17. For all integers n, k such that 1 ≤ k < n, the number of 1-insertion flattened parking functions with k runs satisfies the recurrence relation

f({1}; n + 1, k) = k · f({1}; n, k) + (n − 1) · f({1}; n − 1, k − 1) + f_{n,k−1}.

Before we proceed with the proof of Theorem 17 we give some definitions and an initial result which provides a set partition of flat_{k}(PF_{n+1}({1})). We follow that with an example to illustrate the proof of Theorem 17. Recall that a word α is said to contain a subword w if there exists consecutive entries in α whose values are precisely the values in w in the same order. For example, α = 12315647 contains the subword 315 but not the subword 213. We remark that Nabawanda et al. [8] utilized the idea of patterns to describe these subwords. For simplicity we omit this technicality as subwords are enough to present our results.

Proposition 18. The set flat_{k}(PF_{n+1}({1})) can be partitioned (as a set) into the following four subsets:

1. elements ending with n + 1,

2. elements beginning with the subword 1(n + 1)1,

3. elements containing the subword a(n + 1)b with a < b,

4. elements containing the subword a(n + 1)b with a > b.

Proof. Let α ∈ flat_{k}(PF_{n+1}({1})) and note that α has exactly one instance of the element n + 1. It suffices to consider where the value n + 1 appears in α. First note that since α is flattened, then n + 1 cannot appear at the start of α. Thus, α contains n + 1 either at the end or between two other numbers. If n+1 appears at the end, then α is one of the elements of the subset of case 1. If n + 1 appears between two other numbers, then α contains the subword a(n + 1)b. In which case the following can occur: a = b, or a < b, or a > b. If a = b, then since α ∈ flat_{k}(PF_{n+1}({1})), the only repeated value is one, and so a = b = 1, which implies that α begins with the subword 1(n + 1)1. Hence, α is an element described in case 2. If a < b or a > b, then α is an element described in case 3 or case 4, respectively.

Below we provide an example to illustrate the set partition in Proposition 18 and the enumeration in Theorem 17.

Example 19. Let n + 1 = 4 and k = 3. By Proposition 18 we note that

(1) there are no elements in flat_{3}(PF_{4}({1})) ending with 4,

(2) there is one element in flat_{3}(PF_{4}({1})) beginning with the subword 141: 14132,

(3) there are two elements in flat_{3}(PF_{4}({1})) containing the subword a4b with a < b are: 13142 and 12143

(4) there are no elements in flat_{3}(PF_{4}({1})) containing the subword a4b with a > b.

Note that the number of elements from cases (1) and (4) is zero which is exactly the number f({1}; 3, 3) as there are no 1-insertion flattened parking functions of length four with three runs. The number of elements in case (2) is the number f_{3,2}, which is a permutation of length three with two runs, namely the permutation 132. Lastly, the number of elements in case (3) is the number 2 · f({1}; 2, 2), since f({1}; 2, 2) = 1, as the only 1-insertion flattened parking function of length three with two runs is 121. This shows that Theorem 17

f({1}; 4, 3) = f({1}; 3, 3) + 2 · f({1}; 2, 2) + f_{3,2} = 0 + 2 · 1 + 1 = 3.

The following proposition utilizes techniques of Nabawanda et al. [8, Thm. 9, p. 6].

Proposition 20. The subset of flat_{k}(PF_{n+1}({1})) containing elements with the subword a(n + 1)b where a > b or n + 1 at the end of the parking function is enumerated by

k · f({1}; n, k)

Proof. We start with 1-insertion parking functions of length n which have cardinality

f({1}; n, k).

To get the subword a(n + 1)b where a > b, we must place n + 1 where it will not increase the number of runs. Thus, n + 1 can be placed at the end of each run, including at the very end of the parking function, giving us k options for placement, and accounting for cases 1 and 4.

The following proposition utilizes techniques of Beyene and Mantaci [2, Lemma 25 and Proposition 26].

Proposition 21. The subset of flat_{k}(PF_{n+1}({1})) containing elements with the subword a(n + 1)b with a < b is enumerated by

(n − 1) · f({1}; n − 1, k − 1).

Proof. This proof is constructive. We begin by letting π be a parking function such that π ∈ flat_{k−1}(PF_{n−1}({1})). From π, we construct σ ∈ flat_{k}(PF_{n+1}({1})) such that σ contains the subword a(n + 1)b with 1 ≤ a < b ≤ n − 1.

To construct σ from π, we do the following procedure:

1. Fix a value 1 ≤ i ≤ n − 1.

2. Construct π′ from π by taking every element in π that is greater than i and adding one to each of those elements.

3. Then, insert the subword (n + 1)(i + 1) into π′ after the rightmost element of {1, …, i} in π′.

4. Call the resulting word σ.

We claim that σ ∈ flat_{k}(PF_{n+1}({1})). First note that from step 3, the length of σ is n + 2. Additionally, because π′ does not contain i + 1 or n + 1, we have exactly one instance of every letter j, where 2 ≤ j ≤ n + 1. Hence, σ consists of the letters in the multiset [n + 1] ∪ {1} as desired. Note that by construction of σ, wherever we inserted (n + 1)(i + 1), the value to the left of (n + 1)(i + 1) would never end a run, and hence, since n + 1 > i + 1, this insertion creates an additional run. Lastly, we are guaranteed that σ is flattened, since π ∈ flat_{k−1}(PF_{n−1}({1})) and by step 2 and 3 we inserted (n + 1)(i + 1) after all elements smaller than i + 1 and hence the number of runs to the left of the inserted (n + 1)(i + 1) remains fixed. Moreover, as all of the elements to the right of the newly inserted (n+1)(i+1) are larger than i + 1, we know that the number of those runs also remained fixed. Thus, the total number of runs in σ is equal to one more than the number of runs in π, which is (k − 1) + 1 = k. This establishes that σ ∈ flat_{k}(PF_{n+1}({1})).

Furthermore, this construction can be reversed. Suppose that σ ∈ flat_{k}(PF_{n+1}({1})) containing the subword a(n + 1)b with a < b. Since σ is flattened, removing the subword (n + 1)b from σ yields a new word σ′ of length n that is missing the value b, contains n, and has k − 1 runs. Take all the letters in σ′ that are greater than b and subtract one from each letter. This gives a word π that is in flat_{k−1}(PF_{n−1}({1})).

Given that we fixed the value i satisfying 1 ≤ i ≤ n − 1, we have n − 1 options for this integer. Hence, for each choice, we have created f({1}; n − 1, k − 1) options for π, yielding a total of (n − 1) · f({1}; n − 1, k − 1) parking functions in flat_{k}(PF_{n+1}({1})).

Finally, the following proposition is the piece that is unique to our parking functions.

Proposition 22. The subset of flat_{k}(PF_{n+1}({1})) containing elements with the subword 1(n + 1)1 is enumerated by

f_{n,k−1}.

Proof. Let σ ∈ F_{n,k−1}. In order to get a parking function in flat_{k}(PF_{n+1}({1})) that contains the subword 1(n + 1)1, we insert the subword 1(n + 1) to the start of σ. Since this is the only spot we can insert 1(n + 1) to contain the desired pattern and remain flat, we have that there are f_{n,k−1} parking functions obtained from this process.

We now return to Theorem 17.

Proof of Theorem 17. In Proposition 18, we showed that our four subsets partition

flat_{k}(PF_{n+1}({1})).

Using Propositions 20, 21, and 22, we have

f({1}; n + 1, k) = k · f({1}; n, k) + (n − 1) · f({1}; n − 1, k − 1) + f_{n,k−1}.

Finally, Nabawanda et al. [8, Thm. 12, p. 7] gave one more recursion for f_{n,k}.

Theorem 23. For all integers n, k such that 1 ≤ k ≤ n, the number of flattened partitions of length n + 2 with k runs satisfies the following recursion:

f_{n+2,k} = f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1}.

Our generalization of this recursion appears below. This recursion allows us to build a 1-insertion parking function of length n + 2 by considering whether or not the two ones appear in the same run or in distinct runs.

Theorem 24. For all integers n, k such that 1 ≤ k < n, the number of 1-insertion flattened parking functions with k runs satisfies the recurrence relation

f(\{1\}; n + 1, k) = f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n−i+1,k−1}.

Proof. We construct a 1-insertion flattened parking function π over [n + 1] with k runs. We consider the following two possibilities to enumerate f({1}; n + 1, k):

1. Suppose both ones are in the same run and π is of the form π = 1τ, where τ is a flattened partition of length n + 1 that begins with a one. Remove the first one, and note that what remains is a flattened partition of length n + 1 with k runs.

2. Suppose the two ones are in different runs. Let the first run have i + 1 terms including the first one. Since the one is fixed, we have i terms which can be chosen from the set \{2, 3, …, n + 1\}. There are \binom{n}{i} ways to do this. The remaining k − 1 runs have n+2−(i+1) = n−i+1 elements including the second instance of a one. Since the one is fixed, note that the remaining terms are all distinct values and behave exactly like a permutation in the set F_{n−i+1,k−1}, so they are enumerated by f_{n−i+1,k−1}. Thus, the total number of 1-insertion flattened parking functions with the two ones in separate runs is ∑_{i=1}^{n} (\binom{n}{i}f_{n−i+1,k−1}).

As the cases are disjoint, our count is given by

f(\{1\}; n + 1, k) = f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n−i+1,k−1}.

Theorem 24 implies that flat_{k}(PF_{n+1}({1})) and F_{n+2,k} are equinumerous. We use the recurrence relation provided in Theorem 24 when we study generating functions in Section 5.

We recall that the Bell numbers (\underline{A000110}), denoted B(n), counts the number of set partitions of [n] and has the exact same recurrence relation as that of f({1}; n, k) = f_{n+1,k}. This immediately implies the following.

Corollary 25. The cardinality of the set flat(PF_{n}({1})) is the Bell number B(n).

Also we recall that the Eulerian numbers, denoted A(n, 1), counts the number of permutations of length n with one descent. This is equivalent to the number of permutations of length n with tqo runs. This in turn implies the following.

Corollary 26. The cardinality of the set flat_{2}(PF_{n}({1})) is the Eulerian number A(n, 1).

Next we provide a more general result for the case when k > 2 as the values of f({1}; n+ 1, k) coincides with the triangle in \underline{A124324}. We remark that this result was not noted by Nabawanda et al. [8], though their data corresponds with ours.

Definition 27. Let T (n, k) denote the number of ways to partition the set [n] such that there are exactly k sets in the partition with at least two elements.

For example, if n = 3 and k = 1, the set partitions^{1} of [3] counted by T (3, 1) are 123, 1/23, 2/13, and 3/12, which are the only ways to partition [3] into subsets where exactly one of the subsets has two or more elements. Thus, we get T (3, 1) = 4.

Proposition 28. If n ≥ 1 and k ≥ 1, then f({1}; n, k + 1) = T (n, k).

1As is standard, when writing a set partition of [n] we use the notation “/” to separate the subsets used and we refer to each subset as a block.

Proof. We utilize the bijective map, f, given by Beyene and Mantaci [2, Proposition 11] and Nabawanda et al. [8, Proposition 16]. This map allows us to take a set partition of [n], and create a flattened partition of [n + 1]. Because the sets F_{n+1} and flat(PF_{n}({1})) are in bijection, we use this map to go from set partitions of [n] to flat(PF_{n}({1})). In what follows, we show that in fact the map f takes set partitions of [n] which have exactly k blocks with size greater than or equal to two, and maps them bijectively to flattened partitions with k+1 runs, which we have shown (Theorem 24) are in bijection with elements of flat(PF_{n}({1})).

To begin we let B = B_{1}/B_{2}/ ⋯ /B_{ℓ} be a set partition of [n] where exactly k of the blocks have size at least two and the remaining ℓ − k blocks consist of a single element. Moreover, we assume that min(B_{i}) < min(B_{i+1}) for all i ∈ [ℓ − 1]. For a block B_{i} with size at least two, we create a subword σ_{i} as follows: if B_{i} = {b_{1}, b_{2}, …, b_{m}} with b_{1} < b_{2} < ⋯ < b_{m}, we “cycle” the elements so that they are listed in the order b_{2}b_{3} ⋯ b_{m}b_{1} = σ_{i}. Note that when B_{i} consists of a single element we let the corresponding subword σ_{i} simply be that value. In this way we construct a word from the set partition B through concatenating the subwords to form the word σ_{1}σ_{2} ⋯ σ_{ℓ}. We then introduce a one at the start of the word σ_{1}σ_{2} ⋯ σ_{ℓ} to create a = 1σ_{1}σ_{2} ⋯ σ_{ℓ}.

We claim a is a 1-insertion flattened parking function with k + 1 runs. To prove this we begin by noting that in fact the entries in a consist of the elements in the set [n] ∪ {1}. Next we check the number of runs. First note that if B_{i} has size at least 2, then σ_{i} introduces a descent at its penultimate letter/index. Hence there are at least k descents, as there are k blocks of size at least 2. To see that there are exactly k descents, note that all remaining blocks have size one, and because the blocks are ordered based on their minimum values, they never introduce a new descent when creating a. This means that a has exactly k descents and hence k + 1 runs. The result is flattened since we placed a one at the start of a, which ensures that the first run begins with a one, and since the cycling process along with the ordering of the blocks based on their minimums being in increasing order, ensures that the runs in a satisfy that their leading values are in weakly increasing order. Thus, a is in flat_{k+1}(PF_{n}({1})).

So far, we have shown that under this map, f, an arbitrary set partition with exactly k blocks of size at least two produce an element in flat_{k+1}(PF_{n}({1})).

Now, suppose that we have an arbitrary element, α in flat(PF_{n}({1})). Suppose that, under f^{−1}, α maps to a set partition with exactly k blocks of size at least two, call this corresponding set partition B. We have shown that f(B) is in flat_{k+1}(PF_{n}({1})), and since f is bijective, we must have that f(B) = α. Therefore, α must have been an element in flat_{k+1}(PF_{n}({1})).

4.2 The case of r ≥ 2

Throughout we let 1_{r} denote the multiset consisting of r ones. In this section we extend our results to the case flat(PF_{n}(1_{r})) for r ≥ 2.

4.2.1 Recursions for flat(PF_{n}(1_{r}))

The following is a generalization of the result of Nabawanda et al. [8, Thm. 1, p. 4] and Theorem 15.

Theorem 29. For 2 ≤ k < n + r, the number of 1_{r}-insertion flattened parking functions is enumerated by the following recursion:

f(1_{r}; n, k) = ∑_{m=1}^{n−1} ∑_{i=1}^{r} \binom{n − 1}{m − 1} · f(1_{r−i}; m, k − 1) + ∑_{m=1}^{n−1} (\binom{n − 1}{m − 1} − 1) · f_{m,k−1}. (2)

Proof. To begin we remark that all elements in flat(PF_{n}(1_{r})) have exactly r + 1 ones. To construct an element in flat(PF_{n}(1_{r})), we fix i, the number of ones in the first run. Note that i satisfies 1 ≤ i ≤ r + 1.

Our first case is when 1 ≤ i ≤ r. In this case, there exists at least one 1 and at most r−i+1 ones in the last k − 1 runs. In order to be flattened, the first run has the form \underbrace{111 ⋯ 1}_{i} σ,

where σ is a non-empty word containing n − m values chosen from the set {2, 3, 4, …, n}. Note that this implies that 1 ≤ m ≤ n − 1. In this case there are \binom{n−1}{n−m} = \binom{n−1}{m−1} choices for the values in σ, which must be arranged in increasing order so as to construct the first run. Then, for a given σ, we construct the remaining k − 1 runs, by forming the word τ from the values in the complement of the set {2, 3, …, n} used to form σ along with the remaining r − i + 1 ones. This ensures that τ has length m + r − i.

To construct τ, we take an element of flat_{k−1}(PF_{m}(1_{r−i})), and arrange r − i ones, in addition to the m elements from {2, 3, 4, …, n} that are not included in σ. Again note that this ensures the length of τ is m + r − i, as expected. Each element α ∈ flat_{k−1}(PF_{m}(1_{r−i})) gives a unique τ, by arranging the values of τ in the same relative order as those in α. This yields f(1_{r−i}; m, k − 1) options for our last k − 1 runs which are formed by τ. By varying i from one to r and m from one to n − 1 we arrive at the left-most sum on the right hand-side of Equation (2).

The second case counts the number of 1-insertion parking functions with all ones in the first run. We construct such a parking function in a similar fashion, where σ and τ are arranged to get \underbrace{1111 ⋯ 1}_{r+1} στ. To construct a word σ of length n − m, we selected n − m

elements of \{2, 3, …, n\}, which we can do in \binom{n−1}{n−m} = \binom{n−1}{m−1} ways. We then eliminate the single case where the values of n − m are in increasing order 234 ⋯ n − m + 1, in which case the smallest value of τ would be greater than the greatest value of σ, so τ would not create a new run as required. This gives a total of \binom{n−1}{m−1} − 1 options for σ. Next, we have m elements of {2, 3, 4, …, n} that are not used in σ, which are used to create τ. Note that every α ∈ F_{m,k−1} gives a unique τ, by arranging the values of τ in the same relative order as those in α. This yields f_{m,k−1} options for our last k − 1 runs which are formed by τ. Thus, for each m ∈ [n − 1], there are (\binom{n−1}{m−1} − 1)f_{m,k−1} options for these 1_{r}-insertion parking functions in this case. By varying m from one to n − 1 we arrive at the right-most sum on the right hand-side of Equation (2).

As the two cases discussed are disjoint and account for all possibilities, their sum yields

f(1_{r}; n, k) = ∑_{m=1}^{n−1} ∑_{i=1}^{r} \binom{n − 1}{m − 1} · f(1_{r−i}; m, k − 1) + ∑_{m=1}^{n−1} (\binom{n − 1}{m − 1} − 1) · f_{m,k−1}.

The following is a generalization of the result of Nabawanda et al. [8, Thm. 10, p. 6] and Theorem 17.

Theorem 30. The cardinality of flat_{k}(PF_{n}(1_{r})) satisfies the recurrence relation

f(1_{r}; n + 1, k) = k · f(1_{r}; n, k) + (n − 1) · f(1_{r}; n − 1, k − 1) + r · f(1_{r−1}; n, k − 1).

The proof of Theorem 30 is a direct consequence of following technical results, which are analogous as those in the r = 1 case presented in the previous section.

Proposition 31. The set flat_{k}(PF_{n+1}(1_{r})) can be partitioned (as a set) into the following four subsets:

1. elements ending with n + 1,

2. elements beginning with the subword 1(n + 1)1,

3. elements containing the subword a(n + 1)b with a < b,

4. elements containing the subword a(n + 1)b with a > b.

Proof. This proof is identical to that of Proposition 18.

Proposition 32. The subset of flat_{k}(PF_{n+1}(1_{r})) containing the subword a(n + 1)b where a > b or n + 1 at the end of the parking function is enumerated by

k · f(1_{r}; n, k).

Proof. We start with 1_{r}-insertion flattened parking functions of length n which have cardinality f(1_{r}; n, k). To get the subword a(n + 1)b, where a > b, we must place n + 1 where it will not increase the number of runs. Thus, we can place n + 1 at the end of each existing run (which includes being at the very end of the parking function), giving us k options for placement, and accounting for cases 1 and 4.

Proposition 33. The subset of flat_{k}(PF_{n+1}(1_{r})) containing elements with the subword a(n+ 1)b with a < b is enumerated by

(n − 1) · f(1_{r}; n − 1, k − 1).

Proof. This proof is constructive. We begin by letting π be a parking function such that π ∈ flat_{k−1}(PF_{n−1}(1_{r})). From π we construct σ ∈ flat_{k}(PF_{n+1}(1_{r})) so that σ contains the subword a(n + 1)b with 1 ≤ a < b ≤ n − 1.

To construct σ from π we do the following procedure:

1. Fix a value 1 ≤ i ≤ n − 1.

2. Construct π′ from π by taking every element in π that is greater than i and adding one to each of those elements.

3. Then, insert the subword (n + 1)(i + 1) into π′ after the rightmost element of {1, …, i} in π′.

4. Call the resulting word σ.

We claim that σ ∈ flat_{k}(PF_{n+1}(1_{r})). First note that from step 3, the length of σ is n + 1 + r. Additionally, because π′ does not contain i + 1 or n + 1, we have exactly one instance of every letter j, where 2 ≤ j ≤ n+1. Hence, σ consists of the letters in the multiset [n + 1] ∪ 1_{r} as desired. Note that by construction of σ, wherever we inserted (n + 1)(i + 1), the value to the left of (n + 1)(i + 1) would never end a run, and hence, since n + 1 > i + 1, this insertion creates an additional run. Lastly, we are guaranteed that σ is flattened, since π ∈ flat_{k−1}(PF_{n−1} (1_{r})) and by steps 2 and 3 we inserted (n + 1)(i + 1) after all elements smaller than i + 1 and hence the number of runs to the left of the inserted (n + 1)(i + 1) remains fixed. Moreover, as all of the elements to the right of the newly inserted (n+1)(i+1) are larger than i + 1, we know that the number of those runs also remained fixed. Thus, the total number of runs in σ is equal to one more than the number of runs in π, which is (k − 1) + 1 = k. This establishes that σ ∈ flat_{k}(PF_{n+1} (1_{r})).

Furthermore, this construction can be reversed. Suppose that σ ∈ flat_{k}(PF_{n+1} (1_{r})) containing the subword a(n + 1)b with a < b. Since σ is flattened, removing the subword (n + 1)b from σ yields a new word σ′ of length n − 1 + r that is missing the value b, contains n, and has k − 1 runs. Take all the letters in σ′ that are greater than b, and subtract one from each letter. This gives a word π that is in flat_{k−1}(PF_{n−1} (1_{r})).

Given that we fixed the value i satisfying 1 ≤ i ≤ n − 1, we have n − 1 options for this integer. Hence, for each choice, we have created f (1_{r}; n − 1, k − 1) options for π, yielding a total of (n − 1) · f (1_{r}; n − 1, k − 1) parking functions in flat_{k}(PF_{n+1} (1_{r})).

Proposition 34. The subset of flat_{k}(PF_{n+1} (1_{r})) containing elements with the subword 1(n + 1)1 is enumerated by

r · f (1_{r−1}; n, k − 1) .

Proof. Let σ ∈ flat_{k−1}(PF_{n} (1_{r−1})). In order to get a parking function in flat_{k}(PF_{n+1} (1_{r})) that contains the subword 1(n + 1)1, we insert the subword 1(n + 1) to the start of σ. Since we can insert the subword 1(n + 1) to the left of every one in σ and remain flat, and since σ contains r ones, we have that there are r · f(1_{r−1}; n, k − 1) parking functions obtained from this process.

We now return to Theorem 30.

Proof. In Proposition 31, we showed that our four subsets partition flat_{k}(PF_{n} (1_{r})). Using Propositions 32, 33, and 34, we have

f(1_{r}; n + 1, k) = k · f(1_{r}; n, k) + (n − 1) · f(1_{r}; n − 1, k − 1) + r · f(1_{r−1}; n, k − 1).

The following is a generalization of the result of Nabawanda et al. [8, Thm. 12, p. 7] and Theorem 24.

Theorem 35. The cardinality of the set flat_{k}(PF_{n} (1_{r})) satisfies the following recursion:

f (1_{r}; n, k) = f (1_{r−1}; n, k) + ∑_{i=1}^{n−1} \binom{n − 1}{i} · f (1_{r−1}; n − i, k − 1) .

Proof. We construct an element π ∈ flat_{k}(PF_{n} (1_{r})). We consider the following two possibilities to enumerate f (1_{r}; n, k).

1. Suppose there is only a single one in the first run and let the length of the first run be i + 1. Then, the first run has a leading term of one and there are \binom{n−1}{i} options for the remaining elements in the first run. The remaining k − 1 runs follow the pattern of an element from flat_{k−1}(PF_{n−i}(1_{r−1})) which is enumerated by f(1_{r−1}; n − i, k − 1).

2. Suppose there is more than a single one in the first run, such that π is of the form 1τ, where τ is a flattened parking function of length n + r − 1. We remove the first instance of a one from π to get an element from flat_{k}(PF_{n}(1_{r−1})), which is enumerated by f(1_{r−1}; n, k).

Adding these two cases together gives

f(1_{r}; n, k) = f(1_{r−1}; n, k) + ∑_{i=1}^{n−1} \binom{n − 1}{i} · f(1_{r−1}; n − i − 1, k − 1).

We now recall that the r-Bell numbers enumerate the set of partitions of [n+r] such that the first r numbers are in different subsets. Let B(n, r) denote these numbers. We define the (r, k)-Bell numbers as follows.

Definition 36. Let B_{k}(n, r) be the number of set of partitions of [n + r] satisfying the following conditions:

1. the first r numbers are in different subsets

2. there are exactly k blocks with at least two elements.

Note that ∑_{k=0}^{n+r} B_{k}(n, r) = B(n, r), with some of the terms in the sum being zero based on the values of n, r, k. The following result proves that 1_{r}-insertion flattened parking functions with k + 1 runs are enumerated by the the (r, k)-Bell numbers.

Theorem 37. The set flat_{k+1}(PF_{n+1}(1_{r})) is enumerated by B_{k}(n, r).

Proof. We want to prove a bijection between the set of partitions of [n + r] with the first r numbers in different subsets and flat_{k+1}(PF_{n+1}(1_{r})). To begin let B = B_{1}/B_{2}/ ⋯ /B_{ℓ} be a set partition of [n + r] where the first r integers appear in different blocks. Hence, ℓ ≥ r. Moreover, since the order of the blocks does not affect the count, we assume that min(B_{i}) < min(B_{i+1}) for all i ∈ [ℓ − 1]. Suppose there are k blocks with size at least two and the remaining ℓ − k blocks consist of a single element. For a block B_{i} with size at least 2, we create a subword σ_{i} as follows: if B_{i} = {b_{1}, b_{2}, …, b_{m}} with b_{1} < b_{2} < ⋯ < b_{m}, we “cycle” the elements so that they are listed in the order b_{2}b_{3} ⋯ b_{m}b_{1} = σ_{i}. Note that when B_{i} consists of a single element we let the corresponding subword σ_{i} simply be that value. In this way we construct a word from the set partition B through concatenating the subwords to form the word σ_{1}σ_{2} ⋯ σ_{ℓ}. We then introduce a one at the start of the word σ_{1}σ_{2} ⋯ σ_{ℓ} to create a = 1σ_{1}σ_{2} ⋯ σ_{ℓ}. In σ_{1} ⋯ σ_{ℓ} replace the integers 1, 2, …, r with ones, so that now in a there are exactly r + 1 ones and the remaining numbers are strictly larger than r. We then subtract r − 1 from all other terms creating a parking function of length n + 1 + r, consisting of r + 1 ones and the integers 2, 3, …, n + 1.

We claim a is a 1_{r}-insertion flattened parking function with k + 1 runs. To prove this we begin by noting that in fact the entries in a consist of the elements in the set [n + 1] ∪ 1_{r}. Next we check the number of runs. Since the first r integers must appear in distinct blocks, and since we have ordered the blocks by their minimum values, this ensures that i ∈ B_{i} for each i ∈ [r]. If all of these sets are singletons, then 1σ_{1} ⋯ σ_{r} is replaced with r + 1 ones, which forms the beginning of the first run of a. Whenever B_{i}, for i ∈ [r], has size at least two we have introduced a descent through the cycling process used in forming the subword σ_{i}. As B_{i} includes i and all other numbers in B_{i} are strictly larger than r, then subtracting r − 1 from those entries keep the descent when forming a. This shows that the number of descents in a continues to be k, which is by assumption the number of blocks with at least two elements. Thus, a has k + 1 runs, as claimed.

Next we show that a is flattened. First note that since we placed a one at the start of a, we are ensured that the first run begins with a one. Next, based on the cycling process and the ordering of the blocks based on their minimums being in increasing order, ensures that the runs in 1σ_{1}σ_{2} ⋯ σ_{ℓ} satisfy that their leading values are in weakly increasing order. Replacing the numbers in [r] with all ones, does not change the fact that the leading terms of the runs are still in weakly increasing order. Thus, we know a is in flat_{k+1}(PF_{n+1}(1_{r})).

So far, we have shown that an arbitrary set partition with exactly k blocks of size at least two and whose first r integers appear in distinct blocks, produces an element in flat_{k+1}(PF_{n+1}(1_{r})). Now, suppose that we have an arbitrary element α in the set flat_{k+1}(PF_{n+1}(1_{r})). We construct the set partition of [n + r] where the first r integers appear in distinct blocks and there are exactly k blocks of size at least two, which yields α under our construction above. To begin we take the numbers 2, 3, …, n+1 in a and increase them by r − 1 so that they are now between r + 1, r + 2, …, r + n. Note that this keeps all of the descents and runs of a.

n \ k 1 2 3 4 5
1 1 0 0 0 0
2 1 2 0 0 0
3 1 7 2 0 0
4 1 18 18 0 0
5 1 41 97 12 0

Table of values for B_{k}(n, 2)

n \ k 1 2 3 4 5
1 1 0 0 0 0
2 1 4 0 0 0
3 1 13 12 0 0
4 1 32 84 24 0
5 1 71 391 312 24

Table of values for B_{k}(n, 4)

n \ k 1 2 3 4 5
1 1 0 0 0 0
2 1 3 0 0 0
3 1 10 6 0 0
4 1 25 45 6 0
5 1 56 219 96 0

Table of values for B_{k}(n, 3)

n \ k 1 2 3 4 5
1 1 0 0 0 0
2 1 5 0 0 0
3 1 16 20 0 0
4 1 39 135 60 0
5 1 86 613 720 120

Table of values for B_{k}(n, 5)

Table 2: The r-Bell numbers, aggregated further by requiring that there are exactly k blocks with at least two elements.

Now take the r + 1 ones in a and replace them with the numbers 1, 1, 2, …, r from left to right. Note that since those integers were all ones in a, by replacing them from left to right with the integers 1, 1, 2, …, r, we ensure that these values either remain the leading term of a run (and they are listed in weakly increasing order) or are still within the same run. Moreover, note that this process yields a word of length n + 1 + r with the letters in the set [n + r] ∪ {1}, with k + 1 runs. In Proposition 28 we have shown that this is in bijection with a set partition of [n + r] satisfying that there are exactly k blocks with at least two elements. It now suffices to show that the first r integers appear in distinct blocks. This follows from the bijective map f^{−1} given by Nabawanda et al. [8, Proposition 16], which ensures that our construction satisfies that the numbers 1, 2, …, r appear in this order from left to right corresponding to the “left-to-right” minima, which ensured that each of these elements appears in a distinct block.

By summing over k, Theorem 37 immediately implies the following.

Corollary 38. The set flat(PF_{n+1}(1_{r})) is enumerated by B(n, r), that is the n^{th} r-Bell number.

We conclude this section by noting that the numbers B_{k}(n, r) are a generalization of \underline{A124234} that include the notion that the first r integers are in distinct blocks. This sequence of numbers does not yet appear in the OEIS so we provide the Table 2 containing the values of B_{k}(n, r) for small values of k, n, r with r fixed.

5 Generating functions

In this section, we attempted give a closed differential form for the following exponential generating function:

F (x, y, z) = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{y^{n}}{n!} \frac{z^{r}}{r!} = ∑_{n≥1} ∑_{r≥1} ∑_{α∈flat(PF_{n}(1_{r}))} x^{run(α)} \frac{y^{n}}{n!} \frac{z^{r}}{r!} .

Note that, for r = 1, Theorem 24 implies that flat_{k}(PF_{n−1} ({1})) and F_{n,k} are equinumerous, immediately implying that the result of Nabawanda et al. [8, Thm. 13, p. 8] would hold for this case. However, as we attempted to generalize further, we identified an error in the result below.

Theorem 39. The exponential generating function F (x, y) of the run distribution over flat(PF_{n−1}({1})) has the closed differential form

\frac{∂F (x, y)}{∂y} = x exp(x(exp(y) − 1) + y(1 − x))

with initial condition \frac{∂F (x,0)}{∂y} = x.

We now detail our computations which show that Theorem 39 does not hold. Remark 40. Nabawanda et al. [8, Thm. 13, p. 8] claimed that

\frac{∂F}{∂y} = ∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{y^{n}}{n!} ,

which is not quite true. The partial derivative gives us

\frac{∂F}{∂y} = ∑_{n≥1} ∑_{k≥1} f_{n,k}x^{k} \frac{y^{n−1}}{(n − 1)!},

and

f_{1,k} = \begin{cases}1, & when k = 1; \\ 0, & otherwise. \end{cases}

Thus,

\frac{∂F}{∂y} = x + ∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{y^{n}}{n!} ,

which, to be fair, does line up with their claim that \frac{∂F (x,0)}{∂y} = x. Similarly, Nabawanda et al. [8, Thm. 13, p. 8] claimed that

\frac{∂^{2}F}{∂y^{2}} = ∑_{n≥1} ∑_{k≥1} f_{n+2,k}x^{k} \frac{y^{n}}{n!} ,

which is also not true. The second partial derivative gives us

\frac{∂^{2}F}{∂y^{2}} = ∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{y^{n−1}}{(n − 1)!},

and

f_{2,k} = \begin{cases}1, & when k = 1; \\ 0, & otherwise. \end{cases}

Thus,

\frac{∂^{2}F}{∂y^{2}} = x + ∑_{n≥1} ∑_{k≥1} f_{n+2,k}x^{k} \frac{y^{n}}{n!} .

Using this starting point, the result of Nabawanda et al. [8, Thm. 12, p. 7] produces the equality

\frac{∂^{2}F}{∂y^{2}} = \frac{∂F}{∂y} + \frac{∂F}{∂y} · x · (exp(y) − 1).

From our work above, this equality should actually be

\frac{∂^{2}F}{∂y^{2}} = x + (\frac{∂F}{∂y} − x) + (\frac{∂F}{∂y} − x) · x · (exp(y) − 1).

This reduces to

\frac{∂^{2}F}{∂y^{2}} = \frac{∂F}{∂y} + \frac{∂F}{∂y} · x · (exp(y) − 1) − x^{2} · (exp(y) − 1),

which is not solvable in the way claimed by Nabawanda et al. [8, Proof of Theorem 13].

Given the content of our remark above and the fact that our work relies on theirs, we conclude by providing the details of our analysis and where the lack of a solution to their differential equation prevents us from arriving at a closed form solution.

Remark 41. We have

F (x, y, z) = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!} = ∑_{n≥1} g_{n}(x, z)\frac{y^{n}}{n!} ,

where g_{n}(x, z) is the polynomial defined by ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{z^{r}}{r!} .

First, we see that

∫_{0}^{z} F (x, y, t)dt = ∫_{0}^{z} ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} · \frac{t^{r}}{r!} \frac{y^{n}}{n!} dt

= ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} · \frac{z^{r+1}}{(r + 1)!} \frac{y^{n}}{n!} .

Note that

\frac{∂F}{∂y} = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{y^{n−1}}{(n − 1)!} \frac{z^{r}}{r!} ,

where

f(1_{r}; 1, k) = \begin{cases}1, & when k = 1; \\ 0, & otherwise. \end{cases}

This means that, when n = 1, we have

∑_{k≥1} ∑_{r≥1} f(1_{r}; 1, k)x^{k} \frac{z^{r}}{r!} = ∑_{r≥1} f(1_{r}; 1, 1)x^{1} \frac{z^{r}}{r!} = x · exp(z),

and thus

\frac{∂F}{∂y} = x · exp(z) + ∑_{n≥2} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{y^{n−1}}{(n − 1)!} \frac{z^{r}}{r!}  (3)

= x · exp(z) + ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n + 1, k)x^{k} \frac{y^{n}}{n!} \frac{z^{r}}{r!} .  (4)

Shortly, we use this in order to see that

\frac{∂F}{∂y} − x · exp(z) = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n + 1, k)x^{k} \frac{y^{n}}{n!} \frac{z^{r}}{r!} .

From Theorem 35, and summing over n, and k, and r, we have

\frac{∂F}{∂y} = x · exp(z) + ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n + 1, k)x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!}

= x · exp(z) + ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r−1}; n + 1, k)x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!}

+ ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} (∑_{i=1}^{n} \binom{n}{i}f(1_{r−1}; (n + 1) − i, k − 1)) x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!} .

We define B as follows:

B := ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r−1}; n + 1, k)x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!} .

We note that simplifying B gives us (using both the derivative and integral forms we established above),

B = ∑_{n≥1} ∑_{k≥1} f(1_{0}; n + 1, k)x^{k} · \frac{z^{1}}{1!} \frac{y^{n}}{n!} + ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n + 1, k)x^{k} · \frac{z^{r+1}}{(r + 1)!} \frac{y^{n}}{n!}

= z (∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{y^{n}}{n!} ) + ∫_{0}^{z} (\frac{∂F (x, y, t)}{∂y} − x exp(t)) dt.

According to Remark 40, the result of Nabawanda et al. [8, Thm. 13, p. 8] should be

∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{y^{n}}{n!} = \frac{∂F (x, y)}{∂y} − x.

This implies that

B = z (\frac{∂F (x, y)}{∂y} − x) + ∫_{0}^{z} (\frac{∂F (x, y, t)}{∂y} − x exp(t)) dt.

Let

C = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} (∑_{i=1}^{n} \binom{n}{i}f(1_{r−1}; (n + 1) − i, k − 1)) x^{k} · \frac{z^{r}}{r!} \frac{y^{n}}{n!} .

Fixing i and summing over k and r in the next triple sum gives

C = ∑_{n≥1} ∑_{i=1}^{n} (∑_{k≥1} ∑_{r≥1} \binom{n}{i}f(1_{r−1}; (n + 1) − i, k − 1)x^{k} · \frac{z^{r}}{r!} ) \frac{y^{n}}{n!} .

Expanding the binomial coefficient for C, and factoring out an x, we have

C = x ∑_{n≥1} ∑_{i=1}^{n} \frac{y^{i}}{i!} (∑_{k≥1} ∑_{r≥1} f(1_{r−1}; n − i + 1, k − 1)x^{k−1} · \frac{y^{n−i}}{(n − i)!} \frac{z^{r}}{r!} ) .

Because n ≥ 1 and i ranges from one to n, we know n − i ranges from zero to n − 1. Simplifying and swapping the order of our sums and reindexing the inner sum indexed by n gives

C = x ∑_{i≥1} \frac{y^{i}}{i!} (∑_{n≥i} ∑_{k≥1} ∑_{r≥1} f(1_{r−1}; n − i + 1, k − 1)x^{k−1} · \frac{y^{n−i}}{(n − i)!} \frac{z^{r}}{r!} ) .

We have

C = x · B · (exp(y) − 1) .

Substituting and simplifying, we get

\frac{∂F}{∂y} = x · exp(z) + B + C.

Since we also were unable to give a closed form solution for B, we stopped our analysis here. Thus, we conclude with this open problem: Consider the exponential generating function

F (x, y, z) = ∑_{n≥1} ∑_{k≥1} ∑_{r≥1} f(1_{r}; n, k)x^{k} \frac{y^{n}}{n!} \frac{z^{r}}{r!} = ∑_{n≥1} ∑_{r≥1} ∑_{α∈flat(PF_{n}(1_{r}))} x^{run(α)} \frac{y^{n}}{n!} \frac{z^{r}}{r!} ,

and give a closed form.

6 1_{r}-insertion flattened parking functions with the first s terms in different runs

In this section, we consider r ≥ 1. We begin by stating the recursive result of Nabawanda et al. [8, Thm. 14, p. 10], which considers the first s integers in [n] being in separate runs.

Theorem 42. For all integers s, k, and n satisfying 1 ≤ s ≤ k < n, let f^{(s)}(n + s, k) represent the number of flattened partitions where the first s distinct integers are in separate runs. The numbers f^{(s)}(n + s, k) satisfy the recursion

f^{(s+1)}(n + s + 1, k) = ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1}, …, i_{s}}f(n + 1 − ∑_{j=1}^{s} i_{j} , k − s),

where we let f(n, k) := f_{n,k} denote the number of flattened partitions of length n with k runs.

Let f^{(s)}(1_{r}; n + s, k) represent the number of 1_{r}-insertion flattened parking functions where the first s integers are in separate runs. Note that this means that k ≥ s.

There are many cases to consider here: the ones can be separate from all the other s − 1 integers in many ways. Since there are r + 1 instances of the integer one in all 1_{r}-insertion flattened parking functions, we would have to consider all compositions of the integer r + 1 as options for how to distribute the ones among the k runs. Our general recurrence for f^{(s)}(1_{r}; n + s, k) takes into account all such options. However, we begin with some special cases that are used in the proof of our main result which are also direct generalizations of the work of Nabawanda et al. [8].

In the following result we suppose that all of the ones are contained in the same run. In this case, we recover the result of Nabawanda et al. [8, Thm. 14, p. 10].

Theorem 43. For all integers s, k, n, and r satisfying 1 ≤ s < k < n and r ≥ 1, let g^{(s)}(1_{r}; n + s, k) denote the number of 1_{r}-insertion flattened parking functions where the first s distinct integers are in separate runs and all ones are in the same run. The numbers g^{(s)}(1_{r}; n + s, k) satisfy the recursion

g^{(s+1)}(1_{r}; n + s + 1, k) = ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1}, …, i_{s}}f(n + 1 − ∑_{j=1}^{s} i_{j}, k − s).

Proof. Let π be an element in flat_{k}(PF_{n+s+1} (1_{r})) where the first s+1 distinct integers are in separate runs and all ones are in the first run. To maintain flattenedness, the first s + 1 runs begin with 1, 2, …, s, s + 1, respectively. Let i_{1} + r + 1, i_{2} + 1, i_{3} + 1, …, i_{s} + 1 be the lengths of the first s runs. Note that the leading terms of each run, as well as the placement of the ones, are fixed. Thus, we have i_{1} terms to arrange out of (n+s+1+r)−(s+1+r) = n terms for the first run, and there are \binom{n}{i_{1}} ways to do so. For the second run, we have i_{2} terms to arrange out of n−i_{1} terms, and there are \binom{n−i_{1}}{i_{2}} ways to do so. Repeating this process s times, yields \binom{n}{i_{1}}\binom{n−i_{1}}{i_{2}} ⋯ \binom{n−∑_{j=1}^{s−1} i_{j}}{i_{s}} = \binom{n}{i_{1},...,i_{s}} possibilities for the first way to arrange the entries in the first s runs. Now that the first s runs have been chosen, we consider the remaining n + 1 − ∑_{j=1}^{s} i_{j} elements that are arranged into the final k − s runs. The smallest number in this set is s + 1 by design, so it starts the (s + 1)th run. There are f(n + 1 − ∑_{j=1}^{s} i_{j}, k − s) possible ways to arrange the remaining elements into a flattened subword. Thus, we have a total of ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1},...,i_{s+r}}f(n + 1 − ∑_{j=1}^{s} i_{j}, k − s) words that are 1_{r}-insertion flattened parking functions where the first s + 1 distinct integers are in separate runs and all of the ones are in the first run, as desired.

Next, we consider the case where each one is contained in a distinct run, which again recovers the result of Nabawanda et al. [8, Thm. 14, p. 10].

Theorem 44. For all integers s, k, n, and r satisfying 1 ≤ s+r < k < n, let h^{(s)}(1_{r}; n+s, k) denote the number of 1_{r}-insertion flattened parking functions where the r ones and first s distinct integers are all in separate runs. The numbers h^{(s)}(1_{r}; n + s, k) satisfy the recursion

h^{(s+1)}(1_{r}; n + s + 1, k) = ∑_{i_{1},...,i_{s+r}≥1} \binom{n}{i_{1}, …, i_{s+r}}f(n + 1 − ∑_{j=1}^{s+r} i_{j}, k − s − r).

Proof. Let π be an element in flat_{k}(PF_{n+s} (1_{r})) where the r ones and first s + 1 distinct integers are in separate runs. Let i_{1} + 1, i_{2} + 1, i_{3} + 1, …, i_{s+r} + 1 be the lengths of the first s + r runs. Note that, to preserve flattenedness, the leading terms of each run are fixed. Thus, we have i_{1} terms to arrange out of (n + s + r + 1) − (s + r + 1) = n terms for the first run, and there are \binom{n}{i_{1}} ways to do so. For the second run, we have i_{2} terms to arrange out of n − i_{1} terms, and there are \binom{n−i_{1}}{i_{2}} ways to do so. Repeating this process s + r

times, we have \binom{n}{i_{1}}\binom{n−i_{1}}{i_{2}} ⋯ \binom{n−∑_{j=1}^{s−1} i_{j}}{i_{s}} = \binom{n}{i_{1},...,i_{s+r}} possibilities for the first s + r runs. The remaining k − s − r runs are determined by the integers not used in the first s + r runs. The smallest number in this set is s + 1 by design, so it starts the (s + 1 + r)th run. There are f(n + 1 − ∑_{j=1}^{s+r} i_{j}, k − s − r) possibilities for the pattern of these integers. Thus, we have a total of ∑_{i_{1},i_{2},...,i_{s+r}≥1} \binom{n}{i_{1},...,i_{s+r}}f(n + 1 − ∑_{j=1}^{s+r} i_{j}, k − s − r) words that are 1_{r}-insertion flattened parking functions where the first s + 1 distinct integers and the additional r ones are in separate runs.

Theorem 45. For all integers s, k, n, and r such that 1 ≤ s + r < k < n, let f^{(s)}(1_{r}; n + s, k) denote the number of 1_{r}-insertion flattened parking functions where the first s distinct integers are all in separate runs, with the ones in every possible composition of runs. The numbers f^{(s)}(1_{r}; n + s, k) satisfy the recursion

f^{(s+1)}(1_{r}; n + s + 1, k) =

∑_{x=1}^{r+1} (\binom{r}{x − 1} · ( ∑_{i_{1},...,i_{s+x−1}≥1} \binom{n}{i_{1}, …, i_{s+x−1}}f (n + 1 − ∑_{j=1}^{s+x−1} i_{j}, k − s − x + 1))) .

Proof. Let π be an element in flat_{k}(PF_{n+s} (1_{r})) where the r ones and first s + 1 distinct integers are in separate runs. We begin by counting the number of 1_{r}-insertion flattened parking functions such that the r + 1 ones are in x different runs, with at least a single one in each of the x runs, note that this necessitates 1 ≤ x ≤ r + 1. Recall from Theorem 44 that ∑_{i_{1},i_{2},...,i_{s+x}≥1} \binom{n}{i_{1},...,i_{s+x}}f(n + 1 − ∑_{j=1}^{s+x} i_{j}, k − s − x) counts the number of 1_{x}-insertion flattened parking functions with the first s + 1 integers in different runs. Observe that there are r + 1 − x ones that are missing for π to be a 1_{r}-insertion flattened parking function. We can arrange these ones in any of the first x runs without changing all other runs of π, and this continues to be flattened.

The number of ways to arrange the ones in the first x runs is the same as the number of integer compositions of r + 1 over x parts. Each part of such a composition indicates the number of ones in each run. This means that we can multiply by a coefficient of \binom{r}{x−1} to get the total number of 1_{r}-insertion flattened parking functions with the first s + 1 integers in different runs and all ones over x runs.

Then, to find the total number of 1_{r}-insertion flattened parking functions with the first s + 1 integers in different runs, we include the instances where all ones are in the same run, two different runs, up to r + 1 different runs. Hence the result is given by a sum over all possible values for x − 1, i.e., x = 1, 2, …, r + 1.

Remark 46. As in the previous section, we attempted to give a generalization of the result of Nabawanda et al. [8, Thm. 15, p. 10]. However, we again identified an error given the incorrect computation of Nabawanda et al. [8, Thm. 13, p. 8]. Given those errors, we ceased our analysis. Thus, we conclude with this open problem: Consider the exponential generating function F^{[s+1]}(x, u) for the numbers h^{(s+1)} (1_{r}, n + s + 1, k) and give a closed form.

7 Future directions

Aside from the generating function questions we posed in Remark 41 and Remark 46, we present two additional directions for further study: 1. the insertion process and bijections, 2. enumerating flattened parking functions with k runs. We expand on these future directions below.

In this paper, we introduced the S insertion process for permutations. which always created a parking function. We wonder if there are other bijections between related insertion sets, similar to the results we presented in Section 3. One could also expand to other S consisting of other repeated values to see what of our results can be generalized further.

Flattened parking functions still need more consideration. We provided some initial data on the enumeration of flattened parking functions of length n with k runs, but these sequences do not appear in the OEIS. Thus, it remains an open problem to provide recurrences or formulas enumerating these combinatorial objects.

8 Acknowledgments

The authors were supported by the National Science Foundation under Grant No. DMS-1929284 while in residence at the Institute for Computational and Experimental Research in Mathematics in Providence, RI. We thank ICERM for funding support and extend our gratitude to Susanna Fishel and Gordon Rojas Kirby for many helpful conversations throughout the writing of this manuscript. The authors also extend their thanks to Alexander Woo for key insights which helped establish Lemma 12. P. E. Harris was supported through a Karen Uhlenbeck EDGE Fellowship.

References

[1] D. Armstrong, N. A. Loehr, and G. S. Warrington, Rational parking functions and Catalan numbers, Ann. Comb. 20 (2016), 21–58.

[2] F. Beyene and R. Mantaci, Merging-free partitions and run-sorted permutations, J. Integer Sequences 25 (2022), Article 22.7.6.

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

[4] J. Elder, N. Lafreniére, E. McNicholas, J. Striker, and A. Welch, Homomesies on permutations: an analysis of maps and statistics in the FindStat database, arxiv preprint arXiv:2206.13409 [math.CO], 2022. Available at https://arxiv.org/abs/2206.13409.

[5] I. M. Gessel, Generating functions and enumeration of sequences, Thesis (Ph.D.)– Massachusetts Institute of Technology, 1977, http://dspace.mit.edu/handle/1721.

1/16342.

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

[7] T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, Discrete Math. 338 (2015), 1989–2005.

[8] O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run distribution over flattened partitions, J. Integer Sequences 23 (2020), Article 20.9.6.

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

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

at https://oeis.org.

[11] J. Steinhardt, Permutations with ascending and descending blocks, Electron. J. Combin. 17 (2010), #R14.

[12] C. H. Yan, Parking Functions, in M. Bóna, ed., Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 835–893.

[13] Y. Zhuang, Counting permutations by runs, J. Combin. Theory Ser. A 142 (2016), 147–176.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A10, 05A15, 05A17, 05A18. Keywords: flattened parking function, recurrence relation, run, set partition.

(Concerned with sequences \underline{A000108}, \underline{A000110}, \underline{A077802}, and \underline{A124324}.)

Received October 25 2022; revised versions received October 26 2022; March 31 2023; June 5 2023; June 7 2023; June 9 2023. Published in Journal of Integer Sequences, June 10 2023.

Return to Journal of Integer Sequences home page.