A331408 Number of subsets of {1..n} that contain exactly three odd numbers.

0, 0, 0, 0, 4, 8, 32, 64, 160, 320, 640, 1280, 2240, 4480, 7168, 14336, 21504, 43008, 61440, 122880, 168960, 337920, 450560, 901120, 1171456, 2342912, 2981888, 5963776, 7454720, 14909440, 18350080, 36700160, 44564480, 89128960, 106954752, 213909504, 254017536, 508035072, 597688320

Offset: 1

Author

Enrique Navarrete, Jan 16 2020

Keywords

• nonn
• easy

Comments

2*a(n-1) for n > 1 is the number of subsets of {1..n} that contain three even numbers. For example, for n=6, 2*a(5)=8 and the 8 subsets are {2,4,6}, {1,2,4,6}, {2,3,4,6}, {2,4,5,6}, {1,2,3,4,6}, {1,2,4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}.

Examples

			For n = 6, a(6) = 8 and the 8 subsets are {1,3,5}, {1,2,3,5}, {1,3,4,5}, {1,3,5,6}, {1,2,3,4,5}, {1,2,3,5,6}, {1,3,4,5,6}, {1,2,3,4,5,6}.
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (0,8,0,-24,0,32,0,-16).

Crossrefs

Cf. A330592.

Programs

Magma

[IsOdd(n) select Binomial((n+1) div 2, 3)*2^((n-1) div 2) else Binomial((n div 2), 3)*2^(n div 2): n in [1..39]]; // Marius A. Burtea, Jan 17 2020

Mathematica

a[n_] := If[OddQ[n], Binomial[(n + 1)/2, 3]*2^((n - 1)/2), Binomial[n/2, 3]*2^(n/2)]; Array[a, 39] (* Amiram Eldar, Jan 17 2020 *)

PARI

concat([0,0,0,0], Vec(4*x^5*(1 + 2*x) / (1 - 2*x^2)^4 + O(x^40))) \\ Colin Barker, Jan 17 2020

Formula

a(n) = binomial((n+1)/2,3) * 2^((n-1)/2), n odd;

a(n) = binomial(n/2,3) * 2^(n/2), n even.

From Colin Barker, Jan 17 2020: (Start)

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

a(n) = 8*a(n-2) - 24*a(n-4) + 32*a(n-6) - 16*a(n-8) for n>8. (End)

From Amiram Eldar, Mar 24 2022: (Start)

Sum_{n>=5} 1/a(n) = (9/8)*(2*log(2)-1).

Sum_{n>=5} (-1)^(n+1)/a(n) = (3/8)*(2*log(2)-1). (End)