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

Author

Seiichi Manyama, Sep 21 2020

Keywords

• nonn
• look

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.

Examples

			   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
		

Links

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

Crossrefs

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

Programs

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)