A383333 Square array read by antidiagonals: T(n,k) is the number of n-tuples of nonnegative integers, not all equal to 0, with a shortest vectorial addition chain of length k; n >= 1, k >= 0.

1, 1, 2, 2, 3, 3, 3, 7, 6, 4, 5, 16, 16, 10, 5, 9, 37, 46, 30, 15, 6, 15, 91, 134, 101, 50, 21, 7, 26, 229, 411, 349, 190, 77, 28, 8, 44, 585, 1319, 1264, 751, 323, 112, 36, 9, 78, 1528, 4368, 4817, 3106, 1426, 511, 156, 45, 10, 136, 4034, 14925, 19131, 13532, 6586, 2478, 766, 210, 55, 11

Offset

1,3

Comments

The n unit tuples (1, 0, ..., 0), ... (0, ..., 0, 1) are given for free, so T(n,0) = n.

Starting with the n unit tuples, each tuple of a chain must be equal to the sum of two preceding tuples. The length of the chain is defined to be the number of tuples in the chain, excluding the unit tuples.

Also, T(n,k) is the number of non-constant monomials x_1^e_1*...*x_n^e_n that requires k multiplications, given x_1, ..., x_n.

Links

Table of n, a(n) for n=1..66.

Jorge Olivos, On vectorial addition chains, Journal of Algorithms 2 (1981), 13-21.

E. G. Straus, Partial solution to problem 5125: Addition chains of vectors, Problems and solutions, The American Mathematical Monthly 71 (1964), 806-808.

Edward G. Thurber and Neill M. Clift, Addition chains, vector chains, and efficient computation, Discrete Mathematics 344 (2021), 112200.

Wikipedia, Vectorial addition chain.

Example

Array begins:
  n\k| 0  1  2   3    4    5     6      7
  ---+-----------------------------------
  1  | 1  1  2   3    5    9    15     26
  2  | 2  3  7  16   37   91   229    585
  3  | 3  6 16  46  134  411  1319   4368
  4  | 4 10 30 101  349 1264  4817  19131
  5  | 5 15 50 190  751 3106 13532  61748
  6  | 6 21 77 323 1426 6586 32035 163594
There are 12 triples of nondecreasing nonnegative integers with a shortest addition chain of length 3. Counting also the permutations of these, we get T(3,3) = 46:
  (0, 0, 5):  3
  (0, 0, 6):  3
  (0, 0, 8):  3
  (0, 1, 3):  6
  (0, 1, 4):  6
  (0, 2, 3):  6
  (0, 2, 4):  6
  (0, 3, 3):  3
  (0, 4, 4):  3
  (1, 1, 2):  3
  (1, 2, 2):  3
  (2, 2, 2):  1
      Total: 46

Crossrefs

Cf. A383334.

Rows: A003065 (n=1), A383331 (n=2).

Columns: A000027 (k=0), A000217 (k=1), A005581 (k=2).

Sequence in context: A025496 A099959 A099964 * A369302 A363826 A094440

Adjacent sequences: A383330 A383331 A383332 * A383334 A383335 A383336

Keyword

nonn,tabl

Author

Pontus von Brömssen, Apr 26 2025

Status

approved