A325686 -id:A325686 - cp's OEIS frontend

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

N. J. A. Sloane, Aug 01 2010

nonn

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

			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)

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

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.

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

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

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

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

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

A008642 Quarter-squares repeated.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 12, 12, 16, 16, 20, 20, 25, 25, 30, 30, 36, 36, 42, 42, 49, 49, 56, 56, 64, 64, 72, 72, 81, 81, 90, 90, 100, 100, 110, 110, 121, 121, 132, 132, 144, 144, 156, 156, 169, 169, 182, 182, 196, 196, 210, 210, 225, 225

Offset: 0

N. J. A. Sloane

The area of the largest rectangle whose perimeter is not greater than n. - Dmitry Kamenetsky, Aug 30 2006
Also number of partitions of n into parts 1, 2 or 4. - Reinhard Zumkeller, Aug 12 2011
Let us consider a rectangle composed of unit squares. Then count how many squares are necessary to surround this rectangle by a layer whose width is 1 unit. And repeat this surrounding ad libitum. This sequence, prepended by 4 zeros and with offset 0, gives the number of rectangles that need 2*n unit squares in one of their surrounding layers. - Michel Marcus, Sep 19 2015
a(n) is the number of nonnegative integer solutions (x,y,z) for n-2 <= 2*x + 3*y + 4*z <= n. For example, the two solutions for 1 <= 2*x + 3*y + 4*z <= 3 are (1,0,0) and (0,1,0). - Ran Pan, Oct 07 2015
Conjecture: Consider the number of compositions of n>=4*k+8 into odd parts, where the order of the parts 1,3,..,2k+1 does not count. Then, as k approaches infinity, a(n-4*k-8) is equal to the number of these restricted compositions minus A000009(n), the number of strict partitions of n. - Gregory L. Simay, Aug 12 2016
From Gus Wiseman, May 17 2019: (Start)
Also the number of length-3 integer partitions of n + 4 whose largest part is greater than the sum of the other two. These are unordered triples that cannot be the sides of a triangle. For example, the a(1) = 1 through a(10) = 9 partitions are (A = 10, B = 11, C = 12):
  (311)  (411)  (421)  (521)  (522)  (622)  (632)  (732)   (733)   (833)
                (511)  (611)  (531)  (631)  (641)  (741)   (742)   (842)
                              (621)  (721)  (722)  (822)   (751)   (851)
                              (711)  (811)  (731)  (831)   (832)   (932)
                                            (821)  (921)   (841)   (941)
                                            (911)  (A11)   (922)   (A22)
                                                           (931)   (A31)
                                                           (A21)   (B21)
                                                           (B11)   (C11)
(End)
This sequence, prepended by four 0's and with offset 0, is the number of partitions of n into four parts whose smallest two parts are equal. - Wesley Ivan Hurt, Jan 05 2021
This sequence, prepended by four 0's and with offset 0, is the number of incongruent obtuse triangles formed from the vertices of a regular n-gon. - Frank M Jackson, Nov 27 2022

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 105.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 112, D(n).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Sara C. Billey, Matjaž Konvalinka, and Joshua P. Swanson, Asymptotic normality of the major index on standard tableaux, arXiv:1905.00975 [math.CO], 2019.
Ran Pan, Exercise U, Project P.
Harold N. Ward, A Normal Graph Algebra, arXiv:2201.00389 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,-1,1).

Cf. A002620.

Cf. A001399, A005044 (triangles without self-intersections), A069905, A124278, A266223, A325686, A325689, A325690, A325691, A325695.

[Floor(((n+1)*((-1)^n+n+6)+9)/16): n in [0..70]]; // Vincenzo Librandi, Apr 02 2014

seq((7/8+(-1)^k/8 + k + k^2/4)$2, k=0..100); # Robert Israel, Oct 08 2015

CoefficientList[Series[1/((1-x)(1-x^2)(1-x^4)), {x, 0, 70}], x] (* Vincenzo Librandi, Apr 02 2014 *)
LinearRecurrence[{1,1,-1,1,-1,-1,1},{1,1,2,2,4,4,6}, 70] (* Harvey P. Dale, Jun 03 2015 *)
Table[Floor[((n + 1) ((-1)^n + n + 6) + 9)/16], {n, 0, 70}] (* Michael De Vlieger, Aug 14 2016 *)

Vec(1/((1-x)*(1-x^2)*(1-x^4)) + O(x^70)) \\ Michel Marcus, Mar 31 2014

vector(70, n, n--; floor(((n+1)*((-1)^n+n+6)+9)/16)) \\ Altug Alkan, Oct 08 2015

