A309402 Number T(n,k) of nonempty subsets of [n] whose element sum is divisible by k; triangle T(n,k), n >= 1, 1 <= k <= n*(n+1)/2, read by rows.

1, 3, 1, 1, 7, 3, 3, 1, 1, 1, 15, 7, 5, 3, 3, 2, 2, 1, 1, 1, 31, 15, 11, 7, 7, 5, 4, 3, 3, 3, 2, 2, 1, 1, 1, 63, 31, 23, 15, 13, 11, 9, 7, 7, 6, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 127, 63, 43, 31, 25, 21, 19, 15, 14, 12, 11, 10, 9, 9, 8, 8, 7, 7, 6, 5, 5, 4, 3, 2, 2, 1, 1, 1

Offset

1,2

Comments

T(n,k) is defined for all n >= 0, k >= 1. The triangle contains only the positive terms. T(n,k) = 0 if k > n*(n+1)/2.

Links

Alois P. Heinz, Rows n = 1..50, flattened

Formula

Sum_{k=1..n*(n+1)/2} k * T(n,k) = A309281(n).

T(n+1,n*(n+1)/2+1) = A000009(n) for n >= 0.

Example

Triangle T(n,k) begins:
   1;
   3,  1,  1;
   7,  3,  3,  1,  1,  1;
  15,  7,  5,  3,  3,  2, 2, 1, 1, 1;
  31, 15, 11,  7,  7,  5, 4, 3, 3, 3, 2, 2, 1, 1, 1;
  63, 31, 23, 15, 13, 11, 9, 7, 7, 6, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1;
  ...

Maple

b:= proc(n, s) option remember; `if`(n=0, add(x^d,
      d=numtheory[divisors](s)), b(n-1, s)+b(n-1, s+n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n, 0)):
seq(T(n), n=1..10);

Mathematica

b[n_, s_] := b[n, s] = If[n == 0, Sum[x^d,
    {d, Divisors[s]}], b[n-1, s] + b[n-1, s+n]];
T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i],
    {i, 1, Exponent[p, x]}]];
Array[T, 10] // Flatten (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

Crossrefs

Column k=1 gives A000225.

Row sums give A309403.

Row lengths give A000217.

T(n,n) gives A082550.

Rows reversed converge to A000009.

Cf. A309280, A309281.

Sequence in context: A346906 A228524 A116407 * A135288 A078026 A350635

Adjacent sequences: A309399 A309400 A309401 * A309403 A309404 A309405

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Jul 28 2019

Status

approved