Merging-free partitions and run-sorted permutations

zbMATH Open1498.05004arXiv2101.07081MaRDI QIDQ5043577FDOQ5043577

Authors: Fufa Beyene, R. Mantaci 

Publication date: 6 October 2022

Abstract: In this paper, we study merging-free partitions with their canonical forms 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 run-sorted permutations and we give the exponential generating function for their joint distribution. We show the number of right-to-left minima is given by the shifted distribution of the Stirling number of the second kind. We also prove that the non-crossing merging-free partitions are enumerated by powers 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 number of runs.

Full work available at URL: https://arxiv.org/abs/2101.07081

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Peaks are preserved under run-sorting
• New refined enumerations of set partitions related to sorting
• Peaks are preserved under run-sorting (extended abstract)
• The runsort permuton
• Computing the number of mergings with constraints

zbMATH Keywords

algorithmnon-crossing partitioncanonical formmerging-free partitionrun-sorted permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17) Combinatorial identities, bijective combinatorics (05A19)

Cites Work

• Title not available (Why is that?)
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• Pattern avoidance in ``flattened partitions
• Combinatorics of set partitions
• Noncrossing partitions
• Counting subwords in flattened partitions of sets
• The Number of Partitions of a Set
• Introduction to enumerative combinatorics. With a foreword by Richard Stanley
• Combinatorial statistics on non-crossing partitions
• Set partitions with successions and separations
• On 1212-avoiding restricted growth functions
• Run distribution over flattened partitions
• Peaks are preserved under run-sorting

Cited In (4)

• Title not available (Why is that?)
• Peaks are preserved under run-sorting
• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• OEIS

This page was built for publication: Merging-free partitions and run-sorted permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043577)