[floor(floor(n/2+2)^2/2)/2 for n in (0..70)] # Bruno Berselli, Mar 03 2016

G.f.: 1/((1-x)*(1-x^2)*(1-x^4)).
a(n) = (2*n^2 + 14*n + 21 + (2*n + 7)*(-1)^n)/32 + ((1 + (-1)^n)/2 - (1 - (-1)^n)*i/2)*i^n/8, with i = sqrt(-1).
a(n) = floor(((n+1)*((-1)^n+n+6)+9)/16). - Tani Akinari, Jun 16 2013
a(n) = Sum_{i=1..floor((n+6)/2)} floor((n+6-2*i-(n mod 2))/4). - Wesley Ivan Hurt, Mar 31 2014
a(0)=1, a(1)=1, a(2)=2, a(3)=2, a(4)=4, a(5)=4, a(6)=6; for n>6, a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) - a(n-6) + a(n-7). - Harvey P. Dale, Jun 03 2015
a(n) = floor(floor(n/2+2)^2/4) = floor(floor(n/2+2)^2/2)/2. - Bruno Berselli, Mar 03 2016
E.g.f.: ((14 + 7*x + x^2)*cosh(x) + 2*(cos(x) + sin(x)) + (7 + 9*x + x^2)*sinh(x))/16. - Stefano Spezia, Mar 05 2023
a(n) = floor((n + 4)/4)*floor((n + 6)/4). - Ridouane Oudra, Apr 01 2023

A325677 Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 1, 4, 2, 1, 6, 6, 1, 6, 8, 1, 8, 18, 1, 8, 16, 1, 10, 30, 4, 1, 10, 34, 14, 1, 12, 48, 28, 1, 12, 48, 42, 1, 14, 72, 76, 1, 14, 72, 100, 1, 16, 96, 160, 8, 1, 16, 98, 190, 8, 1, 18, 126, 284, 40, 1, 18, 128, 316, 70

Offset: 1

Gus Wiseman, May 13 2019

Also the number of length-k compositions of n such that every restriction to a subinterval has a different sum. A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   1
   1   2
   1   2
   1   4
   1   4   2
   1   6   6
   1   6   8
   1   8  18
   1   8  16
   1  10  30   4
   1  10  34  14
   1  12  48  28
   1  12  48  42
   1  14  72  76
   1  14  72 100
   1  16  96 160   8
   1  16  98 190   8
   1  18 126 284  40
   1  18 128 316  70
Row n = 8 counts the following rulers:
  {0,8}  {0,1,8}  {0,1,3,8}
         {0,2,8}  {0,1,5,8}
         {0,3,8}  {0,1,6,8}
         {0,5,8}  {0,2,3,8}
         {0,6,8}  {0,2,7,8}
         {0,7,8}  {0,3,7,8}
                  {0,5,6,8}
                  {0,5,7,8}
and the following compositions:
  (8)  (17)  (125)
       (26)  (143)
       (35)  (152)
       (53)  (215)
       (62)  (251)
       (71)  (341)
             (512)
             (521)

Eric Weisstein's World of Mathematics, Golomb Ruler.

Row sums are A169942.
Row lengths are A325678(n) = A143824(n + 1) - 1.
Column k = 2 is A052928.
Column k = 3 is A325686.
Rightmost column is A325683.
Cf. A000079, A007318, A103295, A108917, A143823, A325676, A325679, A325687.

DeleteCases[Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,15},{k,n}],0,{2}]

A325688 Number of length-3 compositions of n such that every distinct consecutive subsequence has a different sum.

Original entry on oeis.org

0, 0, 0, 1, 0, 4, 5, 12, 12, 25, 24, 40, 41, 60, 60, 85, 84, 112, 113, 144, 144, 181, 180, 220, 221, 264, 264, 313, 312, 364, 365, 420, 420, 481, 480, 544, 545, 612, 612, 685, 684, 760, 761, 840, 840, 925, 924, 1012, 1013, 1104, 1104, 1201, 1200, 1300, 1301, 1404

Offset: 0

Gus Wiseman, May 15 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

Confirmed recurrence relation from Colin Barker for n <= 5000. - Fausto A. C. Cariboni, Feb 13 2022

			The a(3) = 1 through a(8) = 12 compositions:
  (111)  (113)  (114)  (115)  (116)
         (122)  (132)  (124)  (125)
         (221)  (222)  (133)  (143)
         (311)  (231)  (142)  (152)
                (411)  (214)  (215)
                       (223)  (233)
                       (241)  (251)
                       (322)  (332)
                       (331)  (341)
                       (412)  (512)
                       (421)  (521)
                       (511)  (611)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..5000

