A247184 a(0) = 0. a(n) is the number of distinct sums of two elements in [a(0), ... a(n-1)] chosen without replacement.

0, 0, 1, 2, 4, 7, 11, 15, 20, 26, 32, 40, 48, 57, 65, 73, 81, 90, 98, 106, 114, 123, 132, 147, 157, 170, 190, 202, 223, 236, 251, 270, 291, 314, 338, 361, 380, 398, 421, 443, 471, 495, 520, 544, 567, 592, 616, 639, 663, 692, 720, 749, 781, 819, 852, 885, 913, 948, 987, 1023, 1055, 1088

Offset: 0

Author

Derek Orr, Nov 22 2014

Keywords

• nonn

Comments

a(n) <= A000217(n)-n.

Without replacement means that a(i)+a(i) is not a valid sum to include. However, if a(i) = a(j), a(i)+a(j) is still a valid sum to include because they have different indices.

If you include a(i)+a(i) (i.e., with replacement) as a valid sum, the sequence becomes 0, 1, 3, 6, 9, 12, ... = 0, 1, followed by A008585(n) for n > 0.

a(i)+a(j) and a(j)+a(i) are regarded as the same for all indices i and j.

Examples

			a(1) gives the number of distinct sums of two elements of [0]. There aren't two elements so a(1) = 0.
a(2) gives the number of distinct sums of two elements of [0,0]. There is only 1 sum, 0, so a(2) = 1.
a(3) gives the number of distinct sums of two elements of [0,0,1]. There are 2 distinct possible sums 0 and 1, so a(3) = 2.
a(4) gives the number of distinct sums of two elements of [0,0,1,2]. There are 4 distinct possible sums {0, 1, 2, 3}, so a(4) = 4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000217, A008585, A247185.

Programs

Maple

s:= proc(n) option remember; `if`(n=0, {},
      {s(n-1)[], seq(a(i)+a(n), i=0..n-1)})
    end:
a:= proc(n) option remember;
      `if`(n=0, 0, nops(s(n-1)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 16 2020

Mathematica

s[n_] := s[n] = If[n == 0, {},
   Union@Join[s[n-1], Table[a[i] + a[n], {i, 0, n-1}]]];
a[n_] := a[n] =
   If[n == 0, 0, Length[s[n-1]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2021, after Alois P. Heinz *)

PARI

v=[0];n=1;while(n<75,w=[];for(i=1,#v,for(j=i+1,#v,w=concat(w,v[i]+v[j])));v=concat(v,#vecsort(w,,8));n++);v