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, 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

Offset: 0

Author

Benjamin Chaffin and N. J. A. Sloane, Jan 07 2010

Keywords

• nonn

Comments

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

Examples

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

Links

• Lars Blomberg, Table of n, a(n) for n = 0..43

Crossrefs

Cf. A003410, A028445, A135491.

Extensions

a(24)-a(42) from Lars Blomberg, Aug 22 2013