A309128 (1/n) times the sum of the elements of all subsets of [n] whose sum is divisible by n.

1, 1, 4, 4, 12, 20, 40, 70, 150, 284, 564, 1116, 2212, 4392, 8768, 17404, 34704, 69214, 137980, 275264, 549340, 1096244, 2188344, 4369196, 8724196, 17422500, 34797476, 69505628, 138845940, 277383904, 554189344, 1107296248, 2212559996, 4421289872, 8835361488

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Formula

Conjecture: a(n) = (n + 1) * A063776(n)/4 - (phi(n)/2) * (1 + (-1)^n)/2 = ((n + 1)/(4*n)) * A053636(n) - (phi(n)/2) * (1 + (-1)^n)/2. - Petros Hadjicostas, Jul 20 2019

a(n) = A309280(n,n). - Alois P. Heinz, Jul 21 2019

Example

The subsets of [5] whose sum is divisible by 5 are: {}, {5}, {1,4}, {2,3}, {1,4,5}, {2,3,5}, {1,2,3,4}, {1,2,3,4,5}.  The sum of their elements is 0 + 5 + 5 + 5 + 10 + 10 + 10 + 15 = 60.  So a(5) = 60/5 = 12.

Maple

b:= proc(n, m, s) option remember; `if`(n=0, [`if`(s=0, 1, 0), 0],
      b(n-1, m, s) +(g-> g+[0, g[1]*n])(b(n-1, m, irem(s+n, m))))
    end:
a:= proc(n) option remember; forget(b); b(n$2, 0)[2]/n end:
seq(a(n), n=1..40);

Mathematica

b[n_, m_, s_] := b[n, m, s] = If[n == 0, {If[s == 0, 1, 0], 0},
     b[n-1, m, s] + Function[g, g+{0, g[[1]] n}][b[n-1, m, Mod[s+n, m]]]];
a[n_] := b[n, n, 0][[2]]/n;
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

Crossrefs

Cf. A000010, A001792 (the same for all subsets), A053636, A063776, A309122, A309280.

Sequence in context: A303315 A331606 A079902 * A120033 A097073 A019085

Adjacent sequences: A309125 A309126 A309127 * A309129 A309130 A309131

Keyword

nonn

Author

Alois P. Heinz, Jul 13 2019

Status

approved