A065494 Number of (binary) bit strings in which no even length block of 0's is followed by an even length block of 1's.

1, 2, 4, 8, 15, 30, 57, 112, 216, 420, 815, 1580, 3069, 5950, 11552, 22408, 43487, 84378, 163725, 317700, 616444, 1196172, 2321007, 4503704, 8738921, 16956954, 32903164, 63845000, 123884479, 240384374, 466440273, 905077080, 1756205088

Offset

0,2

Links

Table of n, a(n) for n=0..32.

Index entries for linear recurrences with constant coefficients, signature (0,3,2,-1).

Formula

O.g.f.: (1+x)^2/(1-3x^2-2x^3+x^4)

Example

a(6)=64-7=57 because 000011, 001111, 001100, 001101, 100110, 010011, 110011 are forbidden.

Crossrefs

Cf. A061279 (forbids odd block 0's - odd block 1's), A065455, A065495, A065497.

Sequence in context: A026023 A077596 A091865 * A134044 A079967 A192655

Adjacent sequences: A065491 A065492 A065493 * A065495 A065496 A065497

Keyword

nonn,easy

Author

Len Smiley, Nov 24 2001

Status

approved