A004137 -id:A004137 - cp's OEIS frontend

A241094 Triangle read by rows: T(n,i) = number of gracefully labeled graphs with n edges that do not use the label i, 1 <= i <= n-1, n > 1.

0, 1, 1, 4, 4, 4, 18, 24, 24, 18, 96, 144, 144, 96, 600, 960, 1080, 1080, 960, 600, 4320, 7200, 8460, 8460, 8460, 7200, 4320, 35280, 60840, 75600, 80640, 80640, 75600, 60480, 35280, 322560, 564480, 725760, 806400, 806400, 806400, 725760, 564480, 322560

Offset: 2

Christian Barrientos and Sarah Minion, Apr 15 2014

A graph with n edges is graceful if its vertices can be labeled with distinct integers in the range 0,1,...,n in such a way that when the edges are labeled with the absolute differences between the labels of their end-vertices, the n edges have the distinct labels 1,2,...,n.

			For n=7 and i=3, g(7,3) = 1080.
For n=7 and i=5, g(7,5) = 960.
Triangle begins:
[n\i]  [1]     [2]     [3]     [4]     [5]     [6]     [7]     [8]
[2]     0;
[3]     1,      1;
[4]     4,      4,      4;
[5]    18,     24,     24,     18;
[6]    96,    144,    144,    144,     96;
[7]   600,    960,   1080,   1080,    960,    600;
[8]  4320,   7200,   8640,   8640,   8640,   7200,   4320;
[9] 35280,  60480,  75600,  80640,  80640,  75600,  60480,  35280;
...
- _Bruno Berselli_, Apr 23 2014

C. Barrientos and S. M. Minion, Enumerating families of labeled graphs, J. Integer Seq., 18(2015), article 15.1.7.
J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.

Cf. A001563, A003022, A004137, A005488, A006967, A033472, A081621, A103300, A117747, A212661.

/* As triangle: */ [[i le Floor(n/2) select Factorial(n-2)*(n-1-i)*i else Factorial(n-2)*(n-i)*(i-1): i in [1..n-1]]: n in [2..10]]; // Bruno Berselli, Apr 23 2014

Labeled:=(i,n) piecewise(n<2 or i<1, -infinity, 1 <= i <= floor(n/2), GAMMA(n-1)*(n-1-i)*i, ceil((n+1)/2) <= i <= n-1, GAMMA(n-1)*(n-i)*(i-1), infinity):

n=10; (* This number must be replaced every time in order to produce the different entries of the sequence *)
For[i = 1, i <= Floor[n/2], i++, g[n_,i_]:=(n-2)!*(n-1-i)*i; Print["g(",n,",",i,")=", g[n,i]]]
For[i = Ceiling[(n+1)/2], i <= (n-1), i++, g[n_,i_]:=(n-2)!*(n-i)*(i-1); Print["g(",n,",",i,")=",g[n,i]]]

For n >=2, if 1 <= i <= floor(n/2), g(n,i) = (n-2)!*(n-1-i)*i; if ceiling((n+1)/2) <= i <= n-1, g(n,i) = (n-2)!*(n-i)*(i-1).
# alternative
A241094 := proc(n,i)
    if n <2 or i<1 or i >= n then
        0;
    elif i <= floor(n/2) then
        GAMMA(n-1)*(n-1-i)*i;
    else
        GAMMA(n-1)*(n-i)*(i-1) ;
    fi ;
end proc:
seq(seq(A241094(n,i),i=1..n-1),n=2..12); # R. J. Mathar, Jul 30 2024

A103297 Number of different lengths that perfect rulers with n segments can have.

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 4, 6, 6, 7, 7, 7, 8, 10, 11, 11, 11, 11, 11, 13, 14, 15, 15, 16, 14, 19

Offset: 0

Peter Luschny, Feb 28 2005

For definitions, references and links related to complete rulers see A103294.

			a(5)=4 because a perfect ruler with 5 segments may have the length 10, 11, 12 or 13.

F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
Index entries for sequences related to perfect rulers.

Cf. A103298.

a(n) = A004137(n+1) - A004137(n) for n>= 1.

Term a(19) corrected and terms a(20)-a(25) added by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 23 2021

A193802 Length of optimal Wichmann rulers.

Original entry on oeis.org

3, 6, 9, 29, 36, 43, 50, 68, 79, 90, 101, 112, 123, 138, 153, 168, 183, 198, 213

Offset: 1

Peter Luschny, Oct 22 2011

R is an optimal Wichmann ruler iff R is an optimal ruler (for definition see A103294) and there exist two integers r>=0 and s>=0 such that the type of the difference representation of the ruler is [1*r, r+1, (2r+1)*r, (4r+3)*s, (2r+2)*(r+1), 1*r].

a(n) is a subsequence of A193803.

			[0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68] is an optimal Wichmann ruler with length 68 of Wichmann type (2,3). By contrast [0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68] is an optimal ruler with length 68 which is not a Wichmann ruler.

L. Egidi and G. Manzini, Spaced seeds design using perfect rulers, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
Peter Luschny, Perfect rulers
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.

Cf. A004137, A193803.

