|
%I #40 Jun 27 2022 08:49:59
%S 0,0,0,1,4,12,31,74,168,369,792,1672,3487,7206,14788,30185,61356,
%T 124308,251199,506578,1019920,2050785,4119280,8267216,16580799,
%U 33236622,66594636,133385689,267089188,534692604,1070217247,2141780762,4285739832,8575004241
%N Number of binary sequences of length n that contain at least one contiguous subsequence 011.
%C From _Gus Wiseman_, Jun 26 2022: (Start)
%C 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 (121) (122) (123)
%C (221) (141)
%C (1121) (222)
%C (1211) (321)
%C (1122)
%C (1212)
%C (1221)
%C (2121)
%C (2211)
%C (11121)
%C (11211)
%C (12111)
%C The odd version is A274230.
%C (End)
%H Colin Barker, <a href="/A232580/b232580.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,-1,2).
%F O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).
%F a(n) ~ 2^n.
%F From _Colin Barker_, Nov 03 2016: (Start)
%F a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).
%F a(n) = 4*a(n-1) - 4*a(n-2) - a(n-3) + 2*a(n-4) for n > 3. (End)
%F a(n) = 2^n - Fibonacci(n+3) + 1. - _Ehren Metcalfe_, Dec 27 2018
%F 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 a(4) = 4 because we have: 0011, 0110, 0111, 1011.
%t nn=40;a=x/(1-x);CoefficientList[Series[a^2 x/(1-a x)/(1-2x),{x,0,nn}],x]
%t (* second program *)
%t Table[Length[Select[Tuples[{0,1},n],MatchQ[#,{___,0,1,1,___}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 26 2022 *)
%o (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 The complement is counted by A000071(n) = A001911(n) + 1.
%Y For the contiguous pattern (1,1) or (0,0) we have A000225.
%Y For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.
%Y For the contiguous pattern (1,0) or (0,1) we have A000295.
%Y Numbers whose binary expansion is of this type are A004750.
%Y For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.
%Y The not necessarily contiguous version is A324172.
%Y Cf. A034691, A261983, A274230, A335455, A335457, A335458, A335516.
%K nonn,easy
%O 0,5
%A _Geoffrey Critzer_, Nov 26 2013
|
