A054578 Number of subsequences of {1..n} such that all differences of pairs of terms are distinct (i.e., number of Golomb rulers on {1..n}).

1, 3, 6, 12, 21, 35, 56, 90, 139, 215, 316, 462, 667, 961, 1358, 1918, 2665, 3693, 5034, 6844, 9187, 12365, 16416, 21786, 28707, 37721, 49082, 63920, 82639, 106721, 136674, 174894, 222557, 283107, 357726, 451574, 567535, 712855, 890404, 1112080, 1382415

Offset: 1

Author

John W. Layman, Apr 11 2000

Keywords

• nonn

Examples

			a(4) = 12: [1], [2], [3], [4], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [1,2,4], [1,3,4]. - _Alois P. Heinz_, Jan 16 2013
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..100
• Index entries for sequences related to Golomb rulers

Crossrefs

Cf. A003022, A036501, A143823.

Partial sums of A308251.

Programs

Maple

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) a(n):= b(n-1, [n]) +`if` (n=0, -1, a(n-1)) end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 16 2013

Mathematica

b[n_, s_List] := b[n, s] = Module[{sn, m}, If[n < 1, 1, sn = Append[s, n]; m = Length[sn]; If[m(m - 1)/2 == Length @ Union @ Flatten @ Table[ Table[ sn[[i]] - sn[[j]], {j, i + 1, m}], {i, 1, m - 1}], b[n - 1, sn], 0] + b[n - 1, s]]];
a[n_] := a[n] = b[n - 1, {n}] + If [n == 0, -1, a[n - 1]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 41}] (* Jean-François Alcover, Apr 28 2020, after Alois P. Heinz *)

Formula

a(n) = A143823(n) - 1. - Carl Najafi, Jan 16 2013

Extensions

More terms from Carl Najafi, Jan 15 2013