betaFeedback

WorksMathematics

Rainbow maps and the number of graceful labelings of trees

Abstract

Let τ(N)τ(N) be the number of graceful labelings of trees with NN edges, that is, the number of spanning trees of the complete graph on {0,1,…,N}\{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⁡(nln⁡n−nln⁡(e/b)+O(log⁡n))τ(n)=\exp(n\ln n-n\ln(e/b)+O(\log n)) with b≈0.636b\approx0.636, and that rigorous proofs are unknown. We prove that ∣log⁡τ(N)−(Nlog⁡N−Nlog⁡(e/b))∣≤152(1+log⁡(N+1))4|\logτ(N)-(N\log N-N\log(e/b))|\le152(1+\log(N+1))^4 for every N≥3N\ge3, with b=2/πb=2/π. A rainbow map of order NN sends each vertex k∈{1,…,N−1}k\in\{1,\dots,N-1\} to a vertex f(k)∈{0,…,N}f(k)\in\{0,\dots,N\} so that the lengths ∣f(k)−k∣|f(k)-k| are 1,…,N−11,\dots,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)W(N) (OEIS A134983). We show that τ(N)≤W(N)≤τ(N)e151(1+log⁡(N+1))4τ(N)\le W(N)\leτ(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)O(\log^2N) cycles on average; and an inequality on the periods of a word shows that the cc cycles of a rainbow map can be removed by changing O(clog⁡N)O(c\log N) edges. We also show that W(N)W(N) is the total weight of a family of weighted Motzkin paths. This yields exact enumerations, an alternating sum for W(N)W(N), and a representation of W(N)W(N) as a moment of a continuous dual Hahn weight, from which ∣log⁡W(N)−(Nlog⁡(2N/π)−N)∣≤5(1+log⁡(N+1))|\log W(N)-(N\log(2N/π)-N)|\le5(1+\log(N+1)). The main theorem has been formalized in Lean 4; its combinatorial half uses no axioms beyond those of Lean.

Introduction

The problem

A graceful labeling of a tree with NN edges is a bijection from its vertices to {0,1,…,N}\{0,1,\ldots,N\} such that the NN edge lengths ∣i−j∣|i-j| (ii and jj being the labels of the two ends) are distinct. Using the labels as vertex names, a graceful labeling is a spanning tree of the complete graph on {0,…,N}\{0,\ldots,N\} whose edges have distinct lengths; we define τ(N)\tau(N) to be the number of such spanning trees. (Thus a labeling and its complement i↦N−ii\mapsto N-i are counted separately unless they give the same tree.) With this definition τ(N)=A033472(N+1)\tau(N)=\mathrm{A033472}(N+1) [11]. Exercise 7.2.2.3–106 of The Art of Computer Programming [7], rated [HM46], asks for the asymptotics of τ(n)\tau(n). The answer in the first printing reads:

  1. Empirical investigations by D. Anick suggest that τ(n)/τ(n−1)\tau(n)/\tau(n-1) grows approximately as a+bn+(−1)nc/na+bn+(-1)^nc/n for some constants aa, bb, cc. If that is true, τ(n)=exp⁡(nln⁡n−nln⁡(e/b)+O(log⁡n))\tau(n)=\exp(n\ln n-n\ln(e/b)+O(\log n)). The exact values for n<30n<30 suggest further that a≈0.19a\approx0.19, b≈0.636b\approx0.636, and c≈0.42c\approx0.42. But rigorous proofs are unknown. (This function τ(n)\tau(n) was introduced by A. Kotzig, who computed it by hand for n≤6n\le6 in 1984.)

Anick’s study appeared in [2].

Results

Throughout, m:=N−1m := N - 1, Λ:=1+log⁡(N+1)\Lambda:= 1 + \log(N + 1), and log⁡\log is the natural logarithm. (The constants aa, bb, cc of the quoted answer appear only here and in § 8; elsewhere these letters have local meanings, and cc usually denotes a number of cycles.) Let W(N)W(N) be the number of rainbow maps of order NN (§ 2); it is the permanent of an explicit matrix with entries 0, 1, 2.

