A065497 -id:A065497 - 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.

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

Len Smiley, Nov 24 2001

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

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

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

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

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

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

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

a(n)=([0,1,0;0,0,1;1,3,0]^n*[1;2;4])[1,1] \\ Charles R Greathouse IV, Jun 11 2015

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

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

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

Original entry on oeis.org

1, 2, 4, 8, 15, 30, 57, 112, 216, 420, 815, 1580, 3069, 5950, 11552, 22408, 43487, 84378, 163725, 317700, 616444, 1196172, 2321007, 4503704, 8738921, 16956954, 32903164, 63845000, 123884479, 240384374, 466440273, 905077080, 1756205088

Offset: 0

Len Smiley, Nov 24 2001

			a(6)=64-7=57 because 000011, 001111, 001100, 001101, 100110, 010011, 110011 are forbidden.

Index entries for linear recurrences with constant coefficients, signature (0,3,2,-1).

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

O.g.f.: (1+x)^2/(1-3x^2-2x^3+x^4)

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

Original entry on oeis.org

1, 2, 6, 14, 32, 72, 156, 336, 712, 1496, 3120, 6464, 13328, 27360, 55968, 114144, 232192, 471296, 954816, 1931264, 3900800, 7869312, 15858432, 31928832, 64232704, 129128960, 259431936, 520941056, 1045557248, 2097616896

Offset: 2

Len Smiley, Nov 24 2001

			a(4) = 6 because of 0100, 0101, 1010, 1101, 0111, 0001.

Index entries for linear recurrences with constant coefficients, signature (2,2,-2,-4).

Cf. A061279 [=2^n - a(n)], A065455, A065494, A065497.

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula