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