A027711 Number of binary sequences of length n with an even number of ones, at least two of the ones being contiguous.

0, 1, 2, 4, 9, 21, 47, 101, 212, 440, 907, 1859, 3791, 7699, 15586, 31476, 63445, 127689, 256671, 515433, 1034248, 2073968, 4156791, 8327911, 16679007, 33395527, 66851750, 133801708, 267762321, 535781757, 1071979535

Offset

1,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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

Formula

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

a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3) + a(n-4) - 2*a(n-5).

Mathematica

LinearRecurrence[{4, -5, 2, 1, -2}, {0, 1, 2, 4, 9}, 40] (* Vincenzo Librandi, Jun 20 2012 *)
CoefficientList[Series[x^2*(1-2*x+x^2+x^3)/((2*x-1)*(x^2+x-1)*(x^2-x+1)), {x, 0, 50}], x] (* G. C. Greubel, Jun 10 2017 *)

Prog

(Magma) I:=[0, 1, 2, 4, 9]; [n le 5 select I[n] else 4*Self(n-1)-5*Self(n-2)+2*Self(n-3)+Self(n-4)-2*Self(n-5): n in [1..40]]; // Vincenzo Librandi, Jun 20 2012
(PARI) x='x+O('x^50); Vec(x^2*(1-2*x+x^2+x^3)/((2*x-1)*(x^2+x-1)*(x^2-x+1))) \\ G. C. Greubel, Jun 10 207

Crossrefs

Sequence in context: A091619 A061439 A351644 * A307548 A084634 A137256

Adjacent sequences: A027708 A027709 A027710 * A027712 A027713 A027714

Keyword

nonn,easy

Author

R. K. Guy

Extensions

Typo in denominator of g.f. corrected by R. J. Mathar, Sep 03 2010

Status

approved