Strings from linear recurrences and permutations: a Gray code

Abstract: Each positive increasing integer sequence

{a_{n}}_{n g e q 0}

can serve as a numeration system to represent each non-negative integer by means of suitable coefficient strings. We analyse the case of

k

-generalized Fibonacci sequences leading to the binary strings avoiding

1^{k}

. We prove a bijection between the set %

F_{n}^{(k)}

of strings of length

n

and the set of permutations of

S_{n + 1} (321, 312, 23 l d o t s (k + 1) 1)

. Finally, basing on a known Gray code for those strings, we define a Gray code for

S_{n + 1} (321, 312, 23 l d o t s (k + 1) 1)

, where two consecutive permutations differ by an adjacent transposition.

This page was built for publication: Strings from linear recurrences and permutations: a Gray code