A241674 Number of factors of length 2n of the Fibonacci word (A003849) that are abelian squares.

1, 3, 5, 1, 9, 5, 5, 15, 3, 13, 13, 5, 25, 9, 15, 25, 1, 27, 19, 11, 41, 9, 27, 33, 5, 45, 21, 23, 49, 5, 43, 35, 15, 67, 19, 37, 55, 3, 63, 35, 27, 77, 13, 55, 57, 13, 85, 33, 43, 81, 5, 75, 55, 27, 109, 25, 63, 81, 9, 101, 49, 45, 111, 15, 85, 77, 25, 129, 41, 67, 109, 1, 113, 69, 45

Offset

1,2

Comments

A "factor" is a contiguous block. An "abelian square" is a word of the form x x' where x' is a permutation of x.

References

Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties. See just below Theorem 11.

Links

Table of n, a(n) for n=1..75.

Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance, arXiv:1406.0670 [cs.FL], 2014.

Gabriele Fici, Filippo Mignosi, Words with the Maximum Number of Abelian Squares, arXiv:1506.03562 [cs.DM], 2015.

Gabriele Fici, Filippo Mignosi, Jeffrey Shallit, Abelian-Square-Rich Words, arXiv:1701.00948 [cs.DM], 2016. See Table 2 p. 14.

Formula

a(F(n)) = 2*F(n) - 1 for n >= 2, where F(n) is the n-th Fibonacci number.

a(n) = #{x such that x = {-i*alpha} for some 1<=i<=n and x <= {-n*alpha} if the integer part of n*alpha is even, or x >= {-n*alpha} if the integer part of n*alpha is odd}, where alpha=(sqrt(5)-1)/2. - Gabriele Fici, Sep 17 2015

Example

a(3) = 5 because the length-6 words {010010, 001010, 010100, 100100, 001001} all occur in the Fibonacci word and are abelian squares (and no others).

Crossrefs

Cf. A003849.

Sequence in context: A283838 A228146 A328013 * A021970 A115335 A214062

Adjacent sequences: A241671 A241672 A241673 * A241675 A241676 A241677

Keyword

nonn

Author

Jeffrey Shallit, Jul 10 2014

Status

approved