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.

1, 2, 4, 7, 14, 25, 49, 89, 172, 316, 605, 1120, 2131, 3965, 7513, 14026, 26504, 49591, 93538, 175277, 330205, 619369, 1165892, 2188312, 4117045, 7730828, 14539447, 27309529, 51349169, 96468034, 181357036, 340753271, 640539142, 1203616849

Offset: 0

Author

Len Smiley, Nov 24 2001

Keywords

• nonn
• easy

Comments

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

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

Examples

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

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (0,3,1).

Crossrefs

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

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

Programs

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

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

Mathematica

LinearRecurrence[{0,3,1}, {1,2,4}, 40] (* G. C. Greubel, May 31 2019 *)
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}]
Table[a[n,3,8],{n,0,40}]//Round (* Herbert Kociemba, Sep 17 2020 *)
CoefficientList[Series[(1+x)^2/(1-3x^2-x^3),{x,0,50}],x] (* Harvey P. Dale, Jul 16 2021 *)

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

Sage

((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 31 2019

Formula

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