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

Author

Pontus von Brömssen, Apr 26 2025

Keywords

• nonn
• tabl

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.

Examples

			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
		

Links

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

Crossrefs

Cf. A383334.

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

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