TOPICS
Search

Graceful Permutation

A graceful permutation sigma on n letters is a permutation 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. "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.Wilf, H. S. and Yoshimura, N. "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-350, 1987.

Referenced on Wolfram|Alpha

Graceful Permutation

Cite this as:

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

Subject classifications