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

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,3

Comments

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

References

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

Links

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

Formula

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

Example

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

Prog

(PARI) { 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

Crossrefs

Cf. A006967, A337274.

Sequence in context: A215070 A188479 A062962 * A134983 A330679 A342225

Adjacent sequences: A033469 A033470 A033471 * A033473 A033474 A033475

Keyword

nonn

Author

Glenn G. Chappell

Status

approved