Gray codes for Fibonacci q-decreasing words

DOI10.1016/J.TCS.2022.06.003MaRDI QIDQ6351665arXivFDO

Authors Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki

Publication date 19 October 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.06.003

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

arXiv classification

cs.DMmath.CO

Abstract: An $n$-length binary word is $q$-decreasing, $qgeq1$, if every of its length maximal factor of the form $0^a{1}^b$ satisfies $a=0$ or $qcdota>b$.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 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 $qgeq1$, 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 Eu{g}eciou{g}lu and Irv{s}iv{c}.

This page was built for publication: Gray codes for Fibonacci q-decreasing words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6351665)