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,5

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}.

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

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)

Example

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}.

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

Prog

(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
(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

Crossrefs

Cf. A330592.

Sequence in context: A034041 A050442 A229953 * A291938 A358046 A094015

Adjacent sequences: A331405 A331406 A331407 * A331409 A331410 A331411

Keyword

nonn,easy

Author

Enrique Navarrete, Jan 16 2020

Status

approved