Merging-free partitions and run-sorted permutations

MaRDI QIDQ5043577zbMATH OpenFDO

Authors Fufa Beyene, R. Mantaci

Publication date 6 October 2022

Full work available at URL https://arxiv.org/abs/2101.07081, https://cs.uwaterloo.ca/journals/JIS/VOL25/Beyene/beyene10.html

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

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)

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.

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

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 7662495 (Why is no real title available?)
• Peaks are preserved under run-sorting
• scientific article; zbMATH DE number 7732121 (Why is no real title available?)
• scientific article; zbMATH DE number 7732129 (Why is no real title available?)

Describes a project that uses

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)