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

Author

Alois P. Heinz, Jul 13 2019

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

Cf. A000010, A053636, A267632, A309128.

Programs

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

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)