Theorem 1.1 (Comparison). For N≥3N \ge3, τ(N)≤W(N)≤τ(N)exp⁡(151Λ4)\tau(N) \le W(N) \le\tau(N)\exp(151\Lambda^4).

Theorem 1.2 (Size of the Whitty number W(N)W(N)). For N≥3N \ge3,

17(2π)mm!≤W(N)≤45(2π)m(m+3)!,hence∣log⁡W(N)−(Nlog⁡2Nπ−N)∣≤5Λ.\frac{1}{7}\left(\frac{2}{\pi}\right)^m m! \le W(N) \le45\left(\frac{2}{\pi}\right)^m (m+3)!, \qquad\text{hence} \qquad\left|\log W(N)-\left(N\log\frac{2N}{\pi}-N\right)\right| \le5\Lambda.

Theorem 1.3 (Main theorem). For every N≥3N \ge3,

∣log⁡τ(N)−(Nlog⁡2Nπ−N)∣≤152Λ4,\left|\log\tau(N)-\left(N\log\frac{2N}{\pi}-N\right)\right| \le152\Lambda^4,

and Nlog⁡2Nπ−N=Nlog⁡N−Nlog⁡ebN\log\frac{2N}{\pi}-N=N\log N-N\log\frac{e}{b} with b=2πb=\frac{2}{\pi}. In particular τ(N)=N!(2/π)NeO(log⁡4N)\tau(N)=N!(2/\pi)^N e^{O(\log^4 N)}.

Proof of Theorem 1.3 from Theorems 1.1 and 1.2. Theorem 1.1 gives −151Λ4≤log⁡τ(N)−log⁡W(N)≤0-151\Lambda^4 \le\log\tau(N)-\log W(N) \le0, and Theorem 1.2 gives ∣log⁡W(N)−(Nlog⁡2Nπ−N)∣≤5Λ\left|\log W(N)-\left(N\log\frac{2N}{\pi}-N\right)\right| \le5\Lambda. Add them and use 5Λ≤Λ45\Lambda\le\Lambda^4, which holds because Λ≥2.38\Lambda\ge2.38 for N≥3N \ge3. The last assertion follows from (3) below.

Section 3 also gives a Motzkin path formula for W(N)W(N) (Theorem 3.1) and several exact enumerations derived from it.

Approach

A graceful labeling is a spanning tree subject to two constraints: It has no cycle, and its edge lengths are distinct. Every such tree contains the edge {0,N}\{0,N\}, the only edge of length NN. Delete this edge and orient every other edge towards whichever of 0 and NN lies in its component; then every vertex other than 0 and NN has exactly one outgoing edge, and we obtain a rainbow map. If we drop the condition “no cycle”, the remaining object is of product type: Each vertex chooses an outgoing edge, subject only to the lengths being distinct. The number of such choices is a permanent. This relaxation is due to Whitty [14]. Theorem 1.1 shows that the relaxation loses almost nothing, and Theorems 3.1 and 1.2 compute the permanent.

Outline. Section 2 defines rainbow maps, their types, and the Whitty numbers. Section 3 reads a type as a lattice path. Sections 4–6 prove Theorem 1.1: There are few cycles, cycles are easy to repair, and a counting argument finishes the proof. Section 7 determines the size of W(N)W(N).

Formal verification. The main theorem has been formalized in Lean 4 [9] with Mathlib [10] (ancillary files, directory anc/lean). The formal statement uses only the definition of τ(N)\tau(N) as the number of spanning trees of the complete graph on {0,…,N}\{0,\ldots,N\} with edge lengths 1,…,N1,\ldots,N. The combinatorial half (Theorem 1.1) is proved with no axioms beyond those of Lean; the analytic half uses Facts 7.6 and 7.11 as axioms, and Theorem A.1 also uses Fact A.2.

