Merging-Free Partitions and Run-Sorted Permutations

Fufa Beyene Department of Mathematics Addis Ababa University Addis Ababa 1176 Ethiopia

                          fufa.beyene@aau.edu.et

Roberto Mantaci IRIF, Université de Paris 8, Place Aurélie Nemours, 75013 France

                              mantaci@irif.fr

Abstract

In this paper, we study merging-free partitions and run-sorted permutations. We give a combinatorial proof of the conjecture made by Nabawanda et al. We describe the distribution of the statistics of runs and right-to-left minima over the set of runsorted permutations, and we give the exponential generating function for their joint distribution. We show that the distribution of right-to-left minima is the shifted distribution of the Stirling number of the second kind. We also prove that the number of non-crossing merging-free partitions is a power of 2. We use one of the constructive proofs given in the paper to implement an algorithm for the exhaustive generation of run-sorted permutations by the number of runs.

1 Introduction

Given a non-empty finite subset A of positive integers, a set partition P of A is a collection of disjoint, non-empty subsets of A, called blocks of A, such that every element of A belongs to exactly one subset [?, ?]. We shall use the notation [n] := {1, 2, …, n}, where n is a fixed positive integer. It is well known that the set partitions over [n] and set partitions over [n] having k blocks are counted by the Bell numbers, b_{n}, and Stirling numbers of the second kind, S(n, k), respectively [?, ?, ?]. Mansour [?] defined the block representation of a set partition where the elements in a block are arranged increasingly, and the blocks are arranged in increasing order of their first elements. Mansour also gave a way to encode a set partition (in its block representation) by its canonical form, i. e., every integer is encoded by the number of the block it belongs to. We note that canonical forms of set partitions coincide with the so-called restricted growth functions (RGF).

Callan [?] introduced the “flattening” operation (Flatten) on set partitions, which acts in such a way that a permutation σ is obtained from a set partition P by removing the separators enclosing the different blocks of P in its block representation. For example, the block representation of the set partition P = {1, 2, 6}, {3}, {4, 8}, {5, 7} is P = 126/3/48/57, and so we remove the separators “/” and obtain the permutation σ = 12634857. As a result of Callan’s work, such objects are getting the attention of different researchers, and several new findings are emerging [?, ?, ?].

In the literature, permutations obtained this way are sometimes called “flattened partitions”. We found this term somewhat confusing because these objects are permutations and not partitions, consequently, since the runs of the resulting permutations are sorted by the increasing values of their respective minima, we chose to adopt the term run-sorted permutations already used by Alexandersson and Nabawanda [?]. Run-sorted permutations are counted by the shifted Bell numbers [?].

The same permutation can be obtained by flattening several set partitions. For instance, the permutation σ = 12634857 can also be obtained by flattening the set partition P′ = 126/348/57. Among all the set partitions having the same Flatten, we will distinguish the only one whose number of blocks is the same as the number of runs of the permutation obtained by flattening it (this is the set partition P′ for the permutation σ). For obvious reasons we named these objects merging-free partitions. The Flatten operation clearly becomes injective and hence a bijection if restricted to the set of merging-free partitions.

In this article, we study some properties of run-sorted permutations as well as of mergingfree partitions and their canonical forms, we compute the distribution of the number of runs and the number of right-to-left minima on these sets, we relate these classes to the class of separated partitions, we study non-crossing merging-free partitions, and we provide an exhaustive generation algorithm for the run-sorted permutations partitioned by the number of runs. In particular, in Section 2, we give a characterization of the canonical forms of merging-free partitions, and we show that they can be bijectively related to RGFs of one size smaller.

In Section 3, we give a combinatorial bijective proof of a recurrence relation in Theorem 25 satisfied by run-sorted permutations over [n] having k runs, a recurrence relation that was conjectured by Nabawanda et al. [?]. We also give the interpretation of the proof of the same result by working on the canonical forms of merging-free partitions.

In Section 4.1, we prove that the distribution of right-to-left minima over run-sorted permutations is the same as the distribution of the number of blocks over set partitions of one size smaller (and also given by the shifted Stirling number of the second kind). We refine the recurrence relation satisfied by the number of run-sorted permutations over [n] having k runs by counting these permutations by the number of runs and by the number of right-to-left minima simultaneously, and we obtain an exponential generating function for the associated three-variables formal series. Munagi [?] proved that the set partitions over [n] having k blocks such that no two consecutive integers are in the same block are also counted by the shifted Stirling numbers of the second kind. So, in this section, we also show that these partitions bijectively correspond to run-sorted permutations over [n] having k right-to-left minima.

The set of non-crossing partitions is a Catalan enumerated object introduced in the founding work of Becker [?] and later deeply studied by different eminent scholars like Kreweras and Simion [?, ?]. In Section 5, we present the non-crossing merging-free partitions. We enumerate them according to their number of blocks, and we show that the total number of such partitions is a power of 2.

Finally, Section ?? presents an exhaustive generation algorithm for the run-sorted permutations partitioned by the number of runs, based on the recurrence relation proved in Theorem 25 and using the classical dynamic programming techniques.

1.1 Definitions, notation, and preliminaries

Definition 1. A set partition P of [n] is defined as a collection B_{1}, …, B_{k} of nonempty disjoint subsets [n] such that ∪_{i=1}^{k}B_{i} = [n]. The subsets B_{i} will be referred to as “blocks”.

Definition 2. The block representation of a set partition P is P = B_{1}/ ⋯ /B_{k}, where the blocks B_{1}, …, B_{k} are sorted in such way that min(B_{1}) < min(B_{2}) < ⋯ < min(B_{k}) and the elements of every block are arranged in increasing order.

We will always write set partitions in their block representations. We let SP(n) denote the set of all set partitions over [n] and b_{n} = | SP(n)|, the n-th Bell number.

