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

%I #25 Jun 20 2024 16:25:36

%S 1,2,3,6,10,18,32,56,100,176,312,552,976,1728,3056,5408,9568,16928,

%T 29952,52992,93760,165888,293504,519296,918784,1625600,2876160,

%U 5088768,9003520,15929856,28184576,49866752,88228864,156102656

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

%C 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

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

%H Yunseo Choi and Katelyn Gan, <a href="https://arxiv.org/abs/2406.10927">Ungar Games on the Young-Fibonacci and the Shifted Staircase Lattices</a>, arXiv:2406.10927 [math.CO], 2024. See p. 2.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,2).

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

%F 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

%e 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

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

%t LinearRecurrence[{0,2,2},{1,2,3},40] (* _Harvey P. Dale_, May 05 2023 *)

%K easy,nonn

%O 0,2

%A _Vladeta Jovovic_, Jun 04 2001