Gray codes for Fibonacci q-decreasing words

A length nbinary word is q-decreasing, q >= 1, if every of its maximal factors of the form 0(a)1(b) satisfies a = 0 or q . a > b. In particular, in 1-decreasing words every run of 0s is immediately followed by a strictly shorter run of 1s. We show constructively that these words are in bijection with binary words having no occurrences of 1(q+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 1(q+1) in terms of the frequency of 1-bits. 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 Egecioglu and Irsic. (c) 2022 Elsevier B.V. All rights reserved.