OFFSET
0,3
COMMENTS
a(n) is the number of binary strings of length n that contain none, two, five, or a larger odd number of 0's.
LINKS
Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).
FORMULA
E.g.f.: exp(x)*(sinh(x) + 1 - x + x^2/2 - x^3/6).
From Stefano Spezia, Aug 11 2021: (Start)
O.g.f.: (1 - 5*x + 10*x^2 - 10*x^3 + 4*x^4 + x^5)/((1 - x)^4*(1 - 2*x)).
a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5) for n > 5. (End)
EXAMPLE
a(6)=22 since the strings are the 15 permutations of 001111, the 6 permutations of 000001, and 111111.
MATHEMATICA
Table[Floor[2^(n-1)]-Binomial[n, 3]+Binomial[n, 2]-n+1, {n, 0, 40}] (* or *) LinearRecurrence[{6, -14, 16, -9, 2}, {1, 1, 2, 4, 7, 12}, 40] (* Harvey P. Dale, Sep 02 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Aug 10 2021
STATUS
approved