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
Examples
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}.
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).
Programs
-
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
-
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 *) -
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
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)