A065495 Number of (binary) bit strings of length n in which an odd length block of 0's is followed by an odd length block of 1's.

1, 2, 6, 14, 32, 72, 156, 336, 712, 1496, 3120, 6464, 13328, 27360, 55968, 114144, 232192, 471296, 954816, 1931264, 3900800, 7869312, 15858432, 31928832, 64232704, 129128960, 259431936, 520941056, 1045557248, 2097616896

Offset: 2

Author

Len Smiley, Nov 24 2001

Keywords

• nonn
• easy

Examples

			a(4) = 6 because of 0100, 0101, 1010, 1101, 0111, 0001.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2,2,-2,-4).

Crossrefs

Cf. A061279 [=2^n - a(n)], A065455, A065494, A065497.

Formula

G.f.: x^2/((1-2*x)*(1-2*x^2-2*x^3)).