A133552 Number of length n binary sequences with at most 4 of every adjacent 6 bits set.

1, 2, 4, 8, 16, 31, 57, 109, 209, 401, 769, 1473, 2817, 5391, 10321, 19761, 37834, 72432, 138663, 265455, 508195, 972909, 1862575, 3565778, 6826437, 13068741, 25019217, 47897608, 91696751, 175547250, 336073354, 643389727, 1231726180

Offset

0,2

Links

Table of n, a(n) for n=0..32.

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

Formula

Conjectures from Colin Barker, Feb 22 2018: (Start)

G.f.: (1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - 2*x^6 - 3*x^7 - 2*x^8 - x^10 - x^11 + x^13 + x^14) / (1 - x - x^2 - x^3 - x^5 - 2*x^6 + 2*x^8 + 2*x^9 + x^12 - x^15).

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-5) + 2*a(n-6) - 2*a(n-8) - 2*a(n-9) - a(n-12) + a(n-15) for n>14.

(End)

Mathematica

CoefficientList[Series[(1+x+x^2+x^3+2x^4+2x^5-2x^6-3x^7-2x^8-x^10-x^11+x^13+x^14)/(1-x-x^2-x^3-x^5-2x^6+2x^8+2x^9+x^12-x^15), {x, 0, 50}], x] (* or *) LinearRecurrence[ {1, 1, 1, 0, 1, 2, 0, -2, -2, 0, 0, -1, 0, 0, 1}, {1, 2, 4, 8, 16, 31, 57, 109, 209, 401, 769, 1473, 2817, 5391, 10321}, 50] (* Harvey P. Dale, Aug 14 2023 *)

Crossrefs

Sequence in context: A325749 A056183 A000127 * A174439 A000128 A106399

Adjacent sequences: A133549 A133550 A133551 * A133553 A133554 A133555

Keyword

nonn

Author

R. H. Hardin, Dec 24 2007

Status

approved