A325683 Number of maximal Golomb rulers of length n.

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

Author

Gus Wiseman, May 13 2019

Keywords

• nonn

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.

Examples

			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)
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100
• Eric Weisstein's World of Mathematics, Golomb Ruler.

Crossrefs

Rightmost column of A325677.

Cf. A000079, A103295, A108917, A143823, A169942, A276024.

Cf. A325676, A325678, A325679, A325681, A325687.

Programs

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}]

Extensions

a(21)-a(50) from Fausto A. C. Cariboni, Feb 22 2022