Definition 3. The canonical form of a set partition of [n] is an n-tuple indicating the block in which each integer occurs, i. e., f = f(1)f(2) ⋯ f(n) such that j ∈ B_{f(j)} for all j ∈ [n].

Example 4. If P = 138/2/47/56 ∈ SP(n), then its canonical form is f = 12134431.

Definition 5. A restricted growth function (RGF) over [n] is a function f : [n] ↦ [n], where f = f(1) ⋯ f(n) such that f(1) = 1 and f(i) ≤ 1 + max{f(1), …, f(i−1)} for 2 ≤ i ≤ n, or equivalently, such that the set {f(1), f(2), …, f(i)} is an integer interval for all i ∈ [n].

The canonical forms of set partitions are exactly the restricted growth functions (RGF). We let RGF(n) denote the set of all restricted growth functions over [n]. We will denote f ∈ RGF(n) as a word f_{1}f_{2} ⋯ f_{n} over the alphabet [n], where f_{i} = f(i). We define the set of left-to-right maxima of f by

LrMax(f) = {i : f_{i} > f_{j}, 1 ≤ i ≤ n, j < i},

and the set of weak left-to-right maxima of f by

WLrMax(f) = {i : f_{i} ≥ f_{j}, 1 ≤ i ≤ n, j < i},

We also use the notation lrmax(f) := | LrMax(f)| and wlrmax(f) := | WLrMax(f)|.

Example 6. Take f = 121132342 ∈ RGF(9). We have LrMax(f) = {1, 2, 5, 8} and WLrMax(f) = {1, 2, 5, 7, 8}.

A permutation π over [n] is a bijective map π : [n] ↦ [n]. From now on, we will use the one-line notation to represent π, i. e., we write π = π_{1}π_{2} ⋯ π_{n}, where π_{i} = π(i), ∀i ∈ [n]. In particular, every permutation can be considered as a word of length n, with letters in [n]. We define the set of right-to-left minima of π by

RlMin(π) = {π_{i} : π_{i} < π_{j}, j > i},

and we use the notation rlmin(π) := | RlMin(π)|.

Definition 7. A maximal increasing subsequence of consecutive letters of a permutation π is called a run.

Definition 8. [?] A flattening of a set partition is an operation by which we obtain a permutation from the set partition P = B_{1}/ ⋯ /B_{k} by concatenating its blocks. We denote the resulting permutation by π = Flatten(P).

If a permutation is obtained by flattening a set partition, then its runs are ordered in such a way that the minima of the runs are increasing, therefore, we will call all permutations in Flatten(SP(n)) run-sorted permutations. We let RsP(n) := Flatten(SP(n)) and r_{n} := | RsP(n)|.

Definition 9. A merging-free partition is a set partition P = B_{1}/ ⋯ /B_{k} such that for 1 ≤ i ≤ k−1, max(B_{i}) > min(B_{i+1}).

Remark 10. Merging-free partitions over [n] and run-sorted permutations over [n] are in bijection, because the restriction of Flatten to the merging-free partitions is a bijection.

Proposition 11. [?, Section 4] The number of set partitions over [n] and the number of run-sorted permutations over [n + 1] (and therefore, the number of merging-free partitions over [n + 1]) are equal. That is, r_{n+1} = b_{n} for all n ≥ 0.

To prove the above result, the authors provided a bijection α : SP(n) ↦ RsP(n + 1), which can be described as follows. Let P = B_{1}/ ⋯ /B_{k} ∈ SP(n). Then π = α(P) is constructed as follows: move each minimum element of the block to the end of its block, remove the slashes, increase every integer by 1, and finally attach the integer 1 at the front. Conversely, we construct the set partition over [n] corresponding to a run-sorted permutation π ∈ RsP(n + 1) as follows. Put a slash after each right-to-left minimum of π, then delete the integer 1, decrease the remaining integers by 1, and finally arrange the elements of each block in increasing order.

Example 12. If P = 14/258/37/6 ∈ SP(8), then we have π = 152693847 ∈ RsP(9). Conversely, for π = 152693847 ∈ RsP(9) we have RlMin(π) = {1, 2, 3, 4, 7}. So by putting a slash after each right-to-left minimum we obtain 1/52/693/84/7 ⟶ 14/258/37/6 = P.

2 Canonical forms of merging-free partitions

In this section, we characterize the RGFs corresponding to merging-free partitions and we present some results related to these canonical forms.

Remark 13. Let f = f_{1} ⋯ f_{n} be the canonical form of a set partition P = B_{1}/ ⋯ /B_{k} over [n] having k blocks. We have i ∈ LrMax(f) if and only if i = min(B_{f_{i}}).

If i ∈ LrMax(f), then we call f_{i} the left-to-right maximum letter. We let T_{n} denote the set of all RGFs f = f_{1}f_{2} ⋯ f_{n} over [n] satisfying the condition that every left-to-right maximum letter s > 1 of f has at least one occurrence of s−1 on its right.

Proposition 14. Let P ∈ SP(n) and let f ∈ RGF(n) be the canonical form of P. Then P is merging-free if and only if f ∈ T_{n}.

Proof. If P = B_{1}/B_{2}/ ⋯ /B_{k} is a merging-free partition having k blocks, then min(B_{s−1}) < min(B_{s}) and max(B_{s−1}) > min(B_{s}), s = 2, …, k. Note that every leftmost occurrence of a letter in f is a left-to-right maximum letter. The positions of the leftmost and rightmost occurrences of the letter s in f correspond to the minimum and the maximum elements of the block B_{s}, respectively. Thus, if 1 < s ≤ k, then f_{min(B_{s})} = s and f_{max(B_{s−1})} = s − 1. Conversely, consider f ∈ T_{n}. Let i ∈ LrMax(f), where f_{i} > 1. Then, by definition, there is at least one integer j > i such that f_{j} = f_{i}−1. Let us choose j as the maximum of such integer(s). Thus, B_{f_{j}} = B_{f_{i}−1} and j = max(B_{f_{i}−1}). Since i = min(B_{f_{i}}), we have j > i and hence the corresponding set partition P is merging-free.

