

A248425


Number of "squares" (repeated identical blocks) in the nth Fibonacci word.


0



0, 0, 0, 0, 1, 4, 11, 26, 57, 118, 235, 454, 857, 1588, 2899, 5228, 9333, 16520, 29031, 50702, 88077, 152290, 262239, 449930, 769461, 1312104, 2231591, 3786456, 6410857, 10832908, 18272195, 30769154, 51733857, 86859598, 145642579, 243907918, 408005393, 681773980, 1138094971, 1898045252, 3162632157, 5265345680
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

Here the Fibonacci words are given by X_0 = 0, X_1 = 1, and X_n = X_{n1} X_{n2} where juxtaposition means concatenation.


LINKS

Table of n, a(n) for n=1..42.
A. S. Fraenkel and J. Simpson, The exact number of squares in Fibonacci words, Theoret. Comput. Sci. 218 (1999), 95106. Note: the formula given there has a small error, which has been corrected below.
A. S. Fraenkel and J. Simpson, Corrigendum to “The exact number of squares in Fibonacci words”, Theoret. Comput. Sci. 218 (1999), 95106.


FORMULA

a(n) = (4/5)nF(n+1)  (2/5)(n+6)F(n)  4F(n1) + n + 1 (for n >= 3).
Empirical g.f.: x^5*(x^4x^2+1) / ((x1)^2*(x^2+x1)^2).  Colin Barker, Oct 07 2014


EXAMPLE

The 5th Fibonacci word is 10110101, which has the following four squares: 11 starting at position 3, 1010 at position 4, 0101 at position 5, and 101101 at position 1.


CROSSREFS

Cf. A061107.
Sequence in context: A027660 A002940 A030196 * A130103 A000295 A125128
Adjacent sequences: A248422 A248423 A248424 * A248426 A248427 A248428


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, Oct 06 2014


STATUS

approved



