Strings from linear recurrences and permutations: A Gray code

Each positive increasing integer sequence 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 k consecutive ones. We prove a bijection between the set of such strings of length n and the set of the permutations of length n+1 avoiding a suitable set of permutation patterns. Finally, basing on a known Gray code for those strings, we define a Gray code for this set of permutations, where two consecutive permutations differ by an adjacent transposition.