Definition 15. Let f = f_{1}f_{2} ⋯ f_{n} ∈ RGF(n). If the occurrence of the letter f_{i} in f has no repetition, then we say that f_{i} is unique in f, i. e., f_{i} is unique if and only if i forms a singleton block in the partition. A weak left-to-right maximum i in f for which there exists i_{0} < i such that f_{i} = f_{i_{0}} is called a non-strict left-to-right maximum.

We shall translate a combinatorial proof of Proposition 11 in terms of canonical forms. For each i ∈ [n] we define u_{i} as the number of unique left-to-right maximum letters of f in the positions 1, …, i − 1 that are smaller than f_{i}. We let u = (u_{1}, …, u_{n}). Let δ = (δ_{1}, …, δ_{n}), where

δ_{i} = \begin{cases}1, & if f_{i} is a non-unique left-to-right maximum letter of f; \\ 0, & otherwise. \end{cases}

Define a mapping α : RGF(n) ↦ T_{n+1}, where T_{n+1} is the set of canonical forms of merging-free partitions over [n + 1], by α(f) = 1 · f′, i. e., a concatenation of 1 and f′, where f′ = f′_{1} ⋯ f′_{n} is obtained from f as follows:

f′ = f − u + δ.

Example 16. If f = 1213124 ∈ RGF(7), then f_{1} = 1 and f_{2} = 2 are non-unique left-to-right maximum letters, while f_{4} = 3 and f_{7} = 4 are the unique ones. So, u = (0, 0, 0, 0, 0, 0, 1) and δ = (1, 1, 0, 0, 0, 0, 0). Thus, f′ = f − u + δ = 2313123 and α(f) = 1 · f′ = 12313123 ∈ T_{8}.

Lemma 17. If f ∈ RGF(n) and f′ is obtained from f as in the above construction, then LrMax(f) ⊆ WLrMax(f′).

Proof. Let LrMax(f) = {i_{1}, … i_{k}}. For j = 2, …, k, we have f_{i_{j}} = f_{i_{j−1}} + 1 and

u_{i_{j}} = \begin{cases}u_{i_{j−1}} + 1, & if f_{i_{j−1}} is unique; \\ u_{i_{j−1}}, & otherwise. \end{cases}

If f_{i_{j}} is unique, then δ_{i_{j}} = 0, and in either cases we have

f′_{i_{j}} = f_{i_{j}} − u_{i_{j}} = f′_{i_{j−1}}.

If f_{i_{j}} is non-unique, then δ_{i_{j}} = 1, and in either cases we have

f′_{i_{j}} = f_{i_{j}} − u_{i_{j}} + 1 = f′_{i_{j−1}} + 1.

Therefore, in all of the cases we have f′_{i_{j}} ≥ f′_{i_{j−1}}. Consider the intermediate values (if any), i. e., i_{j−1} < i < i_{j}. We show that f′_{i} < f′_{i_{j−1}}. There is some i_{ℓ} < i such that f_{i} = f_{i_{ℓ}} and then u_{i} = u_{i_{ℓ}}. Thus, f′_{i} = f_{i} − u_{i} = f′_{i_{ℓ}} − 1 < f′_{i_{ℓ}} because δ_{i} = 0 and δ_{i_{ℓ}} = 1. Since f′_{i_{ℓ}} ≤ f′_{i_{j−1}}, we have f′_{i} < f′_{i_{j−1}}. Therefore, i_{j}’s are the weak left-to-right maxima of f′.

Remark 18. The above lemma implies that the set of left-to-right maxima of f′ is the set of non-unique left-to-right maxima of f.

Lemma 19. For all f ∈ RGF(n) we have that α(f) ∈ T_{n+1}.

Proof. By construction f′_{i} ≤ f_{i}+1, ∀i ∈ [n]. Thus, 1·f′ ∈ RGF(n+1), where f′ = f′_{1}f′_{2} ⋯ f′_{n}. If f′_{i} > 1 is a left-to-right maximum letter in 1 · f′, then by Remark 18 f_{i} is a non-unique left-to-right maximum letter in f. This implies that there is some j > i such that f_{i} = f_{j}. Thus u_{i} = u_{j}, δ_{j} = 0. So, α(f)(i) = f′_{i} = f_{i} − u_{i} + 1 = f′_{j} + 1. Therefore, every left-to-right maximum letter s > 1 of 1·f′ has some occurrence s−1 from its right. Hence 1·f′ ∈ T_{n+1}.

We now define a map β : T_{n+1} ↦ RGF(n) which associates each 1·g = 1·g_{1} ⋯ g_{n} ∈ T_{n+1} with a function g′ = β(1 · g) = g′_{1}g′_{2} ⋯ g′_{n}, where g′ is obtained from g as follows. For each i ∈ [n], we let v_{i} denote the number of non-strict left-to-right maximum letters in g that are less than or equal to g_{i} in the positions 1, …, i − 1. We let v = (v_{1}, …, v_{n}). Further, let δ′ = (δ′_{1}, …, δ′_{n}), where

δ′_{i} = \begin{cases}1, & if g_{i} is a left-to-right maximum of g; \\ 0, & otherwise. \end{cases}

Then,

g′ = g + v − δ′.

