cp's OEIS Frontend

A338987 Number of rooted graceful labelings with n edges.

%I A338987 #20 Mar 07 2025 16:13:33
%S A338987 1,1,2,6,24,108,596,3674,26068,202470,1753884,16435754,168174596,
%T A338987 1842418704,21757407158,272771715272,3649515044178,51532670206504,
%U A338987 770442883634326,12093451621846094,199856952123506304,3452120352032161404,62471981051497913826,1177664861561125869100,23163177237781937250558
%N A338987 Number of rooted graceful labelings with n edges.
%C A338987 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.
%C A338987 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.
%H A338987 David A. Sheppard, <a href="http://dx.doi.org/10.1016/0012-365X(76)90051-0">The factorial representation of major balanced labelled graphs</a>, Discrete Math., Vol. 15, No. 4 (1976), 379-388.
%e A338987 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.
%o A338987 (Python)
%o A338987 def solve(d, m_in):
%o A338987     global _n, _cache
%o A338987     args = (d, m_in)
%o A338987     if args in _cache:
%o A338987         return _cache[args]
%o A338987     if d == 0:
%o A338987         rv = 1
%o A338987     else:
%o A338987         rv = 0
%o A338987         m_test = 1 | (1<<d)
%o A338987         for p in range(_n + 1 - d):
%o A338987             if m_in & m_test:
%o A338987                 rv += solve(d-1, m_in | m_test)
%o A338987             m_test <<= 1
%o A338987     _cache[args] = rv
%o A338987     return rv
%o A338987 def a338987(n):
%o A338987     global _cache, _n
%o A338987     _cache, _n = {}, n
%o A338987     return 1 if n<2 else 2*solve(n-2, 3|(1<<n))
%o A338987 # _Bert Dobbelaere_, Dec 23 2020
%Y A338987 Without rootedness, the number of graceful labelings is n!, A000142, as observed by Sheppard in 1976.
%K A338987 nonn
%O A338987 0,3
%A A338987 _Don Knuth_, Dec 20 2020
%E A338987 a(17)-a(24) from _Bert Dobbelaere_, Dec 23 2020