Column k = 3 of A325687.
Cf. A000217 (all length-3).
Cf. A000079, A001399, A005044, A008642, A069905, A108917, A124278, A266223.
Cf. A325686, A325689, A325690, A325691.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{3}],UnsameQ@@Total/@Union[ReplaceList[#,{_,s__,_}:>{s}]]&]],{n,0,30}]

Conjectures from Colin Barker, May 16 2019: (Start)
G.f.: x^3*(1 + 2*x^2 + 4*x^3 + 5*x^4) / ((1 - x)^3*(1 + x)^2*(1 + x + x^2)).
a(n) = 2*a(n-2) + a(n-3) - a(n-4) - 2*a(n-5) + a(n-7) for n>7.
(End)

A325695 Number of length-3 strict integer partitions of n such that the largest part is not the sum of the other two.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 2, 5, 5, 8, 7, 12, 11, 16, 15, 21, 20, 27, 25, 33, 32, 40, 38, 48, 46, 56, 54, 65, 63, 75, 72, 85, 83, 96, 93, 108, 105, 120, 117, 133, 130, 147, 143, 161, 158, 176, 172, 192, 188, 208, 204, 225, 221, 243, 238, 261, 257, 280, 275

Offset: 0

Gus Wiseman, May 15 2019

nonn

			The a(7) = 1 through a(15) = 12 partitions (A = 10, B = 11, C = 12):
  (421)  (521)  (432)  (631)  (542)  (543)  (643)   (653)   (654)
                (531)  (721)  (632)  (732)  (652)   (842)   (753)
                (621)         (641)  (741)  (742)   (851)   (762)
                              (731)  (831)  (751)   (932)   (843)
                              (821)  (921)  (832)   (941)   (852)
                                            (841)   (A31)   (861)
                                            (931)   (B21)   (942)
                                            (A21)           (951)
                                                            (A32)
                                                            (A41)
                                                            (B31)
                                                            (C21)

Cf. A000041, A001399, A005044, A008642, A069905, A124278.

Cf. A325686, A325690, A325691, A325694, A325696.

Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&#[[1]]!=#[[2]]+#[[3]]&]],{n,0,30}]

Conjectures from Colin Barker, May 15 2019: (Start)
G.f.: x^7*(1 + x + 2*x^2) / ((1 - x)^3*(1 + x)^2*(1 + x^2)*(1 + x + x^2)).
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9) for n>9.
(End)
a(n) = A325696(n)/6. - Alois P. Heinz, Jun 18 2020

A325696 Number of length-3 strict compositions of n such that no part is the sum of the other two.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 6, 6, 18, 12, 30, 30, 48, 42, 72, 66, 96, 90, 126, 120, 162, 150, 198, 192, 240, 228, 288, 276, 336, 324, 390, 378, 450, 432, 510, 498, 576, 558, 648, 630, 720, 702, 798, 780, 882, 858, 966, 948, 1056, 1032, 1152, 1128, 1248, 1224, 1350

Offset: 0

Gus Wiseman, May 15 2019

nonn

A composition of n is a finite sequence of positive integers summing to n. It is strict if all parts are distinct.

			The a(6) = 6 through a(10) = 12 compositions:
  (124)  (125)  (126)  (127)
  (142)  (152)  (135)  (136)
  (214)  (215)  (153)  (163)
  (241)  (251)  (162)  (172)
  (412)  (512)  (216)  (217)
  (421)  (521)  (234)  (271)
                (243)  (316)
                (261)  (361)
                (315)  (613)
                (324)  (631)
                (342)  (712)
                (351)  (721)
                (423)
                (432)
                (513)
                (531)
                (612)
                (621)

Cf. A000079, A001399, A005044, A266223.

Cf. A325686, A325688, A325689 (non-strict case), A325695.

Table[Length[Cases[Join@@Permutations/@IntegerPartitions[n,{3}],{x_,y_,z_}/;x!=y!=z&&x+y!=z&&x!=y+z&&y!=x+z]],{n,0,30}]

Conjectures from Colin Barker, May 16 2019: (Start)
G.f.: 6*x^7*(1 + x + 2*x^2) / ((1 - x)^3*(1 + x)^2*(1 + x^2)*(1 + x + x^2)).
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9) for n>9.
(End)
a(n) = 6 * A325695(n). - Alois P. Heinz, Jun 18 2020

cp's OEIS Frontend

A169942 Number of Golomb rulers of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A008642 Quarter-squares repeated.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A325677 Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325688 Number of length-3 compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325695 Number of length-3 strict integer partitions of n such that the largest part is not the sum of the other two.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A325696 Number of length-3 strict compositions of n such that no part is the sum of the other two.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula