A241689 -id:A241689 - cp's OEIS frontend

A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.

1, 2, 4, 7, 13, 22, 36, 57, 91, 140, 216, 317, 463, 668, 962, 1359, 1919, 2666, 3694, 5035, 6845, 9188, 12366, 16417, 21787, 28708, 37722, 49083, 63921, 82640, 106722, 136675, 174895, 222558, 283108, 357727, 451575, 567536, 712856, 890405, 1112081, 1382416, 1717540

Offset: 0

John W. Layman, Sep 02 2008

nonn

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
See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property.
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

			{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}.
From _Gus Wiseman_, May 17 2019: (Start)
The a(0) = 1 through a(5) = 22 subsets:
  {}  {}   {}     {}     {}       {}
      {1}  {1}    {1}    {1}      {1}
           {2}    {2}    {2}      {2}
           {1,2}  {3}    {3}      {3}
                  {1,2}  {4}      {4}
                  {1,3}  {1,2}    {5}
                  {2,3}  {1,3}    {1,2}
                         {1,4}    {1,3}
                         {2,3}    {1,4}
                         {2,4}    {1,5}
                         {3,4}    {2,3}
                         {1,2,4}  {2,4}
                         {1,3,4}  {2,5}
                                  {3,4}
                                  {3,5}
                                  {4,5}
                                  {1,2,4}
                                  {1,2,5}
                                  {1,3,4}
                                  {1,4,5}
                                  {2,3,5}
                                  {2,4,5}
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100 (terms 0..60 from Alois P. Heinz, 61..81 from Vaclav Kotesovec)
Wikipedia, Sidon sequence.

First differences are A308251.
Second differences are A169942.
Row sums of A381476.
The maximal case is A325879.
The integer partition case is A325858.
The strict integer partition case is A325876.
Heinz numbers of the counterexamples are given by A325992.
Cf. A143824, A054578, A169947.
Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864, A241688, A241689, A241690.

b:= proc(n, s) local sn, m;
      if n<1 then 1
    else sn:= [s[], n];
         m:= nops(sn);
         `if`(m*(m-1)/2 = nops(({seq(seq(sn[i]-sn[j],
           j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)
      fi
    end:
a:= proc(n) option remember;
       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 14 2011

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 *)
Table[Length[Select[Subsets[Range[n]],UnsameQ@@Abs[Subtract@@@Subsets[#,{2}]]&]],{n,0,15}] (* Gus Wiseman, May 17 2019 *)

from itertools import combinations
def is_sidon_set(s):
    allsums = []
    for i in range(len(s)):
        for j in range(i, len(s)):
            allsums.append(s[i] + s[j])
    if len(allsums)==len(set(allsums)):
        return True
    return False
def a(n):
    sidon_count = 0
    for r in range(n + 1):
        subsets = combinations(range(1, n + 1), r)
        for subset in subsets:
            if is_sidon_set(subset):
                sidon_count += 1
    return sidon_count
print([a(n) for n in range(20)]) # Sayan Dutta, Feb 15 2024

from functools import cache
def b(n, s):
    if n < 1: return 1
    sn = s + [n]
    m = len(sn)
    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)
@cache
def a(n): return b(n-1, [n]) + (0 if n==0 else a(n-1))
print([a(n) for n in range(31)]) # Michael S. Branicky, Feb 15 2024 after Alois P. Heinz

a(n) = A169947(n-1) + n + 1 for n>=2. - Nathaniel Johnston, Nov 12 2010

a(n) = A054578(n) + 1 for n>0. - Alois P. Heinz, Jan 17 2013

a(21)-a(29) from Nathaniel Johnston, Nov 12 2010

Corrected a(21)-a(29) and more terms from Alois P. Heinz, Sep 14 2011

A381476 Triangle read by rows: T(n,k) is the number of subsets of {1..n} with k elements such that every pair of distinct elements has a different difference, 0 <= k <= A143824(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 6, 15, 14, 1, 7, 21, 26, 2, 1, 8, 28, 44, 10, 1, 9, 36, 68, 26, 1, 10, 45, 100, 60, 1, 11, 55, 140, 110, 1, 12, 66, 190, 190, 4, 1, 13, 78, 250, 304, 22, 1, 14, 91, 322, 466, 68, 1, 15, 105, 406, 676, 156

Offset: 0

Andrew Howroyd, Mar 27 2025

Equivalently, a(n) is the number of Sidon sets of {1..n} of size k.

			Triangle begins:
   0 | 1;
   1 | 1,  1;
   2 | 1,  2,  1;
   3 | 1,  3,  3;
   4 | 1,  4,  6,   2;
   5 | 1,  5, 10,   6;
   6 | 1,  6, 15,  14;
   7 | 1,  7, 21,  26,   2;
   8 | 1,  8, 28,  44,  10;
   9 | 1,  9, 36,  68,  26;
  10 | 1, 10, 45, 100,  60;
  11 | 1, 11, 55, 140, 110;
  12 | 1, 12, 66, 190, 190, 4;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..464 (rows 0..60)
Wikipedia, Sidon sequence.
Index entries for sequences related to Golomb rulers.

Columns 0..5 are A000012, A001477, A161680, A212964(n-1), A241688, A241689, A241690.
Row sums are A143823.
Cf. A003022, A143824, A325879, A382395.

row(n)={
  local(L=List());
  my(recurse(k,r,b,w)=
      if(k > n, if(r>=#L,listput(L,0)); L[1+r]++,
         self()(k+1, r, b, w);
         b+=1<

T(n,A143824(n)) = A382395(n).

cp's OEIS Frontend

A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python