Set partitions and parity successions. (17th November 2017) - Mansour, Toufik; Shattuck, Mark
Abstract: By a ( parity ) succession within a sequence w = w 1 w 2  … , we will mean an index i such that wi ≡ w i + 1 (mod2). In this paper, we address the problem of counting successions in set partitions, represented sequentially as restricted growth functions. Among our results, we find explicit formulas for the relevant generating functions and for the number of parity-alternating set partitions, i.e., those having no successions. We also compute a formula for the total number of successions within all partitions of a fixed length and number of blocks, and a combinatorial proof of this result is provided. Finally, we consider the problem of counting successions in non-crossing partitions, i.e., those having no occurrence of the pattern 1212, and determine, with the aid of programming, formulas for the generating functions.