A054578 - OEIS

%I #32 Feb 15 2024 15:15:08

%S 1,3,6,12,21,35,56,90,139,215,316,462,667,961,1358,1918,2665,3693,

%T 5034,6844,9187,12365,16416,21786,28707,37721,49082,63920,82639,

%U 106721,136674,174894,222557,283107,357726,451574,567535,712855,890404,1112080,1382415

%N 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}).

%H Alois P. Heinz, <a href="/A054578/b054578.txt">Table of n, a(n) for n = 1..100</a>

%H <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>

%F a(n) = A143823(n) - 1. - _Carl Najafi_, Jan 16 2013

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

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

%p       if n<1 then 1

%p     else sn:= [s[], n]; 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) a(n):= b(n-1, [n]) +`if` (n=0, -1, a(n-1)) end:

%p seq(a(n), n=1..30);  # _Alois P. Heinz_, Jan 16 2013

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

%t a[n_] := a[n] = b[n - 1, {n}] + If [n == 0, -1, a[n - 1]];

%t Table[Print[n, " ", a[n]]; a[n], {n, 1, 41}] (* _Jean-François Alcover_, Apr 28 2020, after _Alois P. Heinz_ *)

%Y Cf. A003022, A036501, A143823.

%Y Partial sums of A308251.

%K nonn

%O 1,2

%A _John W. Layman_, Apr 11 2000

%E More terms from _Carl Najafi_, Jan 15 2013