For instance, if 1 · g = 122134321 ∈ T_{9}, then g = 22134321, v = (0, 0, 0, 1, 1, 1, 1, 0), and δ′ = (1, 0, 0, 1, 1, 0, 0, 0). Thus, g′ = 12134431 ∈ RGF(8). Note that β = α^{−1}. As a result, we have the following proposition.

Proposition 20. The mapping α from the set RGF(n) to the set T_{n+1} is a bijection.

Corollary 21. If f ∈ RGF(n) and α(f) = 1 · f′, then LrMax(f) = WLrMax(f′).

We now evaluate the number ℓ_{n} of f ∈ RGF(n) having the sequence u = 0, i. e., if f = f_{1}f_{2} ⋯ f_{n}, then for each i ∈ [n] there is no unique left-to-right maximum letter smaller than f_{i} on its left. The set partitions corresponding to such functions are exactly those satisfying the condition that their blocks have a size of at least two except for the last block, which may be a singleton. The sequence of the numbers ℓ_{n}, n ≥ 0 is the same as the OEIS \underline{A346771}.

Theorem 22. For all n ≥ 2 we have

ℓ_{n} = ∑_{k=1}^{n−1} \binom{n − 1}{k}ℓ_{n−k−1}, ℓ_{0} = ℓ_{1} = 1.

Proof. Let f ∈ RGF(n) satisfy the above condition. Since f_{1} = 1 is the smallest integer, every such function has at least two 1’s. Suppose that f has k + 1 occurrences of 1’s. If we delete all the 1’s and decrease each of the remaining integers by 1, then we obtain an RGF over [n−k−1], with the same condition as f. So, there are ℓ_{n−k−1} such functions. We

now choose k positions from \{2, 3, …, n\} where to insert 1, and this is possible in \binom{n − 1}{k}

ways. Therefore, by applying the product rule and then taking the sum over all possible k, we have the right hand side.

3 Run distribution in run-sorted permutations

The following table presents the first few values r_{n,k} of the number of run-sorted permutations over [n] having k runs (presented in OEIS entry number \underline{A124324}, counting the number of set partitions in SP(n−1) by the number of non-singleton blocks).

n\k 1 2 3 4 5 6 7
1 0
2 1 0
3 1 1 0
4 1 4 0 0
5 1 11 3 0 0
6 1 26 25 0 0 0
7 1 57 130 15 0 0 0
Table 1: The values of r_{n,k} for 1 ≤ k, n ≤ 7

Remark 23. The number k of runs of a run-sorted permutation over [n] satisfies the condition

1 ≤ k ≤ ⌈\frac{n}{2}⌉, n ≥ 1,

because each run except the last has length at least 2.

Remark 24. By Theorem 22 and Remark 23, the set of merging-free partitions is a subset of those set partitions having canonical forms with sequence u = 0.

The following result was conjectured by Nabawanda et al. (personal communication), who also gave a justification of the first term of the right-hand side of (1). We were able to provide a combinatorial bijective proof to justify the second term and thus to prove the conjecture in our preliminary version of this article, entitled ‘Exhaustive generation algorithm for flattened set partitions’. Nabawanda et al. referred to this original proof in [?] and provided an alternative full proof of their own. We here present that original proof, employing our bijection.

Theorem 25. The number r_{n,k} of run-sorted permutations of [n] having k runs satisfies the recurrence relation

r_{n,k} = kr_{n−1,k} + (n − 2)r_{n−2,k−1}, n ≥ 2, k ≥ 1,  (1)

where r_{0,0} = 1, r_{1,0} = 0, r_{1,1} = 1.

To prove this result, we partition the set RsP(n, k) of run-sorted permutations over [n] having k runs into two subsets: RsP^{(1)}(n, k) and RsP^{(2)}(n, k), where RsP^{(1)}(n, k) is the set of elements of RsP(n, k) in which the removal of the integer n does not decrease the number of runs, and RsP^{(2)}(n, k) is the set of elements of RsP(n, k) in which the removal of the integer n decreases the number of runs, this happens when the integer n occurs between two integers x and y with x < y. For example, 12435 ∈ RsP^{(1)}(5, 2) and 15234 ∈ RsP^{(2)}(5, 2). We will denote the cardinalities of these subsets by r_{n,k}^{(1)} and r_{n,k}^{(2)}, respectively.

Let ϕ : [k] × RsP(n − 1, k) ↦ RsP^{(1)}(n, k) associating each element (i, σ) ∈ [k] × RsP(n − 1, k) with the permutation σ′ = ϕ(i, σ) obtained from σ by inserting n at the end of the i-th run of the permutation σ. It is easy to see that ϕ is a bijection [?, p. 6].

We now define the mapping ψ : [n−2]×RsP(n−2, k−1) ↦ RsP^{(2)}(n, k), associating each element (i, π) ∈ [n − 2] × RsP(n − 2, k − 1) with the permutation π′ = ψ(i, π) obtained from π by increasing all integers greater than i by 1 and inserting the subword n i+1 immediately after the rightmost of the integers of the set {1, 2, …, i}.

Example 26. Let i = 3 and π = 13524 ∈ RsP(5, 2). We construct ψ(i, π) as follows: increase each integer greater than 3 in π by 1 to get 13625, then insert the subword 7 (3+1) = 7 4 into the position after the rightmost of the integers 1, 2, 3, thus the subword must be inserted between 2 and 5, hence, ψ(3, 13524) = π′ = 1362745 ∈ RsP^{(2)}(7, 3).

Lemma 27. For all (i, π) ∈ [n − 2] × RsP(n − 2, k − 1), we have ψ(i, π) ∈ RsP^{(2)}(n, k).

