cp's OEIS Frontend

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

%I A054578 #32 Feb 15 2024 15:15:08
%S A054578 1,3,6,12,21,35,56,90,139,215,316,462,667,961,1358,1918,2665,3693,
%T A054578 5034,6844,9187,12365,16416,21786,28707,37721,49082,63920,82639,
%U A054578 106721,136674,174894,222557,283107,357726,451574,567535,712855,890404,1112080,1382415
%N 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}).
%H A054578 Alois P. Heinz, <a href="/A054578/b054578.txt">Table of n, a(n) for n = 1..100</a>
%H A054578 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>
%F A054578 a(n) = A143823(n) - 1. - _Carl Najafi_, Jan 16 2013
%e A054578 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 A054578 b:= proc(n, s) local sn, m;
%p A054578       if n<1 then 1
%p A054578     else sn:= [s[], n]; m:= nops(sn);
%p A054578          `if` (m*(m-1)/2 = nops (({seq (seq (sn[i]-sn[j],
%p A054578            j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)
%p A054578       fi
%p A054578     end:
%p A054578 a:= proc(n) a(n):= b(n-1, [n]) +`if` (n=0, -1, a(n-1)) end:
%p A054578 seq(a(n), n=1..30);  # _Alois P. Heinz_, Jan 16 2013
%t A054578 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 A054578 a[n_] := a[n] = b[n - 1, {n}] + If [n == 0, -1, a[n - 1]];
%t A054578 Table[Print[n, " ", a[n]]; a[n], {n, 1, 41}] (* _Jean-François Alcover_, Apr 28 2020, after _Alois P. Heinz_ *)
%Y A054578 Cf. A003022, A036501, A143823.
%Y A054578 Partial sums of A308251.
%K A054578 nonn
%O A054578 1,2
%A A054578 _John W. Layman_, Apr 11 2000
%E A054578 More terms from _Carl Najafi_, Jan 15 2013