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

%I #22 Oct 13 2020 21:12:31

%S 1,2,4,8,15,28,50,86,143,236,376,594,913,1380,2048,3016,4367,6302,

%T 8974,12670,17685,24580,33738,46072,62367,83990,112342,149734,198153,

%U 261562,343210,448694,583445,756846,976086,1255658,1607831,2053186,2610560,3312040,4183689

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

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

%H Fausto A. C. Cariboni, <a href="/A196723/b196723.txt">Table of n, a(n) for n = 0..110</a>

%e 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}.

%p b:= proc(n, s) local sn, m;

%p m:= nops(s);

%p sn:= [s[], n];

%p `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(

%p sn[i]+sn[j], j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))

%p end:

%p a:= proc(n) option remember;

%p b(n-1, [n]) +`if`(n=0, 0, a(n-1))

%p end:

%p seq(a(n), n=0..20);

%t 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]]];

%t 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 *)

%t Table[Length[Select[Subsets[Range[n]],UnsameQ@@Plus@@@Subsets[#,{2}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 03 2019 *)

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

%Y The subset case is A196723 (this sequence).

%Y The maximal case is A325878.

%Y The integer partition case is A325857.

%Y The strict integer partition case is A325877.

%Y Heinz numbers of the counterexamples are given by A325991.

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

%K nonn

%O 0,2

%A _Alois P. Heinz_, Oct 06 2011

%E Edited by _Gus Wiseman_, Jun 03 2019