2020/10/19 by Jean-Luc Baril, Baril, Jean-Luc, Sergey Kirgizov +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #05A05 (Primary) 05A15 #05A19 #68R15 (Secondary) #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Fractal and DNA sequence analysis
paper · doi:10.48550/arxiv.2010.09505
openalex publication_date 2020/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An n-length binary word is q-decreasing, q≥ 1, if every of its length maximal factor of the form 0a1b satisfies a=0 or q⋅ a > b.We show constructively that these words are in bijection with binary words having no occurrences of 1q+1, and thus they are enumerated by the (q+1)-generalized Fibonacci numbers. We give some enumerative results and reveal similarities between q-decreasing words and binary words having no occurrences of 1q+1 in terms of frequency of 1 bit. In the second part of our paper, we provide an efficient exhaustive generating algorithm for q-decreasing words in lexicographic order, for any q≥ 1, show the existence of 3-Gray codes and explain how a generating algorithm for these Gray codes can be obtained. Moreover, we give the construction of a more restrictive 1-Gray code for 1-decreasing words, which in particular settles a conjecture stated recently in the context of interconnection networks by Eğecioğlu and Iršič.