Proof. Since π ∈ RsP(n−2, k −1) and the procedure inserts the subword n i+1 immediately after the rightmost integer of the set {1, …, i}, all integers to the right of i + 1 are greater than i + 1 and i + 1 is the first element of a new run. Thus the resulting permutation is runsorted with the number of runs increased by 1. Furthermore, in the resulting permutation, the integer n is immediately preceded by some integer in the set {1, …, i} and immediately followed by i + 1, hence its removal decreases the number of runs, so π′ ∈ RsP^{(2)}(n, k).

Proposition 28. The map ψ defined above is a bijection.

Proof. We prove that ψ is both injective and surjective. First let us assume that (i_{1}, π_{1}) ≠ (i_{2}, π_{2}) for i_{1}, i_{2} ∈ [n−2] and π_{1}, π_{2} ∈ RsP(n−2, k−1). Let ψ(i_{1}, π_{1}) = π′_{1} and ψ(i_{2}, π_{2}) = π′_{2}. Then π′_{1} and π′_{2} are run-sorted permutations in RsP^{(2)}(n, k) by the previous lemma. We consider two cases. If i_{1} ≠ i_{2}, then in one of the two resulting permutations n is followed by i_{1} + 1 while in the other n is followed by i_{2} + 1. If i_{1} = i_{2} and π_{1} ≠ π_{2}, then the two run-sorted permutations π_{1} and π_{2} have at least two entries in which they differ. Thus inserting n i_{1}+1 = n i_{2}+1 after the rightmost element of the set {1, 2, …, i_{1} = i_{2}}, produces two different permutations π′_{1} and π′_{2}. Thus, in both cases, π′_{1} = ψ(i_{1}, π_{1}) ≠ ψ(i_{2}, π_{2}) = π′_{2}, hence ψ is injective. Next, consider any π′ ∈ RsP^{(2)}(n, k), then n does not appear in the last position. Let j > 1 be the integer following n in π′. We exhibit a pair (i, π) ∈ [n − 2] × RsP(n − 2, k − 1) such that ψ(i, π) = π′. Define π to be the run-sorted permutation obtained from π′ by deleting the subword n j and by decreasing by 1 every integer greater than or equal to j + 1 in the resulting word. Note that if n follows the integer i in π′, then i < j, and hence deleting the subword n j from π′ reduces the number of runs by 1 and the size of the partition by 2, whence π ∈ RsP(n − 2, k − 1) and ψ(j + 1, π) = π′. Therefore, ψ is a bijection.

We are now ready to present the proof of Theorem 25.

Proof. The left-hand side counts the number of run-sorted permutations in RsP(n, k). The first term of the right-hand side counts the number of elements in RsP^{(1)}(n, k). Since ϕ is a bijection, we have r_{n,k}^{(1)} = kr_{n−1,k}. We show that the second term of the right-hand side counts the number of elements in RsP^{(2)}(n, k). By Proposition 28 the sets [n−2]×RsP(n−2, k −1) and RsP^{(2)}(n, k) have the same cardinality, i. e., (n − 2)r_{n−2,k−1} = r_{n,k}^{(2)}. Thus by combining the two parts we obtain r_{n,k} = r_{n,k}^{(1)} + r_{n,k}^{(2)}, and hence the recurrence relation in (1).

We also provide a bijective proof of Theorem 25 in terms of canonical forms. Let T_{n,k} = {f ∈ T_{n} : lrmax(f) = k}, so |T_{n,k}| = r_{n,k}. Recall that T_{n,k} is the set of the canonical forms of merging-free partitions over [n] having k blocks.

Proof. Firstly, if f = f_{1}f_{2} ⋯ f_{n−1} ∈ T_{n−1,k}, then by concatenating any integer i ∈ [k] at the end of f we obtain a f′ ∈ T_{n,k}. This is because, f′ satisfies the condition of Proposition 14 if and only if f does. This construction obviously produces kr_{n−1,k} functions of T_{n,k} having the property that by erasing the last value f_{n} we obtain a function in T_{n−1,k}.

Secondly, if f = f_{1}f_{2} ⋯ f_{n−2} ∈ T_{n−2,k−1}, let i ∈ [n − 2], and let m = max_{1≤j≤i}{f_{j}}, then we construct f′ = f′_{1}f′_{2} ⋯ f′_{n} ∈ T_{n,k} associated with (i, f) as follows: increase by 1 all f_{j}s such that f_{j} ≥ m, j > i, insert m + 1 at the position i + 1, and append m at the end. The functions obtained with the second construction are all different from those obtained using the former one. Indeed, by erasing the last integer from f′ we do not obtain a function in T_{n−1,k}. The reason is that the value m + 1 in the position i + 1 is a left-to-right maximum letter because of the choice of m. Now, by construction, the only occurrence of m in f′ is at position n. By erasing this value, the left-to-right maximum letter m + 1 in the position i + 1 is left without an occurrence of m on its right. Therefore, f′_{1}f′_{2} ⋯ f′_{n−1} does not satisfy the property characterizing canonical forms of merging-free partitions. So, this contributes (n − 2)r_{n−2,k−1} to the number r_{n,k} as there are n − 2 possibilities for i and the number of image values of f′ increases by 1.

Example 29. Take f = 12132 ∈ T_{5,3} and let i = 3. We construct (i, f) ↦ f′ as follows: we have m = max_{1≤j≤3}{f_{j}} = max_{1≤j≤3}{1, 2, 1} = 2, and f′_{1} = f_{1} = 1, f′_{2} = f_{2} = 2, f′_{3} = f_{3} = 1, f′_{4} = m + 1 = 3, f′_{5} = f_{4} + 1 = 4, f′_{6} = f_{5} + 1 = 3, f′_{7} = m = 2. Thus, f′ = 1213432 ∈ T_{7,4}.

4 Right-to-left minima in run-sorted permutations

4.1 The distribution of right-to-left minima over the set of runsorted permutations

The following proposition gives us the relation between the statistics of right-to-left minima of run-sorted permutations and the weak left-to-right maxima of the canonical forms of the corresponding merging-free partitions.

