Set partitions and parity successions. (17th November 2017)

• Record Type: Journal Article
• Authors: Mansour, Toufik; Shattuck, Mark
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 20:Number 8(2017)
• Page Start: 1651
• Page End: 1674
• Publication Date: 2017-11-17
• Subjects: 05A18 -- 05A15 -- 05A19; Set partition -- Parity succession -- Non-crossing partitions -- q-generalization; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2016.1160514
• Languages: English
• ISSNs: 0972-0529

Abstract

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-al­ternating 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.