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,2

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

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

Formula

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

Example

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

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

Prog

(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
(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
(Sage) ((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 31 2019
(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

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

Sequence in context: A065491 A072810 A167606 * A220842 A026010 A088813

Adjacent sequences: A065452 A065453 A065454 * A065456 A065457 A065458

Keyword

nonn,easy

Author

Len Smiley, Nov 24 2001

Status

approved