A061279 a(n) = Sum_{k >= 0} 2^k * binomial(k+2,n-2*k).

1, 2, 3, 6, 10, 18, 32, 56, 100, 176, 312, 552, 976, 1728, 3056, 5408, 9568, 16928, 29952, 52992, 93760, 165888, 293504, 519296, 918784, 1625600, 2876160, 5088768, 9003520, 15929856, 28184576, 49866752, 88228864, 156102656

Offset: 0

Author

Vladeta Jovovic, Jun 04 2001

Keywords

• easy
• nonn

Comments

a(n) counts (binary) bit strings of length n in which no odd length block of 0's is followed by an odd length block of 1's. - Len Smiley, Nov 23 2001

Examples

			a(3) = 6 because only 2 of the 8 binary words of length 3 are such that an odd maximal block of 1's follows an odd maximal block of 0's: 010 and 101. - _Geoffrey Critzer_, May 28 2017
		

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(2.4.6).

Links

• Yunseo Choi and Katelyn Gan, Ungar Games on the Young-Fibonacci and the Shifted Staircase Lattices, arXiv:2406.10927 [math.CO], 2024. See p. 2.
• Index entries for linear recurrences with constant coefficients, signature (0,2,2).

Programs

Mathematica

nn = 30; a[x] := 1/(1 - x);c[x_] := x/(1 - x^2); CoefficientList[Series[a[x]^2/(1 - (x^2 a[x]^2 - c[x]^2)) , {x, 0, nn}], x] (*Geoffrey Critzer, May 28 2017*)
LinearRecurrence[{0,2,2},{1,2,3},40] (* Harvey P. Dale, May 05 2023 *)

Formula

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

a(n) = 2*a(n-2) + 2*a(n-3) for n>=3 with a(0)=1, a(1)=2, a(2)=3. - Wesley Ivan Hurt, Jan 01 2024