The number of valid factorizations of Fibonacci prefixes

Autor:	Bonardo, Pierre, Frid, Anna E., Shallit, Jeffrey
Rok vydání:	2018
Předmět:	Mathematics - Combinatorics Computer Science - Formal Languages and Automata Theory 68R15 11B39
Druh dokumentu:	Working Paper
DOI:	10.1016/j.tcs.2018.12.016
Popis:	We establish several recurrence relations and an explicit formula for V(n), the number of factorizations of the length-n prefix of the Fibonacci word into a (not necessarily strictly) decreasing sequence of standard Fibonacci words. In particular, we show that the sequence V(n) is the shuffle of the ceilings of two linear functions of n. Comment: Version accepted to Theoretical Computer Science
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1806.09534 Zobrazit plný text záznamu View this record from Arxiv