cp's OEIS Frontend

A338988 Number of rooted graceful labelings of the path P_n.

%I A338988 #11 Dec 21 2020 06:49:59
%S A338988 1,1,1,1,1,2,3,1,3,3,4,5,7,3,3,15,4,5,10,12,12,13,11,19,13,18,20,17,
%T A338988 15,34,37,38,18,54,29,35,29,46,102,44,101,72,103,110,89,96,116,64,176,
%U A338988 111,203,140,87,226,200,272,157,179,217,240,247,224,224,467
%N A338988 Number of rooted graceful labelings of the path P_n.
%C A338988 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 A338988 Two labelings of the path P_n are considered to be the same if we get one from the other by reflecting the path left<->right and/or by complementing the labels with respect to n-1. Thus we can assume that the labeling contains the subsequence (n-2)0(n-1) when n > 2.
%C A338988 If x[1]...x[t] is the subsequence containing all differences > k > 1, the subsequence for k-1 must be either (x[1]\pm k)x[1]...x[t] or x[1]...x[t](x[t]\pm k).
%C A338988 So a[n] <= 4^(n-3) for n > 2.
%D A338988 D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3 (in preparation)
%H A338988 Don Knuth, <a href="/A338988/b338988.txt">Table of n, a(n) for n = 0..173</a>
%e A338988 For n = 6 the a(6) = 3 canonical labelings are 140532, 214053, 231405.
%Y A338988 A338987 counts rooted graceful labelings of all graphs (times 2 when n > 1 because it also counts complementary labelings).
%Y A338988 A338986(n) = 4*a(n) when n > 2, because it also counts complementary labelings and reverses of labelings.
%K A338988 nonn
%O A338988 0,6
%A A338988 _Don Knuth_, Dec 20 2020