Proposition 30. The set of right-to-left minima of a run-sorted permutation over [n] and the set of weak left-to-right maxima of the canonical form of the corresponding merging-free partition are the same.

Proof. Let Flatten(P) = π = π(1) ⋯ π(n) ∈ RsP(n), where P is a merging-free partition over [n]. Let f = f_{1} ⋯ f_{n} be the canonical form of P and let {i_{1}, …, i_{r}} be the set of the positions of the right-to-left minima of π, then by definition of right-to-left minima RlMin(π) = {1 = π(i_{1}) < π(i_{2}) < ⋯ < π(i_{r}) = π(n)}. Furthermore, if 1 ≤ j_{1} < j_{2} ≤ r and we let B_{q_{1}} be the block of P containing π(i_{j_{1}}) and B_{q_{2}} the block of P containing π(i_{j_{2}}), then q_{1} ≤ q_{2} and by the definition of canonical form we have f_{π(i_{1})} ≤ f_{π(i_{2})} ≤ ⋯ ≤ f_{π(i_{r})}. Assume that π(j) ∉ RlMin(π), then there exists some integer s such that π(j) > π(s), s > j. Hence f_{π(s)} > f_{π(j)} and π(j) ∉ WLrMax(f). Thus, {π(i_{1}), …, π(i_{k})} ⊆ WLrMax(f).

Conversely, if WLrMax(f) = {i_{1}, …, i_{s}}, then for each i_{j} we have f_{i_{j}} ≥ f_{t}, t < i_{j}, that is, all integers t < i_{j} belong either to f_{i_{j}}-th block or to a preceding block of P, therefore, in π there is no integer smaller than i_{j} on the right of i_{j}. Hence i_{j} ∈ RlMin(π). Therefore, RlMin(π) = WLrMax(f).

Example 31. If P = 149/238/57/6, then its canonical form is f = 122134321 and π = Flatten(P) = 149238576. Thus, we have RlMin(π) = {1, 2, 3, 5, 6} = WLrMax(f).

Let h_{n,r} denote the number of run-sorted permutations over [n] having r right-to-left minima.

Proposition 32. For all positive integers n and r with 2 ≤ r ≤ n we have

h_{n,r} = h_{n−1,r−1} + (r − 1)h_{n−1,r}, h_{1,1} = 1.  (2)

Proof. A run-sorted permutation π′ over [n] can be obtained from a run-sorted permutation π over [n−1] either by appending n at its end or by inserting n before any of its right-to-left minima that is different from 1. Otherwise, the resulting permutation would not be run-sorted. In the former case, the number of right-to-left minima increases by 1, hence this contributes h_{n−1,r−1} to the number h_{n,r}. In the latter case, if RlMin(π) = {π(i_{1}), π(i_{2}), …, π(i_{r})}, then 1 = π(i_{1}) < π(i_{2}) < ⋯ < π(i_{r}). So, inserting n before any π(i_{j}) for j ≠ 1 makes π(i_{j}) to be the minimum element of its run in π′. Thus the permutation π′ is run-sorted having the same number of right-to-left minima as π, and this contributes (r −1)h_{n−1,r} as there are r−1 right-to-left minima different from 1.

We also give the interpretation of the bijective proof of the recursion formula in (2) for the corresponding set of canonical forms of merging-free partitions using Proposition 30. We interpret h_{n,r} as the number of canonical forms in T_{n} having r weak left-to-right maxima, i. e., h_{n,r} = |{f ∈ T_{n} : wlrmax(f) = r}|. All the elements of the set {f ∈ T_{n} : wlrmax(f) = r} are obtained in a unique way

1. either from a f = f_{1}f_{2} ⋯ f_{n−1} ∈ T_{n−1,r−1} by concatenating max_{1≤j≤n−1}{f_{j}} at its end;

2. or from a f = f_{1}f_{2} ⋯ f_{n−1} ∈ T_{n−1,r} with weak left-to-right maxima {i_{1}, i_{2}, …, i_{r}} as follows. For each j = 2, …, r:

- if f_{i_{j}} is a non-strict left-to-right maximum letter of f, then increase by 1 every integer f_{s} such that f_{s} ≥ f_{i_{j}} and s ≥ i_{j}, and

- concatenate f_{i_{j−1}} at the end of the resulting function.

Thus, the recurrence relation in (2) follows.

Recall that the recurrence relation satisfied by the Stirling numbers of the second kind is S(n, r) = S(n − 1, r − 1) + rS(n − 1, r). It is easy to see that from Corollary 21 of Section 2 and Proposition 30, the number of blocks in a set partition over [n − 1] is one less than the number of right-to-left minima of the corresponding run-sorted permutation over [n] under the bijection in Proposition 11. So, the values of h_{n,r} given in (2) are the shifted values of the Stirling numbers of the second kind, i. e., h_{n,r} = S(n − 1, r − 1), for all n ≥ r ≥ 1.

4.2 The joint distribution of run and rlmin over the set of runsorted permutations

The statistics run and rlmin of a run-sorted permutation are related. In particular, each minimum element of a run is always a right-to-left minimum, so run(π) ≤ rlmin(π), ∀π ∈ RsP(n). We are interested in the joint distribution of these statistics. Let a_{n,k,r} denote the number of run-sorted permutations over [n] having k runs and r right-to-left minima. If n = 0, then the only nonzero term is a_{0,0,0} = 1; if n ≥ 1, then a_{n,k,r} = 0, where k > ⌈\frac{n}{2}⌉, r > n, r < k, k < 1, r < 1, or r > n − k + 1.

Proposition 33. For all integers n, k, r such that 1 ≤ k, r ≤ n, the numbers a_{n,k,r} of runsorted permutations over [n + 2] having k runs and r right-to-left minima satisfy

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

