New refined enumerations of set partitions related to sorting. Issue 10 (3rd October 2018) - Mansour, Toufik; Shattuck, Mark
ABSTRACT: 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.