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

Author

Enrique Navarrete, Aug 10 2021

Keywords

• nonn
• easy

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.

Examples

			a(6)=22 since the strings are the 15 permutations of 001111, the 6 permutations of 000001, and 111111.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Crossrefs

Cf. A002664, A342379, A342380.

Programs

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 *)

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)