

A338987


Number of rooted graceful labelings with n edges.


2



1, 1, 2, 6, 24, 108, 596, 3674, 26068, 202470, 1753884, 16435754, 168174596, 1842418704, 21757407158, 272771715272, 3649515044178, 51532670206504, 770442883634326, 12093451621846094, 199856952123506304, 3452120352032161404, 62471981051497913826, 1177664861561125869100, 23163177237781937250558
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

A graceful labeling of a graph with n edges assigns distinct labels l(v) to the vertices such that 0<=l(v)<=n and the n differences l(u)l(v) between labels of adjacent vertices are distinct. It is rooted if, in addition, either l(u)l(w)>l(u)l(v) for some neighbor of u or l(v)l(w)>l(u)l(v) for some neighbor of v, whenever l(u)l(v)<n.
To generate such a labeling, choose one of the k+1 edges 0(nk), 1(n+1k), ..., k(nk), for each k=0, 1, ..., n1, provided that at least one of the endpoints has already appeared in a previously chosen edge when k>0.


LINKS

Table of n, a(n) for n=0..24.
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., Vol. 15, No. 4 (1976), 379388.


EXAMPLE

a(5) = 108 < 120 = 5!, because 05,04,03,35,12 and 05,15,25,02,13 are forbidden, as well as five each beginning with 05,04,25,13 and 05,14,03,24.


PROG

(Python)
def solve(d, m_in):
....global _n, _cache
....args = (d, m_in)
....if args in _cache:
........return _cache[args]
....if d == 0:
........rv = 1
....else:
........rv = 0
........m_test = 1  (1<<d)
........for p in range(_n + 1  d):
............if m_in & m_test:
................rv += solve(d1, m_in  m_test)
............m_test <<= 1
...._cache[args] = rv
....return rv
def a338987(n):
....global _cache, _n
...._cache, _n = {}, n
....return 1 if n<2 else 2*solve(n2, 3(1<<n))
# Bert Dobbelaere, Dec 23 2020


CROSSREFS

Without rootedness, the number of graceful labelings is n!, A000142, as observed by Sheppard in 1976.
Sequence in context: A189840 A189255 A324591 * A174076 A230695 A177519
Adjacent sequences: A338984 A338985 A338986 * A338988 A338989 A338990


KEYWORD

nonn


AUTHOR

Don Knuth, Dec 20 2020


EXTENSIONS

a(17)a(24) from Bert Dobbelaere, Dec 23 2020


STATUS

approved



