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--(n-k), 1--(n+1-k), ..., k--(n-k), for each k=0, 1, ..., n-1, provided that at least one of the endpoints has already appeared in a previously chosen edge when k>0.
LINKS
David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., Vol. 15, No. 4 (1976), 379-388.
EXAMPLE
a(5) = 108 < 120 = 5!, because 0--5,0--4,0--3,3--5,1--2 and 0--5,1--5,2--5,0--2,1--3 are forbidden, as well as five each beginning with 0--5,0--4,2--5,1--3 and 0--5,1--4,0--3,2--4.
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(d-1, 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(n-2, 3|(1<<n))
# Bert Dobbelaere, Dec 23 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Don Knuth, Dec 20 2020
EXTENSIONS
a(17)-a(24) from Bert Dobbelaere, Dec 23 2020
STATUS
approved