[go: up one dir, main page]

login
A196723
Number of subsets of {1..n} (including empty set) such that the pairwise sums of distinct elements are all distinct.
32
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
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.
Sequence in context: A056181 A101976 A339656 * A036615 A006808 A006727
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 06 2011
EXTENSIONS
Edited by Gus Wiseman, Jun 03 2019
STATUS
approved