Proof. Let π ∈ RsP(n + 2). Let us suppose that the integers 1 and 2 are in the same run of π. Let π′ be the permutation obtained from π by deleting 1 and then decreasing each of the remaining integers by 1, then π′ ∈ RsP(n + 1) and run(π) = run(π′) and rlmin(π) = rlmin(π′) + 1. This implies that

|{π ∈ RsP(n + 2) : run(π) = k, rlmin(π) = r, 1 and 2 are in the same run}| = a_{n+1,k,r−1}.

Let us suppose now that 1 and 2 are in different runs of π and that the first run (containing 1) has length i + 1, i ≥ 1, then we can choose i elements from the set {3, 4, …, n + 2} to

include in the first run. There are \binom{n}{i} ways to do so. The remaining part of π is a run-

sorted permutation over n + 1 − i letters and thus there are a_{n+1−i} of them. In this case, the number of runs and the number of right-to-left minima of π each increase by 1. This completes the proof.

Theorem 34. We have

a_{n,k,r} = a_{n−1,k,r−1} + (k − 1)a_{n−1,k,r} + (n − 2)a_{n−2,k−1,r−1}, n ≥ 2, k, r ≥ 1  (3)

with the initial conditions a_{0,0,0} = 1, a_{1,1,1} = 1.

Proof. The proof is based on the technique used in the proof of Theorem 25. Let π′ be a run-sorted permutation over [n] obtained from π ∈ RsP(n−1) by inserting n at the end of any of its runs. This operation preserves the number of runs. It also preserves the number of right-to-left minima except when n is inserted at the end of the last run of π, in which case the number of right-to-left minima increases by 1. So, we get the first two terms of the right-hand side of (3). Again, if π′ ∈ RsP(n) is obtained from π ∈ RsP(n−2) by the operation defined in Lemma 27, i. e., π′ = ψ(i, π), where i ∈ [n − 2], then the number of runs and the number of right-to-left minima each increase by 1. We showed already that this is true for the number of runs, let us show it for the number of right-to-left minima. The operation increases each integer greater than i in π by 1 and inserts the subword n i+1 immediately after the rightmost position of the integers of the set {1, 2, …, i}, then the newly created run beginning at i + 1 contributes one more right-to-left minimum since the minima of the runs form an increasing subsequence. Thus, we have the last term on the right-hand side of the recurrence.

Remark 35. If we use the interpretation with set partitions, a_{n,k,r} counts the number of set partitions in SP(n−1) having r−1 blocks in which k−1 of them are non-singleton blocks.

Theorem 36. The exponential generating function

A(x, y, z) = ∑_{n,k,r≥0} a_{n,k,r} \frac{x^{n}}{n!} y^{k}z^{r}

satisfies the differential equation

\frac{∂A}{∂x} = yze^{xz−yz(1+x−e^{x})}  (4)

with the initial condition \frac{∂A}{∂x}|_{x=0} = yz.

Proof. By (3) we have

∑_{n≥2,k,r≥1} a_{n,k,r} \frac{x^{n}}{n!} y^{k}z^{r} = ∑_{n≥2,k,r≥1} a_{n−1,k,r−1} \frac{x^{n}}{n!} y^{k}z^{r} + ∑_{n≥2,k,r≥1}(k − 1)a_{n−1,k,r} \frac{x^{n}}{n!} y^{k}z^{r}+

∑_{n≥2,k,r≥1} a_{n−2,k−1,r−1} \frac{x^{n}}{n!} y^{k}z^{r}.

Using the notation A_{y} = \frac{∂A}{∂y} and expressing the above equation in terms of A we obtain

A = z (∫ Adx − x) + ∫ yA_{y}dx − (∫ Adx − x) + xyz ∫ Adx−
2yz ∫ ∫ Adxdx + 1 + xyz
= ∫ yA_{y}dx − (1 − z − xyz) ∫ Adx + x − xz − 2yz ∫ ∫ Adxdx + 1 + xyz. (5)

By differentiating both sides of (5) with respect to x we obtain the following:

A_{x} = yA_{y} − (1 − z − xyz)A + 1 − z − yz ∫ Adx + yz.

Again by differentiating the above equation with respect to x we obtain

A_{xx} = yA_{yx} − (1 − z − xyz)A_{x}.  (6)

By letting B = A_{x} in (6) we obtain

B_{x} − yB_{y} + (1 − z − xyz)B = 0.  (7)

Then, the characteristic equation is \frac{dy}{dx} = \frac{−y}{1} or ln y + x = k with k constant. We make the transformation with ϵ = x, μ = ln y + x, ζ = z, and w(ϵ, μ, ζ) = B(x, y, z). Using the substitution we find that (7) transforms to

w_{ϵ} + (1 − ζ − ϵζe^{μ−ϵ}) w = 0.

By the integrating factor method we have

\frac{∂}{∂ϵ} (e^{∫ (1−ζ−ϵζe^{μ−ϵ})dϵ}w) = 0

and then integrating the above equation with respect to ϵ and simplifying

w(ϵ, μ, ζ) = g(μ, ζ)e^{∫ (−1+ζ+ϵζe^{μ−ϵ})dϵ}
= g(μ, ζ)e^{ϵ(−1+ζ)−ζe^{μ−ϵ}(1+ϵ)+h(μ,ζ)},

where g and h are any differentiable functions of two variables. Using the initial condition B(0, y, z) = yz we have x = 0, ϵ = 0, μ = ln y, ζ = z, w(ϵ = 0, μ = ln y, ζ = z) = yz, and

yz = g(ln y, z)e^{−yz+h(ln y,z)}
yze^{yz} = g(ln y, z)e^{h(ln y,z)}.

