A347017 a(n) = floor(2^(n-1)) - binomial(n,3) + binomial(n,2) - n + 1.

1, 1, 2, 4, 7, 12, 22, 44, 93, 200, 428, 904, 1883, 3876, 7906, 16020, 32313, 64976, 130392, 261328, 523319, 1047436, 2095822, 4192764, 8386837, 16775192, 33552132, 67106264, 134214803, 268432180, 536867258, 1073737764, 2147479153, 4294962336, 8589929136, 17179863200, 34359731823

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

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

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

Cf. A002664, A342379, A342380.

Sequence in context: A072641 A280352 A135360 * A082548 A270995 A299023

Adjacent sequences: A347014 A347015 A347016 * A347018 A347019 A347020

Keyword

nonn,easy

Author

Enrique Navarrete, Aug 10 2021

Status

approved