1,3

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

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.

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

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

(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

Cf. A006967, A337274.

Sequence in context: A188479 A381360 A062962 * A134983 A330679 A342225

Adjacent sequences: A033469 A033470 A033471 * A033473 A033474 A033475

approved