|
|
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}).
|
|
8
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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
|
|
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:
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|