Thus, we obtain g(t, z) = h(t, z) = ze^{t}. Therefore, we back the transformation in terms of x, y, z so that

B(x, y, z) = g(ln y + x, z)e^{−x+xz−yz(1+x)+h(ln y+x,z)}
= yze^{xz−yz(1+x−e^{x})}.

By specializing z = 1 in (4) we obtain the result about the exponential generating function counting run-sorted permutations by the number of runs [?]. Recall that r_{n,k} is the number of run-sorted permutations over [n] having k runs.

Corollary 37. If A(x, y) = ∑_{n,k≥1} r_{n,k} \frac{x^{n}}{n!} y^{k}, then A satisfies

\frac{∂A}{∂x} = ye^{x−y(1+x−e^{x})}

with the initial condition \frac{∂A}{∂x}|_{x=0} = y.

By specializing y = z = 1 in (4) we obtain the well-known result about the exponential generating function counting the number of run-sorted permutations (merging-free partitions) [?, ?].

Corollary 38. The exponential generating function A(x) of the number of run-sorted permutations has the closed differential form

A′(x) = e^{e^{x}−1}.

Corollary 39. For all positive integer n ≥ 1, the number a_{n} of run-sorted permutations over [n] is given by

a_{n} = \frac{1}{e} ∑_{m≥0} \frac{m^{n−1}}{m!} .

4.3 A bijection with separated partitions

We now consider set partitions with no two consecutive integers in the same block. Such partitions have been studied, for instance, by Munagi [?], who called them “separated” partitions and proved that separated partitions over [n] having k blocks are counted by the shifted Stirling numbers of the second kind (\underline{A008277}), like the run-sorted permutations over [n] having k right-to-left minima.

It is then natural to provide a bijection between these two equisized classes of objects. Let P_{n} denote the set of all separated partitions over [n]. Let P = B_{1}/B_{2}/ ⋯ /B_{k} ∈ P_{n} with k blocks. Define a map θ : P_{n} ↦ RsP(n) given by π = θ(P), where π is obtained as follows:

- for i = 2, …, k:

if b ∈ B_{i}, b ≠ min(B_{i}) and b − 1 ∈ B_{j} such that j < i, then

move b to B_{i−1} and rearrange the elements of B_{i−1} in increasing order;

- flatten the resulting partition and set it to π.

Example 40. If P = 1358/26/47, then 1358/26/47 → 13568/2/47 → 13568/27/4 → 13568274 = π.

Theorem 41. The map θ is a bijection.

Proof. We first prove that π ∈ RsP(n), for every P ∈ P_{n}. The procedure never moves min(B_{i}) for all i. Thus, the minima remain in increasing order, hence π is a run-sorted permutation. We now show that if P has k blocks, then π has k right-to-left minima. Obviously, the minimum of each block of P becomes a right-to-left minimum of π. Let b be in the block B_{i} with b ≠ min(B_{i}). The integer b − 1 is in a different block, say B_{j}. If j < i, then the procedure moves b to the block B_{i−1} leaving min(B_{i}) on its right in π. Therefore, b cannot be a right-to-left minimum of π. Suppose that j > i. Since b − 1 ≥ min(B_{j}) we have b > min(B_{j}), so the procedure moves neither b nor min(B_{j}) which implies that b cannot be a right-to-left minimum of π. Therefore, b is a right-to-left minimum of π if and only if b = min(B_{i}), i = 1, …, k. We next prove that θ is one-to-one. Suppose that P ≠ P′, where P, P′ ∈ P_{n}. If the number of blocks of P and the number of blocks of P′ are different, then we are done since θ(P) and θ(P′) have different number of right-to-left minima. Let P = B_{1}/ ⋯ /B_{k} and P′ = B′_{1}/ ⋯ /B′_{k}, and assume that there exists an element b ∈ B_{i} and b ∈ B′_{j} such that B_{i} is the block of P and B′_{j} is the block of P′ with i ≠ j. We take the minimal of these elements. Up to exchanging of P and P′ we can suppose i < j.

1. If b = min(B_{i}), then b is the i-th right-to-left minimum of θ(P) and it would not be the case for θ(P′).

2. Let b ≠ min(B_{i}) and let b − 1 ∈ B_{m}. Note that b − 1 ∈ B′_{m} for the minimality of b. Three sub-cases are possible:

• if m < i < j, then θ moves b to the block B_{i−1} of P and moves b to the block B′_{j−1} of P′;

• if i < m < j, then θ leaves b in the block B_{i} in P while it moves b to the block B′_{j−1} in P′. Note that j − 1 ≠ i, because i ⪇ m ⪇ j;

• if i < j < m, then θ leaves b in the block B_{i} in P and leaves b in the block B′_{j} in P′.

In all cases we have θ(P) ≠ θ(P′). Therefore, θ is a bijection.

We now present the inverse of θ. Let π ∈ RsP(n) having k right-to-left minima. We construct P = θ^{−1}(P′) as follows:

- insert a slash before each right-to-left minimum of π and let B_{1}/ ⋯ /B_{k} be the resulting partition;

- for i = k, …, 1:

for b in B_{i} \ {min(B_{i})} taken in increasing order

if b − 1 ∈ B_{j}, j ≤ i, then

move b to B_{i+1} and rearrange the elements in each block in increasing order.

It can be easily checked that θ^{−1} constructs a separated partition. For instance, if π = 13625784, then by inserting slashes before each right-to-left minimum we have the partition 136/2578/4, and we move 7 to B_{3} since 6 ∈ B_{1}. So, P = 136/258/47.

5 Non-crossing merging-free partitions

Let P = B_{1}/ ⋯ /B_{k} ∈ SP(n). The standard representation of P is the graph on the vertex set [n] whose edge set consists of arcs connecting the elements of each block in numerical