Journal of Integer Sequences, Vol. 25 (2022), Article 22.7.6

Merging-Free Partitions and Run-Sorted Permutations

Fufa Beyene
Department of Mathematics
Addis Ababa University
Addis Ababa 1176

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


In this paper, we study merging-free partitions and run-sorted permutations. We give a combinatorial proof of a conjecture of Nabawanda, Rakotondrajao, and Bamunoba. We describe the distribution of the statistics of runs and right-to-left minima over the set of run-sorted 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 numbers 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.

Full version:  pdf,    ps,    latex    

(Concerned with sequences A008277 A124324 A346771.)

Received January 13 2022; revised versions received January 14 2022; July 16 2022; August 30 2022; September 17 2022; September 19 2022. Published in Journal of Integer Sequences, September 19 2022.

Return to Journal of Integer Sequences home page