Gao, Zhicheng; MacFie, Andrew Locally restricted compositions over a finite group. (English) Zbl 1469.05009 Eur. J. Comb. 97, Article ID 103386, 21 p. (2021). Summary: 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. MSC: 05A15 Exact enumeration problems, generating functions 05A05 Permutations, words, matrices 05C20 Directed graphs (digraphs), tournaments 20D60 Arithmetic and combinatorial problems involving abstract finite groups Keywords:locally restricted composition; walks in a digraph; subword pattern Software:ROTA PDFBibTeX XMLCite \textit{Z. Gao} and \textit{A. MacFie}, Eur. J. Comb. 97, Article ID 103386, 21 p. (2021; Zbl 1469.05009) Full Text: DOI References: [1] Bender, E. A.; Canfield, R., Locally restricted compositions II. General restrictions and infinite matrices, Electron. J. Combin., 16, 1, R108 (2009) · Zbl 1186.05009 [2] Bender, E. A.; Canfield, R.; Gao, Z., Locally restricted compositions IV. Nearly free large parts and gap-freeness, Discrete Math. Theor. Comput. Sci. (2012) · Zbl 1296.05006 [3] Bender, E. A.; Gao, Z., Part sizes of smooth supercritical compositional structures, Combin. Probab. Comput., 23, 5, 686-716 (2014) · Zbl 1298.05029 [4] Bender, E. A.; Richmond, L. B.; Williamson, S., Central and local limit theorems applied to asymptotic enumeration. III. Matrix recursions, J. Combin. Theory Ser. A, 35, 3, 263-278 (1983) · Zbl 0524.05017 [5] Bertoni, A.; Choffrut, C.; Goldwurm, M.; Lonati, V., On the number of occurrences of a symbol in words of regular languages, Theoret. Comput. Sci., 302, 1-3, 431-456 (2003) · Zbl 1044.68083 [6] Brändén, P.; Mansour, T., Finite automata and pattern avoidance in words, J. Combin. Theory Ser. A, 110, 1, 127-145 (2005) · Zbl 1059.05003 [7] Burstein, A.; Mansour, T., Counting occurrences of some subword patterns, Discrete Math. Theor. Comput. Sci., 6, 1, 1-11 (2003) · Zbl 1025.68026 [8] Dahmani, F.; Futer, D.; Wise, D. T., Growth of quasiconvex subgroups, (Mathematical Proceedings of the Cambridge Philosophical Society (2018), Cambridge University Press), 1-26 [9] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 [10] Gao, Z.; MacFie, A.; Wang, Q., Counting compositions over finite abelian groups, Electron. J. Combin., 25, 2, P2.19 (2018) · Zbl 1391.05029 [11] Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Dover · Zbl 0621.05013 [12] Heubach, S.; Mansour, T., Combinatorics of Compositions and Words (2010), Chapman & Hall/CRC [13] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1994), Cambridge University Press: Cambridge University Press Cambridge, Corrected reprint of the 1991 original · Zbl 0801.15001 [14] MacFie, A., Enumerative Properties of Restricted Words and Compositions (2018), Carleton University, (Ph.D. thesis) [15] Mansour, T.; Sirhan, B., Counting \(l\)-letter subwords in compositions, Discrete Math. Theor. Comput. Sci., 8, 285-297 (2006) · Zbl 1153.05300 [16] Stanley, R. P., Enumerative Combinatorics, Cambridge Studies in Advanced Mathematics (2012), Cambridge University Press, Cambridge · Zbl 1247.05003 [17] Zeilberger, D., The umbral transfer-matrix method. I. Foundations, J. Combin. Theory Ser. A, 91, 1-2, 451-463 (2000) · Zbl 0961.05003 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.