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

Author

Alois P. Heinz, Jul 28 2019

Keywords

• nonn
• look
• tabf

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.

Examples

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

Links

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

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.

Programs

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

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.