Notation. NN: number of edges, also the order of a rainbow map; m=N−1m=N-1: number of interior vertices, also the number of available lengths; ρ(k)=min⁡(k,N−k)\rho(k)=\min(k,N-k): the rank of kk; R=⌊N/2⌋R=\lfloor N/2\rfloor; δk\delta_k: the length used by kk; σ\sigma: type; ℓk\ell_k: the upper bound of δk\delta_k for a given type; cc: number of cycles; HR=∑j≤R1/jH_R=\sum_{j\le R}1/j; D=⌈log⁡2m⌉D=\lceil\log_2 m\rceil (for N≥2N\ge2); Λ=1+log⁡(N+1)\Lambda=1+\log(N+1); [P][P] is 1 if the statement PP is true and 0 otherwise.

Rainbow maps

The vertices are 0,1,…,N0,1,\ldots,N. We call 00 and NN the ground and 1,…,m1,\ldots,m the interior vertices. The rank of an interior vertex kk is ρ(k):=min⁡(k,N−k)\rho(k) := \min(k,N-k), its distance to the nearer end. Each rank is shared by at most two vertices (kk and N−kN-k), and there are R:=⌊N/2⌋R := \lfloor N/2\rfloor ranks.

Definition. A rainbow map of order NN is a function f:{1,…,m}→{0,…,N}f:\{1,\ldots,m\}\to\{0,\ldots,N\} such that the numbers ∣f(k)−k∣\lvert f(k)-k\rvert are 1,…,m1,\ldots,m, each exactly once.

The name rainbow map is due to D. E. Knuth (private communication). We call f(k)f(k) the target of kk and δk:=∣f(k)−k∣\delta_k := \lvert f(k)-k\rvert its length. Drawing the arcs k→f(k)k\to f(k) and the arc 0→N0\to N gives a directed graph in which every interior vertex has exactly one outgoing arc. The type σ∈{L,R}m\sigma\in\{\mathrm{L},\mathrm{R}\}^{m} records the directions: σk=L\sigma_k=\mathrm{L} if and only if f(k)<kf(k)<k. Given the type, the length of kk is bounded by

