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

%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