login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033472 Number of n-vertex labeled graphs that are gracefully labeled trees. 1
1, 1, 2, 4, 12, 40, 164, 752, 4020, 23576, 155632, 1112032, 8733628, 73547332, 670789524, 6502948232, 67540932632, 740949762580, 8634364751264, 105722215202120, 1366258578159064, 18468456090865364, 262118487952306820 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

The gp/pari 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

LINKS

Table of n, a(n) for n=1..23.

David Anick, Counting Graceful Labelings of Trees: A Theoretical and Empirical Study, preprint, 2015.

Index entries for sequences related to trees

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) ) }

CROSSREFS

Cf. A006967.

Sequence in context: A215070 A188479 A062962 * A134983 A218144 A222919

Adjacent sequences:  A033469 A033470 A033471 * A033473 A033474 A033475

KEYWORD

nonn

AUTHOR

Glenn G. Chappell

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 17:03 EDT 2019. Contains 324196 sequences. (Running on oeis4.)