A164457 Number of binary strings of length n with no substrings equal to 0001, 0011, or 1010.

1, 2, 4, 8, 13, 21, 33, 52, 82, 128, 200, 313, 488, 761, 1188, 1852, 2887, 4503, 7020, 10943, 17063, 26601, 41468, 64652, 100792, 157128, 244965, 381898, 595363, 928166, 1446998, 2255827, 3516797, 5482628, 8547285, 13325053, 20773513, 32385456, 50488278

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 500 terms from R. H. Hardin)

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

Formula

G.f.: -(x^7-2*x^6+x^2+1)/((x-1)*(x^4-2*x^3-x+1)). - R. J. Mathar, Jan 19 2011

Mathematica

LinearRecurrence[{2, -1, 2, -3, 1}, {1, 2, 4, 8, 13, 21, 33, 52}, 40] (* Harvey P. Dale, Aug 19 2022 *)

Prog

(PARI) a(n)=if(n>2, ([0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; 1, -3, 2, -1, 2]^(n-3)*[8; 13; 21; 33; 52])[1, 1], [1, 2, 4][n+1]) \\ Charles R Greathouse IV, May 28 2026

Crossrefs

Sequence in context: A164429 A073336 A164420 * A164419 A164431 A164480

Adjacent sequences: A164454 A164455 A164456 * A164458 A164459 A164460

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Extensions

Edited by Alois P. Heinz, Oct 12 2017

Status

approved