login
A325683
Number of maximal Golomb rulers of length n.
24
1, 1, 1, 2, 2, 4, 2, 6, 8, 18, 16, 24, 20, 28, 42, 76, 100, 138, 168, 204, 194, 272, 276, 450, 588, 808, 992, 1578, 1612, 1998, 2166, 2680, 2732, 3834, 3910, 5716, 6818, 9450, 10524, 15504, 16640, 22268, 23754, 30430, 31498, 40644, 40294, 52442, 56344, 72972, 77184
OFFSET
0,4
COMMENTS
A Golomb ruler of length n is a subset of {0..n} containing 0 and n and such that every pair of distinct terms has a different difference up to sign.
Also the number of minimal (most refined) compositions of n such that every restriction to a subinterval has a different sum.
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Golomb Ruler.
EXAMPLE
The a(1) = 1 through a(8) = 8 maximal Golomb rulers:
{0,1} {0,2} {0,1,3} {0,1,4} {0,1,5} {0,1,4,6} {0,1,3,7} {0,1,3,8}
{0,2,3} {0,3,4} {0,2,5} {0,2,5,6} {0,1,5,7} {0,1,5,8}
{0,3,5} {0,2,3,7} {0,1,6,8}
{0,4,5} {0,2,6,7} {0,2,3,8}
{0,4,5,7} {0,2,7,8}
{0,4,6,7} {0,3,7,8}
{0,5,6,8}
{0,5,7,8}
The a(1) = 1 through a(10) = 16 minimal compositions:
(1) (2) (12) (13) (14) (132) (124) (125) (126) (127)
(21) (31) (23) (231) (142) (143) (135) (136)
(32) (214) (152) (153) (154)
(41) (241) (215) (162) (163)
(412) (251) (216) (172)
(421) (341) (234) (217)
(512) (243) (253)
(521) (261) (271)
(315) (316)
(324) (352)
(342) (361)
(351) (451)
(423) (613)
(432) (631)
(513) (712)
(531) (721)
(612)
(621)
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Accumulate/@Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]]], {n, 0, 15}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 13 2019
EXTENSIONS
a(21)-a(50) from Fausto A. C. Cariboni, Feb 22 2022
STATUS
approved