A196723 Number of subsets of {1..n} (including empty set) such that the pairwise sums of distinct elements are all distinct.

1, 2, 4, 8, 15, 28, 50, 86, 143, 236, 376, 594, 913, 1380, 2048, 3016, 4367, 6302, 8974, 12670, 17685, 24580, 33738, 46072, 62367, 83990, 112342, 149734, 198153, 261562, 343210, 448694, 583445, 756846, 976086, 1255658, 1607831, 2053186, 2610560, 3312040, 4183689

Offset

0,2

Comments

The number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum is A143823(n).

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..110

Example

a(4) = 15: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

Maple

b:= proc(n, s) local sn, m;
      m:= nops(s);
      sn:= [s[], n];
      `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
       sn[i]+sn[j], j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
    end:
a:= proc(n) option remember;
      b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..20);

Mathematica

b[n_, s_] := b[n, s] = Module[{sn, m}, m = Length[s]; sn = Append[s, n]; If[n<1, 1, b[n-1, s] + If[m*(m+1)/2 == Length[ Union[ Flatten[ Table[ sn[[i]] + sn[[j]], {i, 1, m}, {j, i+1, m+1}]]]], b[n-1, sn], 0]]];
a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jan 31 2017, translated from Maple *)
Table[Length[Select[Subsets[Range[n]], UnsameQ@@Plus@@@Subsets[#, {2}]&]], {n, 0, 10}] (* Gus Wiseman, Jun 03 2019 *)

Crossrefs

Cf. A143823, A196719, A196720, A196721, A196722, A196724.

The subset case is A196723 (this sequence).

The maximal case is A325878.

The integer partition case is A325857.

The strict integer partition case is A325877.

Heinz numbers of the counterexamples are given by A325991.

Cf. A108917, A325858, A325862, A325863, A325864.

Sequence in context: A056181 A101976 A339656 * A036615 A006808 A006727

Adjacent sequences: A196720 A196721 A196722 * A196724 A196725 A196726

Keyword

nonn

Author

Alois P. Heinz, Oct 06 2011

Extensions

Edited by Gus Wiseman, Jun 03 2019

Status

approved