login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #46 Sep 08 2022 08:45:04

%S 1,2,4,7,14,25,49,89,172,316,605,1120,2131,3965,7513,14026,26504,

%T 49591,93538,175277,330205,619369,1165892,2188312,4117045,7730828,

%U 14539447,27309529,51349169,96468034,181357036,340753271,640539142,1203616849

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

%C The limit of the ratio of successive terms as n increases can be shown to be 2*cos(Pi/9). In the opposite direction, as n—->-oo (see A052545), a(n+1)/a(n) approaches 2*cos(5*Pi/9). For example, a(-6)/a(-7) = -92/265, which is close to 2*cos(5*Pi/9). - _Richard Locke Peterson_, Apr 22 2019

%C Let P(n, j, m) = Sum_{r=1..m} (2^n*(1-(-1)^r)*cos(Pi*r/(m+1))^n*cot(Pi*r/(2*(m+1)))* sin(j*Pi*r/(m+1)))/(m+1) denote the number of paths of length n starting at the j-th node on the path graph P_m. We have a(n) = P(n, 3, 8). - _Herbert Kociemba_, Sep 17 2020

%H G. C. Greubel, <a href="/A065455/b065455.txt">Table of n, a(n) for n = 0..1000</a>

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

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

%e a(5) = 32-7 = 25 because 00111, 00101, 00100, 10010, 01001, 11001, 00001 are forbidden.

%t LinearRecurrence[{0,3,1}, {1,2,4}, 40] (* _G. C. Greubel_, May 31 2019 *)

%t a[n_,j_,m_]:=Sum[(2^(n+1)Cos[Pi r/(m+1)]^n Cot[Pi r/(2(m+1))] Sin[j Pi r/(m+1)])/(m+1),{r,1,m,2}]

%t Table[a[n,3,8],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 17 2020 *)

%t CoefficientList[Series[(1+x)^2/(1-3x^2-x^3),{x,0,50}],x] (* _Harvey P. Dale_, Jul 16 2021 *)

%o (PARI) a(n)=([0,1,0;0,0,1;1,3,0]^n*[1;2;4])[1,1] \\ _Charles R Greathouse IV_, Jun 11 2015

%o (Magma) I:=[1,2,4]; [n le 3 select I[n] else 3*Self(n-2) +Self(n-3): n in [1..40]]; // _G. C. Greubel_, May 31 2019

%o (Sage) ((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, May 31 2019

%o (GAP) a:=[1,2,4];; for n in [4..40] do a[n]:=3*a[n-2]+a[n-3]; od; a; # _G. C. Greubel_, May 31 2019

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

%Y Cf. A052545 (this is what we get if n takes negative values).

%K nonn,easy

%O 0,2

%A _Len Smiley_, Nov 24 2001