A006967 -id:A006967 - cp's OEIS frontend

A004049 Erroneous version of A006967.

Original entry on oeis.org

1, 1, 4, 4, 8, 24, 32, 40, 120, 296

Offset: 1

N. J. A. Sloane

dead

A112362 A006967(n)/2.

Original entry on oeis.org

1, 2, 2, 4, 12, 16, 20, 60, 148, 324, 664, 1600, 4956, 12796, 27960, 71596, 255348, 725648, 1748672

Offset: 2

N. J. A. Sloane, Dec 02 2005

nonn

A033472 Number of n-vertex labeled graphs that are gracefully labeled trees.

Original entry on oeis.org

1, 1, 2, 4, 12, 40, 164, 752, 4020, 23576, 155632, 1112032, 8733628, 73547332, 670789524, 6502948232, 67540932632, 740949762580, 8634364751264, 105722215202120, 1366258578159064, 18468456090865364, 262118487952306820

Offset: 1

Glenn G. Chappell

nonn

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.
The PARI/GP program below uses the Matrix-Tree Theorem and sums over {1,-1} vectors to isolate the multilinear term. It takes time 2^n * n^O(1) to compute graceful_tree_count(n). - Noam D. Elkies, Nov 18 2002
Noam D. Elkies and I have independently verified the existing terms and computed more, up to a(31). - Don Knuth, Feb 09 2021

			For n=3 we have 1-3-2 and 2-1-3, so a(3)=2.

A. Kotzig, Recent results and open problems in graceful graphs, Congressus Numerantium, 44 (1984), 197-219 (esp. 200, 204).

Don Knuth and Noam Elkies, Table of n, a(n) for n = 1..31
David Anick, Counting graceful labelings of trees: a theoretical and empirical study, Discrete Applied Mathematics 198 (2016), 65-81.
Index entries for sequences related to trees

Cf. A006967, A337274.

{ treedet(v, n) = n=length(v); matdet(matrix(n,n,i,j, if(i-j,-v[abs(i-j)], sum(m=1,n+1,if(i-m,v[abs(i-m)],0))))) }
{ graceful_tree_count(n, s,v,v1,v0)= if(n==1,1, s=0; v1=vector(n-1,m,1); v0=vector(n-1,m,if(m==1,1,0)); for(m=2^(n-2),2^(n-1)-1, v= binary(m) - v0; s = s + (-1)^(v*v1~) * treedet(v1-2*v) ); s/2^(n-2) ) } \\ Noam D. Elkies, Nov 18 2002
for(n=1,18,print1(graceful_tree_count(n),", ")) \\ Example of function call

a(n) = 2 * A337274(n) for n >= 3. - Hugo Pfoertner, Oct 05 2020

A040018 (Number of permutations of {1,2,...,n} for which sums of adjacent numbers are all distinct)/2n.

Original entry on oeis.org

1, 1, 3, 8, 46, 176, 955, 5446, 36122, 259084, 2043944, 17371318, 159616680, 1566391958

Offset: 3

Erich Friedman

Essentially different ways 1,2,3,...,n can be placed around a circle so that sums of adjacent numbers are distinct.

Sean A. Irvine, Java program (github)

Cf. A091217, A006967.

a(10) from Vladeta Jovovic, Aug 25 2007
a(11)-a(13) from Steve Butler, Feb 08 2012
a(14)-a(16) from Sean A. Irvine, Mar 05 2021

A131529 Number of permutations of {1,2,...n} for which differences of adjacent numbers are all distinct.

Original entry on oeis.org

1, 2, 4, 12, 44, 176, 788, 3936, 23264, 152112, 1104876, 8725320, 74715908, 687915040, 6782261964, 71294227456, 796138700016, 9409401651840, 117378774461812

Offset: 1

Vladeta Jovovic, Aug 26 2007

Joerg Arndt, lexicopraphically first permutation with distinct differences for n=1..30 (permutations of {0,1,2,..,n-1}, i.e., zero based).

Cf. A040018, A091217, A006967.

2 more terms from R. J. Mathar, Oct 25 2007

