Rainbow maps and the number of graceful labelings of trees
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality