Merging-Free Partitions and Run-Sorted Permutations
Department of Mathematics
Addis Ababa University
Addis Ababa 1176
Université de Paris
8, Place Aurélie
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,
(Concerned with sequences
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.
Journal of Integer Sequences home page