login
Number of rooted graceful labelings of the path P_n.
2

%I #11 Dec 21 2020 06:49:59

%S 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 15,34,37,38,18,54,29,35,29,46,102,44,101,72,103,110,89,96,116,64,176,

%U 111,203,140,87,226,200,272,157,179,217,240,247,224,224,467

%N Number of rooted graceful labelings of the path P_n.

%C 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 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 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 So a[n] <= 4^(n-3) for n > 2.

%D D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3 (in preparation)

%H Don Knuth, <a href="/A338988/b338988.txt">Table of n, a(n) for n = 0..173</a>

%e For n = 6 the a(6) = 3 canonical labelings are 140532, 214053, 231405.

%Y A338987 counts rooted graceful labelings of all graphs (times 2 when n > 1 because it also counts complementary labelings).

%Y A338986(n) = 4*a(n) when n > 2, because it also counts complementary labelings and reverses of labelings.

%K nonn

%O 0,6

%A _Don Knuth_, Dec 20 2020