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.

Strings from linear recurrences and permutations: A Gray code / Barcucci, Elena; Bernini, Antonio; Pinzani, Renzo. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 938:(2022), pp. 112-120. [10.1016/j.tcs.2022.10.012]

Strings from linear recurrences and permutations: A Gray code

Barcucci, Elena;Bernini, Antonio
;
Pinzani, Renzo
2022

Abstract

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.
938
112
120
Barcucci, Elena; Bernini, Antonio; Pinzani, Renzo
File in questo prodotto:
File Dimensione Formato  
GC_for_prmutations_PREPRINT.pdf

Accesso chiuso

Tipologia: Preprint (Submitted version)
Licenza: DRM non definito
Dimensione 312.51 kB
Formato Adobe PDF
312.51 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/1286305
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact