cp's OEIS Frontend

A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.

%I A232580 #40 Jun 27 2022 08:49:59
%S A232580 0,0,0,1,4,12,31,74,168,369,792,1672,3487,7206,14788,30185,61356,
%T A232580 124308,251199,506578,1019920,2050785,4119280,8267216,16580799,
%U A232580 33236622,66594636,133385689,267089188,534692604,1070217247,2141780762,4285739832,8575004241
%N A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.
%C A232580 From _Gus Wiseman_, Jun 26 2022: (Start)
%C A232580 Also the number of integer compositions of n + 1 with an even part other than the first or last. For example, the a(3) = 1 through a(5) = 12 compositions are:
%C A232580   (121)  (122)   (123)
%C A232580          (221)   (141)
%C A232580          (1121)  (222)
%C A232580          (1211)  (321)
%C A232580                  (1122)
%C A232580                  (1212)
%C A232580                  (1221)
%C A232580                  (2121)
%C A232580                  (2211)
%C A232580                  (11121)
%C A232580                  (11211)
%C A232580                  (12111)
%C A232580 The odd version is A274230.
%C A232580 (End)
%H A232580 Colin Barker, <a href="/A232580/b232580.txt">Table of n, a(n) for n = 0..1000</a>
%H A232580 Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 34.
%H A232580 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,-1,2).
%F A232580 O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).
%F A232580 a(n) ~ 2^n.
%F A232580 From _Colin Barker_, Nov 03 2016: (Start)
%F A232580 a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).
%F A232580 a(n) = 4*a(n-1) - 4*a(n-2) - a(n-3) + 2*a(n-4) for n > 3. (End)
%F A232580 a(n) = 2^n - Fibonacci(n+3) + 1. - _Ehren Metcalfe_, Dec 27 2018
%F A232580 E.g.f.: 2*exp(x/2)*(5*exp(x)*cosh(x/2) - 5*cosh(sqrt(5)*x/2) - 2*sqrt(5)*sinh(sqrt(5)*x/2))/5. - _Stefano Spezia_, Apr 06 2022
%e A232580 a(4) = 4 because we have: 0011, 0110, 0111, 1011.
%t A232580 nn=40;a=x/(1-x);CoefficientList[Series[a^2 x/(1-a x)/(1-2x),{x,0,nn}],x]
%t A232580 (* second program *)
%t A232580 Table[Length[Select[Tuples[{0,1},n],MatchQ[#,{___,0,1,1,___}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 26 2022 *)
%o A232580 (PARI) concat(vector(3), Vec(x^3/(-2*x^4+x^3+4*x^2-4*x+1) + O(x^40))) \\ _Colin Barker_, Nov 03 2016
%Y A232580 The complement is counted by A000071(n) = A001911(n) + 1.
%Y A232580 For the contiguous pattern (1,1) or (0,0) we have A000225.
%Y A232580 For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.
%Y A232580 For the contiguous pattern (1,0) or (0,1) we have A000295.
%Y A232580 Numbers whose binary expansion is of this type are A004750.
%Y A232580 For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.
%Y A232580 The not necessarily contiguous version is A324172.
%Y A232580 Cf. A034691, A261983, A274230, A335455, A335457, A335458, A335516.
%K A232580 nonn,easy
%O A232580 0,5
%A A232580 _Geoffrey Critzer_, Nov 26 2013