cp's OEIS Frontend

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.

%I A383333 #6 Apr 26 2025 11:27:21
%S A383333 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,
%T A383333 7,26,229,411,349,190,77,28,8,44,585,1319,1264,751,323,112,36,9,78,
%U A383333 1528,4368,4817,3106,1426,511,156,45,10,136,4034,14925,19131,13532,6586,2478,766,210,55,11
%N 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.
%C A383333 The n unit tuples (1, 0, ..., 0), ... (0, ..., 0, 1) are given for free, so T(n,0) = n.
%C A383333 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.
%C A383333 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.
%H A383333 Jorge Olivos, <a href="https://doi.org/10.1016/0196-6774(81)90003-1">On vectorial addition chains</a>, Journal of Algorithms 2 (1981), 13-21.
%H A383333 E. G. Straus, <a href="https://doi.org/10.2307/2310929">Partial solution to problem 5125: Addition chains of vectors</a>, Problems and solutions, The American Mathematical Monthly 71 (1964), 806-808.
%H A383333 Edward G. Thurber and Neill M. Clift, <a href="https://doi.org/10.1016/j.disc.2020.112200">Addition chains, vector chains, and efficient computation</a>, Discrete Mathematics 344 (2021), 112200.
%H A383333 Wikipedia, <a href="https://en.wikipedia.org/wiki/Vectorial_addition_chain">Vectorial addition chain</a>.
%e A383333 Array begins:
%e A383333   n\k| 0  1  2   3    4    5     6      7
%e A383333   ---+-----------------------------------
%e A383333   1  | 1  1  2   3    5    9    15     26
%e A383333   2  | 2  3  7  16   37   91   229    585
%e A383333   3  | 3  6 16  46  134  411  1319   4368
%e A383333   4  | 4 10 30 101  349 1264  4817  19131
%e A383333   5  | 5 15 50 190  751 3106 13532  61748
%e A383333   6  | 6 21 77 323 1426 6586 32035 163594
%e A383333 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:
%e A383333   (0, 0, 5):  3
%e A383333   (0, 0, 6):  3
%e A383333   (0, 0, 8):  3
%e A383333   (0, 1, 3):  6
%e A383333   (0, 1, 4):  6
%e A383333   (0, 2, 3):  6
%e A383333   (0, 2, 4):  6
%e A383333   (0, 3, 3):  3
%e A383333   (0, 4, 4):  3
%e A383333   (1, 1, 2):  3
%e A383333   (1, 2, 2):  3
%e A383333   (2, 2, 2):  1
%e A383333       Total: 46
%Y A383333 Cf. A383334.
%Y A383333 Rows: A003065 (n=1), A383331 (n=2).
%Y A383333 Columns: A000027 (k=0), A000217 (k=1), A005581 (k=2).
%K A383333 nonn,tabl
%O A383333 1,3
%A A383333 _Pontus von Brömssen_, Apr 26 2025