Rainbow maps and the number of graceful labelings of trees
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,\dots,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(n\ln n-n\ln(e/b)+O(\log n))$ with $b\approx0.636$, and that rigorous proofs are unknown. We prove that $|\logτ(N)-(N\log N-N\log(e/b))|\le152(1+\log(N+1))^4$ for every $N\ge3$, with $b=2/π$. A rainbow map of order $N$ sends each vertex $k\in\{1,\dots,N-1\}$ to a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.34877
curl -X POST /api/v1/records/arxiv/2610.34877/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.34877/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'