A234933 The number of binary sequences that contain at least two consecutive 1's and contain at least two consecutive 0's.

0, 0, 0, 0, 2, 8, 24, 62, 148, 336, 738, 1584, 3344, 6974, 14412, 29576, 60370, 122712, 248616, 502398, 1013156, 2039840, 4101570, 8238560, 16534432, 33161598, 66473244, 133189272, 266771378, 534178376, 1069385208, 2140434494, 4283561524, 8571479664, 17150008482, 34311422736, 68641300400

Offset

0,5

Links

Colin Barker, Table of n, a(n) for n = 0..1000

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

Formula

a(n) = 2*A232580(n-1) for n>0.

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

From Colin Barker, Nov 03 2016: (Start)

a(n) = 2^(-n)*(5*2^n*(2+2^n)+(1-sqrt(5))^n*(-5+3*sqrt(5))-(1+sqrt(5))^n*(5+3*sqrt(5)))/5 for n>0.

a(n) = 4*a(n-1)-4*a(n-2)-a(n-3)+2*a(n-4) for n>4.

(End)

a(n) = 2*(A000079(n-1)-A000045(n+2)+1) for n>0. - Ehren Metcalfe, Dec 27 2018

Example

a(5) = 8 because we have:
1: {0, 0, 0, 1, 1},
2: {0, 0, 1, 1, 0},
3: {0, 0, 1, 1, 1},
4: {0, 1, 1, 0, 0},
5: {1, 0, 0, 1, 1},
6: {1, 1, 0, 0, 0},
7: {1, 1, 0, 0, 1},
8: {1, 1, 1, 0, 0}.

Mathematica

nn = 25; a = (x + x^2)/(1 - x^2); b = 1/(1 - 2x); c = 1/(1 - x - x^2); CoefficientList[Series[2x^3 a b c, {x, 0, nn}], x]
(* or *)
Table[Length[Select[Tuples[{0, 1}, n], MatchQ[#, {___, 1, 1, ___}] && MatchQ[#, {___, 0, 0, ___}] &]], {n, 0, 15}]
Join[{0}, LinearRecurrence[{4, -4, -1, 2}, {0, 0, 0, 2}, 40]] (* Vincenzo Librandi, Dec 28 2018 *)

Prog

(PARI) concat([0, 0, 0, 0], Vec(2*x^4/(1-4*x+4*x^2+x^3-2*x^4)+O(x^66))) \\ Joerg Arndt, Jan 04 2014
(Magma) I:=[0, 0, 0, 0, 2]; [n le 5 select I[n] else 4*Self(n-1)-4*Self(n-2)-Self(n-3)+2*Self(n-4): n in [1..40]]; // Vincenzo Librandi, Dec 28 2018

Crossrefs

Cf. A000045, A000079, A232580.

Sequence in context: A263598 A075218 A006728 * A222808 A075216 A127790

Adjacent sequences: A234930 A234931 A234932 * A234934 A234935 A234936

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 01 2014

Status

approved