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

Author

Glenn G. Chappell

Keywords

• nonn

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

Examples

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

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

Crossrefs

Cf. A006967, A337274.

Programs

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

Formula

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