Skip to main content

New refined enumerations of set partitions related to sorting


Toufik Mansoura, Mark Shattuck*

Source title: 
Journal of Difference Equations and Applications, 24(10): 1588-1603, 2018 (ISI)
Academic year of acceptance: 

In this paper, we consider a statistic defined on the sequential representation of a finite set partition which tracks the number of steps required, i.e. pushes, to put the sequence in weakly increasing order. A generating function is computed for the distribution of the statistic that records the number of pushes considered jointly with some other combinatorial parameters on the set of partitions of [n]={1,2,…,n} for each fixed n. Some further attention is paid to the distribution for the number of pushes by itself. Generating function formulas are also found for the comparable distribution on the set of non-crossing and non-nesting partitions of [n]. As a consequence of our results, one obtains new polynomial generalizations of the Stirling, Bell and Catalan numbers.