

A170877


Number of binary words of length n with properties that there is no pair of adjacent 1's and no subword of the form X^4 for any string X.


1



1, 2, 3, 5, 7, 10, 15, 22, 30, 43, 61, 88, 123, 173, 246, 348, 487, 688, 972, 1371, 1928, 2714, 3822, 5387, 7582, 10681, 15046, 21194, 29835, 42009, 59159, 83305, 117292, 165170, 232593, 327530, 461198, 649431, 914493, 1287747, 1813281, 2553346, 3595465
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The subword 01010101 (corresponding to X = 01) for example cannot occur.


LINKS



EXAMPLE

a(3) = 5: 000, 001, 010, 100, 101.
a(4) = 7: 0001, 0010, 0100, 1000, 0101, 1010, 1001.


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