a(16)-a(19) from Hugo Pfoertner, Jul 12 2017

A193803 Length of perfect Wichmann rulers.

Original entry on oeis.org

3, 6, 9, 12, 15, 18, 22, 29, 36, 43, 46, 50, 57, 64, 68, 71, 79, 90, 101, 108, 112, 123, 134, 138, 145, 153, 156, 168, 175, 183

Offset: 1

Peter Luschny, Oct 22 2011

R is a perfect Wichmann ruler iff R is a perfect ruler (for definition see A103294) and there exist two integers r>=0 and s>=0 such that the type of the difference representation of the ruler is [1*r, r+1, (2r+1)*r, (4r+3)*s, (2r+2)*(r+1), 1*r].

			[0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68] is a perfect Wichmann ruler with length 68 of Wichmann type (2,3). By contrast [0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68] is a perfect ruler with length 68 which is not a Wichmann ruler.

L. Egidi and G. Manzini, Spaced seeds design using perfect rulers, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
Peter Luschny, Perfect rulers
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.

Cf. A004137, A193802.

A212661 a(n) = smallest number of edges that must be removed from K_n to obtain a graceful graph.

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 7, 9, 12, 16, 20, 23, 26, 30, 35, 41, 48, 52, 57, 63, 70, 78, 87, 93

Offset: 3

N. J. A. Sloane, Jun 05 2012

G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications. Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
Miller, J. C. P. Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817) - From N. J. A. Sloane, Jun 05 2012
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552. - From N. J. A. Sloane, Jun 05 2012

G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
Index entries for sequences related to Golomb rulers

Cf. A003022, A078106, A004137.

n(n-1)/2 = a(n)+A004137(n). - Kellen Myers, Jun 06 2016

a(26) using extension of A004137 from Hugo Pfoertner, Feb 28 2021

A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.

Original entry on oeis.org

1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2

Offset: 0

Labib Haddad and Michel Marcus, Dec 06 2015

Let A be a subset of the set N of nonnegative integers. Let pA(n) be the number of pairs (x, y) of elements of A such that n = x + y and x <= y. The sequence pA = [pA(0), pA(1), ... , pA(n), ... ] is called the profile of A. A Sidon set is a subset A whose profile has only 0's and 1's.
An [order 2 additive] basis of N is a subset A whose profile has no 0’s. Erdős and Turán conjectured that the profile of a basis is always unbounded (see the Erdős and Turán link). The conjecture is, up till now, still undecided.
The tree below displays the infinite sequences [1, pA(2), . . . ], associated to the profiles pA = [1, 1, pA(2), . . . ] of all the subsets A of N to which 0 and 1 belong. Those are the so-called hemitropic sequences. The Erdős-Turán conjecture would not hold if (and only if) the tree contained an infinite bounded branch with no 0's.
The length of the n-th row is 2^n. The right leaf of a node is equal to the left leaf + 1.

			First few levels of the tree:
                       1;
           1,                      2;
     0,          1,          1,         2;
  0,    1,    1,    2,    1,    2,    2,   3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...
First few rows of the irregular array:
1;
1, 2;
0, 1, 1, 2;
0, 1, 1, 2, 1, 2, 2, 3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...

Michel Marcus, Table of n, a(n) for n = 0..8190
P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
Labib Haddad, Some peculiarities of order 2 bases of N and the Erdos-Turan conjecture, arXiv:1507.05849 [math.NT], 2015 (see The binary tree of hemitropic sequences chapter).
Wikipedia, Erdős-Turán conjecture on additive bases

Cf. A004137, A066062, A217793.

with(ListTools):
v:=n->Reverse( convert(n,base,2)):
m:=n->nops(v(n)):
c:=n-> v(n)[m(n)] + sum(v(n)[k]*v(n)[m(n)-k],k=1..floor(m(n)/2)):
d:= h->[seq(c(n),n=2^h..2^(h+1)-1)]: # the h-th row
f:= p->[seq(c(n),n=1..p)]: # the first p terms

