A338986 Number of rooted graceful permutations of length n.

1, 1, 2, 4, 4, 8, 12, 4, 12, 12, 16, 20, 28, 12, 12, 60, 16, 20, 40, 48, 48, 52, 44, 76, 52, 72, 80, 68, 60, 136, 148, 152, 72, 216, 116, 140, 116, 184, 408, 176, 404, 288, 412, 440, 356, 384, 464, 256, 704, 444, 812, 560, 348, 904, 800, 1088, 628, 716, 868

Offset: 0

Author

Don Knuth, Dec 20 2020

Keywords

• nonn

Comments

A permutation p[1]...p[n] of {1,...n} is graceful if the n-1 differences |p[j+1] -p[j]| are distinct. It is rooted if, in addition, |p[j+1] - p[j]| = k < n-1 implies that either |p[j] - p[j-1]| > k or |p[j+2] - p[j+1]| > k.

Examples

			For n = 6 the a(6) = 12 solutions are 162534, 251643, 316254, 325164, 342516, 346152, 431625, 435261, 452613, 461523, 526134, 615243.
		

Links

• Don Knuth, Table of n, a(n) for n = 0..173

Crossrefs

A006967 counts all graceful permutations.

If n > 2, a(n) = 4*A338988(n).