cp's OEIS Frontend

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

%I A033472 #47 Jun 25 2021 23:11:12
%S A033472 1,1,2,4,12,40,164,752,4020,23576,155632,1112032,8733628,73547332,
%T A033472 670789524,6502948232,67540932632,740949762580,8634364751264,
%U A033472 105722215202120,1366258578159064,18468456090865364,262118487952306820
%N A033472 Number of n-vertex labeled graphs that are gracefully labeled trees.
%C A033472 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.
%C A033472 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
%C A033472 _Noam D. Elkies_ and I have independently verified the existing terms and computed more, up to a(31). - _Don Knuth_, Feb 09 2021
%D A033472 A. Kotzig, Recent results and open problems in graceful graphs, Congressus Numerantium, 44 (1984), 197-219 (esp. 200, 204).
%H A033472 Don Knuth and Noam Elkies, <a href="/A033472/b033472.txt">Table of n, a(n) for n = 1..31</a>
%H A033472 David Anick, <a href="https://doi.org/10.1016/j.dam.2015.05.031">Counting graceful labelings of trees: a theoretical and empirical study</a>, Discrete Applied Mathematics 198 (2016), 65-81.
%H A033472 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A033472 a(n) = 2 * A337274(n) for n >= 3. - _Hugo Pfoertner_, Oct 05 2020
%e A033472 For n=3 we have 1-3-2 and 2-1-3, so a(3)=2.
%o A033472 (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))))) }
%o A033472 { 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
%o A033472 for(n=1,18,print1(graceful_tree_count(n),", ")) \\ Example of function call
%Y A033472 Cf. A006967, A337274.
%K A033472 nonn
%O A033472 1,3
%A A033472 _Glenn G. Chappell_