f(t,n,va) = 1+ sum(k=1, n+1, va[k]*t^k);
row(n) = {if (n==0, vc = [1], vc = []; for (ni = 2^n, 2^(n+1)-1, b = binary(ni); ft = f(t, n, b); pt = (f(t, n, b)^2 + f(t^2, n, b))/2; vc = concat(vc, polcoeff(pt, n+1)););); vc;}
tabf(nn) = for (n=0, nn, vrow = row(n); for (k=1, #vrow, print1(vrow[k], ", ")); print());

For each k>=0, let u(k)=1 if k is in A, u(k)=0 is k is not in A. Then pA(n) = Sum_{k=0..floor(n/2)} u(k)*u(n-k). See formula (5) on p. 8 and p. 28 in Haddad link.

A289873 Related to perfect Wichmann rulers: a(n) = ( n^2 - (mod(n, 6) - 3)^2 ) / 3.

Original entry on oeis.org

1, 3, 5, 7, 9, 15, 21, 27, 33, 39, 45, 55, 65, 75, 85, 95, 105, 119, 133, 147, 161, 175, 189, 207, 225, 243, 261, 279, 297, 319, 341, 363, 385, 407, 429, 455, 481, 507, 533, 559, 585, 615, 645, 675, 705, 735, 765, 799, 833, 867, 901, 935, 969, 1007, 1045, 1083, 1121, 1159, 1197, 1239, 1281, 1323, 1365

Offset: 2

Hugo Pfoertner, Jul 14 2017

Leading term in length A289761 of longest perfect Wichmann ruler with n segments.

Hugo Pfoertner, Table of n, a(n) for n = 2..10001

Cf. A004137, A193802, A193803, A289761.

A014641 is a subsequence.

p := (n, x) -> (2*n - 3*(1 + x))*(1 + x):
a := n -> p(n, 2*floor(n/6)):
seq(a(n), n = 2..64); # Peter Luschny, Jul 14 2017

Table[(n^2 - (Mod[n, 6] - 3)^2)/3, {n, 2, 64}] (* Michael De Vlieger, Jul 14 2017 *)

def A289873(n): return (n+(m:=n%6))*(n-(k:=m-3))//3+k-n # Chai Wah Wu, Jun 20 2024

a(n) = A289761(n) - n.
G.f.: x^2*(1 + x - x^2)*(1 + x^2 - x^3 + 2*x^4 + x^5) / ((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)) (conjectured). - Colin Barker, Jul 14 2017
Can be seen as a family of parabolas p_{n}(x) = (2*n - 3*(1 + x))*(1 + x) evaluated at x = 2*floor(n/6). - Peter Luschny, Jul 14 2017

A102508 Suppose there are equally spaced chairs around a round table. Then a(n) is the maximal number of chairs for which there exists a seating arrangement of n people around the table such that if a waiter puts two glasses (randomly) on the table in front of two (different) chairs, it is always possible to turn the table so that the two glasses end up in front of two seated persons.

Original entry on oeis.org

1, 3, 7, 13, 21, 31, 39, 57, 73, 91, 95, 133

Offset: 1

Ard Van Moer (ard.van.moer(AT)vub.ac.be), Mar 15 2005

a(n) <= n(n-1)+1. Moreover, a(n)=n(n-1)+1 iff A058241(n)>0, i.e., when a perfect difference set modulo n(n-1)+1 exists. In particular, a(12) = 133, a(14)=183, a(17)=273, etc.
This problem is a circular analog of an optimal ruler problem; see A004137. - David Wasserman, Apr 15 2008
Solutions do not always exist for table sizes less than a(n). For example, for n = 5 there is no solution for a table of size 20. - David Wasserman, Apr 15 2008
Equivalently, largest value of S such that in some cyclic array of positive integers of length n, every positive integer <= S is the sum of consecutive terms. For example, the numbers 1..21 can be written as the sum of consecutive terms in the cyclic array [10,3,1,5,2]. So a(5) = 21. - Phil Scovis, Jan 29 2016
If there exists a ruler of length L and n marks, then it can be trivially transformed to a ruler of length L and n+1 marks, by simply dividing one of the segments into two. In other words, a(n+1) >= a(n). - Dmitry Kamenetsky, Aug 02 2025
a(14)=183, a(17)=273, a(18)=307, a(20)=381, a(24)=553 and so on. See Dan Gordon's site in links. - Dmitry Kamenetsky, Aug 02 2025
a(16) >= 195, since every length from 1 to 195 can be generated with the cyclic ruler [3,14,2,5,29,1,4,66,6,9,11,1,1,10,8,25]. - Dmitry Kamenetsky, Aug 02 2025

			a(5)=21 because if we have 21 chairs, 5 persons can sit down on chairs 1, 4, 5, 10 and 12. 1 == 5-4 (mod 21). 2 == 12-10 (mod 21). 3 == 4-1 (mod 21). 4 == 5-1 (mod 21). 5 == 10-5 (mod 21). 6 == 10-4 (mod 21). 7 == 12-5 (mod 21). 8 == 12-4 (mod 21). 9 == 10-1 (mod 21). 10 == 1-12 (mod 21). It is impossible to do the same with 22 or more chairs.

Dan Gordon, Difference Sets
Don Reble, C++ Program

Cf. A004137, A058241.

3 more terms from David Wasserman, Apr 15 2008
Edited by Max Alekseyev, Apr 29 2010, Mar 01 2015
a(11) = 95 from Don Reble, Feb 25 2015. - N. J. A. Sloane, Mar 01 2015
a(12) from Max Alekseyev, Mar 01 2015

cp's OEIS Frontend

A241094 Triangle read by rows: T(n,i) = number of gracefully labeled graphs with n edges that do not use the label i, 1 <= i <= n-1, n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A103297 Number of different lengths that perfect rulers with n segments can have.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A193802 Length of optimal Wichmann rulers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A193803 Length of perfect Wichmann rulers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A212661 a(n) = smallest number of edges that must be removed from K_n to obtain a graceful graph.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A289873 Related to perfect Wichmann rulers: a(n) = ( n^2 - (mod(n, 6) - 3)^2 ) / 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Views

Author

Keywords

Comments

Examples

Links