A337787 Number of addition triangles whose sum is n (version 2).

1, 1, 1, 2, 1, 2, 1, 3, 1, 3, 2, 4, 1, 5, 1, 6, 3, 5, 2, 8, 2, 8, 4, 8, 3, 12, 3, 11, 6, 11, 5, 15, 4, 16, 9, 14, 7, 20, 8, 18, 11, 20, 12, 25, 8, 25, 18, 24, 12, 31, 16, 32, 19, 29, 21, 39, 19, 36, 28, 38, 25, 47, 25, 46, 33, 46, 34, 55, 31, 56, 44, 55, 39, 67, 42, 66, 52, 66, 53, 76, 50, 81, 65, 77, 57

Offset

1,4

Comments

An addition triangle has any set of positive numbers as base; other rows are formed by adding pairs of adjacent numbers.

Reversing the base does not count as a different triangle.

Links

Seiichi Manyama, Table of n, a(n) for n = 1..500

Example

   n |
-----+-------------------------------
   1 |  1
-----+-------------------------------
   2 |  2
-----+-------------------------------
   3 |  3
-----+-------------------------------
   4 |      2
     |  4  1,1
-----+-------------------------------
   5 |  5
-----+-------------------------------
   6 |      3
     |  6  1,2
-----+-------------------------------
   7 |  7
-----+-------------------------------
   8 |      4    4
     |  8  1,3  2,2
-----+-------------------------------
   9 |  9
-----+-------------------------------
  10 |      5    5
     | 10  1,4  2,3
-----+-------------------------------
  11 |       4
     |      2,2
     | 11  1,1,1
-----+-------------------------------
  12 |      6    6    6
     | 12  1,5  2,4  3,3
-----+-------------------------------
  13 | 13
-----+-------------------------------
  14 |                      5
     |      7    7    7    2,3
     | 14  1,6  2,5  3,4  1,1,2
-----+-------------------------------
  15 | 15
-----+-------------------------------
  16 |                           6
     |      8    8    8    8    3,3
     | 16  1,7  2,6  3,5  4,4  1,2,1
-----+-------------------------------
  17 |       6      6
     |      2,4    3,3
     | 17  1,1,3  2,1,2
-----+-------------------------------
  18 |      9    9    9    9
     | 18  1,8  2,7  3,6  4,5
-----+-------------------------------
  19 |       7
     |      3,4
     | 19  1,2,2

Prog

(Ruby)
def f(n)
  ary = [1]
  (n - 1).times{|i|
    ary = [0] + ary + [0]
    ary = (0..i + 1).map{|j| ary[j] + ary[j + 1] + 1}
  }
  ary
end
def A(n)
  f_ary = (1..n / 2).map{|i| [i]}
  cnt = 2
  s = 1
  while f_ary.size > 0
    s_ary = f(s + 1)
    b_ary = []
    f_ary.each{|i|
      (1..i[0] - 1).each{|j|
        a = [j]
        (0..s - 1).each{|k|
          num = i[k] - a[k]
          if num > 0
            a << num
          else
            break
          end
        }
        if a.size == s + 1
          sum = (0..s).inject(0){|t, m| t + s_ary[m] * a[m]}
          if sum < n
            b_ary << a
          elsif sum == n
            cnt += 1
            cnt += 1 if a == a.reverse
          end
        end
      }
    }
    f_ary = b_ary
    s += 1
  end
  cnt / 2
end
def A337787(n)
  (1..n).map{|i| A(i)}
end
p A337787(50)

Crossrefs

Cf. A014430, A062684, A062896, see A337785 for version 1.

Sequence in context: A324938 A362181 A079413 * A027351 A029349 A168676

Adjacent sequences: A337784 A337785 A337786 * A337788 A337789 A337790

Keyword

nonn,look

Author

Seiichi Manyama, Sep 21 2020

Status

approved