2017/10/18 by Zhicheng Gao, Gao, Zhicheng, Andrew MacFie +3
Computer Science · Engineering · Mathematics · #05A15 #05A16 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1710.06797
openalex publication_date 2017/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We find the number of compositions over finite abelian groups under two types of restrictions: (i) each part belongs to a given subset and (ii) small runs of consecutive parts must have given properties. Waring's problem over finite fields can be converted to type~(i) compositions, whereas Carlitz and locally Mullen compositions can be formulated as type~(ii) compositions. We use the multisection formula to translate the problem from integers to group elements, the transfer matrix method to do exact counting, and finally the Perron-Frobenius theorem to derive asymptotics. We also exhibit bijections involving certain restricted classes of compositions.