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

0, 0, 0, 1, 4, 12, 31, 74, 168, 369, 792, 1672, 3487, 7206, 14788, 30185, 61356, 124308, 251199, 506578, 1019920, 2050785, 4119280, 8267216, 16580799, 33236622, 66594636, 133385689, 267089188, 534692604, 1070217247, 2141780762, 4285739832, 8575004241

Offset: 0

Author

Geoffrey Critzer, Nov 26 2013

Keywords

• nonn
• easy

Comments

From Gus Wiseman, Jun 26 2022: (Start)

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:

(121) (122) (123)

(221) (141)

(1121) (222)

(1211) (321)

(1122)

(1212)

(1221)

(2121)

(2211)

(11121)

(11211)

(12111)

The odd version is A274230.

(End)

Examples

			a(4) = 4 because we have: 0011, 0110, 0111, 1011.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 34.
• Index entries for linear recurrences with constant coefficients, signature (4,-4,-1,2).

Crossrefs

The complement is counted by A000071(n) = A001911(n) + 1.

For the contiguous pattern (1,1) or (0,0) we have A000225.

For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.

For the contiguous pattern (1,0) or (0,1) we have A000295.

Numbers whose binary expansion is of this type are A004750.

For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.

The not necessarily contiguous version is A324172.

Cf. A034691, A261983, A274230, A335455, A335457, A335458, A335516.

Programs

Mathematica

nn=40;a=x/(1-x);CoefficientList[Series[a^2 x/(1-a x)/(1-2x),{x,0,nn}],x]
(* second program *)
Table[Length[Select[Tuples[{0,1},n],MatchQ[#,{_,0,1,1,_}]&]],{n,0,10}] (* Gus Wiseman, Jun 26 2022 *)

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

Formula

O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).

a(n) ~ 2^n.

From Colin Barker, Nov 03 2016: (Start)

a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).

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

a(n) = 2^n - Fibonacci(n+3) + 1. - Ehren Metcalfe, Dec 27 2018

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