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

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

References

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

Links

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

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).

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

Example

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

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 *)

Crossrefs

Sequence in context: A011957 A019436 A147852 * A018073 A357451 A224342

Adjacent sequences: A061276 A061277 A061278 * A061280 A061281 A061282

Keyword

easy,nonn

Author

Vladeta Jovovic, Jun 04 2001

Status

approved