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,5

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)

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).

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

Example

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

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 *)

Prog

(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

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.

Sequence in context: A001982 A129707 A320545 * A133546 A190376 A276785

Adjacent sequences: A232577 A232578 A232579 * A232581 A232582 A232583

Keyword

nonn,easy

Author

Geoffrey Critzer, Nov 26 2013

Status

approved