cp's OEIS Frontend

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

%I A065455 #50 May 06 2025 00:51:55
%S A065455 1,2,4,7,14,25,49,89,172,316,605,1120,2131,3965,7513,14026,26504,
%T A065455 49591,93538,175277,330205,619369,1165892,2188312,4117045,7730828,
%U A065455 14539447,27309529,51349169,96468034,181357036,340753271,640539142,1203616849
%N A065455 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 A065455 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 A065455 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 A065455 G. C. Greubel, <a href="/A065455/b065455.txt">Table of n, a(n) for n = 0..1000</a>
%H A065455 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,3,1).
%F A065455 G.f.: (1+x)^2/(1-3*x^2-x^3).
%e A065455 a(5) = 32-7 = 25 because 00111, 00101, 00100, 10010, 01001, 11001, 00001 are forbidden.
%t A065455 LinearRecurrence[{0,3,1}, {1,2,4}, 40] (* _G. C. Greubel_, May 31 2019 *)
%t A065455 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 A065455 Table[a[n,3,8],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 17 2020 *)
%t A065455 CoefficientList[Series[(1+x)^2/(1-3x^2-x^3),{x,0,50}],x] (* _Harvey P. Dale_, Jul 16 2021 *)
%o A065455 (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 A065455 (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 A065455 (Sage) ((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, May 31 2019
%o A065455 (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 A065455 Cf. A061279 (forbids odd block 0's-odd block 1's), A065494, A065495, A065497.
%Y A065455 Cf. A052545 (this is what we get if n takes negative values).
%K A065455 nonn,easy
%O A065455 0,2
%A A065455 _Len Smiley_, Nov 24 2001