A169942 Number of Golomb rulers of length n.

1, 1, 3, 3, 5, 7, 13, 15, 27, 25, 45, 59, 89, 103, 163, 187, 281, 313, 469, 533, 835, 873, 1319, 1551, 2093, 2347, 3477, 3881, 5363, 5871, 8267, 9443, 12887, 14069, 19229, 22113, 29359, 32229, 44127, 48659, 64789, 71167, 94625, 105699, 139119, 151145, 199657

Offset

1,3

Comments

Wanted: a recurrence. Are any of A169940-A169954 related to any other entries in the OEIS?

Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012

Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..99

T. Pham, Enumeration of Golomb Rulers (Master's thesis), San Francisco State U., 2011.

Eric Weisstein's World of Mathematics, Golomb Ruler.

Index entries for sequences related to carryless arithmetic

Index entries for sequences related to Golomb rulers

Formula

a(n) = A169952(n) - A169952(n-1) for n>1. - Andrew Howroyd, Jul 09 2017

Example

For n=2, there is one Golomb Ruler: {0,2}.  For n=3, there are three: {0,3}, {0,1,3}, {0,2,3}. - Tomas Boothby, May 15 2012
From Gus Wiseman, May 16 2019: (Start)
The a(1) = 1 through a(8) = 15 compositions such that every restriction to a subinterval has a different sum:
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)
            (12)  (13)  (14)  (15)   (16)   (17)
            (21)  (31)  (23)  (24)   (25)   (26)
                        (32)  (42)   (34)   (35)
                        (41)  (51)   (43)   (53)
                              (132)  (52)   (62)
                              (231)  (61)   (71)
                                     (124)  (125)
                                     (142)  (143)
                                     (214)  (152)
                                     (241)  (215)
                                     (412)  (251)
                                     (421)  (341)
                                            (512)
                                            (521)
(End)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}] (* Gus Wiseman, May 16 2019 *)

Prog

(Sage)
def A169942(n):
    R = QQ['x']
    return sum(1 for c in cartesian_product([[0, 1]]*n) if max(R([1] + list(c) + [1])^2) == 2)
[A169942(n) for n in range(1, 8)]
# Tomas Boothby, May 15 2012

Crossrefs

Related to thickness: A169940-A169954, A061909.

Related to Golomb rulers: A036501, A054578, A143823.

Row sums of A325677.

Cf. A000079, A103295, A103300, A108917, A143824, A325466, A325545, A325676, A325678, A325679, A325683, A325686.

Sequence in context: A107029 A352912 A240180 * A215777 A147095 A161626

Adjacent sequences: A169939 A169940 A169941 * A169943 A169944 A169945

Keyword

nonn

Author

N. J. A. Sloane, Aug 01 2010

Extensions

a(15)-a(30) from Nathaniel Johnston, Nov 12 2011

a(31)-a(50) from Tomas Boothby, May 15 2012

Status

approved