7 more terms from R. H. Hardin, Nov 26 2009

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.

Original entry on oeis.org

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

A084894 Number of permutations of length n such that at least one absolute difference between consecutive elements has a distinct partner.

Original entry on oeis.org

0, 0, 2, 20, 112, 696, 5008, 40280, 362760, 3628504, 39916152, 479000272, 6227017600, 87178281288, 1307674342408, 20922789832080, 355687427952808, 6402373705217304, 121645100407380704, 2432902008173142656, 51090942171698988176, 1124000727777569109296

Offset: 1

Jon Perry, Jun 10 2003

nonn

			a(3)=2 as only 123 and 321 have the required property, with differences of 1,1. The rest all have differences of 1,2.

Jean-François Alcover, Table of n, a(n) for n = 1..40

Cf. A000142, A006967.

A006967 = Cases[Import["https://oeis.org/A006967/b006967.txt", "Table"], {, }][[All, 2]];
a[n_] := n! - A006967[[n+1]];
a /@ Range[40] (* Jean-François Alcover, Jan 31 2020 *)

{ for (n=3,10,x=vector(n-1); s=0; for (i=1,n!,v=numtoperm(n,i); for (j=1,n-1,x[j]=abs(v[j+1]-v[j])); x=vecsort(x); fl=0; for (k=1,n-2,if (x[k]==x[k+1],fl=1; break)); if (fl==1,s++)); print(n"; "s)) }

a(n) = n! - A006967(n).

A338986 Number of rooted graceful permutations of length n.

Original entry on oeis.org

1, 1, 2, 4, 4, 8, 12, 4, 12, 12, 16, 20, 28, 12, 12, 60, 16, 20, 40, 48, 48, 52, 44, 76, 52, 72, 80, 68, 60, 136, 148, 152, 72, 216, 116, 140, 116, 184, 408, 176, 404, 288, 412, 440, 356, 384, 464, 256, 704, 444, 812, 560, 348, 904, 800, 1088, 628, 716, 868

Offset: 0

Don Knuth, Dec 20 2020

nonn

A permutation p[1]...p[n] of {1,...n} is graceful if the n-1 differences |p[j+1] -p[j]| are distinct. It is rooted if, in addition, |p[j+1] - p[j]| = k < n-1 implies that either |p[j] - p[j-1]| > k or |p[j+2] - p[j+1]| > k.

			For n = 6 the a(6) = 12 solutions are 162534, 251643, 316254, 325164, 342516, 346152, 431625, 435261, 452613, 461523, 526134, 615243.

Don Knuth, Table of n, a(n) for n = 0..173

A006967 counts all graceful permutations.

If n > 2, a(n) = 4*A338988(n).

A336833 Triangle read by rows, 1 <= k <= n: T(n,k) is the number of graceful labelings of the n X k grid graph.

Original entry on oeis.org

1, 2, 16, 4, 128, 5728, 4, 1416, 580728, 758857152

Offset: 1

Pontus von Brömssen, Aug 05 2020

			Triangle begins:
  n\k  1    2      3          4
-------------------------------
  1:   1
  2:   2   16
  3:   4  128   5728
  4:   4 1416 580728  758857152

Eric Weisstein's World of Mathematics, Graceful Labeling
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Graceful labeling

First column: A006967; second column: A333719; diagonal: A337796.

T(4,4) from Pontus von Brömssen, Nov 04 2020 (Copied from A337796.)

cp's OEIS Frontend

A004049 Erroneous version of A006967.

Views

Author

Keywords

A112362 A006967(n)/2.

Views

Author

Keywords

A033472 Number of n-vertex labeled graphs that are gracefully labeled trees.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A040018 (Number of permutations of {1,2,...,n} for which sums of adjacent numbers are all distinct)/2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A131529 Number of permutations of {1,2,...n} for which differences of adjacent numbers are all distinct.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

A084894 Number of permutations of length n such that at least one absolute difference between consecutive elements has a distinct partner.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A338986 Number of rooted graceful permutations of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336833 Triangle read by rows, 1 <= k <= n: T(n,k) is the number of graceful labelings of the n X k grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions