论文标题
斐波那契的灰色代码q删除单词
Gray codes for Fibonacci q-decreasing words
论文作者
论文摘要
$ n $ - lengtth二进制单词是$ q $ -decreasing，$ q \ geq 1 $，如果其每一个长度的最大因素$ 0^a1^b $满足$ 0^a1^b $满足$ a = 0 $ a = 0 $ a = 0 $或$ q \ cdot a> b $。 $（Q+1）$ - 广义斐波那契号。我们给出了一些枚举结果，并揭示了$ q $删除单词和二进制单词之间的相似之处，而在$ 1 $ bit的频率方面，没有出现$ 1^{q+1} $。在论文的第二部分中，我们提供了一种有效的详尽生成算法，以$ q $ - 以词典序列的方式删除单词，对于任何$ q \ geq 1 $，显示3灰色代码的存在，并解释如何获得这些灰色代码的生成算法。此外，我们为$ 1 $淘汰的单词提供了更严格的1灰色代码的构建，尤其是在Eğecioğlu和iršič的互连网络中陈述的猜想。
An $n$-length binary word is $q$-decreasing, $q\geq 1$, if every of its length maximal factor of the form $0^a1^b$ satisfies $a=0$ or $q\cdot a > 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 $q\geq 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č.
