A033472 -id:A033472 - 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

A337274 Number of distinct graceful labelings of trees with n vertices.

Original entry on oeis.org

1, 1, 1, 2, 6, 20, 82, 376, 2010, 11788, 77816, 556016, 4366814, 36773666, 335394762, 3251474116, 33770466316, 370474881290, 4317182375632, 52861107601060, 683129289079532, 9234228045432682, 131059243976153410

Offset: 1

Don Knuth, Sep 03 2020

Consider vertices numbered 1 to n. Add the edges 1--n, 2--n, and either 1--(n+1-k), 2--(n+2-k), ... or k--n for 3<=k

			For example, the six labelings for n=5 are:
  1--5, 2--5, 1--3, 3--4;
  1--5, 2--5, 1--3, 4--5;
  1--5, 2--5, 2--4, 2--3;
  1--5, 2--5, 2--4, 3--4;
  1--5, 2--5, 3--5, 3--4;
  1--5, 2--5, 3--5, 4--5.
There are three trees (A000055); the path P4 has two labelings, the graph K_{1,4} has one, the other ("chair" or "fork") has three.

David Anick, Counting graceful labelings of trees: a theoretical and empirical study, Discrete Applied Mathematics 198 (2016), 65-81.

Cf. A000055, A033472.

\\ After David Anick's C program GLs
a337274(N) = {  if(N<4,return(1)); my (n=N-1, count, i, j, k, m, nn, n1, u, v, z, a=vectorsmall(N), r= vectorsmall(N), t=vectorsmall(N), w=vectorsmall(N,i,-1));
  nn = n-1; n1 = n+1; w[n1] = 1; w[n] = 2; t[1] = n; t[2] = nn; m = nn - 1;
  while (a[nn]==0,
    for (jj=n1-m, n,
      u = a[n1-jj]; v = u + n1 - jj;
      z = w[u+1]; while (z > 0, u = r[z]; z = w[u+1]);
      z = w[v+1]; while (z > 0, v = r[z]; z = w[v+1]);
      if (v == u, j=jj; break);
      if (v > u, w[v+1] = jj; r[jj] = u; t[jj] = v,
                 w[u+1] = jj; r[jj] = v; t[jj] = u);
      j=jj+1
    );
    if (j > n, count++; w[t[n]+1] = -1 );
    if (j >= n, a[1]++; if (a[1] < nn, m = 1; next );
                a[1] = 0; j = nn; w[t[nn]+1] = -1 );
    m = n1 - j; a[m]++;
    while (a[m]> n-m, a[m]=0; a[m++]++; w[t[n1-m]+1]=-1)
  ); count};
for(k=1,12,print1(a337274(k),", ")) \\ Hugo Pfoertner, Sep 04 2020

If n>3, a(n) = A033472(n)/2.

a(18)-a(19) from Bert Dobbelaere, Sep 06 2020

a(20)-a(23) (from A033472) from Joerg Arndt, Sep 15 2020

A329790 Irregular triangle read by rows: T(n,k) = total number of graceful labelings of connected graphs with n edges (n>=1) and k vertices (k>=1).

Original entry on oeis.org

0, 1, 0, 0, 2, 0, 0, 2, 4, 0, 0, 0, 12, 12, 0, 0, 0, 8, 68, 40, 0, 0, 0, 2, 106, 400, 164, 0, 0, 0, 0, 88, 1184, 2496, 752, 0, 0, 0, 0, 32, 1728, 11932, 17338, 4020, 0, 0, 0, 0, 8, 1696, 29444, 121084, 127660, 23576, 0, 0, 0, 0, 0, 964, 45472, 442222, 1259838, 1030524, 155632, 0, 0, 0, 0, 0, 432, 50292, 1051048, 6488844, 13590300, 8852398, 1112032

Offset: 1

N. J. A. Sloane, Dec 02 2019, based on email from Don Knuth, Dec 01 2019

Consider a connected graph with E edges and V vertices. The vertices are given labels in the range 0 to E so that the differences between edges' endpoints are {1,...,E}. None of the vertices are isolated; hence each vertex label participates in at least one edge.

			Rows 1 through 16 are:
0,1,
0,0,2,
0,0,2,4,
0,0,0,12,12,
0,0,0,8,68,40,
0,0,0,2,106,400,164,
0,0,0,0,88,1184,2496,752,
0,0,0,0,32,1728,11932,17338,4020,
0,0,0,0,8,1696,29444,121084,127660,23576,
0,0,0,0,0,964,45472,442222,1259838,1030524,155632,
0,0,0,0,0,432,50292,1051048,6488844,13590300,8852398,1112032,
0,0,0,0,0,104,40176,1744982,21410862,93887854,153385084,82121018,8733628,
0,0,0,0,0,24,24688,2250864,51470648,420080516,1378054500,1803091192,806839236,73547332,
0,0,0,0,0,0,11208,2184056,92513144,1340857860,7975757616,20604457050,22263918324,8481362264,670789524,
0,0,0,0,0,0,3780,1818244,136668880,3335302886,33380409234,151167588580,315541333316,286284099998,93933923996,6502948232,
0,0,0,0,0,0,864,1141312,159551124,6537511962,106698003000,795992914532,2869123162654,4974721374674,3859250594040,1104325114202,67540932632,

D. E. Knuth, Program for counting graceful graph labelings.
D. E. Knuth, Output from program

A033472, A329788, A329789 are diagonals.

A329788 Total number of graceful labelings of connected graphs with n edges.

Original entry on oeis.org

1, 2, 6, 24, 116, 672, 4520, 35050, 303468, 2934652, 31145346, 361323708, 4535359000, 61431851046, 890284097146, 13784350300996

Offset: 1

N. J. A. Sloane, Dec 01 2019, based on email from Don Knuth, Dec 01 2019

In general, consider a connected graph with E edges and V vertices. The vertices are given labels in the range 0 to E so that the differences between edges' endpoints are {1,...,E}. None of the vertices are isolated; hence each vertex label participates in at least one edge. For this sequence V is unrestricted and E = n.

D. E. Knuth, Program for counting graceful graph labelings.

Cf. A033472 (V=E+1), A329789 (V=E). A diagonal of the triangle in A329790.

A329789 Total number of graceful labelings of connected graphs with n vertices and n edges.

Original entry on oeis.org

0, 0, 2, 12, 68, 400, 2496, 17338, 127660, 1030524, 8852398, 82121018, 806839236, 8481362264, 93933923996, 1104325114202

Offset: 1

N. J. A. Sloane, Dec 01 2019, based on email from Don Knuth, Dec 01 2019

D. E. Knuth, Program for counting graceful graph labelings.

Cf. A033472 (V=E+1), A329788 (any V). A diagonal of the triangle in A329790.

Showing 1-5 of 5 results.

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

A337274 Number of distinct graceful labelings of trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A329790 Irregular triangle read by rows: T(n,k) = total number of graceful labelings of connected graphs with n edges (n>=1) and k vertices (k>=1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A329788 Total number of graceful labelings of connected graphs with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

A329789 Total number of graceful labelings of connected graphs with n vertices and n edges.

Views

Author

Keywords

Comments

Links

Crossrefs