Given a sequence famgm 0 of strictly increasing positive integers such that a0 = 1, any non-negative integer N can be uniquely represented by N = Pi 0 diai, where di are non negative integers. The coe cients di form a string over a nite alphabet and all these strings form a language having di erent properties depending on the sequence. We investigate on the possibility of de ning a Gray code over the language arising from particular choices of famgm 0. We consider the sequence de ned by a two termed linear recurrence with constant coe cients having some particular properties.
In the present paper we consider a language of strings de ned in [BR01] over a particular alphabet. These strings are the representations of integers by means of a system of numeration [Fra82] derived from certain sequences. Given a strictly increasing sequence of non-negative integers 1 = a0 < a1 < a2 < :::, it is possible to represent each non-negative integer N by recording the quotient dn obtained by dividing N by the largest member an of the sequence that is less than or equal to N , then dividing the remainder rn by an 1 and recording the quotient dn 1 and so on until you get to d0, since dividing by 1 leaves a remainder of 0. The various quotients form a string which is an element of the language. In [BR01] sequences are de ned by a two termed linear recurrence depending on two parameters k and h, and the arising language, strictly depending on k and h, is seen as a combinatorial interpretation of the sequence ai = kai 1 + hai 2. In this paper we aim at providing a Gray code for the language derived from particular conditions on k and h.
We point out that the considered language was introduced in order to provide a general solution to a previous issue appeared in [BSS93], where the authors asked for a combinatorial interpretation of the recurrence fm+1 = 6fm fm 1, with f0 = 1, f1 = 7 (sequence M4423 of [SP96]). After some interesting answers (see [BBDD98, PP90, Sul98]), in their paper [BR01] the authors gave a general combinatorial interpretation for the recurrences of the form am = kam 1 + ham 2, under some conditions on h and k which include the most frequently occurring two-termed recurrences. We also noted, in the previous paragraph, that this language is strictly linked to the system of numeration presented in [Fra82]. This is based on a very simple iterated division algorithm which is the main tool which produces the representation for any non-negative integer N , in terms of any sequence of the form 1 = u0 < u1 < u2 < : : : . Clearly, the particular choice of the sequence a ects the representation of N , and in some particular cases interesting and useful representations can be obtained. In the references within [Fra82] several application of di erent systems of numeration can be found, ranging from compressing and partitioning large dictionaries, ranking permutations with repetitions, up to designing error-insensitive codes for data transmission.
The de nition of the Gray code in the present paper could be presented independently of the de nition of numeration systems and without showing which are the links between the considered language and the sequence. Nevertheless, in order to provide a self-contained paper and for the sake of completeness, we prefer to present concepts and preliminaries useful for our purpose. Section 2 and Section 3 are devoted to the presentation of some main notion about numeration systems and properties of the considered recurrence relations. In Section 4 we recall the de nition of the language introduced in [BR01] and nally we de ne a Gray code for listing its elements. 2
Given a sequence famgm 0 of positive integers such that a0 = 1 and am < am+1 for each m 2 N, let N be any non-negative integer. Consider the largest term an of the sequence such that an N . More precisely, an = maxfam j am N g (for the particular case N = 0, see below). We divide N by an obtaining N = dnan +rn. Obviously, for the remainder rn, it is clear that rn < an. If we divide rn by an 1, we get rn = dn 1an 1 + rn 1, with rn 1 < an 1. Then, iterating this procedure until the division by a0 = 1 (where of course the remainder is 0), we have:
N rn rn 1 r3 r2 r1 = = = = = = = = dnan + rn dn 1an 1 + rn 1 dn 2an 2 + rn 2 d2a2 + r2 d1a1 + r1
Expression (1) is the representation of N in the numeration system S = fa0; a1; a2; : : : : : :g, and the string dndn 1 : : : d1d0 is associated to the number N (in what follows the term \representation" equivalently refers to the expression (1) or to its associated string). The method presented here can be applied to every non-negative integer and in the case N = 0, clearly, all the coe cients di are 0 (in other words the representation of 0 is simply the string 0). Moreover, we have
ri = di 1ai 1 + di 2ai 2 + : : : : : : + d1a1 + d0a0 < ai ; for each i
0.
It is possible to show [Fra82] that if N = Pn
i 0 diai with diai + di 1ai 1 + : : : + d1a1 + d0a0 < ai+1 for each i 0, then the representation N = Pin 0 diai is unique. For the sake of completeness, we recall the complete theorem: Theorem 2.1. Let 1 = a0 < al < a2 < : : : be any integer N has precisely one representation in the system S = fa0; a1; a2; :::g of the form N = nite or in nite sequence of integers. Any non-negative n X diai where the i 0 di are non-negative integers satisfying (3).
As an example, consider the well-known sequence of Pell numbers (sequence M1413 in [SP96]) pm = 1; 2; 5; 12; 29; : : : de ned by p0 = 1, p1 = 2, pm = 2pm 1 + pm 2. The representation of N = 16 is associated to the string 1020. 3
The next step is the de nition of the language arising from the representations of non-negative numbers. Given m > 0, we consider all the integers ` 2 f0; 1; 2; : : : ; am 1g. According to the scheme of the previous section, the representations of the integers j with am 1 j < am is j = dm 1am 1 + dm 2am 2 + : : : + d0a0 (so that the associated string is dm 1dm 2 : : : d0), while, following the same scheme, the remaining integers have a representation with less than m digits. For example: the representation of am 1 1 = dm 2am 2 + : : : + d0a0 has m 1 digits. For our purpose (the construction of a Gray code), we require that all the representations of the considered integers ` 2 f0; 1; 2; : : : ; am 1g have m digits, so we pad the string on the left with 0's until we have m digits: the representation of am 1 1 becomes am 1 1 = 0am 1 + dm 2am 2 + : : : + d0a0 (therefore, the associated string is 0dm 2 : : : d0).
With this little adjustment, we now de ne the following sets: (2) (3) L0 = f"g , L = Sm 0 Lm.
Lm = fdm 1 : : : d0j the string dm 1 : : : d0 is the representation of each ` < am in the
numeration system famgm 0 g.
Finally, we denote by L the language obtained by taking the union of all the sets Lm: We remark that each element of Lm has precisely m digits, so that some string dm 1 : : : d0 can admit a pre x constituted by a certain number of consecutive 0's. Moreover, each Lm contains precisely am elements (which are the representations of each ` 2 f0; 1; : : : ; am 1g). L0 L1 L2 L3
It is not di cult to realize that the alphabet of the language L strictly depends on the sequence famgm 0. In general it is possible to set an upper bound for the digits di. From (3), we deduce diai < ai+1 Pij=10 djaj, so that, since the numbers are all integers: diai ai+1 1 i 1 X djaj < ai+1 j=0
1 ; di ai+1 ai 1
: t = max i ai+1 ai 1
: 81 if m = 0 > am = <k if m = 1 >:kam 1 + ham 2 if m 2
Therefore, the alphabet for Lm is given by f0; 1; : : : ; sg with s = and, denoting by the alphabet for L , we have
max i=0;1;:::;m 1 = f0; 1; : : : ; tg with ai+1 ai 1 ; In this paper we focus our attention on sequences de ned by linear recurrences of the form am = kam 1 + ham 2, with suitable initial conditions and some restrictions on k and h. More precisely, we consider sequences of the form: (4) where k 2 N+ and h 2 Z . Using standard techniques for solving recurrences (see for example [Aig07]) it is possible to show the the general term of the sequence is
1 am = pk2 + 4h k + pk2 + 4h
!m+1 2
1 pk2 + 4h k pk2 + 4h
!m+1 2 and, following [BR01], we require the condition k2 + 4h m 0 (which are the hypothesis of Theorem 2.1). 0 which assures that am 0 and am+1 > am for each
Actually, here we further restrict to a more limiting case for k and h. More precisely we consider the case k h 0, which, of course, implies k2 + 4h 0. From [BR01] it is possible to deduce that in this case the alphabet of the language L is = f0; 1; : : : ; kg. The language L is the set of words w 2 such that 1. w = drdr 1 : : : d1d0 with di 2 2. if di = k, then di 1 < h, for i = 1; 2; : : : ; r; 3. d0 6= k.
In the above list, point 2. is due to the fact that, if N < ai+1 is an integer such that di = k, then, if also di 1 = h, it is N kai + hai 1 = ai+1, which is in contrast with N < ai+1. Moreover, since in the representation of N it is r1 < a1 = k, we have d0 < k.
We recall [BR01] that the following unambiguous regular grammar generates L :
S ! T 0jT 1j T ! T 0jT 1j jT (h jT (h
jS(k jS(k)j . if i and j are symbols, then ij L is the list obtained by concatenating i to each string of i L (or equivalently ij L = i (j L)); if L is a list of word, L is the list in the reverse order; if L is a list of word, (L)i is L if i is even and L if i is odd; if L and M are two lists, L
M is their concatenation; if Lj ; Lj+1; : : : ; Lj+r are lists, r `=0Lj+` is the list Lj : : : Lj+r.
if L is a list of words, then f irst(L) is the rst element of L and last(L) is the last element of L. With the above notation it is not di cult to realize that L can be de ned as follows: > > >>>0 Ln 1 [ 1 Ln 1 [ : : : [ (k > > >:k0 Ln 2 [ k1 Ln 2 [ : : : [ k(h 1) Ln 1[ 1) Ln 2 if n 2 :
Note that from the recursive construction of Ln (n 2), if an element w 2 Ln starts with k, then k is followed by a symbol di erent from h, according to the de nition of the language L in the previous section. If w starts with a symbol di erent from k, then it can be concatenated to any element of Ln 1.
We propose the following de nition providing a particular placement of the elements of L which reveals itself to be a Gray code.
De nition 4.1. Given k 2 N, h 2 Z, with k f0; 1; 2; : : : ; kg: h 0; we de ne the string list Ln over the alphabet = Ln = 8 " >f g > > > > > > <>f0; 1; : : : ; k
1g >8f"g > > > > > < > > > > > > : Ln = f0; 1; : : : ; k
1g ik=01 i (Ln 1)k+i ih=01 ki (Ln 2)k+i Theorem 4.2. The string list Ln is a Gray code with Hamming distance equal to one.
Proof. We proceed by induction on n. If n = 1, then L1 is trivially seen to be a Gray code. Suppose that Li is a Gray code for i = 2; : : : ; n 1 where n 2 and consider the list Ln. The sub-lists arising from each parenthesis in the third case of (6) are Gray codes since the lists Ln 1 and Ln 2 (which are Gray codes by the inductive hypothesis) are read alternatively from left to right and vice versa (depending on the parity of k + 1). Therefore, we have to check only the Hamming distance between last (k 1) (Ln 1)k+i with i = k 1 and f irst k0 (Ln 2)k+i with i = 0.
In the case of k even we have: last (k 1) (Ln 1)k+k 1 = last (k 1) Ln 1 = (k 1)last(Ln 1) = (k 1)f irst(Ln 1) ; and Easily, from (6), we have f irst k0 (Ln 2)k+0
= f irst (k0 Ln 2) = k0f irst(Ln 2) : f irst(Ln 1) = 0f irst(Ln 2) ; then the only di erent digit between (k code.
The proof in the case of k odd can be conducted with similar arguments.
1)f irst(Ln 1) and k0f irst(Ln 2) is the rst one. So Ln is a Gray 5
In the present paper we considered the recurrence relation de ned by am = kam 1 + ham 2 with k h 0, which is one of the two cases analysed in [BR01]. The other interesting case is k h 0 which again leads to a strictly increasing sequence de ning a language L 0 over an alphabet 0 slightly di erent from , with di erent properties. We think that also in this case it is possible to de ne a Gray code for listing the elements of L 0, with Hamming distance 1.
It could be interesting to investigate on the possibilities to characterize the language in terms of restricted words, following the line of [BBBP17b] or [Ber17] where sets of pattern avoiding words and recurrence relations are considered.
Acknowledgements
This work is partially supported by the GNCS 2018 project \Proprieta combinatorie e rilevamento di pattern in strutture discrete lineari e bidimensionali". [Aig07] M. Aigner. Discrete Mathematics. American Mathematical Society, USA, 2007. [BBBP17a] E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani. Cross-bi x-free sets in two dimensions. Theoretical
Computer Science, 664:29{38, 2017. [BBBP17b] E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani. Non-overlapping matrices. Theoretical Computer
Science, 658:36{45, 2017. [BBDD98] E. Barcucci, S. Brunetti, A. Del Lungo and F. Del Ristoro. A combinatorial interpretation of the sequence fn+1 = 6fn fn 1. Discrete Mathematics, 190:235{240, 1998. [BR01] E. Barcucci and S. Rinaldi. Some linear recurrences and their combinatorial interpretation by means of regular languages. Theoretical Computer Science, 255:679{686, 2001. [Ber17] A. Bernini. Restricted binary strings and generalized Fibonacci numbers. Lecture Notes in Computer Science, 10248:32{43, 2017.