A065455 - OEIS

%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