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

%I #37 Sep 08 2022 08:46:06

%S 0,0,0,0,2,8,24,62,148,336,738,1584,3344,6974,14412,29576,60370,

%T 122712,248616,502398,1013156,2039840,4101570,8238560,16534432,

%U 33161598,66473244,133189272,266771378,534178376,1069385208,2140434494,4283561524,8571479664,17150008482,34311422736,68641300400

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

%H Colin Barker, <a href="/A234933/b234933.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,-1,2).

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

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

%F From _Colin Barker_, Nov 03 2016: (Start)

%F 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.

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

%F (End)

%F a(n) = 2*(A000079(n-1)-A000045(n+2)+1) for n>0. - _Ehren Metcalfe_, Dec 27 2018

%e a(5) = 8 because we have:

%e 1: {0, 0, 0, 1, 1},

%e 2: {0, 0, 1, 1, 0},

%e 3: {0, 0, 1, 1, 1},

%e 4: {0, 1, 1, 0, 0},

%e 5: {1, 0, 0, 1, 1},

%e 6: {1, 1, 0, 0, 0},

%e 7: {1, 1, 0, 0, 1},

%e 8: {1, 1, 1, 0, 0}.

%t 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]

%t (* or *)

%t Table[Length[Select[Tuples[{0, 1}, n], MatchQ[#, {___, 1, 1, ___}] && MatchQ[#, {___, 0, 0, ___}] &]], {n, 0, 15}]

%t Join[{0}, LinearRecurrence[{4, -4, -1, 2}, {0, 0, 0, 2}, 40]] (* _Vincenzo Librandi_, Dec 28 2018 *)

%o (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

%o (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

%Y Cf. A000045, A000079, A232580.

%K nonn,easy

%O 0,5

%A _Geoffrey Critzer_, Jan 01 2014