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

1, 0, 1, 2, 3, 5, 8, 12, 17, 22, 28, 35, 43, 52, 60, 69, 77, 86, 92, 103, 112, 123, 137, 151, 168, 180, 194, 204, 224, 245, 261, 280, 301, 318, 335, 352, 369, 387, 413, 433, 459, 482, 507, 528, 552, 586, 614, 638, 669, 701, 733, 761, 791, 824, 855, 885, 917, 952, 985, 1020

Offset: 0

Author

Derek Orr, Nov 15 2020

Keywords

• nonn

Comments

a(n) <= A000217(n)-n for n >= 1.

Without replacement means a(i)+a(i) is not included. However, if a(i)=a(j), a(i)+a(j) still counts because they have two different indices. If you include a(i)+a(i), the sequence becomes A000012 (all ones).

If you include the distinct sums between 3 elements and more, you arrive at the sequence 1, 0, followed by A000079 (2^n).

Same rule as in A247184, but with a(0)=1.

Examples

			a(1) gives the number of distinct sums between two elements of [1]. There aren't two elements so a(1)=0.
a(2) gives the number of distinct sums between two elements of [1,0]. The only sum are 1+0, so a(2) = 1.
a(3) gives the number of distinct sums between two elements of [1,0,1]. The two sums are 1+0 and 1+1 so a(3)=2.
		

Crossrefs

Cf. A000217, A000012, A247184, 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, 1, nops(s(n-1)))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Nov 16 2020

Mathematica

a[0] = 1; a[1] = 0;
a[n_Integer?Positive] := a[n] = Length[Union[Total[Subsets[Array[a, n, 0], {2}], {2}]]];
Array[a, 61, 0] (* Jan Mangaldan, Nov 23 2020 *)

PARI

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