A309122 Sum of the sizes of all subsets of [n] whose sum is divisible by n.

1, 1, 6, 6, 20, 34, 70, 124, 270, 516, 1034, 2060, 4108, 8198, 16440, 32760, 65552, 131142, 262162, 524312, 1048740, 2097162, 4194326, 8388856, 16777300, 33554444, 67109418, 134217764, 268435484, 536872072, 1073741854, 2147483632, 4294969404, 8589934608

Offset

1,3

Comments

The bivariate g.f. of array T(n,k) = A267632(n,k) is Sum_{n, k >= 1} T(n,k) * x^n * y^k = -x/(1 - x) - Sum_{s >= 1} (phi(s)/s) * log(1 - x^s + (-x*y)^s). Differentiating w.r.t. y and setting y = 1, we get the g.f. of a(n) = k * Sum_{1 <= k <= n} T(n,k) (see below). - Petros Hadjicostas, Jul 13 2019

Links

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

Formula

a(n) = Sum_{k=1..n} k * A267632(n,k).

From Petros Hadjicostas, Jul 13 2019: (Start)

G.f.: Sum_{s >= 1} phi(s) * (-x)^(s-1)/(1 - x^s + (-x)^s) = -Sum_{m >= 1} phi(2*m) * x^(2*m-1) + Sum_{m >= 0} phi(2*m+1) * x^(2*m)/(1 - 2*x^(2*m+1)).

a(2*m + 1) = A053636(2*m + 1)/2 = (1/2) * Sum_{d|2*m+1} phi(d) * 2^((2*m+1)/d) for m >= 0.

a(2*m) = -phi(2*m) + A053636(2*m)/2 for m >= 1.

(End)

Example

a(5) = 20 = 0 + 1 + 2 + 2 + 3 + 3 + 4 + 5 = |{}| + |{5}| + |{1,4}| + |{2,3}| + |{1,4,5}| + |{2,3,5}| + |{1,2,3,4}| + |{1,2,3,4,5}|.

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]])(b(n-1, m, irem(s+n, m))))
    end:
a:= proc(n) option remember; forget(b); b(n$2, 0)[2] 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]]}][b[n-1, m, Mod[s+n, m]]]];
a[n_] := b[n, n, 0][[2]];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

Crossrefs

Cf. A000010, A053636, A267632, A309128.

Sequence in context: A246037 A351832 A045896 * A115046 A004983 A298936

Adjacent sequences: A309119 A309120 A309121 * A309123 A309124 A309125

Keyword

nonn

Author

Alois P. Heinz, Jul 13 2019

Status

approved