A382833 Square array read by antidiagonals: T(n,k) is the number of distinct sum-of-powers vectors (Sum_{x in X} x^m, 0 <= m <= k) for subsets X of {0, ..., n-1}; n, k >= 0.

1, 1, 2, 1, 2, 3, 1, 2, 4, 4, 1, 2, 4, 8, 5, 1, 2, 4, 8, 15, 6, 1, 2, 4, 8, 16, 26, 7, 1, 2, 4, 8, 16, 32, 42, 8, 1, 2, 4, 8, 16, 32, 64, 64, 9, 1, 2, 4, 8, 16, 32, 64, 126, 93, 10, 1, 2, 4, 8, 16, 32, 64, 128, 247, 130, 11, 1, 2, 4, 8, 16, 32, 64, 128, 256, 476, 176, 12

Offset

0,3

Links

Table of n, a(n) for n=0..77.

Formula

T(n,k) <= 2^n with equality if and only if n < A382832(k).

Example

Array begins:
  n\k|  0   1     2     3     4
  ---+-------------------------
   0 |  1   1     1     1     1
   1 |  2   2     2     2     2
   2 |  3   4     4     4     4
   3 |  4   8     8     8     8
   4 |  5  15    16    16    16
   5 |  6  26    32    32    32
   6 |  7  42    64    64    64
   7 |  8  64   126   128   128
   8 |  9  93   247   256   256
   9 | 10 130   476   512   512
  10 | 11 176   908  1024  1024
  11 | 12 232  1682  2048  2048
  12 | 13 299  3067  4080  4096
  13 | 14 378  5364  8128  8192
  14 | 15 470  9132 16128 16384
  15 | 16 576 14948 31992 32768
  16 | 17 697 23635 63163 65520
For n = 4, k = 1, there is only one pair of subsets of {0, 1, 2, 3} for which the two subsets have the same number of elements (sum of 0th powers) and the same sum (sum of 1st powers), namely {0, 3}, {1, 2}. Hence, T(4,1) = 2^4-1 = 15.

Crossrefs

Cf. A000027 (column k=0), A000125 (column k=1), A382383, A382832.

Sequence in context: A259324 A216274 A145111 * A104795 A347570 A116925

Adjacent sequences: A382830 A382831 A382832 * A382834 A382835 A382836

Keyword

nonn,tabl

Author

Pontus von Brömssen, Apr 10 2025

Status

approved