Rainbow maps and the number of graceful labelings of trees

arXiv:2610.34877 · math.CO · Submitted 2026-10-26 · Read on arXiv

math.CO

Submitted: 2026-10-26

Updated: 2026-10-26

Comments: 27 pages, 2 figures. A Lean 4 formalization of the main theorem is included in the ancillary files (directory anc/lean)

License: http://creativecommons.org/licenses/by/4.0/

The gist: Let τ(N) be the number of graceful labelings of trees with N edges, that is, the number of spanning trees of the complete graph on 0,1,,N whose edges have distinct lengths.

Abstract

Let τ(N) be the number of graceful labelings of trees with N edges, that is, the number of spanning trees of the complete graph on 0,1,,N whose edges have distinct lengths. The answer to exercise 7.2.2.3-106 of The Art of Computer Programming states that, if an empirical observation of Anick is true, then τ(n)= (n n-n (e/b)+O(n)) with b about0.636, and that rigorous proofs are unknown. We prove that τ(N)-(N N-N (e/b)) at most152(1+ (N+1)) 4 for every N at least3, with b=2/π. A rainbow map of order N sends each vertex k in1,,N-1 to a vertex f(k) in0,,N so that the lengths f(k)-k are 1,,N-1 in some order. Acyclic rainbow maps are exactly the graceful labelings, and all rainbow maps are counted by the Whitty numbers W(N) (OEIS A134983). We show that τ(N) at most W(N) at mostτ(N)e 151(1+ (N+1)) 4 by a combinatorial argument: for fixed directions, rainbow maps are rook placements on a Ferrers board; a swap injection shows that a uniformly random rainbow map has O(2N) cycles on average; and an inequality on the periods of a word shows that the c cycles of a rainbow map can be removed by changing O(c N) edges. We also show that W(N) is the total weight of a family of weighted Motzkin paths. This yields exact enumerations, an alternating sum for W(N), and a representation of W(N) as a moment of a continuous dual Hahn weight, from which W(N)-(N (2N/π)-N) at most5(1+ (N+1)). The main theorem has been formalized in Lean 4; its combinatorial half uses no axioms beyond those of Lean.

Related papers