|
%I #71 Mar 09 2024 11:44:03
%S 1,2,4,7,13,22,36,57,91,140,216,317,463,668,962,1359,1919,2666,3694,
%T 5035,6845,9188,12366,16417,21787,28708,37722,49083,63921,82640,
%U 106722,136675,174895,222558,283108,357727,451575,567536,712856,890405,1112081,1382416,1717540
%N Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.
%C When the set {x(1),x(2),...,x(k)} satisfies the property that all differences |x(i)-x(j)| are distinct (or alternately, all the sums are distinct), then it is called a Sidon set. So this sequence is basically the number of Sidon subsets of {1,2,...,n}. - _Sayan Dutta_, Feb 15 2024
%C See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property.
%C Also the number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum. - _Gus Wiseman_, Jun 07 2019
%H Fausto A. C. Cariboni, <a href="/A143823/b143823.txt">Table of n, a(n) for n = 0..100</a> (terms 0..60 from Alois P. Heinz, 61..81 from Vaclav Kotesovec)
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%F a(n) = A169947(n-1) + n + 1 for n>=2. - _Nathaniel Johnston_, Nov 12 2010
%F a(n) = A054578(n) + 1 for n>0. - _Alois P. Heinz_, Jan 17 2013
%e {1,2,4} is a subset of {1,2,3,4}, with distinct differences 2-1=1, 4-1=3, 4-2=2 between pairs of elements, so {1,2,4} is counted as one of the 13 subsets of {1,2,3,4} with the desired property. Only 2^4-13=3 subsets of {1,2,3,4} do not have this property: {1,2,3}, {2,3,4}, {1,2,3,4}.
%e From _Gus Wiseman_, May 17 2019: (Start)
%e The a(0) = 1 through a(5) = 22 subsets:
%e {} {} {} {} {} {}
%e {1} {1} {1} {1} {1}
%e {2} {2} {2} {2}
%e {1,2} {3} {3} {3}
%e {1,2} {4} {4}
%e {1,3} {1,2} {5}
%e {2,3} {1,3} {1,2}
%e {1,4} {1,3}
%e {2,3} {1,4}
%e {2,4} {1,5}
%e {3,4} {2,3}
%e {1,2,4} {2,4}
%e {1,3,4} {2,5}
%e {3,4}
%e {3,5}
%e {4,5}
%e {1,2,4}
%e {1,2,5}
%e {1,3,4}
%e {1,4,5}
%e {2,3,5}
%e {2,4,5}
%e (End)
%p b:= proc(n, s) local sn, m;
%p if n<1 then 1
%p else sn:= [s[], n];
%p m:= nops(sn);
%p `if`(m*(m-1)/2 = nops(({seq(seq(sn[i]-sn[j],
%p j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)
%p fi
%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..30); # _Alois P. Heinz_, Sep 14 2011
%t b[n_, s_] := Module[{ sn, m}, If[n<1, 1, sn = Append[s, n]; m = Length[sn]; If[m*(m-1)/2 == Length[Table[sn[[i]] - sn[[j]], {i, 1, m-1}, {j, i+1, m}] // Flatten // Union], b[n-1, sn], 0] + b[n-1, s]]]; a[n_] := a[n] = b[n - 1, {n}] + If[n == 0, 0, a[n-1]]; Table [a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 08 2015, after _Alois P. Heinz_ *)
%t Table[Length[Select[Subsets[Range[n]],UnsameQ@@Abs[Subtract@@@Subsets[#,{2}]]&]],{n,0,15}] (* _Gus Wiseman_, May 17 2019 *)
%o (Python)
%o from itertools import combinations
%o def is_sidon_set(s):
%o allsums = []
%o for i in range(len(s)):
%o for j in range(i, len(s)):
%o allsums.append(s[i] + s[j])
%o if len(allsums)==len(set(allsums)):
%o return True
%o return False
%o def a(n):
%o sidon_count = 0
%o for r in range(n + 1):
%o subsets = combinations(range(1, n + 1), r)
%o for subset in subsets:
%o if is_sidon_set(subset):
%o sidon_count += 1
%o return sidon_count
%o print([a(n) for n in range(20)]) # _Sayan Dutta_, Feb 15 2024
%o (Python)
%o from functools import cache
%o def b(n, s):
%o if n < 1: return 1
%o sn = s + [n]
%o m = len(sn)
%o return (b(n-1, sn) if m*(m-1)//2 == len(set(sn[i]-sn[j] for i in range(m-1) for j in range(i+1, m))) else 0) + b(n-1, s)
%o @cache
%o def a(n): return b(n-1, [n]) + (0 if n==0 else a(n-1))
%o print([a(n) for n in range(31)]) # _Michael S. Branicky_, Feb 15 2024 after _Alois P. Heinz_
%Y First differences are A308251.
%Y Second differences are A169942.
%Y The subset case is A143823 (this sequence).
%Y The maximal case is A325879.
%Y The integer partition case is A325858.
%Y The strict integer partition case is A325876.
%Y Heinz numbers of the counterexamples are given by A325992.
%Y Cf. A143824, A054578, A169947.
%Y Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864, A241688, A241689, A241690.
%K nonn
%O 0,2
%A _John W. Layman_, Sep 02 2008
%E a(21)-a(29) from _Nathaniel Johnston_, Nov 12 2010
%E Corrected a(21)-a(29) and more terms from _Alois P. Heinz_, Sep 14 2011
|
