Binary words avoiding a pattern and marked succession rule

2011/03/29 by Stefano Bilotta, Bilotta, Stefano, Donatella Merlini +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1103.5689

19

arxiv created 2011/03/29 · openalex publication_date 2011/03/29 · arxiv updated 2011/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^j+10^j. By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.

Citations

• On Some Alternative Characterizations of Riordan Arrays

Related

• Generation of binary words avoiding alternating patterns
• Binary words avoiding xx^Rx and strongly unimodal sequences
• Increasing Consecutive Patterns in Words
• Counting Words Avoiding a Short Increasing Pattern and the Pattern\n 1k...2
• Novel Constructions of Words with Strong Avoidance Properties and their Combinatorial Analysis