Rainbow maps and the number of graceful labelings of trees
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)=exp(nln n−nln(e/b)+O(log n)) with b≈0.636, and that rigorous proofs are unknown. We prove that |logτ(N)−(Nlog N−Nlog(e/b))|≤152(1+log(N+1))4 for every N≥3, with b=2/π. A rainbow map of order N sends each vertex k∈{1,…,N−1} to a vertex f(k)∈{0,…,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)≤ W(N)≤τ(N)e151(1+log(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(log2N) 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(clog 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 |log W(N)−(Nlog(2N/π)−N)|≤5(1+log(N+1)). The main theorem has been formalized in Lean 4; its combinatorial half uses no axioms beyond those of Lean.
Related
- Prime Labelings of Trees
- Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs
- A rainbow partition theorem for trees and connected maximin share allocations of chores
- On rainbow saturated graphs with minimum number of edges
- Borel complexity for product of trees and commuting partial maps
BibTeX
@misc{li2026rainbow,
title = {{Rainbow maps and the number of graceful labelings of trees}},
author = {Shisheng Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34877},
eprint = {2610.34877},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34877},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rainbow maps and the number of graceful labelings of trees
AU - Shisheng Li
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34877
UR - https://arxiv.org/abs/2610.34877
AB - 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)=exp(nln n−nln(e/b)+O(log n)) with b≈0.636, and that rigorous proofs are unknown. We prove that |logτ(N)−(Nlog N−Nlog(e/b))|≤152(1+log(N+1))^4 for every N≥3, with b=2/π. A rainbow map of order N sends each vertex k∈{1,…,N−1} to a vertex f(k)∈{0,…,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)≤ W(N)≤τ(N)e^151(1+log(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(log^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(clog 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 |log W(N)−(Nlog(2N/π)−N)|≤5(1+log(N+1)). The main theorem has been formalized in Lean 4; its combinatorial half uses no axioms beyond those of Lean.
ER -