TOPICS
Search

Graceful Permutation

A graceful permutation sigma on n letters, for a positive integer n, is a permutation of {1,2,...,n} such that

{|sigma(i)-sigma(i+1)|:i=1,2,...,n-1}={1,2,...,n-1}.

For example, there are four graceful permutations on {1,2,3,4}: {1,4,2,3}, {2,3,1,4}, {3,2,4,1}, and {4,1,3,2}. The number of graceful permutations on n letters for n=1, 2, ... are 1, 2, 4, 4, 8, 24, 32, 40, ... (OEIS A006967).

The graceful permutations on n letters are isomorphic with graceful labelings of the path graph P_n.

See also

Graceful Graph, Graceful Labeling

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A006967/M3229 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997. https://doi.org/10.1017/CBO9780511662034.049.Wilf, H. S. and Yoshimura, N. A. "Ranking Rooted Trees, and a Graceful Application." In Discrete Algorithms and Complexity (Proceedings of the Japan-US Joint Seminar June 4-6, 1986, Kyoto, Japan) (Ed. D. Johnson, T. Nishizeki, A. Nozaki and H. S. Wilf). Boston, MA: Academic Press, pp. 341-349, 1987. https://doi.org/10.1016/B978-0-12-386870-1.50025-3.

Referenced on Wolfram|Alpha

Graceful Permutation

Cite this as:

Weisstein, Eric W. "Graceful Permutation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GracefulPermutation.html

Subject classifications