login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A210021 Number of binary words of length n containing no subword 11011. 4
1, 2, 4, 8, 16, 31, 60, 116, 225, 437, 849, 1649, 3202, 6217, 12071, 23438, 45510, 88368, 171586, 333171, 646922, 1256136, 2439055, 4735945, 9195847, 17855697, 34670640, 67320433, 130716961, 253814826, 492835556, 956945224, 1858113016, 3607922263, 7005549684 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Math Stack Exchange, circa Sep 09 2016

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,1).

FORMULA

G.f.: -(x^4+x^3+1)/(x^5+x^4-x^3+2*x-1).

a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-3) +a(n-4) +a(n-5) otherwise.

EXAMPLE

a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0011011, 0110110, 0110111, 0111011, 1011011, 1101100, 1101101, 1101110, 1101111, 1110110, 1110111 and 1111011 contain the subword 11011.

MAPLE

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|1|-1|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

MATHEMATICA

LinearRecurrence[{2, 0, -1, 1, 1}, {1, 2, 4, 8, 16}, 40] (* Vincenzo Librandi, Oct 24 2016 *)

PROG

(MAGMA) I:=[1, 2, 4, 8, 16]; [n le 5 select I[n] else 2*Self(n-1)-Self(n-3)+Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Oct 24 2016

CROSSREFS

Column k=27 of A209972. Cf. A276785.

Column k=0 of A277678.

Sequence in context: A141019 A210003 A209888 * A226188 A239556 A152718

Adjacent sequences:  A210018 A210019 A210020 * A210022 A210023 A210024

KEYWORD

nonn,easy

AUTHOR

Alois P. Heinz, Mar 16 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 23:47 EST 2021. Contains 340332 sequences. (Running on oeis4.)