ℓk:={k,σk=L,N−k,σk=R,1≤δk≤ℓk.\ell_k := \begin{cases} k, & \sigma_k=\mathrm{L},\\ N-k, & \sigma_k=\mathrm{R}, \end{cases} \qquad1\leq\delta_k\leq\ell_k.

and ff is determined by σ\sigma and (δ1,…,δm)(\delta_1,\ldots,\delta_m).

Whitty numbers. Let W(N)W(N) be the number of rainbow maps of order NN. If vertex kk receives length dd, the number of possible directions is

Mk,d:=[d≤k]+[d≤N−k]∈{0,1,2},1≤k,d≤m.M_{k,d}:=[d\leq k]+[d\leq N-k]\in\{0,1,2\},\qquad1\leq k,d\leq m.

so that

W(N)=∑δ∏k=1mMk,δk=per⁡M,W(N)=\sum_{\delta}\prod_{k=1}^{m}M_{k,\delta_k}=\operatorname{per} M,

the sum being over all permutations δ\delta of {1,…,m}\{1,\ldots,m\}. For $N=6,

M=(2111122110222002211021111)M=\begin{pmatrix} 2&1&1&1&1\\ 2&2&1&1&0\\ 2&2&2&0&0\\ 2&2&1&1&0\\ 2&1&1&1&1 \end{pmatrix}

and W(6)=168W(6)=168. Rows kk and N−kN-k are equal, and vertices of small rank can use more lengths. The sequence W(N)W(N) begins 1,2,4,12,40,168,784,4272,…1,2,4,12,40,168,784,4272,\ldots (N=1,2,…N=1,2,\ldots); it is OEIS A134983. Whitty [14 Theorem 7] interprets this permanent as the number of rook placements on a Klein bottle chessboard and writes “We do not know of a way of evaluating the permanent involved in closed form”. We call W(N)W(N) the Whitty numbers.

In the directed graph the two ground vertices are absorbing (apart from 0→N0\to N). Let c(f)c(f) be the number of directed cycles. Every cycle has at least 3 vertices, because u→v→uu\to v\to u would use the length ∣u−v∣\lvert u-v\rvert twice.

Lemma 2.1 (cf. [14 Theorem 6 and the remarks before Theorem 7]). The underlying undirected graph of ff, together with the edge {0,N}\{0,N\}, is a tree if and only if c(f)=0c(f)=0. Acyclic rainbow maps correspond bijectively to graceful labelings; hence τ(N)=#{f:c(f)=0}≤W(N)\tau(N)=\#\{f:c(f)=0\}\leq W(N).

Proof. Given a graceful labeling, delete the edge {0,N}\{0,N\}; the tree splits into two trees containing 00 and NN respectively. Orient every edge towards the ground vertex of its tree. Every interior vertex has exactly one outgoing edge and the mm lengths are 1,…,m1,\ldots,m, so this is an acyclic rainbow map. Conversely, the mm edges of an acyclic rainbow map together with {0,N}\{0,N\} are NN edges on N+1N+1 vertices. Following arcs from any interior vertex never closes a cycle, so it reaches the ground; the graph is connected, hence a tree, and its lengths are 1,…,N1,\ldots,N. The two maps are inverse to each other. Finally, a directed cycle has at least 3 vertices, so it is a cycle of the underlying graph, which is then not a tree.

Thus τ(N)/W(N)=Pr⁡[c=0]\tau(N)/W(N) = \Pr[c = 0] for the uniform measure on all rainbow maps of order NN. Reversing a cycle of a rainbow map gives another rainbow map with the same edges.

References

  1. [1]G. E. Andrews and L. L. Littlejohn, A combinatorial interpretation of the Legendre–Stirling numbers, Proc. Amer. Math. Soc. 137 (2009), 2581–2590.DOI
  2. [2]D. Anick, Counting graceful labelings of trees: A theoretical and empirical study, Discrete Appl. Math. 198 (2016), 65–81, doi:10.1016/j.dam.2015.05.031.DOI
  3. [3]B. Deb and A. D. Sokal, Classical continued fractions for some multivariate polynomials generalizing the Genocchi and median Genocchi numbers, arXiv:2212.07232.arxiv.org/abs/2212.07232
  4. [4]NIST Digital Library of Mathematical Functions, https://dlmf.nist.gov/, §§5.4, 5.5, 5.8, 5.11, 18.25.
  5. [5]P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.
  6. [6]Y. Gelineau and J. Zeng, Combinatorial interpretations of the Jacobi–Stirling numbers, Electron. J. Combin. 17 (2010), #R70.arxiv.org/abs/0905.2899
  7. [7]D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 7: Constraint Satisfaction, Addison–Wesley, 2025. Exercises 7.2.2.3–105 and 106 and their answers.
  8. [8]R. Koekoek, P. A. Lesky and R. F. Swarttouw, Hypergeometric Orthogonal Polynomials and Their q-Analogues, Springer, 2010, §9.3.DOI
  9. [9]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction – CADE 28, Lecture Notes in Computer Science 12699, Springer, 2021, 625–635.DOI
  10. [10]The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367–381.
  11. [11]OEIS Foundation, The On-Line Encyclopedia of Integer Sequences, sequences A033472 (graceful labelings) and A134983 (rook placements on a Klein bottle chessboard, that is, W(N)).
  12. [13]G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Lecture notes, Université du Québec à Montréal, 1983.
  13. [14]R. W. Whitty, Rook polynomials on two-dimensional surfaces and graceful labellings of graphs, Discrete Math. 308 (2008), 674–683, doi:10.1016/j.disc.2007.07.054.DOI
  14. [15]J. A. Wilson, Some hypergeometric orthogonal polynomials, SIAM J. Math. Anal. 11 (1980), 690–701.DOI

Paper details

vlnc:W_k9ewebau
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI systems

View statement
Looking for related papers…
Contents