Locally restricted compositions over a finite group. (October 2021)

• Record Type: Journal Article
• Authors: Gao, Zhicheng; MacFie, Andrew
• Is Part Of: European journal of combinatorics. Volume 97(2021)
• Publication Date: 2021-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103386
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: One may generalize integer compositions by replacing the positive integers with a different additive semigroup, giving the broader concept of a "composition over a semigroup". Here we focus on semigroups which are finite groups and achieve asymptotic enumeration of compositions over a finite group which satisfy a local restriction. These compositions are associated to walks on a voltage graph whose structure is exploited to simplify asymptotic expressions. Specifically, we show that under mild conditions the number of locally restricted compositions of a group element is asymptotically independent of the particular group element. We apply this result to subword pattern avoidance and other examples such as generalized Carlitz compositions.