Efficient enumeration of graceful permutations. (English) Zbl 1297.05007

Adamaszek, Michał

J. Comb. Math. Comb. Comput. 87, 191-197 (2013).

Summary: A graceful \(n\)-permutation is a graceful labeling of an \(n\)-vertex path \(P_n\). In this paper we improve the asymptotic lower bound on the number of such permutations from \(\Omega ((5/3)^n)\) to \(\Omega(2.37^n)\). This is a computer-assisted proof based on an effective algorithm that enumerates graceful \(n\)-permutations. Our algorithm is also presented in detail.

MSC:

05A05	Permutations, words, matrices
05A15	Exact enumeration problems, generating functions
05C38	Paths and cycles

Keywords:

graceful \(n\)-permutations; enumeration