Introduction
The problem
A graceful labeling of a tree with N N N edges is a bijection from its vertices to { 0 , 1 , … , N } \{0,1,\ldots,N\} { 0 , 1 , … , N } such that the N N N edge lengths ∣ i − j ∣ |i-j| ∣ i − j ∣ (i i i and j j j 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\} { 0 , … , N } whose edges have distinct lengths; we define τ ( N ) \tau(N) τ ( N ) to be the number of such spanning trees. (Thus a labeling and its complement i ↦ N − i i\mapsto N-i i ↦ N − i are counted separately unless they give the same tree.) With this definition τ ( N ) = A 033472 ( N + 1 ) \tau(N)=\mathrm{A033472}(N+1) τ ( N ) = 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) τ ( n ) . The answer in the first printing reads:
Empirical investigations by D. Anick suggest that τ ( n ) / τ ( n − 1 ) \tau(n)/\tau(n-1) τ ( n ) / τ ( n − 1 ) grows approximately as a + b n + ( − 1 ) n c / n a+bn+(-1)^nc/n a + bn + ( − 1 ) n c / n for some constants a a a , b b b , c c c . If that is true, τ ( n ) = exp ( n ln n − n ln ( e / b ) + O ( log n ) ) \tau(n)=\exp(n\ln n-n\ln(e/b)+O(\log n)) τ ( n ) = exp ( n ln n − n ln ( e / b ) + O ( log n )) . The exact values for n < 30 n<30 n < 30 suggest further that a ≈ 0.19 a\approx0.19 a ≈ 0.19 , b ≈ 0.636 b\approx0.636 b ≈ 0.636 , and c ≈ 0.42 c\approx0.42 c ≈ 0.42 . But rigorous proofs are unknown. (This function τ ( n ) \tau(n) τ ( n ) was introduced by A. Kotzig, who computed it by hand for n ≤ 6 n\le6 n ≤ 6 in 1984.)
Anick’s study appeared in [2 ] .
Results
Throughout, m : = N − 1 m := N - 1 m := N − 1 , Λ : = 1 + log ( N + 1 ) \Lambda:= 1 + \log(N + 1) Λ := 1 + log ( N + 1 ) , and log \log log is the natural logarithm. (The constants a a a , b b b , c c c of the quoted answer appear only here and in § 8 ; elsewhere these letters have local meanings, and c c c usually denotes a number of cycles.) Let W ( N ) W(N) W ( N ) be the number of rainbow maps of order N N N (§ 2 ); it is the permanent of an explicit matrix with entries 0, 1, 2.
Theorem 1.1 (Comparison). For N ≥ 3 N \ge3 N ≥ 3 , τ ( N ) ≤ W ( N ) ≤ τ ( N ) exp ( 151 Λ 4 ) \tau(N) \le W(N) \le\tau(N)\exp(151\Lambda^4) τ ( N ) ≤ W ( N ) ≤ τ ( N ) exp ( 151 Λ 4 ) .
Theorem 1.2 (Size of the Whitty number W ( N ) W(N) W ( N ) ). For N ≥ 3 N \ge3 N ≥ 3 ,
1 7 ( 2 π ) m m ! ≤ W ( N ) ≤ 45 ( 2 π ) m ( m + 3 ) ! , hence ∣ log W ( N ) − ( N log 2 N π − 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. 7 1 ( π 2 ) m m ! ≤ W ( N ) ≤ 45 ( π 2 ) m ( m + 3 )! , hence log W ( N ) − ( N log π 2 N − N ) ≤ 5Λ.
Theorem 1.3 (Main theorem). For every N ≥ 3 N \ge3 N ≥ 3 ,
∣ log τ ( N ) − ( N log 2 N π − N ) ∣ ≤ 152 Λ 4 , \left|\log\tau(N)-\left(N\log\frac{2N}{\pi}-N\right)\right| \le152\Lambda^4, log τ ( N ) − ( N log π 2 N − N ) ≤ 152 Λ 4 , and N log 2 N π − N = N log N − N log e b N\log\frac{2N}{\pi}-N=N\log N-N\log\frac{e}{b} N log π 2 N − N = N log N − N log b e with b = 2 π b=\frac{2}{\pi} b = π 2 . In particular τ ( N ) = N ! ( 2 / π ) N e O ( log 4 N ) \tau(N)=N!(2/\pi)^N e^{O(\log^4 N)} τ ( N ) = N ! ( 2/ π ) N e O ( l o g 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 − 151 Λ 4 ≤ log τ ( N ) − log W ( N ) ≤ 0 , and Theorem 1.2 gives ∣ log W ( N ) − ( N log 2 N π − N ) ∣ ≤ 5 Λ \left|\log W(N)-\left(N\log\frac{2N}{\pi}-N\right)\right| \le5\Lambda log W ( N ) − ( N log π 2 N − N ) ≤ 5Λ . Add them and use 5 Λ ≤ Λ 4 5\Lambda\le\Lambda^4 5Λ ≤ Λ 4 , which holds because Λ ≥ 2.38 \Lambda\ge2.38 Λ ≥ 2.38 for N ≥ 3 N \ge3 N ≥ 3 . The last assertion follows from (3) below.
Section 3 also gives a Motzkin path formula for W ( N ) 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\} { 0 , N } , the only edge of length N N N . Delete this edge and orient every other edge towards whichever of 0 and N N N lies in its component; then every vertex other than 0 and N N N 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) 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) τ ( N ) as the number of spanning trees of the complete graph on { 0 , … , N } \{0,\ldots,N\} { 0 , … , N } with edge lengths 1 , … , N 1,\ldots,N 1 , … , 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. N N N : number of edges, also the order of a rainbow map; m = N − 1 m=N-1 m = N − 1 : number of interior vertices, also the number of available lengths; ρ ( k ) = min ( k , N − k ) \rho(k)=\min(k,N-k) ρ ( k ) = min ( k , N − k ) : the rank of k k k ; R = ⌊ N / 2 ⌋ R=\lfloor N/2\rfloor R = ⌊ N /2 ⌋ ; δ k \delta_k δ k : the length used by k k k ; σ \sigma σ : type; ℓ k \ell_k ℓ k : the upper bound of δ k \delta_k δ k for a given type; c c c : number of cycles; H R = ∑ j ≤ R 1 / j H_R=\sum_{j\le R}1/j H R = ∑ j ≤ R 1/ j ; D = ⌈ log 2 m ⌉ D=\lceil\log_2 m\rceil D = ⌈ log 2 m ⌉ (for N ≥ 2 N\ge2 N ≥ 2 ); Λ = 1 + log ( N + 1 ) \Lambda=1+\log(N+1) Λ = 1 + log ( N + 1 ) ; [ P ] [P] [ P ] is 1 if the statement P P P is true and 0 otherwise.
Rainbow maps
The vertices are 0 , 1 , … , N 0,1,\ldots,N 0 , 1 , … , N . We call 0 0 0 and N N N the ground and 1 , … , m 1,\ldots,m 1 , … , m the interior vertices . The rank of an interior vertex k k k is ρ ( k ) : = min ( k , N − k ) \rho(k) := \min(k,N-k) ρ ( k ) := min ( k , N − k ) , its distance to the nearer end. Each rank is shared by at most two vertices (k k k and N − k N-k N − k ), and there are R : = ⌊ N / 2 ⌋ R := \lfloor N/2\rfloor R := ⌊ N /2 ⌋ ranks.
Definition. A rainbow map of order N N N is a function f : { 1 , … , m } → { 0 , … , N } f:\{1,\ldots,m\}\to\{0,\ldots,N\} f : { 1 , … , m } → { 0 , … , N } such that the numbers ∣ f ( k ) − k ∣ \lvert f(k)-k\rvert ∣ f ( k ) − k ∣ are 1 , … , m 1,\ldots,m 1 , … , m , each exactly once.
The name rainbow map is due to D. E. Knuth (private communication). We call f ( k ) f(k) f ( k ) the target of k k k and δ k : = ∣ f ( k ) − k ∣ \delta_k := \lvert f(k)-k\rvert δ k := ∣ f ( k ) − k ∣ its length . Drawing the arcs k → f ( k ) k\to f(k) k → f ( k ) and the arc 0 → N 0\to N 0 → 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} σ ∈ { L , R } m records the directions: σ k = L \sigma_k=\mathrm{L} σ k = L if and only if f ( k ) < k f(k)<k f ( k ) < k . Given the type, the length of k k k 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. ℓ k := { k , N − k , σ k = L , σ k = R , 1 ≤ δ k ≤ ℓ k .
and f f f is determined by σ \sigma σ and ( δ 1 , … , δ m ) (\delta_1,\ldots,\delta_m) ( δ 1 , … , δ m ) .
Whitty numbers. Let W ( N ) W(N) W ( N ) be the number of rainbow maps of order N N N . If vertex k k k receives length d d d , the number of possible directions is
M k , 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. M k , d := [ d ≤ k ] + [ d ≤ N − k ] ∈ { 0 , 1 , 2 } , 1 ≤ k , d ≤ m .
so that
W ( N ) = ∑ δ ∏ k = 1 m M k , δ k = per M , W(N)=\sum_{\delta}\prod_{k=1}^{m}M_{k,\delta_k}=\operatorname{per} M, W ( N ) = δ ∑ k = 1 ∏ m M k , δ k = per M ,
the sum being over all permutations δ \delta δ of { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } . For $N=6,
M = ( 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 ) 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} M = 2 2 2 2 2 1 2 2 2 1 1 1 2 1 1 1 1 0 1 1 1 0 0 0 1
and W ( 6 ) = 168 W(6)=168 W ( 6 ) = 168 . Rows k k k and N − k N-k N − k are equal, and vertices of small rank can use more lengths. The sequence W ( N ) W(N) W ( N ) begins 1 , 2 , 4 , 12 , 40 , 168 , 784 , 4272 , … 1,2,4,12,40,168,784,4272,\ldots 1 , 2 , 4 , 12 , 40 , 168 , 784 , 4272 , … (N = 1 , 2 , … N=1,2,\ldots N = 1 , 2 , … ); 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) W ( N ) the Whitty numbers .
In the directed graph the two ground vertices are absorbing (apart from 0 → N 0\to N 0 → N ). Let c ( f ) c(f) c ( f ) be the number of directed cycles. Every cycle has at least 3 vertices, because u → v → u u\to v\to u u → v → u would use the length ∣ u − v ∣ \lvert u-v\rvert ∣ u − v ∣ twice.
Lemma 2.1 (cf. [14 Theorem 6 and the remarks before Theorem 7] ). The underlying undirected graph of f f f , together with the edge { 0 , N } \{0,N\} { 0 , N } , is a tree if and only if c ( f ) = 0 c(f)=0 c ( 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) τ ( N ) = # { f : c ( f ) = 0 } ≤ W ( N ) .
Proof. Given a graceful labeling, delete the edge { 0 , N } \{0,N\} { 0 , N } ; the tree splits into two trees containing 0 0 0 and N N N respectively. Orient every edge towards the ground vertex of its tree. Every interior vertex has exactly one outgoing edge and the m m m lengths are 1 , … , m 1,\ldots,m 1 , … , m , so this is an acyclic rainbow map. Conversely, the m m m edges of an acyclic rainbow map together with { 0 , N } \{0,N\} { 0 , N } are N N N edges on N + 1 N+1 N + 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 , … , N 1,\ldots,N 1 , … , 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] τ ( N ) / W ( N ) = Pr [ c = 0 ] for the uniform measure on all rainbow maps of order N N N . Reversing a cycle of a rainbow map gives another rainbow map with the same edges.
Example 2.2. W ( 5 ) = 40 = τ ( 5 ) W(5) = 40 = \tau(5) W ( 5 ) = 40 = τ ( 5 ) . For N = 6 N = 6 N = 6 , W ( 6 ) = 168 W(6) = 168 W ( 6 ) = 168 and τ ( 6 ) = 164 \tau(6) = 164 τ ( 6 ) = 164 ; the four extra rainbow maps each contain a triangle, for example the map of Figure 1 (b). Table 1 lists τ ( N ) \tau(N) τ ( N ) , W ( N ) W(N) W ( N ) and their ratio for N ≤ 30 N \le30 N ≤ 30 .
Figure 1. Two rainbow maps of order 6. Arcs to the right are drawn above the line, arcs to the left below it; the numbers are the lengths, each of 1, . . . , 5 used once. The ground vertices 0 and 6 are shaded. (a) Together with the edge { 0 , 6 } \{0,6\} { 0 , 6 } this is a gracefully labeled tree. (b) A rainbow map with the cycle 1 → 3 → 4 → 1 1 \to3 \to4 \to1 1 → 3 → 4 → 1 .
Types and Ferrers boards
For a given type σ \sigma σ , the set of lengths allowed for vertex k k k is a prefix [ 1 , ℓ k ] [1,\ell_k] [ 1 , ℓ k ] . So the rainbow maps of type σ \sigma σ are the ways to assign the m m m lengths to the m m m rows without repetition, row k k k taking a length in [ 1 , ℓ k ] [1,\ell_k] [ 1 , ℓ k ] ; they are the rook placements on a Ferrers board. Sort the rows as ℓ ( 1 ) ≤ ⋯ ≤ ℓ ( m ) \ell_{(1)} \le\cdots\le\ell_{(m)} ℓ ( 1 ) ≤ ⋯ ≤ ℓ ( m ) . If rooks are placed row by row in this order, all earlier rooks lie in the range of the current row, so
# { f of type σ } = ∏ i = 1 m ( ℓ ( i ) − i + 1 ) (1) \#\{f\text{ of type }\sigma\} = \prod_{i=1}^{m}(\ell_{(i)}-i+1) \tag*{(1)} # { f of type σ } = i = 1 ∏ m ( ℓ ( i ) − i + 1 ) (1)
(which is 0 if some factor is ≤ 0 \le0 ≤ 0 ). A type is feasible if this number is positive. The uniform measure conditioned on a feasible type is the uniform measure on rook placements of its board.
The structure of rainbow maps
This section regroups formula (1) by rank. A type then becomes a lattice path, and W ( N ) W(N) W ( N ) becomes the total weight of a family of weighted Motzkin paths (Theorem 3.1 ). The paths give exact enumerations of types (§ 3.2 ) and are the starting point of the computation of W ( N ) W(N) W ( N ) in § 7 . Only Theorem 3.1 is used later (in § 7 ); the rest of this section, on exact enumerations, on a uniformly random rainbow map of a fixed type, and on a few further statistics, is not needed for the main theorem.
Table 1. τ ( N ) \tau(N) τ ( N ) (from OEIS A033472; recomputed by exhaustive search for N ≤ 12 N \le12 N ≤ 12 ) and W ( N ) W(N) W ( N ) (computed exactly by Theorem 7.5; for N ≤ 15 N \le15 N ≤ 15 in agreement with the terms listed in OEIS A134983).
Pairs and lattice paths
Let R ′ : = ⌊ ( N − 1 ) / 2 ⌋ R' := \lfloor(N-1)/2 \rfloor R ′ := ⌊( N − 1 ) /2 ⌋ . For 1 ≤ r ≤ R ′ 1 \le r \le R' 1 ≤ r ≤ R ′ we pair the two vertices r r r and N − r N-r N − r of rank r r r . Their bounds are r r r or N − r N-r N − r : Vertex r r r pointing left, or vertex N − r N-r N − r pointing right, has the small bound r r r ; vertex r r r pointing right, or vertex N − r N-r N − r pointing left, has the large bound N − r N-r N − r . In other words, an arc with the small bound points to the nearer end, and an arc with the large bound points to the farther end. Let s r ∈ { 0 , 1 , 2 } s_r \in\{0,1,2\} s r ∈ { 0 , 1 , 2 } be the number of vertices of pair r r r with the small bound (s r = 1 s_r=1 s r = 1 arises in two ways). If N N N is even there is also the midpoint N / 2 N/2 N /2 , whose bound is N / 2 N/2 N /2 in both directions. Let
S 0 : = 0 , S r : = s 1 + ⋯ + s r ( 1 ≤ r ≤ R ′ ) , x r : = r − S r − 1 ( 1 ≤ r ≤ R ′ + 1 ) , S_0 := 0,\qquad S_r := s_1+\cdots+s_r\quad(1 \le r \le R'),\qquad x_r := r-S_{r-1}\quad(1 \le r \le R'+1), S 0 := 0 , S r := s 1 + ⋯ + s r ( 1 ≤ r ≤ R ′ ) , x r := r − S r − 1 ( 1 ≤ r ≤ R ′ + 1 ) ,
so that x 1 = 1 x_1=1 x 1 = 1 and x r + 1 = x r + 1 − s r x_{r+1}=x_r+1-s_r x r + 1 = x r + 1 − s r ; the values s r = 0 , 1 , 2 s_r=0,1,2 s r = 0 , 1 , 2 are an up step, a level step and a down step.
Theorem 3.1 (Motzkin paths). The number of rainbow maps of a given type is
∏ r = 1 R ′ w s r ( x r ) × { 1 , N odd , x R ′ + 1 , N even , w 0 ( x ) = x ( x + 1 ) , w 1 ( x ) = x 2 , w 2 ( x ) = x ( x − 1 ) . \prod_{r=1}^{R'} w_{s_r}(x_r)\times
\begin{cases}
1, & N\ \text{odd},\\
x_{R'+1}, & N\ \text{even},
\end{cases}
\qquad
w_0(x)=x(x+1),\quad w_1(x)=x^2,\quad w_2(x)=x(x-1). r = 1 ∏ R ′ w s r ( x r ) × { 1 , x R ′ + 1 , N odd , N even , w 0 ( x ) = x ( x + 1 ) , w 1 ( x ) = x 2 , w 2 ( x ) = x ( x − 1 ) .
Hence W ( N ) W(N) W ( N ) is the total weight of all paths of R ′ R' R ′ steps starting at height x = 1 x=1 x = 1 , where an up step from height x x x has weight x ( x + 1 ) x(x+1) x ( x + 1 ) , a level step 2 x 2 2x^2 2 x 2 , and a down step x ( x − 1 ) x(x-1) x ( x − 1 ) , with an extra factor 2 x R ′ + 1 2x_{R'+1} 2 x R ′ + 1 (twice the final height) when N N N is even.
Proof. Use (1). All small bounds 1 , … , R ′ 1,\ldots,R' 1 , … , R ′ are less than N / 2 N/2 N /2 and all large bounds N − R ′ , … , N − 1 N-R',\ldots,N-1 N − R ′ , … , N − 1 are greater than N / 2 N/2 N /2 . So the sorted order consists of the small bounds by increasing r r r , then the midpoint (if N N N is even), then the large bounds by decreasing r r r . The s r s_r s r rows with small bound r r r occupy positions S r − 1 + 1 , … , S r − 1 + s r S_{r-1}+1,\ldots,S_{r-1}+s_r S r − 1 + 1 , … , S r − 1 + s r , with factors r − ( S r − 1 + j ) + 1 = x r − j + 1 r-(S_{r-1}+j)+1=x_{r-j+1} r − ( S r − 1 + j ) + 1 = x r − j + 1 for j = 1 , … , s r j=1,\ldots,s_r j = 1 , … , s r . Before the 2 − s r 2-s_r 2 − s r rows with large bound N − r N-r N − r come all S R ′ S_{R'} S R ′ small-bound rows, the midpoint row ([ N even ] [N\text{ even}] [ N even ] rows), and ∑ r ′ > r ( 2 − s r ′ ) \sum_{r'>r}(2-s_{r'}) ∑ r ′ > r ( 2 − s r ′ ) large-bound rows. Since S R ′ + ∑ r ′ > r ( 2 − s r ′ ) = S r + 2 ( R ′ − r ) S_{R'}+\sum_{r'>r}(2-s_{r'})=S_r+2(R'-r) S R ′ + ∑ r ′ > r ( 2 − s r ′ ) = S r + 2 ( R ′ − r ) and N − 2 R ′ − [ N even ] = 1 N-2R'-[N\text{ even}]=1 N − 2 R ′ − [ N even ] = 1 , the j j j th such row has factor
( N − r ) − ( S r + 2 ( R ′ − r ) + [ N even ] + j ) + 1 = x r − s r + 2 − j ( j = 1 , … , 2 − s r ) . (N-r)-\left(S_r+2(R'-r)+[N\text{ even}]+j\right)+1=x_r-s_r+2-j \qquad(j=1,\ldots,2-s_r). ( N − r ) − ( S r + 2 ( R ′ − r ) + [ N even ] + j ) + 1 = x r − s r + 2 − j ( j = 1 , … , 2 − s r ) .
Collecting the factors of pair r r r gives x r ( x r + 1 ) x_r(x_r+1) x r ( x r + 1 ) , x r ⋅ x r x_r\cdot x_r x r ⋅ x r , or x r ( x r − 1 ) x_r(x_r-1) x r ( x r − 1 ) for s r = 0 , 1 , 2 s_r=0,1,2 s r = 0 , 1 , 2 . The midpoint is in position S R ′ + 1 S_{R'}+1 S R ′ + 1 , with factor N / 2 − S R ′ = x R ′ + 1 N/2-S_{R'}=x_{R'+1} N /2 − S R ′ = x R ′ + 1 . This proves the first assertion. Summing over types, the two choices for s r = 1 s_r=1 s r = 1 and the two directions of the midpoint each contribute a factor 2.
The height has a direct meaning: The quantity x r − 1 x_r-1 x r − 1 is the number of pairs among the first r − 1 r-1 r − 1 in which both arcs point to the farther end, minus the number of pairs in which both point to the nearer end. A path that reaches height 0 has weight 0, so only Motzkin prefixes (paths staying at height ≥ 1 \geq1 ≥ 1 ) contribute. For example, N = 5 N=5 N = 5 gives R ′ = 2 R'=2 R ′ = 2 , and W ( 5 ) = 2 ⋅ ( 6 + 8 + 2 ) + 2 ⋅ ( 2 + 2 + 0 ) = 40 W(5)=2\cdot(6+8+2)+2\cdot(2+2+0)=40 W ( 5 ) = 2 ⋅ ( 6 + 8 + 2 ) + 2 ⋅ ( 2 + 2 + 0 ) = 40 : The first step is up (weight 2) or level (weight 2), and the brackets are the total weights of the second step from heights 2 and 1.
Exact enumeration of types
Corollary 3.2 (Feasible types). There are exactly ( N ⌊ N / 2 ⌋ ) \binom{N}{\lfloor N/2\rfloor} ( ⌊ N /2 ⌋ N ) feasible types of order N N N .
Proof. By Theorem 3.1 , a type is feasible if and only if x r ≥ 1 x_r\geq1 x r ≥ 1 for 1 ≤ r ≤ R ′ + 1 1\leq r\leq R'+1 1 ≤ r ≤ R ′ + 1 (for s r = 2 s_r=2 s r = 2 , x r ( x r − 1 ) > 0 x_r(x_r-1)>0 x r ( x r − 1 ) > 0 is equivalent to x r + 1 = x r − 1 ≥ 1 x_{r+1}=x_r-1\geq1 x r + 1 = x r − 1 ≥ 1 ). Write + 1 +1 + 1 for each vertex of pair r r r with the large bound and − 1 -1 − 1 for each vertex with the small bound, and list these 2 R ′ 2R' 2 R ′ signs by increasing r r r , vertex r r r before vertex N − r N-r N − r . The partial sums satisfy P 2 r = 2 r − 2 s r = 2 ( x r + 1 − 1 ) P_{2r}=2r-2s_r=2(x_{r+1}-1) P 2 r = 2 r − 2 s r = 2 ( x r + 1 − 1 ) , so feasibility means P 2 r ≥ 0 P_{2r}\geq0 P 2 r ≥ 0 for 1 ≤ r ≤ R ′ 1\leq r\leq R' 1 ≤ r ≤ R ′ . Partial sums with even index are even, so this is
equivalent to all partial sums being ≥ − 1 \ge-1 ≥ − 1 , that is, to the walk prefixed by one step + 1 +1 + 1 staying ≥ 0 \ge0 ≥ 0 . There are ( p ⌊ p / 2 ⌋ ) \binom{p}{\lfloor p/2\rfloor} ( ⌊ p /2 ⌋ p ) walks of length p p p from 0 that stay ≥ 0 \ge0 ≥ 0 , and they all begin with + 1 +1 + 1 . Hence there are ( N R ′ ) \binom{N}{R'} ( R ′ N ) feasible types when N = 2 R ′ + 1 N=2R'+1 N = 2 R ′ + 1 , and 2 ( N − 1 R ′ ) = ( N N / 2 ) 2\binom{N-1}{R'}=\binom{N}{N/2} 2 ( R ′ N − 1 ) = ( N /2 N ) when N = 2 R ′ + 2 N=2R'+2 N = 2 R ′ + 2 , the factor 2 coming from the two directions of the midpoint.
Corollary 3.3 (The largest type). The types in which every arc points to the farther end (s r ≡ 0 s_r\equiv0 s r ≡ 0 , the midpoint in either direction) have the most rainbow maps: R ! ( R + 1 ) ! R!(R+1)! R ! ( R + 1 )! if N = 2 R + 1 N=2R+1 N = 2 R + 1 , and ( R ! ) 2 (R!)^2 ( R ! ) 2 if N = 2 R N=2R N = 2 R .
Proof. The two possible bounds of k k k are k k k and N − k N-k N − k , and this type takes the larger one; so its board contains, row by row, the board of any type, and the number of rook placements is monotone under inclusion. The value follows from Theorem 3.1 with x r = r x_r=r x r = r .
For N = 6 N=6 N = 6 these types are RRLLL and RRRLL, with 36 = ( 3 ! ) 2 36=(3!)^2 36 = ( 3 ! ) 2 rainbow maps each; the first is the type of Figure 2 .
Figure 2. The board of type RRLLL for N = 6 N=6 N = 6 : Row k k k is vertex k k k , and its shaded cells are the allowed lengths 1 , … , ℓ k 1,\ldots,\ell_k 1 , … , ℓ k . The dots show the rainbow map ( δ 1 , … , δ 5 ) = ( 3 , 4 , 1 , 2 , 5 ) (\delta_1,\ldots,\delta_5)=(3,4,1,2,5) ( δ 1 , … , δ 5 ) = ( 3 , 4 , 1 , 2 , 5 ) . Sorting the rows by ℓ \ell ℓ (vertices 3, 2, 4, 1, 5) gives a Ferrers diagram; row by row the numbers of choices are 3 3 3 , 4 − 1 4-1 4 − 1 , 4 − 2 4-2 4 − 2 , 5 − 3 5-3 5 − 3 , 5 − 4 5-4 5 − 4 , so this board carries 3 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 = 36 3\cdot3\cdot2\cdot2\cdot1=36 3 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 = 36 rainbow maps.
Corollary 3.4 (Types with a single rainbow map). Exactly 2 R 2^R 2 R types have a single rainbow map. In each of these maps every interior vertex points directly to the ground (f ( k ) ∈ { 0 , N } f(k)\in\{0,N\} f ( k ) ∈ { 0 , N } ).
Proof. The factors are positive integers, so their product is 1 only if each factor is 1. This forces s r = 1 s_r=1 s r = 1 for every pair (w 0 ( x ) ≥ 2 w_0(x)\ge2 w 0 ( x ) ≥ 2 ; w 2 ( x ) > 0 w_2(x)>0 w 2 ( x ) > 0 needs x ≥ 2 x\ge2 x ≥ 2 , and then w 2 ( x ) ≥ 2 w_2(x)\ge2 w 2 ( x ) ≥ 2 ; w 1 ( x ) = 1 w_1(x)=1 w 1 ( x ) = 1 needs x = 1 x=1 x = 1 ), so x r ≡ 1 x_r\equiv1 x r ≡ 1 and the midpoint factor is 1. There are 2 choices per pair and, if N N N is even, 2 directions of the midpoint, giving 2 R ′ ⋅ 2 [ N even ] = 2 R 2^{R'}\cdot2^{[N\text{ even}]}=2^R 2 R ′ ⋅ 2 [ N even ] = 2 R types. The sorted bounds are then exactly 1 , … , m 1,\ldots,m 1 , … , m , and the only placement is δ k = ℓ k \delta_k=\ell_k δ k = ℓ k .
Corollary 3.5 (One arc to the left). Exactly ⌊ 2 N / 3 ⌋ \lfloor2^N/3\rfloor ⌊ 2 N /3 ⌋ rainbow maps of order N N N have exactly one arc pointing left.
Proof. Let k k k be the vertex pointing left. The multiset of bounds is { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } with N − k N-k N − k replaced by k k k . If k < N / 2 k<N/2 k < N /2 , the bound k k k occurs twice and k + 1 k+1 k + 1 bounds are ≤ k \le k ≤ k , so the type is infeasible. If k = N / 2 k=N/2 k = N /2 the bounds are unchanged and there is one rainbow map. If k > N / 2 k>N/2 k > N /2 , the sorted bounds are 1 , … , N − k − 1 , N − k + 1 , … , k − 1 , k , k , k + 1 , … , N − 1 1,\ldots,N-k-1,N-k+1,\ldots,k-1,k,k,k+1,\ldots,N-1 1 , … , N − k − 1 , N − k + 1 , … , k − 1 , k , k , k + 1 , … , N − 1 ; the rows in sorted positions N − k , … , k − 1 N-k,\ldots,k-1 N − k , … , k − 1 have factor 2 and the others factor 1, giving 2 2 k − N 2^{2k-N} 2 2 k − N . Summing, 2 + 2 3 + ⋯ + 2 N − 2 = ( 2 N − 2 ) / 3 2+2^3+\cdots+2^{N-2}=(2^N-2)/3 2 + 2 3 + ⋯ + 2 N − 2 = ( 2 N − 2 ) /3 for odd N N N and 1 + 2 2 + ⋯ + 2 N − 2 = ( 2 N − 1 ) / 3 1+2^2+\cdots+2^{N-2}=(2^N-1)/3 1 + 2 2 + ⋯ + 2 N − 2 = ( 2 N − 1 ) /3 for even N N N .
The distribution of one row
Fix a feasible board ℓ = ( ℓ 1 , … , ℓ m ) \ell=(\ell_1,\ldots,\ell_m) ℓ = ( ℓ 1 , … , ℓ m ) and take a uniform rook placement on it. For a row r r r and an integer x x x let
u r ( x ) : = x − # { s ≠ r : ℓ s ≤ x } , u_r(x):=x-\#\{s\ne r:\ell_s\le x\}, u r ( x ) := x − # { s = r : ℓ s ≤ x } ,
the factor that row r r r would receive in (1) if its bound were changed to x x x and it were placed last among the rows with bound x x x . Formula (1) remains valid for any order of rows that is compatible with the order of the bounds, and it describes a sampling procedure: In such an order, each row chooses uniformly among its remaining lengths.
Lemma 3.6 (Hazard rate). Let ℓ r = x + 1 \ell_r=x+1 ℓ r = x + 1 and u = u r ( x ) u=u_r(x) u = u r ( x ) . Then Pr [ δ r = x + 1 ] = 1 u + 1 \Pr[\delta_r=x+1]=\frac{1}{u+1} Pr [ δ r = x + 1 ] = u + 1 1 ; and if u > 0 u>0 u > 0 , then conditioned on δ r ≤ x \delta_r\le x δ r ≤ x the placement is uniform on the board with ℓ r \ell_r ℓ r changed to $x.
Proof. Place first the other rows with bound ≤ x \le x ≤ x , then row r r r , then the remaining rows; this order is compatible with the bounds. When row r r r is placed, the earlier rows occupy # { s ≠ r : ℓ s ≤ x } \#\{s \ne r : \ell_s \le x\} # { s = r : ℓ s ≤ x } lengths, all ≤ x \le x ≤ x , so row r r r chooses uniformly among the u u u remaining lengths in [ 1 , x ] [1,x] [ 1 , x ] and the length x + 1 x+1 x + 1 , whatever the earlier choices were. The placements with δ r ≤ x \delta_r \le x δ r ≤ x are exactly the placements of the modified board.
Theorem 3.7 (One-row marginal). For every row r r r and every integer a a a with 0 ≤ a ≤ ℓ r 0 \le a \le\ell_r 0 ≤ a ≤ ℓ r ,
Pr [ δ r ≤ a ] = ∏ x = a ℓ r − 1 u r ( x ) u r ( x ) + 1 . \Pr[\delta_r \le a] = \prod_{x=a}^{\ell_r-1} \frac{u_r(x)}{u_r(x)+1}. Pr [ δ r ≤ a ] = x = a ∏ ℓ r − 1 u r ( x ) + 1 u r ( x ) . In particular, Pr [ δ r = d ] \Pr[\delta_r=d] Pr [ δ r = d ] is constant for d d d in every interval ( a , b ] ⊆ ( 0 , ℓ r ] (a,b] \subseteq(0,\ell_r] ( a , b ] ⊆ ( 0 , ℓ r ] that contains no bound of another row.
Proof. If u r ( x ) = 0 u_r(x)=0 u r ( x ) = 0 for some x x x with a ≤ x < ℓ r a \le x < \ell_r a ≤ x < ℓ r , the rows s ≠ r s \ne r s = r with ℓ s ≤ x \ell_s \le x ℓ s ≤ x use all the lengths $1,\ldots,x$, so Pr [ δ r ≤ a ] = 0 \Pr[\delta_r \le a]=0 Pr [ δ r ≤ a ] = 0 and both sides vanish. Otherwise write Pr [ δ r ≤ a ] = ∏ x = a ℓ r − 1 Pr [ δ r ≤ x ∣ δ r ≤ x + 1 ] \Pr[\delta_r \le a]=\prod_{x=a}^{\ell_r-1}\Pr[\delta_r \le x\mid\delta_r \le x+1] Pr [ δ r ≤ a ] = ∏ x = a ℓ r − 1 Pr [ δ r ≤ x ∣ δ r ≤ x + 1 ] , where every event δ r ≤ x + 1 \delta_r \le x+1 δ r ≤ x + 1 has positive probability by induction on ℓ r − x \ell_r-x ℓ r − x , and apply Lemma 3.6 to each factor; by the second assertion of the lemma, the law given δ r ≤ x + 1 \delta_r \le x+1 δ r ≤ x + 1 is uniform on the board with ℓ r \ell_r ℓ r replaced by $x+1 and the other bounds unchanged. If no other row has its bound in ( a , b ] (a,b] ( a , b ] , then u r ( x ) u_r(x) u r ( x ) increases by one at each step on [ a , b ] [a,b] [ a , b ] , the product telescopes, and Pr [ δ r ≤ x ] = Pr [ δ r ≤ b ] u r ( x ) / u r ( b ) \Pr[\delta_r \le x]=\Pr[\delta_r \le b]\,u_r(x)/u_r(b) Pr [ δ r ≤ x ] = Pr [ δ r ≤ b ] u r ( x ) / u r ( b ) for a ≤ x ≤ b a \le x \le b a ≤ x ≤ b .
Corollary 3.8 (One row of the largest type). On the type of Corollary 3.3, let k k k have rank ρ \rho ρ and recall R = ⌊ N / 2 ⌋ R=\lfloor N/2\rfloor R = ⌊ N /2 ⌋ . Then
Pr [ δ k ≤ d ] = ρ N − d , Pr [ δ k = d ] = ρ ( N − d ) ( N − d + 1 ) ( R < d ≤ N − ρ ) , \Pr[\delta_k \le d] = \frac{\rho}{N-d}, \qquad\Pr[\delta_k=d] = \frac{\rho}{(N-d)(N-d+1)} \qquad(R<d\le N-\rho), Pr [ δ k ≤ d ] = N − d ρ , Pr [ δ k = d ] = ( N − d ) ( N − d + 1 ) ρ ( R < d ≤ N − ρ ) , and on an initial range of lengths the probabilities are constant: Pr [ δ k = d ] = ρ R ( R + 1 ) \Pr[\delta_k=d]=\frac{\rho}{R(R+1)} Pr [ δ k = d ] = R ( R + 1 ) ρ for d ≤ R + 1 d\le R+1 d ≤ R + 1 if N = 2 R + 1 N=2R+1 N = 2 R + 1 , and Pr [ δ k = d ] = ρ R 2 \Pr[\delta_k=d]=\frac{\rho}{R^2} Pr [ δ k = d ] = R 2 ρ for d ≤ R d\le R d ≤ R if N = 2 R N=2R N = 2 R and k ≠ R k\ne R k = R . If N = 2 R N=2R N = 2 R , the midpoint has δ R \delta_R δ R uniform on { 1 , … , R } \{1,\ldots,R\} { 1 , … , R } .
Proof. Let N = 2 R + 1 N=2R+1 N = 2 R + 1 . Each bound v ∈ { R + 1 , … , 2 R } v\in\{R+1,\ldots,2R\} v ∈ { R + 1 , … , 2 R } occurs twice (vertices v v v and N − v N-v N − v ). Row k k k has bound ℓ k = N − ρ \ell_k=N-\rho ℓ k = N − ρ , so u k ( x ) = x u_k(x)=x u k ( x ) = x for x ≤ R x\le R x ≤ R and u k ( x ) = x − 2 ( x − R ) = 2 R − x u_k(x)=x-2(x-R)=2R-x u k ( x ) = x − 2 ( x − R ) = 2 R − x for R + 1 ≤ x ≤ ℓ k − 1 R+1\le x\le\ell_k-1 R + 1 ≤ x ≤ ℓ k − 1 . By Theorem 3.7, Pr [ δ k ≤ a ] = ∏ x = a ℓ k − 1 2 R − x 2 R − x + 1 = 2 R − ℓ k + 1 2 R − a + 1 = ρ N − a \Pr[\delta_k\le a]=\prod_{x=a}^{\ell_k-1}\frac{2R-x}{2R-x+1}=\frac{2R-\ell_k+1}{2R-a+1}=\frac{\rho}{N-a} Pr [ δ k ≤ a ] = ∏ x = a ℓ k − 1 2 R − x + 1 2 R − x = 2 R − a + 1 2 R − ℓ k + 1 = N − a ρ for R + 1 ≤ a ≤ ℓ k R+1\le a\le\ell_k R + 1 ≤ a ≤ ℓ k , and Pr [ δ k ≤ a ] = ρ R + 1 ⋅ a R \Pr[\delta_k\le a]=\frac{\rho}{R+1}\cdot\frac{a}{R} Pr [ δ k ≤ a ] = R + 1 ρ ⋅ R a for a ≤ R a\le R a ≤ R . For N = 2 R N=2R N = 2 R and k ≠ R k\ne R k = R , the bounds R + 1 , … , 2 R − 1 R+1,\ldots,2R-1 R + 1 , … , 2 R − 1 occur twice and R R R once (the midpoint), so u k ( x ) = x u_k(x)=x u k ( x ) = x for x < R x<R x < R , u k ( R ) = R − 1 u_k(R)=R-1 u k ( R ) = R − 1 , and u k ( x ) = 2 R − 1 − x u_k(x)=2R-1-x u k ( x ) = 2 R − 1 − x for R < x < ℓ k R<x<\ell_k R < x < ℓ k . Hence Pr [ δ k ≤ a ] = ρ N − a \Pr[\delta_k\le a]=\frac{\rho}{N-a} Pr [ δ k ≤ a ] = N − a ρ for R + 1 ≤ a ≤ ℓ k R+1\le a\le\ell_k R + 1 ≤ a ≤ ℓ k , then Pr [ δ k ≤ R ] = ρ R 2 ⋅ R − 1 R = ρ R \Pr[\delta_k\le R]=\frac{\rho}{R^2}\cdot\frac{R-1}{R}=\frac{\rho}{R} Pr [ δ k ≤ R ] = R 2 ρ ⋅ R R − 1 = R ρ , and Pr [ δ k ≤ a ] = ρ a R 2 \Pr[\delta_k\le a]=\frac{\rho a}{R^2} Pr [ δ k ≤ a ] = R 2 ρ a for a ≤ R a\le R a ≤ R . All bounds other than the midpoint’s exceed R R R , so u R ( x ) = x u_R(x)=x u R ( x ) = x and δ R \delta_R δ R is uniform.
For example, on the board of Figure 2 the length δ 1 \delta_1 δ 1 takes the values 1 , … , 5 1,\ldots,5 1 , … , 5 with probabilities 1 9 , 1 9 , 1 9 , 1 6 , 1 2 \frac{1}{9},\frac{1}{9},\frac{1}{9},\frac{1}{6},\frac{1}{2} 9 1 , 9 1 , 9 1 , 6 1 , 2 1 .
Negative dependence
Theorem 3.9 (Negative dependence). Take a uniform rook placement on a feasible board. Let I , J I,J I , J be disjoint sets of rows and fix an integer vector a \boldsymbol{a} a (all thresholds below are integers, and inequalities between vectors are coordinatewise). Then Pr [ δ I ≤ a I ∣ δ J ≤ a J ] \Pr[\delta_I\le a_I\mid\delta_J\le a_J] Pr [ δ I ≤ a I ∣ δ J ≤ a J ] is nondecreasing in each a j a_j a j (wherever the conditional probability is defined). Consequently
Pr [ δ I ≤ a I , δ J ≤ b J ] ≤ Pr [ δ I ≤ a I ] Pr [ δ J ≤ b J ] , \Pr[\delta_I\le a_I,\ \delta_J\le b_J]\le\Pr[\delta_I\le a_I]\Pr[\delta_J\le b_J], Pr [ δ I ≤ a I , δ J ≤ b J ] ≤ Pr [ δ I ≤ a I ] Pr [ δ J ≤ b J ] , and Cov ( ϕ 1 ( δ i ) , ϕ 2 ( δ j ) ) ≤ 0 \operatorname{Cov}(\phi_1(\delta_i),\phi_2(\delta_j))\le0 Cov ( ϕ 1 ( δ i ) , ϕ 2 ( δ j )) ≤ 0 for any two rows i ≠ j i\ne j i = j and any nondecreasing functions ϕ 1 , ϕ 2 \phi_1,\phi_2 ϕ 1 , ϕ 2 .
Proof. Conditioning on δ J ≤ y J \delta_J \le y_J δ J ≤ y J gives the uniform measure on the board with ℓ j \ell_j ℓ j replaced by min ( y j , ℓ j ) \min(y_j,\ell_j) min ( y j , ℓ j ) (j ∈ J j \in J j ∈ J ), again a Ferrers board. For I = { i } I=\{i\} I = { i } , Theorem 3.7 expresses the conditional probability as a product of factors u u + 1 \frac{u}{u+1} u + 1 u with u = x − # { s ∉ J , s ≠ i : ℓ s ≤ x } − # { j ∈ J : min ( y j , ℓ j ) ≤ x } u=x-\#\{s\notin J,s\ne i:\ell_s\le x\}-\#\{j\in J:\min(y_j,\ell_j)\le x\} u = x − # { s ∈ / J , s = i : ℓ s ≤ x } − # { j ∈ J : min ( y j , ℓ j ) ≤ x } ; each u u u is nondecreasing in each y j y_j y j , hence so is the product. For larger I I I use the chain rule: The p p p th factor is the one-row case on the board in which J J J is cut at y J y_J y J and i 1 , … , i p − 1 i_1,\ldots,i_{p-1} i 1 , … , i p − 1 are cut at a a a . When comparing y J ≤ y J ′ y_J\le y'_J y J ≤ y J ′ we may assume that the conditional probability at y J y_J y J is positive (otherwise there is nothing to prove); then every intermediate conditioning event has positive probability at y J y_J y J , hence also at y J ′ y'_J y J ′ , and the one-row case applies factor by factor. Feasibility is preserved when y y y increases (Hall’s condition becomes weaker), so the domain is an up-set. The inequality compares y J = b J y_J=b_J y J = b J with y J = ℓ J y_J=\ell_J y J = ℓ J . For two rows this is negative quadrant dependence, and Hoeffding’s identity
Cov ( ϕ 1 ( X ) , ϕ 2 ( Y ) ) = ∑ a , b Δ ϕ 1 ( a ) Δ ϕ 2 ( b ) [ Pr ( X ≤ a , Y ≤ b ) − Pr ( X ≤ a ) Pr ( Y ≤ b ) ] \operatorname{Cov}(\phi_1(X),\phi_2(Y))=\sum_{a,b}\Delta\phi_1(a)\Delta\phi_2(b)\left[\Pr(X\le a,Y\le b)-\Pr(X\le a)\Pr(Y\le b)\right] Cov ( ϕ 1 ( X ) , ϕ 2 ( Y )) = a , b ∑ Δ ϕ 1 ( a ) Δ ϕ 2 ( b ) [ Pr ( X ≤ a , Y ≤ b ) − Pr ( X ≤ a ) Pr ( Y ≤ b ) ]
with Δ ϕ ( a ) : = ϕ ( a + 1 ) − ϕ ( a ) \Delta\phi(a):=\phi(a+1)-\phi(a) Δ ϕ ( a ) := ϕ ( a + 1 ) − ϕ ( a ) , gives the last assertion. □
Equality can also be described. Call t t t a full column if # { s : ℓ s ≤ t } = t \#\{s:\ell_s\le t\}=t # { s : ℓ s ≤ t } = t ; full columns cut the board into independent blocks. The covariance of δ i \delta_i δ i and δ j \delta_j δ j vanishes if and only if one of the two rows is constant or some full column t t t satisfies min ( ℓ i , ℓ j ) ≤ t < max ( ℓ i , ℓ j ) \min(\ell_i,\ell_j)\le t<\max(\ell_i,\ell_j) min ( ℓ i , ℓ j ) ≤ t < max ( ℓ i , ℓ j ) ; otherwise it is strictly negative. (For strictness, let ℓ i ≤ ℓ j \ell_i\le\ell_j ℓ i ≤ ℓ j , a : = ℓ i − 1 a:=\ell_i-1 a := ℓ i − 1 and U : = u i ( a ) U:=u_i(a) U := u i ( a ) ; then U ≥ 1 U\ge1 U ≥ 1 since row i i i is not constant. By Lemma 3.6 , Pr [ δ i ≤ a ] = U U + 1 \Pr[\delta_i\le a]=\frac{U}{U+1} Pr [ δ i ≤ a ] = U + 1 U , while on the board with ℓ j \ell_j ℓ j cut to a a a the same lemma gives Pr [ δ i ≤ a ∣ δ j ≤ a ] = U − 1 U \Pr[\delta_i\le a\mid\delta_j\le a]=\frac{U-1}{U} Pr [ δ i ≤ a ∣ δ j ≤ a ] = U U − 1 . Here Pr [ δ j ≤ a ] > 0 \Pr[\delta_j\le a]>0 Pr [ δ j ≤ a ] > 0 , since otherwise there would be a full column t t t with ℓ i − 1 ≤ t < ℓ j \ell_i-1\le t<\ell_j ℓ i − 1 ≤ t < ℓ j , and t = ℓ i − 1 t=\ell_i-1 t = ℓ i − 1 would make row i i i constant. So the term ( a , a ) (a,a) ( a , a ) of Hoeffding’s sum is strictly negative, and the other terms are ≤ 0 \le0 ≤ 0 .)
For the uniform measure on all rainbow maps, a mixture over types, the quadrant form of Theorem 3.9 fails: For N = 6 N=6 N = 6 , Pr [ δ 1 ≤ 3 , δ 3 ≤ 2 ] = 1 6 > Pr [ δ 1 ≤ 3 ] Pr [ δ 3 ≤ 2 ] = 143 882 \Pr[\delta_1\le3,\delta_3\le2]=\frac{1}{6}>\Pr[\delta_1\le3]\Pr[\delta_3\le2]=\frac{143}{882} Pr [ δ 1 ≤ 3 , δ 3 ≤ 2 ] = 6 1 > Pr [ δ 1 ≤ 3 ] Pr [ δ 3 ≤ 2 ] = 882 143 . Exact computation shows Cov ( δ i , δ j ) < 0 \operatorname{Cov}(\delta_i,\delta_j)<0 Cov ( δ i , δ j ) < 0 for every pair i < j i<j i < j when N ≤ 13 N\le13 N ≤ 13 ; we have no proof in general.
The number of arcs pointing left
Theorem 3.10. Choose f f f uniformly among the W ( N ) W(N) W ( N ) rainbow maps of order N N N ; let L ( f ) L(f) L ( f ) be the number of arcs pointing left and κ \kappa κ the number of level steps of its path (§ 3.1 ), so that paths are weighted as in Theorem 3.1 . Given the path ( s 1 , … , s R ′ ) (s_1,\ldots,s_{R'}) ( s 1 , … , s R ′ ) ,
L = ( R ′ − κ ) + 2 B + [ N e v e n ] B ′ , B ∼ Bin ( κ , 1 2 ) , B ′ ∼ Bernoulli ( 1 2 ) , independent . L=(R'-\kappa)+2B+[N\ \mathrm{even}]B',\qquad B\sim\operatorname{Bin}\left(\kappa,\frac{1}{2}\right),\quad B'\sim\operatorname{Bernoulli}\left(\frac{1}{2}\right),\quad\text{independent}. L = ( R ′ − κ ) + 2 B + [ N even ] B ′ , B ∼ Bin ( κ , 2 1 ) , B ′ ∼ Bernoulli ( 2 1 ) , independent . Hence E L = N − 1 2 \mathbb{E}L=\frac{N-1}{2} E L = 2 N − 1 and Var L = E κ + 1 4 [ N e v e n ] \operatorname{Var}L=\mathbb{E}\kappa+\frac{1}{4}[N\ \mathrm{even}] Var L = E κ + 4 1 [ N even ] .
Proof. A pair with s r = 0 s_r=0 s r = 0 is ( r , R ) , ( N − r , L ) (r,\mathrm{R}),(N-r,\mathrm{L}) ( r , R ) , ( N − r , L ) and a pair with s r = 2 s_r=2 s r = 2 is ( r , L ) , ( N − r , R ) (r,\mathrm{L}),(N-r,\mathrm{R}) ( r , L ) , ( N − r , R ) ; each has one arc pointing left. A level pair is ( r , L ) , ( N − r , L ) (r,\mathrm{L}),(N-r,\mathrm{L}) ( r , L ) , ( N − r , L ) or ( r , R ) , ( N − r , R ) (r,\mathrm{R}),(N-r,\mathrm{R}) ( r , R ) , ( N − r , R ) , with two or zero arcs pointing left. Given the path, all types have the same multiset of bounds and hence, by Theorem 3.1 , the same number of rainbow maps; so the choices in the level pairs and at the midpoint are independent fair coins. Since E [ L ∣ path ] = N − 1 2 \mathbb{E}[L\mid\text{path}]=\frac{N-1}{2} E [ L ∣ path ] = 2 N − 1 is constant, the variance follows from the law of total variance. □
Corollary 3.11. For N ≥ 2 N\ge2 N ≥ 2 , ∑ f z L ( f ) \sum_f z^{L(f)} ∑ f z L ( f ) is a palindromic polynomial of degree N − 1 N-1 N − 1 that vanishes at z = − 1 z=-1 z = − 1 . The number A 2 ( N ) A_2(N) A 2 ( N ) of rainbow maps with exactly two arcs pointing left is given by
90 A 2 ( N ) = { 3 N + 2 − 16 ⋅ 2 N − 15 N + 20 , N odd , 3 N + 2 − 14 ⋅ 2 N − 15 N + 5 , N even . 90A_2(N)=
\begin{cases}
3^{N+2}-16\cdot2^N-15N+20, & N\ \text{odd},\\
3^{N+2}-14\cdot2^N-15N+5, & N\ \text{even}.
\end{cases} 90 A 2 ( N ) = { 3 N + 2 − 16 ⋅ 2 N − 15 N + 20 , 3 N + 2 − 14 ⋅ 2 N − 15 N + 5 , N odd , N even .
Proof. By Theorem 3.10 , the generating function is z R ′ ( 1 + z ) [ N e v e n ] z^{R'}(1+z)^{[N\ \mathrm{even}]} z R ′ ( 1 + z ) [ N even ] times the total weight of the paths in which the level weight 2 x 2 2x^2 2 x 2 is replaced by ( z + z − 1 ) x 2 (z+z^{-1})x^2 ( z + z − 1 ) x 2 and the final factor 2 x R ′ + 1 2x_{R'+1} 2 x R ′ + 1 by x R ′ + 1 x_{R'+1} x R ′ + 1 ; so it is palindromic. It vanishes at z = − 1 z=-1 z = − 1 because of an involution that changes the parity of L L L : If k k k is the vertex of length 1, replace f ( k ) = k + 1 f(k)=k+1 f ( k ) = k + 1 by f ( k ) = k − 1 f(k)=k-1 f ( k ) = k − 1 and vice versa (both targets lie in [ 0 , N ] [0,N] [ 0 , N ] , and all lengths are unchanged). For A 2 A_2 A 2 , the first step that is not level must be up, since a down step from height 1 has weight 0. For N = 2 R ′ + 1 N=2R'+1 N = 2 R ′ + 1 , either all steps are level (height 1 throughout) and exactly one level pair has two left arcs (R ′ R' R ′ ways), or there are exactly two non-level steps r 1 < r 2 r_1<r_2 r 1 < r 2 : The first is up (weight 1 ⋅ 2 1\cdot2 1 ⋅ 2 ), the steps between are level at height 2 (weight 4 each), and the second is up (2 ⋅ 3 2\cdot3 2 ⋅ 3 , then 9 per step) or down (2 ⋅ 1 2\cdot1 2 ⋅ 1 , then 1 per step). Thus A 2 = R ′ + ∑ r 1 < r 2 2 ⋅ 4 r 2 − r 1 − 1 ( 6 ⋅ 9 R ′ − r 2 + 2 ) A_2=R'+\sum_{r_1<r_2}2\cdot4^{r_2-r_1-1}(6\cdot9^{R'-r_2}+2) A 2 = R ′ + ∑ r 1 < r 2 2 ⋅ 4 r 2 − r 1 − 1 ( 6 ⋅ 9 R ′ − r 2 + 2 ) . For N = 2 R ′ + 2 N=2R'+2 N = 2 R ′ + 2 the midpoint contributes the factor x R ′ + 1 x_{R'+1} x R ′ + 1 if it points right and one more left arc if it points left, so A 2 = R ′ + ∑ r 1 < r 2 2 ⋅ 4 r 2 − r 1 − 1 ( 18 ⋅ 9 R ′ − r 2 + 2 ) + ∑ r = 1 R ′ 4 ⋅ 4 R ′ − r A_2=R'+\sum_{r_1<r_2}2\cdot4^{r_2-r_1-1}(18\cdot9^{R'-r_2}+2)+\sum_{r=1}^{R'}4\cdot4^{R'-r} A 2 = R ′ + ∑ r 1 < r 2 2 ⋅ 4 r 2 − r 1 − 1 ( 18 ⋅ 9 R ′ − r 2 + 2 ) + ∑ r = 1 R ′ 4 ⋅ 4 R ′ − r , the last sum counting the paths with a single non-level step r r r (up) and the midpoint pointing left. Summing the geometric series gives the formulas.
Vertices that reach the ground
How few interior vertices can have their orbit k → f ( k ) → ⋯ k\to f(k)\to\cdots k → f ( k ) → ⋯ reach the ground, the others all flowing into cycles?
Theorem 3.12. For N ≥ 3 N\geq3 N ≥ 3 every rainbow map has at least two interior vertices that reach the ground. For N ≥ 6 N\geq6 N ≥ 6 this is attained by
f ( 1 ) = N , f ( k ) = N − 1 ( 2 ≤ k ≤ N − 4 ) , f ( N − 3 ) = N − 4 , f ( N − 2 ) = 0 , f ( N − 1 ) = N − 3 , \begin{aligned}
f(1)&=N, & f(k)&=N-1 \quad(2\leq k\leq N-4),\\
f(N-3)&=N-4, & f(N-2)&=0, & f(N-1)&=N-3,
\end{aligned} f ( 1 ) f ( N − 3 ) = N , = N − 4 , f ( k ) f ( N − 2 ) = N − 1 ( 2 ≤ k ≤ N − 4 ) , = 0 , f ( N − 1 ) = N − 3 , in which only 1 and N − 2 N-2 N − 2 reach the ground. For N = 3 , 4 , 5 N=3,4,5 N = 3 , 4 , 5 the minimum is N − 1 N-1 N − 1 .
Proof. The map f ↦ f ˉ f\mapsto\bar f f ↦ f ˉ , f ˉ ( k ) : = N − f ( N − k ) \bar f(k):=N-f(N-k) f ˉ ( k ) := N − f ( N − k ) , is a bijection on rainbow maps of order N N N that sends the vertices reaching the ground to their mirror images; so we may assume that the arc of length N − 1 N-1 N − 1 is 1 → N 1\to N 1 → N (the only alternative is N − 1 → 0 N-1\to0 N − 1 → 0 ). The arc of length N − 2 N-2 N − 2 is one of 1 → N − 1 1\to N-1 1 → N − 1 , 2 → N 2\to N 2 → N , N − 2 → 0 N-2\to0 N − 2 → 0 , N − 1 → 1 N-1\to1 N − 1 → 1 . An arc starting at 1 is impossible, since vertex 1 already has its arc; in each remaining case the starting vertex differs from 1 and reaches the ground (N − 1 → 1 → N N-1\to1\to N N − 1 → 1 → N ). In the construction the lengths are N − 1 N-1 N − 1 (vertex 1), N − 1 − k N-1-k N − 1 − k for 2 ≤ k ≤ N − 4 2\leq k\leq N-4 2 ≤ k ≤ N − 4 (giving 3 , … , N − 3 3,\ldots,N-3 3 , … , N − 3 ), then 1, N − 2 N-2 N − 2 , 2. Since N − 4 ≥ 2 N-4\geq2 N − 4 ≥ 2 , we have N − 4 → N − 1 N-4\to N-1 N − 4 → N − 1 , so N − 1 → N − 3 → N − 4 → N − 1 N-1\to N-3\to N-4\to N-1 N − 1 → N − 3 → N − 4 → N − 1 is a triangle, and every vertex in [ 2 , N − 4 ] [2,N-4] [ 2 , N − 4 ] points into it. For N ≤ 5 N\leq5 N ≤ 5 we have W ( N ) = τ ( N ) W(N)=\tau(N) W ( N ) = τ ( N ) (Table 1), so there are no cycles.
The bijection f ↦ f ˉ f\mapsto\bar f f ↦ f ˉ has no fixed points for N ≥ 3 N\geq3 N ≥ 3 (a fixed point would need δ k = δ N − k \delta_k=\delta_{N-k} δ k = δ N − k ). Hence W ( N ) W(N) W ( N ) is even, and for each d d d the arc of length d d d points left in exactly half of the rainbow maps.
Graceful trees in which vertex 0 has large degree
Proposition 3.13. Let deg 0 \deg0 deg 0 be the degree of vertex 0 (including the edge ${0,N}). There is 1 graceful tree with deg 0 = N \deg0=N deg 0 = N , there are ⌊ N / 2 ⌋ \lfloor N/2\rfloor ⌊ N /2 ⌋ with deg 0 = N − 1 \deg0=N-1 deg 0 = N − 1 , and for N ≥ 2 N\geq2 N ≥ 2 there are 1 8 N ( N − 2 ) \frac{1}{8}N(N-2) 8 1 N ( N − 2 ) (N N N even) or 1 8 ( 5 N − 7 ) ( N − 1 ) \frac{1}{8}(5N-7)(N-1) 8 1 ( 5 N − 7 ) ( N − 1 ) (N N N odd) with deg 0 = N − 2 \deg0=N-2 deg 0 = N − 2 .
Proof. If deg 0 = N − 1 \deg0=N-1 deg 0 = N − 1 , vertex 0 misses exactly one v v v ; the edge of length v v v avoids 0, so it is { v , 2 v } \{v,2v\} { v , 2 v } with 2 v ≤ N 2v\leq N 2 v ≤ N . If deg 0 = N − 2 \deg0=N-2 deg 0 = N − 2 , vertex 0 misses x < y x<y x < y (y < N y<N y < N ), and the two remaining edges have lengths x x x and y y y . If { x , y } \{x,y\} { x , y } is not an edge, then x x x and y y y hang on neighbors of 0 0 0 : If the edge at x x x has length x x x and the edge at y y y has length y y y , the neighbors are 2 x 2x 2 x and 2 y 2y 2 y (requiring 2 y ≤ N 2y \le N 2 y ≤ N and 2 x ≠ y 2x \ne y 2 x = y ); if the lengths are exchanged, the neighbors are x + y x+y x + y and y ± x y \pm x y ± x (requiring x + y ≤ N x+y \le N x + y ≤ N , and y − x y-x y − x only if y ≠ 2 x y \ne2x y = 2 x ). If { x , y } \{x,y\} { x , y } is an edge, its length y − x y-x y − x must be x x x , so y = 2 x y=2x y = 2 x , and the other edge has length 2 x 2x 2 x and joins x x x to 3 x 3x 3 x or y y y to 4 x 4x 4 x . Each case gives N N N edges connected through 0 0 0 , hence a graceful tree, and they are distinct. With R = ⌊ N / 2 ⌋ R=\lfloor N/2\rfloor R = ⌊ N /2 ⌋ and P = # { 1 ≤ x < y : x + y ≤ N } P=\#\{1 \le x<y:x+y \le N\} P = # { 1 ≤ x < y : x + y ≤ N } (R ( R − 1 ) R(R-1) R ( R − 1 ) for N = 2 R N=2R N = 2 R , R 2 R^2 R 2 for N = 2 R + 1 N=2R+1 N = 2 R + 1 ), the three cases give ( R 2 ) − ⌊ R / 2 ⌋ \binom{R}{2}-\lfloor R/2\rfloor ( 2 R ) − ⌊ R /2 ⌋ , 2 P − ⌊ N / 3 ⌋ 2P-\lfloor N/3\rfloor 2 P − ⌊ N /3 ⌋ and ⌊ N / 3 ⌋ + ⌊ N / 4 ⌋ \lfloor N/3\rfloor+\lfloor N/4\rfloor ⌊ N /3 ⌋ + ⌊ N /4 ⌋ trees; since ⌊ R / 2 ⌋ = ⌊ N / 4 ⌋ \lfloor R/2\rfloor=\lfloor N/4\rfloor ⌊ R /2 ⌋ = ⌊ N /4 ⌋ , the total is ( R 2 ) + 2 P \binom{R}{2}+2P ( 2 R ) + 2 P .
Few cycles
This section and the next two prove the right half of Theorem 1.1 . There are three steps. Few cycles (this section): To close a cycle, its last arc must point exactly back to its first vertex v v v , which requires one specific length. We show that, whatever has been revealed so far (as long as it is not much), the probability that a given vertex points to v v v is at most about 1 / ρ ( v ) 1/\rho(v) 1/ ρ ( v ) . Summing over vertices and cycle sizes gives O ( log 2 N ) O(\log^2 N) O ( log 2 N ) cycles on average. Cycles are easy to repair (§ 5 ): Each cycle can be destroyed by changing O ( log N ) O(\log N) O ( log N ) edges. Counting (§ 6 ): Few changes and few cycles mean that rainbow maps outnumber trees by at most e O ( log 4 N ) e^{O(\log^4 N)} e O ( l o g 4 N ) .
Longer lengths are not harder to get
Fix a feasible type σ \sigma σ and take the uniform measure on its board. Then the target f ( k ) f(k) f ( k ) is determined by the length δ k \delta_k δ k (k − δ k k-\delta_k k − δ k if σ k = L \sigma_k=\mathrm{L} σ k = L , k + δ k k+\delta_k k + δ k if σ k = R \sigma_k=\mathrm{R} σ k = R ).
A row–length pair is a cell . A history is a set of n n n cells in distinct rows and with distinct lengths, consistent with at least one rainbow map of type σ \sigma σ ; it specifies the lengths of n n n rows, which are called revealed . Given a history, the rest is uniform over its completions . Let A A A be the set of lengths not used by the history.
Lemma 4.1 (Swap). Given a history, let row k k k be unrevealed and let d < d ′ d<d' d < d ′ be lengths in A A A with d ′ ≤ ℓ k d' \le\ell_k d ′ ≤ ℓ k . Then # { completions with δ k = d } ≤ # { completions with δ k = d ′ } \#\{\text{completions with }\delta_k=d\} \le\#\{\text{completions with }\delta_k=d'\} # { completions with δ k = d } ≤ # { completions with δ k = d ′ } . Hence, for d ∈ A d \in A d ∈ A with d ≤ ℓ k d \le\ell_k d ≤ ℓ k , Pr [ δ k = d ∣ history ] ≤ 1 / ∣ A ∩ [ d , ℓ k ] ∣ \Pr[\delta_k=d\mid\text{history}] \le1/|A\cap[d,\ell_k]| Pr [ δ k = d ∣ history ] ≤ 1/∣ A ∩ [ d , ℓ k ] ∣ .
Proof. Take a completion with δ k = d \delta_k=d δ k = d . The length d ′ d' d ′ is not used by the history, so the row k ′ k' k ′ using it is unrevealed, and k ′ ≠ k k' \ne k k ′ = k . Swap the lengths of k k k and k ′ k' k ′ : Row k k k gets d ′ ≤ ℓ k d' \le\ell_k d ′ ≤ ℓ k , and row k ′ k' k ′ gets d < d ′ ≤ ℓ k ′ d<d' \le\ell_{k'} d < d ′ ≤ ℓ k ′ , which is allowed because the allowed set of k ′ k' k ′ is a prefix. This is a completion with δ k = d ′ \delta_k=d' δ k = d ′ ; swapping k k k with the row that uses d d d recovers the original, so the map is injective. For the second assertion, each length in A ∩ [ d , ℓ k ] A\cap[d,\ell_k] A ∩ [ d , ℓ k ] is at least as likely for k k k as d d d , and these probabilities sum to at most 1.
The lemma uses only that the allowed sets are prefixes. For example, on the board of Figure 2 with the empty history, the probabilities of the lengths of vertex 1 are nondecreasing (Corollary 3.8), and the swap with d ′ = 5 d'=5 d ′ = 5 sends the placement ( 3 , 4 , 1 , 2 , 5 ) (3,4,1,2,5) ( 3 , 4 , 1 , 2 , 5 ) of the figure to ( 5 , 4 , 1 , 2 , 3 ) (5,4,1,2,3) ( 5 , 4 , 1 , 2 , 3 ) .
Lemma 4.2 (Pointing to a given vertex). Given a history with n n n cells, let row k k k be unrevealed and let v v v be an interior vertex with n ≤ ρ ( v ) n \le\rho(v) n ≤ ρ ( v ) . Then Pr [ k → v ∣ history ] ≤ 1 ρ ( v ) + 1 − n \Pr[k\to v\mid\text{history}] \le\frac{1}{\rho(v)+1-n} Pr [ k → v ∣ history ] ≤ ρ ( v ) + 1 − n 1 .
Proof. The probability is zero if v v v is not in the direction of k k k or the required length d = ∣ k − v ∣ d = \lvert k-v\rvert d = ∣ k − v ∣ is used. Otherwise, if σ k = L \sigma_k = \mathrm{L} σ k = L then d = k − v d = k-v d = k − v and ℓ k = k \ell_k = k ℓ k = k , so [ d , ℓ k ] [d,\ell_k] [ d , ℓ k ] contains v + 1 v+1 v + 1 lengths; if σ k = R \sigma_k = \mathrm{R} σ k = R then d = v − k d = v-k d = v − k and ℓ k = N − k \ell_k = N-k ℓ k = N − k , so it contains N − v + 1 N-v+1 N − v + 1 lengths. Either way there are at least ρ ( v ) + 1 \rho(v)+1 ρ ( v ) + 1 , of which at most n n n are used, so ∣ A ∩ [ d , ℓ k ] ∣ ≥ ρ ( v ) + 1 − n \lvert A\cap[d,\ell_k]\rvert\ge\rho(v)+1-n ∣ A ∩ [ d , ℓ k ]∣ ≥ ρ ( v ) + 1 − n . Apply Lemma 4.1. □ \square □
The bound is uniform in k k k and in the history, and it is attained (N = 3 N=3 N = 3 , type RL: Pr [ 1 → 2 ] = 1 2 \Pr[1\to2]=\frac{1}{2} Pr [ 1 → 2 ] = 2 1 ). It bounds the probabilities without ordering them: Given δ 3 = 1 \delta_3=1 δ 3 = 1 on the board of Figure 2 , the bounds for v = 2 v=2 v = 2 and v = 3 v=3 v = 3 are 1 2 > 1 3 \frac{1}{2}>\frac{1}{3} 2 1 > 3 1 , but Pr [ 1 → 2 ] = 0 < Pr [ 1 → 3 ] = 1 6 \Pr[1\to2]=0<\Pr[1\to3]=\frac{1}{6} Pr [ 1 → 2 ] = 0 < Pr [ 1 → 3 ] = 6 1 .
The expected number of cycles
Lemma 4.3. Let t ≥ 3 t\ge3 t ≥ 3 and ρ ( v ) ≥ t − 1 \rho(v)\ge t-1 ρ ( v ) ≥ t − 1 . Then Pr [ v lies on a t -cycle ∣ σ ] ≤ 1 ρ ( v ) − t + 2 \Pr[v\text{ lies on a }t\text{-cycle}\mid\sigma]\le\frac{1}{\rho(v)-t+2} Pr [ v lies on a t -cycle ∣ σ ] ≤ ρ ( v ) − t + 2 1 , which is at most 2 ρ ( v ) \frac{2}{\rho(v)} ρ ( v ) 2 if moreover ρ ( v ) ≥ 2 t \rho(v)\ge2t ρ ( v ) ≥ 2 t .
Proof. Reveal the forward path from v = u 0 v=u_0 v = u 0 : Revealing the length of u 0 u_0 u 0 gives u 1 u_1 u 1 , revealing the length of u 1 u_1 u 1 gives u 2 u_2 u 2 , and so on, t − 1 t-1 t − 1 arcs in all, ending at u t − 1 u_{t-1} u t − 1 . Stop as soon as some u j u_j u j (1 ≤ j ≤ t − 1 1\le j\le t-1 1 ≤ j ≤ t − 1 ) is a ground vertex or equals an earlier u i u_i u i ; then v v v is not on a t t t -cycle. Each outcome that does not stop is a history with n = t − 1 n=t-1 n = t − 1 cells (the statement that these t − 1 t-1 t − 1 rows have these lengths, with no further condition), in which u 0 , … , u t − 1 u_0,\ldots,u_{t-1} u 0 , … , u t − 1 are distinct and u t − 1 u_{t-1} u t − 1 is unrevealed. The vertex v v v lies on a t t t -cycle if and only if the process does not stop and u t − 1 → v u_{t-1}\to v u t − 1 → v . Apply Lemma 4.2 to each such history (n = t − 1 ≤ ρ ( v ) n=t-1\le\rho(v) n = t − 1 ≤ ρ ( v ) ) and average. For the second bound, ρ ( v ) ≥ 2 t \rho(v)\ge2t ρ ( v ) ≥ 2 t gives ρ ( v ) − t + 2 ≥ ρ ( v ) / 2 \rho(v)-t+2\ge\rho(v)/2 ρ ( v ) − t + 2 ≥ ρ ( v ) /2 . □ \square □
The bound of Lemma 4.3 is useless for vertices of small rank, since after t − 1 t-1 t − 1 revealed cells few lengths may remain. We therefore split cycles into two kinds. Cycles most of whose vertices have large rank are handled by summing Lemma 4.3 over vertices. Cycles most of whose vertices have rank < 2 t <2t < 2 t need no probability at all: There are fewer than 4 t 4t 4 t such vertices, and distinct cycles are disjoint.
Theorem 4.4 (Number of cycles). For every feasible type σ \sigma σ ,
E [ c ∣ σ ] ≤ B N : = 8 H R 2 + 16 ⌊ log 2 m ⌋ , H R = ∑ j = 1 R 1 j . \mathbb{E}[c\mid\sigma]\le B_N:=8\mathcal{H}_R^2+16\lfloor\log_2 m\rfloor,\qquad\mathcal{H}_R=\sum_{j=1}^{R}\frac{1}{j}. E [ c ∣ σ ] ≤ B N := 8 H R 2 + 16 ⌊ log 2 m ⌋ , H R = j = 1 ∑ R j 1 . Averaging over σ \sigma σ , E [ c ] ≤ B N = O ( log 2 2 N ) \mathbb{E}[c]\le B_N=O(\log_2^2 N) E [ c ] ≤ B N = O ( log 2 2 N ) .
Proof. A t t t -cycle is of the first kind if at least t / 2 t/2 t /2 of its vertices have ρ ≥ 2 t \rho\ge2t ρ ≥ 2 t , and of the second kind otherwise (then more than t / 2 t/2 t /2 of its vertices have ρ < 2 t \rho<2t ρ < 2 t ).
First kind. Let V t : = { v : ρ ( v ) ≥ 2 t and v lies on a t -cycle } V_t:=\{v:\rho(v)\ge2t\text{ and }v\text{ lies on a }t\text{-cycle}\} V t := { v : ρ ( v ) ≥ 2 t and v lies on a t -cycle } . Each t t t -cycle of the first kind contributes at least t / 2 t/2 t /2 elements of V t V_t V t , and distinct cycles contribute distinct elements, so the number c t I c_t^{\mathrm{I}} c t I of such cycles satisfies t 2 c t I ≤ ∣ V t ∣ \frac{t}{2}c_t^{\mathrm{I}}\le\lvert V_t\rvert 2 t c t I ≤ ∣ V t ∣ . By Lemma 4.3, E [ ∣ V t ∣ ∣ σ ] ≤ ∑ v : ρ ( v ) ≥ 2 t 2 / ρ ( v ) \mathbb{E}[\lvert V_t\rvert\mid\sigma]\le\sum_{v:\rho(v)\ge2t}2/\rho(v) E [∣ V t ∣ ∣ σ ] ≤ ∑ v : ρ ( v ) ≥ 2 t 2/ ρ ( v ) ; since each rank has at most two vertices,
E [ c t I ∣ σ ] ≤ 2 t ∑ v : ρ ( v ) ≥ 2 t 2 ρ ( v ) ≤ 8 t ∑ j = 2 t R 1 j , ∑ t ≥ 3 E [ c t I ∣ σ ] ≤ 8 ( ∑ t ≤ R / 2 1 t ) H R ≤ 8 H R 2 . \mathbb{E}[c_t^{\mathrm{I}}\mid\sigma]\le\frac{2}{t}\sum_{v:\rho(v)\ge2t}\frac{2}{\rho(v)}\le\frac{8}{t}\sum_{j=2t}^{R}\frac{1}{j},\qquad\sum_{t\ge3}\mathbb{E}[c_t^{\mathrm{I}}\mid\sigma]\le8\left(\sum_{t\le R/2}\frac{1}{t}\right)\mathcal{H}_R\le8\mathcal{H}_R^2. E [ c t I ∣ σ ] ≤ t 2 v : ρ ( v ) ≥ 2 t ∑ ρ ( v ) 2 ≤ t 8 j = 2 t ∑ R j 1 , t ≥ 3 ∑ E [ c t I ∣ σ ] ≤ 8 t ≤ R /2 ∑ t 1 H R ≤ 8 H R 2 .
Second kind (a deterministic bound). Fix a dyadic range 2 j ≤ t < 2 j + 1 2^j\le t<2^{j+1} 2 j ≤ t < 2 j + 1 ; since 3 ≤ t ≤ m 3\le t\le m 3 ≤ t ≤ m , we have 1 ≤ j ≤ ⌊ log 2 m ⌋ 1\le j\le\lfloor\log_2 m\rfloor 1 ≤ j ≤ ⌊ log 2 m ⌋ . Each second-kind cycle in this range uses more than t / 2 ≥ 2 j − 1 t/2\ge2^{j-1} t /2 ≥ 2 j − 1 vertices with ρ < 2 t < 2 j + 2 \rho< 2t < 2^{j+2} ρ < 2 t < 2 j + 2 , and there are fewer than 2 ⋅ 2 j + 2 = 2 j + 3 2 \cdot2^{j+2} = 2^{j+3} 2 ⋅ 2 j + 2 = 2 j + 3 such vertices. Cycles are disjoint, so this range contains fewer than 2 j + 3 / 2 j − 1 = 16 2^{j+3}/2^{j-1} = 16 2 j + 3 / 2 j − 1 = 16 cycles of the second kind. Adding,
E [ c ∣ σ ] ≤ 8 H R 2 + 16 ⌊ log 2 m ⌋ . \mathbb{E}[c \mid\sigma] \le8H_R^2 + 16\lfloor\log_2 m \rfloor. E [ c ∣ σ ] ≤ 8 H R 2 + 16 ⌊ log 2 m ⌋ .
The proof uses no typical property of σ \sigma σ . The bound is not meant for small N N N : For N = 1000 N = 1000 N = 1000 , B N ≈ 513 B_N \approx513 B N ≈ 513 exceeds the trivial bound c ≤ m / 3 c \le m/3 c ≤ m /3 ; for N = 10 6 N = 10^6 N = 1 0 6 , B N ≈ 1805 B_N \approx1805 B N ≈ 1805 .
Cycles are easy to repair
What has to be done
In this section directions play no role: A rainbow map f f f enters only through its undirected edge set X ( f ) : = { { k , f ( k ) } : 1 ≤ k ≤ m } X(f) := \{\{k, f(k)\}: 1 \le k \le m\} X ( f ) := {{ k , f ( k )} : 1 ≤ k ≤ m } , and the type is irrelevant. These m m m edges are distinct (two vertices choosing the same edge would use the same length), and each length 1 , … , m 1,\ldots,m 1 , … , m occurs exactly once.
We work in the contracted graph: Take the complete graph K N + 1 K_{N+1} K N + 1 on { 0 , … , N } \{0,\ldots,N\} { 0 , … , N } , delete the edge { 0 , N } \{0,N\} { 0 , N } , and identify 0 0 0 and N N N into one vertex g g g . Its vertices are g , 1 , … , m g,1,\ldots,m g , 1 , … , m , and each edge keeps its identity and its length from K N + 1 K_{N+1} K N + 1 . It is a multigraph: The edges { 0 , k } \{0,k\} { 0 , k } and { k , N } \{k,N\} { k , N } are two different edges between g g g and k k k (of lengths k k k and N − k N-k N − k ), and two parallel edges form a cycle. Let E E E be its edge set; ∣ E ∣ = ∑ d = 1 N ( N + 1 − d ) = ( N − 1 ) ( N + 2 ) 2 |E| = \sum_{d=1}^{N}(N+1-d) = \frac{(N-1)(N+2)}{2} ∣ E ∣ = ∑ d = 1 N ( N + 1 − d ) = 2 ( N − 1 ) ( N + 2 ) . In the contracted graph the component of X ( f ) X(f) X ( f ) containing g g g is a tree and every other component contains exactly one cycle; these are the cycles of f f f . Graceful labelings correspond to rainbow spanning trees of the contracted graph, that is, spanning trees with exactly one edge of each length: Deleting { 0 , N } \{0,N\} { 0 , N } from a graceful tree and contracting gives such a tree, and conversely a rainbow spanning tree, lifted to K N + 1 K_{N+1} K N + 1 together with { 0 , N } \{0,N\} { 0 , N } , has N N N edges on N + 1 N+1 N + 1 vertices, is connected, and has lengths 1 , … , N 1,\ldots,N 1 , … , N . So there are τ ( N ) \tau(N) τ ( N ) rainbow spanning trees.
Given a rainbow map with cycles, we want to change its edge set into a rainbow spanning tree by changing few edges. Deleting one edge from each cycle leaves a forest in which some lengths are missing. So the problem is this: Given a forest F F F with at most one edge of each length and some length missing, how do we add an edge of a missing length? If some edge of a missing length joins two components of F F F , we simply add it. Otherwise every edge of that length closes a cycle in F F F ; we can add one and delete another edge of that cycle, of some length d ′ d' d ′ , so that d ′ d' d ′ is now missing, and continue. We must show that such chains are short.
For this we need to know: How many edges without a cycle can be chosen using only k k k distinct lengths? The answer is at least min ( 2 k , m ) \min(2k,m) min ( 2 k , m ) (Corollary 5.4). Then the set of lengths involved in a chain at least doubles at each level, so ⌈ log 2 m ⌉ \lceil\log_2 m \rceil ⌈ log 2 m ⌉ levels suffice (Section 5.3).
How large a forest can k k k lengths support?
For Δ ⊆ { 1 , … , m } \Delta\subseteq\{1,\ldots,m\} Δ ⊆ { 1 , … , m } let G Δ G_\Delta G Δ be the graph on { 0 , … , N } \{0,\ldots,N\} { 0 , … , N } consisting of all edges with lengths in Δ ∪ { N } \Delta\cup\{N\} Δ ∪ { N } (the only edge of length N N N is { 0 , N } \{0,N\} { 0 , N } ), and let r ( Δ ) r(\Delta) r ( Δ ) be the number of edges of a spanning forest (a maximal acyclic subgraph) of G Δ G_\Delta G Δ , that is, N + 1 N+1 N + 1 minus the number of components.
The key observation is that an edge of length d d d joins i i i and i + d i+d i + d . So if we label each vertex i i i by the name of its component in G Δ G_\Delta G Δ , the resulting word w = w 0 … w N w = w_0\ldots w_N w = w 0 … w N of length N + 1 N+1 N + 1 has every d ∈ Δ ∪ { N } d \in\Delta\cup\{N\} d ∈ Δ ∪ { N } as a period. The number of lengths becomes a number of periods, and the number of components becomes the number of distinct letters. The following inequality says that many periods force few letters.
A border of a word w w w is a nonempty proper prefix that is also a suffix. Let ∣ w ∣ |w| ∣ w ∣ be the length, sym ( w ) \operatorname{sym}(w) sym ( w ) the number of distinct letters, and bor ( w ) \operatorname{bor}(w) bor ( w ) the number of borders. For 1 ≤ p < ∣ w ∣ 1 \le p < |w| 1 ≤ p < ∣ w ∣ , w w w has a border of length ∣ w ∣ − p |w| - p ∣ w ∣ − p if and only if p p p is a period of w w w (w i = w i + p w_i = w_{i+p} w i = w i + p for 0 ≤ i < ∣ w ∣ − p 0 \le i < |w| - p 0 ≤ i < ∣ w ∣ − p ). For example, the borders of a b a a b a abaaba abaaba are a a a and a b a aba aba (periods 5 5 5 and 3 3 3 ).
Theorem 5.1 (Border bound). If w w w is not constant, then ∣ w ∣ − sym ( w ) ≥ 2 bor ( w ) − 1 |w| - \operatorname{sym}(w) \ge2\operatorname{bor}(w) - 1 ∣ w ∣ − sym ( w ) ≥ 2 bor ( w ) − 1 . (Equality holds for a k b a k a^kba^k a k b a k and a k b c a k a^kbc a^k a k b c a k with k ≥ 1 k \ge1 k ≥ 1 and distinct letters a a a , b b b , c c c .)
Proof. Induction on ∣ w ∣ |w| ∣ w ∣ . If bor ( w ) = 0 \operatorname{bor}(w) = 0 bor ( w ) = 0 then ∣ w ∣ − sym ( w ) ≥ 0 > − 1 |w| - \operatorname{sym}(w) \ge0 > -1 ∣ w ∣ − sym ( w ) ≥ 0 > − 1 . Let bor ( w ) ≥ 1 \operatorname{bor}(w) \ge1 bor ( w ) ≥ 1 and let z z z be the longest border of w w w . Every shorter border of w w w is a prefix and a suffix of z z z , hence a border of z z z , and conversely; so bor ( w ) = 1 + bor ( z ) \operatorname{bor}(w) = 1 + \operatorname{bor}(z) bor ( w ) = 1 + bor ( z ) . Let q : = ∣ z ∣ q := |z| q := ∣ z ∣ ; then p : = ∣ w ∣ − q p := |w| - q p := ∣ w ∣ − q is a period of w w w , and p ≥ 2 p \ge2 p ≥ 2 because p = 1 p = 1 p = 1 would make w w w constant.
z z z is not constant. Then q ≥ 2 q \ge2 q ≥ 2 , and by induction q − sym ( z ) ≥ 2 bor ( z ) − 1 = 2 bor ( w ) − 3 q - \operatorname{sym}(z) \ge2\operatorname{bor}(z) - 1 = 2\operatorname{bor}(w) - 3 q − sym ( z ) ≥ 2 bor ( z ) − 1 = 2 bor ( w ) − 3 . Since w w w has period p p p , every letter of w w w occurs among its first p p p positions; a letter not in z = w 0 … w q − 1 z = w_0 \ldots w_{q-1} z = w 0 … w q − 1 must occur in positions q , … , p − 1 q,\ldots,p-1 q , … , p − 1 , so sym ( w ) − sym ( z ) ≤ max ( 0 , p − q ) \operatorname{sym}(w) - \operatorname{sym}(z) \le\max(0,p-q) sym ( w ) − sym ( z ) ≤ max ( 0 , p − q ) . Hence
( ∣ w ∣ − sym ( w ) ) − ( q − sym ( z ) ) = p − ( sym ( w ) − sym ( z ) ) ≥ min ( p , q ) ≥ 2. \bigl(|w|-\operatorname{sym}(w)\bigr)-\bigl(q-\operatorname{sym}(z)\bigr)=p-\bigl(\operatorname{sym}(w)-\operatorname{sym}(z)\bigr)\ge\min(p,q)\ge2. ( ∣ w ∣ − sym ( w ) ) − ( q − sym ( z ) ) = p − ( sym ( w ) − sym ( z ) ) ≥ min ( p , q ) ≥ 2.
and ∣ w ∣ − sym ( w ) ≥ ( 2 bor ( w ) − 3 ) + 2 = 2 bor ( w ) − 1 |w| - \operatorname{sym}(w) \ge(2\operatorname{bor}(w) - 3) + 2 = 2\operatorname{bor}(w) - 1 ∣ w ∣ − sym ( w ) ≥ ( 2 bor ( w ) − 3 ) + 2 = 2 bor ( w ) − 1 .
z = a q z = a^q z = a q . Then bor ( z ) = q − 1 \operatorname{bor}(z) = q - 1 bor ( z ) = q − 1 and bor ( w ) = q \operatorname{bor}(w) = q bor ( w ) = q . The word w w w begins and ends with a q a^q a q ; if ∣ w ∣ ≤ 2 q |w| \le2q ∣ w ∣ ≤ 2 q it would be constant, so ∣ w ∣ ≥ 2 q + 1 |w| \ge2q + 1 ∣ w ∣ ≥ 2 q + 1 , and the letters other than a a a lie in the middle ∣ w ∣ − 2 q |w| - 2q ∣ w ∣ − 2 q positions. Thus sym ( w ) ≤ 1 + ∣ w ∣ − 2 q \operatorname{sym}(w) \le1 + |w| - 2q sym ( w ) ≤ 1 + ∣ w ∣ − 2 q , that is, ∣ w ∣ − sym ( w ) ≥ 2 q − 1 |w| - \operatorname{sym}(w) \ge2q - 1 ∣ w ∣ − sym ( w ) ≥ 2 q − 1 .
:::
Lemma 5.2 (k k k lengths and the length N N N support a forest of min ( 2 k + 1 , N ) \min(2k+1,N) min ( 2 k + 1 , N ) edges). In the complete graph K N + 1 K_{N+1} K N + 1 , r ( Δ ) ≥ min ( 2 ∣ Δ ∣ + 1 , N ) r(\Delta) \ge\min(2|\Delta|+1,N) r ( Δ ) ≥ min ( 2∣Δ∣ + 1 , N ) for every Δ ⊆ { 1 , … , m } \Delta\subseteq\{1,\ldots,m\} Δ ⊆ { 1 , … , m } .
Proof. Let k = ∣ Δ ∣ k = |\Delta| k = ∣Δ∣ and let w = w 0 … w N w = w_0 \ldots w_N w = w 0 … w N be the word of component names, so r ( Δ ) = ( N + 1 ) − sym ( w ) r(\Delta) = (N+1)-\operatorname{sym}(w) r ( Δ ) = ( N + 1 ) − sym ( w ) . Each d ∈ Δ d \in\Delta d ∈ Δ is a period of w w w and gives a border of length N + 1 − d ∈ { 2 , … , N } N+1-d \in\{2,\ldots,N\} N + 1 − d ∈ { 2 , … , N } ; the edge { 0 , N } \{0,N\} { 0 , N } gives w 0 = w N w_0 = w_N w 0 = w N , a border of length 1 1 1 . These k + 1 k+1 k + 1 borders have distinct lengths, so bor ( w ) ≥ k + 1 \operatorname{bor}(w) \ge k+1 bor ( w ) ≥ k + 1 . If w w w is not constant, Theorem 5.1 gives r ( Δ ) ≥ 2 ( k + 1 ) − 1 = 2 k + 1 r(\Delta) \ge2(k+1)-1 = 2k+1 r ( Δ ) ≥ 2 ( k + 1 ) − 1 = 2 k + 1 . If w w w is constant, G Δ G_\Delta G Δ is connected and r ( Δ ) = N r(\Delta) = N r ( Δ ) = N .
Example 5.3. For N = 6 N = 6 N = 6 and Δ = { 2 , 4 } \Delta= \{2,4\} Δ = { 2 , 4 } the even vertices form one component and the odd vertices another; w = A B A B A B A w = ABABABA w = A B A B A B A , with borders A A A , A B A ABA A B A , A B A B A ABABA A B A B A . Here sym ( w ) = 2 \operatorname{sym}(w) = 2 sym ( w ) = 2 , bor ( w ) = 3 \operatorname{bor}(w) = 3 bor ( w ) = 3 , and r ( { 2 , 4 } ) = 5 = min ( 2 ⋅ 2 + 1 , 6 ) r(\{2,4\}) = 5 = \min(2 \cdot2 + 1,6) r ({ 2 , 4 }) = 5 = min ( 2 ⋅ 2 + 1 , 6 ) : Both Theorem 5.1 and Lemma 5.2 hold with equality.
Corollary 5.4. In the contracted graph, at least min ( 2 ∣ Δ ∣ , m ) \min(2|\Delta|,m) min ( 2∣Δ∣ , m ) edges with lengths in Δ \Delta Δ can be chosen without forming a cycle.
Proof. The edges with lengths in Δ \Delta Δ are the edges of G Δ G_\Delta G Δ with { 0 , N } \{0,N\} { 0 , N } removed and 0 0 0 , N N N identified. Since 0 0 0 and N N N are joined in G Δ G_\Delta G Δ , the identification does not change the number of components and removes one vertex; so its spanning forests (maximal acyclic subgraphs) have r ( Δ ) − 1 r(\Delta)-1 r ( Δ ) − 1 edges. Apply Lemma 5.2.
Augmentation
Recall D = ⌈ log 2 m ⌉ D = \lceil\log_2 m \rceil D = ⌈ log 2 m ⌉ . Below, F F F is always a forest of the contracted graph (an acyclic set of edges, not necessarily maximal) with at most one edge of each length. A length d d d is missing if F F F has no edge of length d d d , and directly insertable if some edge of length d d d not in F F F joins two components of F F F . For an edge e ∉ F e \notin F e ∈ / F of length d d d whose ends lie in the same component of F F F , let P F ( e ) P_F(e) P F ( e ) be the path in F F F joining its ends; each edge of length d ′ d' d ′ on this path gives a relation d → d ′ d \to d' d → d ′ .
Lemma 5.5 (Augmentation). Suppose ∣ F ∣ < m |F| < m ∣ F ∣ < m . Then there exist s ≤ D s \le D s ≤ D , edges e 0 , … , e s ∉ F e_0,\ldots,e_s \notin F e 0 , … , e s ∈ / F and edges f 1 , … , f s ∈ F f_1,\ldots,f_s \in F f 1 , … , f s ∈ F such that
F ′ : = ( F ∪ { e 0 , … , e s } ) ∖ { f 1 , … , f s } F' := (F \cup\{e_0,\ldots,e_s\}) \setminus\{f_1,\ldots,f_s\} F ′ := ( F ∪ { e 0 , … , e s }) ∖ { f 1 , … , f s } is a forest with at most one edge of each length and ∣ F ′ ∣ = ∣ F ∣ + 1 |F'| = |F| + 1 ∣ F ′ ∣ = ∣ F ∣ + 1 .
Proof. Finding a chain. Search by levels: Level 0 consists of the missing lengths (there is at least one since ∣ F ∣ < m |F| < m ∣ F ∣ < m ), and level j + 1 j+1 j + 1 consists of the lengths not seen before that are reached from level j j j by one relation. Let Δ j \Delta_j Δ j be the union of levels 0 , … , j 0,\ldots,j 0 , … , j , and F j F_j F j the set of edges of F F F with lengths in Δ j \Delta_j Δ j .
Suppose Δ j \Delta_j Δ j contains no directly insertable length. Then both ends of every edge with length in Δ j \Delta_j Δ j lie in one component of F j + 1 F_{j+1} F j + 1 : For edges in F F F this is clear, and for e ∉ F e \notin F e ∈ / F the ends lie in one component of F F F and all lengths on P F ( e ) P_F(e) P F ( e ) belong to Δ j + 1 \Delta_{j+1} Δ j + 1 . So an acyclic set of edges with lengths in Δ j \Delta_j Δ j has at most n C − 1 n_C - 1 n C − 1 edges inside each component C C C of F j + 1 F_{j+1} F j + 1 with n C n_C n C vertices, hence at most ∣ F j + 1 ∣ ≤ ∣ Δ j + 1 ∣ |F_{j+1}| \le|\Delta_{j+1}| ∣ F j + 1 ∣ ≤ ∣ Δ j + 1 ∣ edges in all. By Corollary 5.4 such a set can have min ( 2 ∣ Δ j ∣ , m ) \min(2|\Delta_j|,m) min ( 2∣ Δ j ∣ , m ) edges; therefore
∣ Δ j + 1 ∣ ≥ min ( 2 ∣ Δ j ∣ , m ) . |\Delta_{j+1}| \ge\min(2|\Delta_j|,m). ∣ Δ j + 1 ∣ ≥ min ( 2∣ Δ j ∣ , m ) .
If none of Δ 0 , … , Δ D − 1 \Delta_0,\ldots,\Delta_{D-1} Δ 0 , … , Δ D − 1 contained a directly insertable length, then ∣ Δ D ∣ ≥ min ( 2 D , m ) = m |\Delta_D| \ge\min(2^D,m) = m ∣ Δ D ∣ ≥ min ( 2 D , m ) = m , so Δ D \Delta_D Δ D would contain all lengths. But F F F is disconnected (as ∣ F ∣ < m |F| < m ∣ F ∣ < m ) while the contracted graph is connected, so some edge joins two components of F F F ; its length is directly insertable and lies in Δ D \Delta_D Δ D . So some Δ j \Delta_j Δ j with j ≤ D j \le D j ≤ D contains a directly insertable length. Take a shortest chain of relations d 0 → d 1 → ⋯ → d s d_0 \to d_1 \to\cdots\to d_s d 0 → d 1 → ⋯ → d s from a missing length d 0 d_0 d 0 to a directly insertable length d s d_s d s . Then s ≤ D s \le D s ≤ D , the d i d_i d i are distinct, and for 0 ≤ i < s 0 \le i < s 0 ≤ i < s there is an edge e i ∉ F e_i \notin F e i ∈ / F of length d i d_i d i such that P F ( e i ) P_F(e_i) P F ( e i ) contains an edge f i + 1 ∈ F f_{i+1} \in F f i + 1 ∈ F of length d i + 1 d_{i+1} d i + 1 ; and e s ∉ F e_s \notin F e s ∈ / F is an edge of length d s d_s d s joining two components of F F F . As the chain is shortest, f j ∉ P F ( e i ) f_j \notin P_F(e_i) f j ∈ / P F ( e i ) for j > i + 1 j > i+1 j > i + 1 .
The result. F ′ F' F ′ loses one edge of each length d 1 , … , d s d_1,\ldots,d_s d 1 , … , d s and gains one edge of each length d 0 , … , d s d_0,\ldots,d_s d 0 , … , d s ; so only the missing length d 0 d_0 d 0 is added, each length still occurs at most once, and ∣ F ′ ∣ = ∣ F ∣ + 1 |F'| = |F| + 1 ∣ F ′ ∣ = ∣ F ∣ + 1 . To see that F ′ F' F ′ is acyclic, let F ( j ) : = ( F ∪ { e j , … , e s } ) ∖ { f j + 1 , … , f s } F^{(j)} := (F \cup\{e_j,\ldots,e_s\}) \setminus\{f_{j+1},\ldots,f_s\} F ( j ) := ( F ∪ { e j , … , e s }) ∖ { f j + 1 , … , f s } for j = s , s − 1 , … , 0 j = s,s-1,\ldots,0 j = s , s − 1 , … , 0 , so that F ( s ) = F ∪ { e s } F^{(s)} = F \cup\{e_s\} F ( s ) = F ∪ { e s } and F ( 0 ) = F ′ F^{(0)} = F' F ( 0 ) = F ′ . F ( s ) F^{(s)} F ( s ) is a forest because e s e_s e s joins two components of F F F . If F ( j + 1 ) F^{(j+1)} F ( j + 1 ) is a forest (j < s j < s j < s ), the path P F ( e j ) P_F(e_j) P F ( e j ) lies in F F F and avoids f j + 2 , … , f s f_{j+2},\ldots,f_s f j + 2 , … , f s , so it lies in F ( j + 1 ) F^{(j+1)} F ( j + 1 ) and contains f j + 1 f_{j+1} f j + 1 ; it is the unique path in F ( j + 1 ) F^{(j+1)} F ( j + 1 ) joining the ends of e j e_j e j . Replacing f j + 1 f_{j+1} f j + 1 by e j e_j e j on this path leaves a forest F ( j ) F^{(j)} F ( j ) . By induction F ′ F' F ′ is a forest. (The intermediate sets F ( j ) F^{(j)} F ( j ) may contain two edges of the same length; this does not matter.) □ \square □
Lemma 5.6 (Repair). For every rainbow map f f f there is a rainbow spanning tree Y Y Y with ∣ X ( f ) △ Y ∣ ≤ 2 ( D + 1 ) c ( f ) |X(f) \mathbin{\triangle} Y| \le2(D+1)c(f) ∣ X ( f ) △ Y ∣ ≤ 2 ( D + 1 ) c ( f ) .
Proof. Delete an arbitrary edge from each cycle; this gives a forest F 0 F_0 F 0 with at most one edge of each length and ∣ F 0 ∣ = m − c |F_0| = m-c ∣ F 0 ∣ = m − c . Applying Lemma 5.5 c c c times gives a forest with m m m edges, one of each length, that is, a rainbow spanning tree Y Y Y . The deletions change c c c edges and each augmentation changes at most 2 D + 1 2D+1 2 D + 1 , so ∣ X ( f ) △ Y ∣ ≤ c + c ( 2 D + 1 ) = 2 ( D + 1 ) c |X(f)\mathbin{\triangle}Y| \le c+c(2D+1)=2(D+1)c ∣ X ( f ) △ Y ∣ ≤ c + c ( 2 D + 1 ) = 2 ( D + 1 ) c .
Two remarks. First, we only need such a Y Y Y to exist; any choice of Y ( f ) Y(f) Y ( f ) works in § 6 , and no explicit construction is needed. Second, the repair does not proceed one cycle at a time. Each augmentation adds some missing length, and the set of missing lengths shrinks by exactly one; but its exchanges may replace other edges by edges of the same length, including edges that were on no cycle and edges that an earlier augmentation added. Only the total number of changes is counted.
Example 5.7. For the rainbow map of Figure 1 (b), with cycle 1 → 3 → 4 → 1 1 \to3 \to4 \to1 1 → 3 → 4 → 1 , delete the edge { 3 , 4 } \{3,4\} { 3 , 4 } of length 1 1 1 . The components are { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } and { g , 2 , 5 } \{g,2,5\} { g , 2 , 5 } , and the edge { 0 , 1 } \{0,1\} { 0 , 1 } of length 1 1 1 joins them. Adding it gives the tree of Figure 1 (a), with two edges changed.
Counting: proof of Theorem 1.1
For each rainbow map f f f choose a rainbow spanning tree Y ( f ) Y(f) Y ( f ) as in Lemma 5.6 , so that Z ( f ) : = X ( f ) △ Y ( f ) Z(f):=X(f)\mathbin{\triangle}Y(f) Z ( f ) := X ( f ) △ Y ( f ) is small. Different maps may give the same tree, but f f f can be recovered from the tree together with the set Z ( f ) Z(f) Z ( f ) and the orientation of each cycle of f f f . The number of choices of Z Z Z and of orientations is e O ( log 4 N ) e^{O(\log^4 N)} e O ( l o g 4 N ) , since Z Z Z is small and cycles are few. Since Theorem 4.4 controls only the average number of cycles, we discard the maps with more than 2 B N 2B_N 2 B N cycles, which by Markov’s inequality form less than half of all maps.
Proof of Theorem 1.1. The left inequality is Lemma 2.1 . Let c ∗ : = ⌊ 2 B N ⌋ c_*:=\lfloor2B_N\rfloor c ∗ := ⌊ 2 B N ⌋ and G : = { f : c ( f ) ≤ c ∗ } \mathcal{G}:=\{f:c(f)\le c_*\} G := { f : c ( f ) ≤ c ∗ } . By Theorem 4.4 and Markov’s inequality,
# { f : c ( f ) ≥ c ∗ + 1 } ≤ W ( N ) B N c ∗ + 1 < 1 2 W ( N ) , \#\{f:c(f)\ge c_*+1\}\le\frac{W(N)B_N}{c_*+1}<\frac{1}{2}W(N), # { f : c ( f ) ≥ c ∗ + 1 } ≤ c ∗ + 1 W ( N ) B N < 2 1 W ( N ) ,
so ∣ G ∣ > 1 2 W ( N ) |\mathcal{G}|>\frac{1}{2}W(N) ∣ G ∣ > 2 1 W ( N ) .
For f ∈ G f\in\mathcal{G} f ∈ G we have Z ( f ) ⊆ E Z(f)\subseteq E Z ( f ) ⊆ E and ∣ Z ( f ) ∣ ≤ Q : = 2 ( D + 1 ) c ∗ |Z(f)|\le Q:=2(D+1)c_* ∣ Z ( f ) ∣ ≤ Q := 2 ( D + 1 ) c ∗ . The map f f f is determined by Y ( f ) Y(f) Y ( f ) , Z ( f ) Z(f) Z ( f ) and an orientation of each cycle: The set Y ( f ) △ Z ( f ) = X ( f ) Y(f)\mathbin{\triangle}Z(f)=X(f) Y ( f ) △ Z ( f ) = X ( f ) is the edge set of f f f (as a subset of E E E , so edges keep their identities). Each interior vertex leaves along exactly one of these edges and distinct vertices use distinct edges, so in the component containing g g g every edge is oriented towards g g g , and in every other component the edges off the cycle are oriented towards the cycle; only the orientation of each cycle remains. An edge together with its orientation determines the vertex k k k it leaves and f ( k ) f(k) f ( k ) . There are at most τ ( N ) \tau(N) τ ( N ) choices for Y ( f ) Y(f) Y ( f ) , at most
∑ j ≤ Q ( ∣ E ∣ j ) ≤ ( ∣ E ∣ + 1 ) Q \sum_{j\le Q}\binom{|E|}{j}\le(|E|+1)^Q j ≤ Q ∑ ( j ∣ E ∣ ) ≤ ( ∣ E ∣ + 1 ) Q
choices for Z ( f ) Z(f) Z ( f ) (write a set of at most Q Q Q edges as a sequence of length Q Q Q , padded with a blank symbol), and at most 2 c ∗ 2^{c_*} 2 c ∗ orientations. Hence
1 2 W ( N ) < ∣ G ∣ ≤ τ ( N ) ( ∣ E ∣ + 1 ) Q 2 c ∗ , \frac{1}{2}W(N)<|\mathcal{G}|\le\tau(N)(|E|+1)^Q2^{c_*}, 2 1 W ( N ) < ∣ G ∣ ≤ τ ( N ) ( ∣ E ∣ + 1 ) Q 2 c ∗ ,
and, using c ∗ ≤ 2 B N c_*\le2B_N c ∗ ≤ 2 B N ,
log W ( N ) − log τ ( N ) ≤ [ 4 ( D + 1 ) log ( ∣ E ∣ + 1 ) + 2 log 2 ] B N + log 2. \log W(N)-\log\tau(N)\le[4(D+1)\log(|E|+1)+2\log2]B_N+\log2. log W ( N ) − log τ ( N ) ≤ [ 4 ( D + 1 ) log ( ∣ E ∣ + 1 ) + 2 log 2 ] B N + log 2.
The constant. Note that log N ≤ Λ − 1 \log N\le\Lambda-1 log N ≤ Λ − 1 . From D + 1 ≤ log N log 2 + 2 D+1\le\frac{\log N}{\log2}+2 D + 1 ≤ l o g 2 l o g N + 2 and ∣ E ∣ + 1 = N ( N + 1 ) 2 ≤ N 2 |E|+1=\frac{N(N+1)}{2}\le N^2 ∣ E ∣ + 1 = 2 N ( N + 1 ) ≤ N 2 , the bracket is at most 8 log 2 log 2 N + 16 log N + 1.39 ≤ 11.55 Λ 2 \frac{8}{\log2}\log^2N+16\log N+1.39\le11.55\Lambda^2 l o g 2 8 log 2 N + 16 log N + 1.39 ≤ 11.55 Λ 2 . From H R ≤ 1 + log N 2 ≤ Λ − 0.69 \mathcal{H}_R\le1+\log\frac{N}{2}\le\Lambda-0.69 H R ≤ 1 + log 2 N ≤ Λ − 0.69 and ⌊ log 2 m ⌋ ≤ log N log 2 \lfloor\log_2m\rfloor\le\frac{\log N}{\log2} ⌊ log 2 m ⌋ ≤ l o g 2 l o g N we get B N ≤ 8 ( Λ − 0.69 ) 2 + 23.09 ( Λ − 1 ) ≤ 8 Λ 2 + 12.05 Λ B_N\le8(\Lambda-0.69)^2+23.09(\Lambda-1)\le8\Lambda^2+12.05\Lambda B N ≤ 8 ( Λ − 0.69 ) 2 + 23.09 ( Λ − 1 ) ≤ 8 Λ 2 + 12.05Λ . The product is at most 92.4 Λ 4 + 139.2 Λ 3 92.4\Lambda^4+139.2\Lambda^3 92.4 Λ 4 + 139.2 Λ 3 . For N ≥ 3 N\ge3 N ≥ 3 , Λ ≥ 2.38 \Lambda\ge2.38 Λ ≥ 2.38 , so 139.2 Λ 3 ≤ 58.5 Λ 4 139.2\Lambda^3\le58.5\Lambda^4 139.2 Λ 3 ≤ 58.5 Λ 4 and log 2 ≤ 0.03 Λ 4 \log2\le0.03\Lambda^4 log 2 ≤ 0.03 Λ 4 ; the total is at most 151 Λ 4 151\Lambda^4 151 Λ 4 .
The four logarithms in log 4 N \log^4N log 4 N have separate origins: two in B N B_N B N (one of them from summing 1 / t 1/t 1/ t over the sizes t t t of cycles), one from the 2 ( D + 1 ) 2(D+1) 2 ( D + 1 ) changes per cycle, and one from the log ∣ E ∣ \log|E| log ∣ E ∣ needed to name an edge.
Formulas for the Whitty numbers
This section does not involve trees; it determines the size of W ( N ) W(N) W ( N ) and proves Theorem 1.2 , starting from the Motzkin paths of § 3 . We write the path transitions as a difference operator T T T , so that W ( N ) W(N) W ( N ) is the value of a power of T T T at x = 1 x=1 x = 1 (§ 7.1 ). For a special family of polynomials p k p_k p k , the value of p k ( T ) p_k(T) p k ( T ) at x = 1 x=1 x = 1 is a positive lattice path count that turns out to be a factorial (§ 7.2 ). Expanding powers of T T T in the p k ( T ) p_k(T) p k ( T ) gives an alternating sum with factorials and an exact algorithm with O ( N 2 ) O(N^2) O ( N 2 ) integer operations (§ 7.3 ). The alternating sum is hard to estimate, since its terms are much larger than its value; we write it exactly as a moment of a positive measure, a continuous dual Hahn weight, which performs all cancellations at once (§ 7.4 ). The density of this measure lies between two functions of the form polynomial × e − π x \times e^{-\pi x} × e − π x , and the constant 2 / π 2/\pi 2/ π comes from this e − π x e^{-\pi x} e − π x (§ 7.6 ). Everything up to the moment representation is combinatorial; the analysis uses one integral of Wilson (Fact 7.6 ) and standard identities for the Gamma function.
The operator
For functions F F F on { 0 , 1 , 2 , … } \{0,1,2,\ldots\} { 0 , 1 , 2 , … } with F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 let
( T F ) ( x ) : = x 2 ( F ( x + 1 ) + 2 F ( x ) + F ( x − 1 ) ) ( x ≥ 1 ) , ( T F ) ( 0 ) : = 0. (TF)(x):=x^2(F(x+1)+2F(x)+F(x-1)) \qquad(x\geq1), \qquad(TF)(0):=0. ( T F ) ( x ) := x 2 ( F ( x + 1 ) + 2 F ( x ) + F ( x − 1 )) ( x ≥ 1 ) , ( T F ) ( 0 ) := 0.
Lemma 7.1 (Operator form). For q ≥ 1 q\geq1 q ≥ 1 , W ( 2 q + 1 ) = 4 ( T q − 1 x 3 ) ( 1 ) W(2q+1)=4(T^{q-1}x^3)(1) W ( 2 q + 1 ) = 4 ( T q − 1 x 3 ) ( 1 ) and W ( 2 q + 2 ) = 2 ( T q x 2 ) ( 1 ) W(2q+2)=2(T^qx^2)(1) W ( 2 q + 2 ) = 2 ( T q x 2 ) ( 1 ) .
Proof. The transfer operator of the paths of Theorem 3.1 is ( J f ) ( x ) = x ( x + 1 ) f ( x + 1 ) + 2 x 2 f ( x ) + x ( x − 1 ) f ( x − 1 ) (Jf)(x)=x(x+1)f(x+1)+2x^2f(x)+x(x-1)f(x-1) ( J f ) ( x ) = x ( x + 1 ) f ( x + 1 ) + 2 x 2 f ( x ) + x ( x − 1 ) f ( x − 1 ) . The total weight of q q q -step paths from height x x x , with final weight f f f , is ( J q f ) ( x ) (J^qf)(x) ( J q f ) ( x ) . So W ( 2 q + 1 ) = ( J q 1 ) ( 1 ) W(2q+1)=(J^q1)(1) W ( 2 q + 1 ) = ( J q 1 ) ( 1 ) and W ( 2 q + 2 ) = ( J q 2 x ) ( 1 ) W(2q+2)=(J^q2x)(1) W ( 2 q + 2 ) = ( J q 2 x ) ( 1 ) . Expanding shows x ( J f ) ( x ) = T ( x f ) ( x ) x(Jf)(x)=T(xf)(x) x ( J f ) ( x ) = T ( x f ) ( x ) , hence x ( J q f ) ( x ) = ( T q ( x f ) ) ( x ) x(J^qf)(x)=(T^q(xf))(x) x ( J q f ) ( x ) = ( T q ( x f )) ( x ) , and at x = 1 x=1 x = 1 we get W ( 2 q + 1 ) = ( T q x ) ( 1 ) W(2q+1)=(T^qx)(1) W ( 2 q + 1 ) = ( T q x ) ( 1 ) and W ( 2 q + 2 ) = 2 ( T q x 2 ) ( 1 ) W(2q+2)=2(T^qx^2)(1) W ( 2 q + 2 ) = 2 ( T q x 2 ) ( 1 ) . Finally T x = x 2 ( ( x + 1 ) + 2 x + ( x − 1 ) ) = 4 x 3 Tx=x^2((x+1)+2x+(x-1))=4x^3 T x = x 2 (( x + 1 ) + 2 x + ( x − 1 )) = 4 x 3 . □
The bridge lemma
For the two parities let
λ j o : = ( 2 j + 2 ) ( 2 j + 1 ) ( N odd ) , λ j e : = ( 2 j + 1 ) ( 2 j ) ( N even ) , p k ( ω ) : = ∏ j < k ( ω + λ j ) , \lambda_j^o:=(2j+2)(2j+1)\quad(N\ \text{odd}),\qquad\lambda_j^e:=(2j+1)(2j)\quad(N\ \text{even}),\qquad p_k(\omega):=\prod_{j<k}(\omega+\lambda_j), λ j o := ( 2 j + 2 ) ( 2 j + 1 ) ( N odd ) , λ j e := ( 2 j + 1 ) ( 2 j ) ( N even ) , p k ( ω ) := j < k ∏ ( ω + λ j ) ,
with p 0 = 1 p_0=1 p 0 = 1 and λ \lambda λ taken from the relevant parity; p k ( T ) = ∏ j < k ( T + λ j ) p_k(T)=\prod_{j<k}(T+\lambda_j) p k ( T ) = ∏ j < k ( T + λ j ) acts on functions.
Lemma 7.2 (Bridge lemma). For every F F F with F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 and every k ≥ 0 k\geq0 k ≥ 0 ,
( p k ( T ) F ) ( 1 ) = ( k ! ) 2 ∑ y = 1 k + 1 β k ( y ) F ( y ) , β k ( y ) = { ( 2 k + 2 k + 1 − y ) , N odd , y k + 1 ( 2 k + 2 k + 1 − y ) , N even . (p_k(T)F)(1)=(k!)^2\sum_{y=1}^{k+1}\beta_k(y)F(y),\qquad
\beta_k(y)=
\begin{cases}
\binom{2k+2}{k+1-y}, & N\ \text{odd},\\
\frac{y}{k+1}\binom{2k+2}{k+1-y}, & N\ \text{even}.
\end{cases} ( p k ( T ) F ) ( 1 ) = ( k ! ) 2 y = 1 ∑ k + 1 β k ( y ) F ( y ) , β k ( y ) = { ( k + 1 − y 2 k + 2 ) , k + 1 y ( k + 1 − y 2 k + 2 ) , N odd , N even .
The coefficients are positive: The number ( 2 k + 2 k + 1 − y ) \binom{2k+2}{k+1-y} ( k + 1 − y 2 k + 2 ) counts ± 1 \pm1 ± 1 walks of length 2 k + 2 2k+2 2 k + 2 from 0 0 0 to 2 y 2y 2 y , and y k + 1 ( 2 k + 2 k + 1 − y ) \frac{y}{k+1}\binom{2k+2}{k+1-y} k + 1 y ( k + 1 − y 2 k + 2 ) counts those that do not return to 0 0 0 (a ballot number).
Proof. Induction on k k k ; for k = 0 k=0 k = 0 both sides are F ( 1 ) F(1) F ( 1 ) . For a linear functional L ( F ) = ∑ y ≥ 1 a ( y ) F ( y ) \mathcal{L}(F)=\sum_{y\geq1}a(y)F(y) L ( F ) = ∑ y ≥ 1 a ( y ) F ( y ) (with a ( 0 ) = 0 a(0)=0 a ( 0 ) = 0 ), the definition of T T T and F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 give
L ( T F ) = ∑ y ≥ 1 F ( y ) [ ( y − 1 ) 2 a ( y − 1 ) + 2 y 2 a ( y ) + ( y + 1 ) 2 a ( y + 1 ) ] . (2) \mathcal{L}(TF)=\sum_{y\geq1}F(y)\left[(y-1)^2a(y-1)+2y^2a(y)+(y+1)^2a(y+1)\right]. \tag*{(2)} L ( T F ) = y ≥ 1 ∑ F ( y ) [ ( y − 1 ) 2 a ( y − 1 ) + 2 y 2 a ( y ) + ( y + 1 ) 2 a ( y + 1 ) ] . (2)
So it suffices to verify, with n = k + 1 n=k+1 n = k + 1 , the recurrence n 2 β n ( y ) = ( y − 1 ) 2 β k ( y − 1 ) + ( 2 y 2 + λ k ) β k ( y ) + ( y + 1 ) 2 β k ( y + 1 ) n^2\beta_n(y)=(y-1)^2\beta_k(y-1)+(2y^2+\lambda_k)\beta_k(y)+(y+1)^2\beta_k(y+1) n 2 β n ( y ) = ( y − 1 ) 2 β k ( y − 1 ) + ( 2 y 2 + λ k ) β k ( y ) + ( y + 1 ) 2 β k ( y + 1 ) (the factor n 2 n^2 n 2 comes from ( k ! ) 2 → ( n ! ) 2 (k!)^2\to(n!)^2 ( k ! ) 2 → ( n ! ) 2 ). For odd N N N , λ k = 2 n ( 2 n − 1 ) \lambda_k=2n(2n-1) λ k = 2 n ( 2 n − 1 ) , and we need
n 2 ( 2 n + 2 n + 1 − y ) = ( y − 1 ) 2 ( 2 n n + 1 − y ) + ( 2 y 2 + 2 n ( 2 n − 1 ) ) ( 2 n n − y ) + ( y + 1 ) 2 ( 2 n n − 1 − y ) . n^2\binom{2n+2}{n+1-y}=(y-1)^2\binom{2n}{n+1-y}+(2y^2+2n(2n-1))\binom{2n}{n-y}+(y+1)^2\binom{2n}{n-1-y}. n 2 ( n + 1 − y 2 n + 2 ) = ( y − 1 ) 2 ( n + 1 − y 2 n ) + ( 2 y 2 + 2 n ( 2 n − 1 )) ( n − y 2 n ) + ( y + 1 ) 2 ( n − 1 − y 2 n ) .
For 1 ≤ y ≤ n 1\le y\le n 1 ≤ y ≤ n , divide by ( 2 n n − y ) \binom{2n}{n-y} ( n − y 2 n ) and multiply by ( n + 1 ) 2 − y 2 (n+1)^2-y^2 ( n + 1 ) 2 − y 2 . The left side becomes 2 n 2 ( n + 1 ) ( 2 n + 1 ) 2n^2(n+1)(2n+1) 2 n 2 ( n + 1 ) ( 2 n + 1 ) . On the right, the first and third terms give 2 y 4 + ( 2 n 2 − 6 n − 2 ) y 2 + 2 n 2 + 2 n 2y^4+(2n^2-6n-2)y^2+2n^2+2n 2 y 4 + ( 2 n 2 − 6 n − 2 ) y 2 + 2 n 2 + 2 n and the middle term gives − 2 y 4 − ( 2 n 2 − 6 n − 2 ) y 2 + 4 n 4 + 6 n 3 − 2 n -2y^4-(2n^2-6n-2)y^2+4n^4+6n^3-2n − 2 y 4 − ( 2 n 2 − 6 n − 2 ) y 2 + 4 n 4 + 6 n 3 − 2 n ; the sum is 4 n 4 + 6 n 3 + 2 n 2 = 2 n 2 ( n + 1 ) ( 2 n + 1 ) 4n^4+6n^3+2n^2=2n^2(n+1)(2n+1) 4 n 4 + 6 n 3 + 2 n 2 = 2 n 2 ( n + 1 ) ( 2 n + 1 ) . For y = n + 1 y=n+1 y = n + 1 only the first term survives and both sides equal n 2 n^2 n 2 ; for y > n + 1 y>n+1 y > n + 1 all terms vanish. For even N N N , λ k = ( 2 n − 1 ) ( 2 n − 2 ) \lambda_k=(2n-1)(2n-2) λ k = ( 2 n − 1 ) ( 2 n − 2 ) , and the same computation with the extra factor y / n y/n y / n gives 2 n 3 ( 2 n + 1 ) y 2n^3(2n+1)y 2 n 3 ( 2 n + 1 ) y on both sides after multiplication by n ( ( n + 1 ) 2 − y 2 ) n((n+1)^2-y^2) n (( n + 1 ) 2 − y 2 ) for 1 ≤ y ≤ n 1\le y\le n 1 ≤ y ≤ n ; for y = n + 1 y=n+1 y = n + 1 both sides equal n 2 n^2 n 2 again.
Corollary 7.3. For odd N N N , ( p k ( T ) x 3 ) ( 1 ) = ( 2 k + 2 ) ! 2 (p_k(T)x^3)(1)=\frac{(2k+2)!}{2} ( p k ( T ) x 3 ) ( 1 ) = 2 ( 2 k + 2 )! ; for even N N N , ( p k ( T ) x 2 ) ( 1 ) = ( 2 k + 1 ) ! (p_k(T)x^2)(1)=(2k+1)! ( p k ( T ) x 2 ) ( 1 ) = ( 2 k + 1 )! .
Proof. Let n = k + 1 n=k+1 n = k + 1 . The ballot identity y n ( 2 n n − y ) = ( 2 n − 1 n − y ) − ( 2 n − 1 n − y − 1 ) \frac{y}{n}\binom{2n}{n-y}=\binom{2n-1}{n-y}-\binom{2n-1}{n-y-1} n y ( n − y 2 n ) = ( n − y 2 n − 1 ) − ( n − y − 1 2 n − 1 ) telescopes to ∑ y ≥ 1 y ( 2 n n − y ) = n 2 ( 2 n n ) \sum_{y\ge1}y\binom{2n}{n-y}=\frac{n}{2}\binom{2n}{n} ∑ y ≥ 1 y ( n − y 2 n ) = 2 n ( n 2 n ) . With y 2 = n 2 − ( n − y ) ( n + y ) y^2=n^2-(n-y)(n+y) y 2 = n 2 − ( n − y ) ( n + y ) and ( n − y ) ( n + y ) ( 2 n n − y ) = 2 n ( 2 n − 1 ) ( 2 n − 2 n − 1 − y ) (n-y)(n+y)\binom{2n}{n-y}=2n(2n-1)\binom{2n-2}{n-1-y} ( n − y ) ( n + y ) ( n − y 2 n ) = 2 n ( 2 n − 1 ) ( n − 1 − y 2 n − 2 ) ,
∑ y ≥ 1 y 3 ( 2 n n − y ) = n 2 ⋅ n 2 ( 2 n n ) − 2 n ( 2 n − 1 ) ⋅ n − 1 2 ( 2 n − 2 n − 1 ) = n 2 2 ( 2 n n ) . \sum_{y\ge1}y^3\binom{2n}{n-y}=n^2\cdot\frac{n}{2}\binom{2n}{n}-2n(2n-1)\cdot\frac{n-1}{2}\binom{2n-2}{n-1}=\frac{n^2}{2}\binom{2n}{n}. y ≥ 1 ∑ y 3 ( n − y 2 n ) = n 2 ⋅ 2 n ( n 2 n ) − 2 n ( 2 n − 1 ) ⋅ 2 n − 1 ( n − 1 2 n − 2 ) = 2 n 2 ( n 2 n ) .
By Lemma 7.2, the odd case gives ( k ! ) 2 ⋅ n 2 2 ( 2 n n ) = ( 2 k + 2 ) ! 2 (k!)^2\cdot\frac{n^2}{2}\binom{2n}{n}=\frac{(2k+2)!}{2} ( k ! ) 2 ⋅ 2 n 2 ( n 2 n ) = 2 ( 2 k + 2 )! , and the even case gives ( k ! ) 2 ⋅ 1 n ⋅ n 2 2 ( 2 n n ) = ( 2 k + 1 ) ! (k!)^2\cdot\frac{1}{n}\cdot\frac{n^2}{2}\binom{2n}{n}=(2k+1)! ( k ! ) 2 ⋅ n 1 ⋅ 2 n 2 ( n 2 n ) = ( 2 k + 1 )! .
An alternating sum and a triangle
Lemma 7.4 (Triangle). Let t 0 , 0 = 1 t_{0,0}=1 t 0 , 0 = 1 , t s , k = 0 t_{s,k}=0 t s , k = 0 outside 0 ≤ k ≤ s 0\le k\le s 0 ≤ k ≤ s , and t s , k = t s − 1 , k − 1 + λ k t s − 1 , k t_{s,k}=t_{s-1,k-1}+\lambda_k t_{s-1,k} t s , k = t s − 1 , k − 1 + λ k t s − 1 , k . Then, for each parity, ω s = ∑ k = 0 s ( − 1 ) s − k t s , k p k ( ω ) \omega^s=\sum_{k=0}^{s}(-1)^{s-k}t_{s,k}p_k(\omega) ω s = ∑ k = 0 s ( − 1 ) s − k t s , k p k ( ω ) as polynomials in ω \omega ω .
Proof. Induction on s s s , using ω p k = p k + 1 − λ k p k \omega p_k=p_{k+1}-\lambda_kp_k ω p k = p k + 1 − λ k p k : ω ⋅ ω s − 1 = ∑ k ( − 1 ) s − 1 − k t s − 1 , k ( p k + 1 − λ k p k ) = ∑ k ( − 1 ) s − k [ t s − 1 , k − 1 + λ k t s − 1 , k ] p k \omega\cdot\omega^{s-1}=\sum_k(-1)^{s-1-k}t_{s-1,k}(p_{k+1}-\lambda_kp_k)=\sum_k(-1)^{s-k}[t_{s-1,k-1}+\lambda_kt_{s-1,k}]p_k ω ⋅ ω s − 1 = ∑ k ( − 1 ) s − 1 − k t s − 1 , k ( p k + 1 − λ k p k ) = ∑ k ( − 1 ) s − k [ t s − 1 , k − 1 + λ k t s − 1 , k ] p k .
The recurrence gives t s , k = h s − k ( λ 0 , … , λ k ) t_{s,k}=h_{s-k}(\lambda_0,\ldots,\lambda_k) t s , k = h s − k ( λ 0 , … , λ k ) , a complete homogeneous symmetric function. In terms of the Jacobi–Stirling numbers of the second kind JS n k ( z ) \operatorname{JS}_n^k(z) JS n k ( z ) of Gelineau and Zeng [6 ] (JS n k = JS n − 1 k − 1 + k ( k + z ) JS n − 1 k \operatorname{JS}_n^k=\operatorname{JS}_{n-1}^{k-1}+k(k+z)\operatorname{JS}_{n-1}^k JS n k = JS n − 1 k − 1 + k ( k + z ) JS n − 1 k ),
t s , k e = 4 s − k JS s k ( 1 2 ) , t s , k o = 4 s − k JS s + 1 k + 1 ( − 1 2 ) , t_{s,k}^{e}=4^{s-k}\operatorname{JS}_s^k\left(\frac{1}{2}\right),\qquad t_{s,k}^{o}=4^{s-k}\operatorname{JS}_{s+1}^{k+1}\left(-\frac{1}{2}\right), t s , k e = 4 s − k JS s k ( 2 1 ) , t s , k o = 4 s − k JS s + 1 k + 1 ( − 2 1 ) ,
since both sides are h s − k h_{s-k} h s − k at the same nodes (λ j e = 4 j ( j + 1 2 ) \lambda_j^e=4j(j+\frac{1}{2}) λ j e = 4 j ( j + 2 1 ) and λ i o = 4 i ( i − 1 2 ) \lambda_i^o=4i(i-\frac{1}{2}) λ i o = 4 i ( i − 2 1 ) with i = j + 1 i=j+1 i = j + 1 ; a zero node does not change h h h ). The two sets of nodes, K ( K + 1 ) K(K+1) K ( K + 1 ) for K K K even and for K K K odd, together form the Legendre eigenvalues K ( K + 1 ) K(K+1) K ( K + 1 ) ; since h h h of a union of two disjoint sets of nodes is ∑ i h i ( first set ) h n − i ( second set ) \sum_i h_i(\text{first set})h_{n-i}(\text{second set}) ∑ i h i ( first set ) h n − i ( second set ) , the Legendre–Stirling numbers of the second kind [1 ] , PS ( n , k ) = h n − k ( 0 ⋅ 1 , 1 ⋅ 2 , … , k ( k + 1 ) ) \operatorname{PS}(n,k)=h_{n-k}(0\cdot1,1\cdot2,\ldots,k(k+1)) PS ( n , k ) = h n − k ( 0 ⋅ 1 , 1 ⋅ 2 , … , k ( k + 1 )) , satisfy PS ( n , k ) = ∑ i t a + i , a e t b + n − k − i , b o \operatorname{PS}(n,k)=\sum_i t_{a+i,a}^{e}t_{b+n-k-i,b}^{o} PS ( n , k ) = ∑ i t a + i , a e t b + n − k − i , b o with a = ⌊ k / 2 ⌋ a=\lfloor k/2\rfloor a = ⌊ k /2 ⌋ , b = ⌈ k / 2 ⌉ − 1 b=\lceil k/2\rceil-1 b = ⌈ k /2 ⌉ − 1 (k ≥ 1 k\ge1 k ≥ 1 ).
Theorem 7.5 (Alternating sum). For q ≥ 1 q\ge1 q ≥ 1 ,
W ( 2 q + 1 ) = 2 ∑ k = 0 q − 1 ( − 1 ) q − 1 − k t q − 1 , k o ( 2 k + 2 ) ! , W(2q+1)=2\sum_{k=0}^{q-1}(-1)^{q-1-k}t_{q-1,k}^{o}(2k+2)!, W ( 2 q + 1 ) = 2 k = 0 ∑ q − 1 ( − 1 ) q − 1 − k t q − 1 , k o ( 2 k + 2 )! , W ( 2 q + 2 ) = 2 ∑ k = 0 q ( − 1 ) q − k t q , k e ( 2 k + 1 ) ! . W(2q+2)=2\sum_{k=0}^{q}(-1)^{q-k}t_{q,k}^{e}(2k+1)!. W ( 2 q + 2 ) = 2 k = 0 ∑ q ( − 1 ) q − k t q , k e ( 2 k + 1 )! .
Proof. Lemma 7.4 is a polynomial identity, so ω \omega ω may be replaced by T T T . Apply it to x 3 x^3 x 3 (odd N N N ) or x 2 x^2 x 2 (even N N N ), evaluate at x = 1 x=1 x = 1 , and use Lemma 7.1 and Corollary 7.3.
For F ( x ) = x 3 F(x)=x^3 F ( x ) = x 3 (odd case) or F ( x ) = x 2 F(x)=x^2 F ( x ) = x 2 (even case), ( p k ( T ) F ) ( 1 ) (p_k(T)F)(1) ( p k ( T ) F ) ( 1 ) is the total weight of “lazy” paths, which at each step either take a step of T T T or pause with weight λ j \lambda_j λ j , with terminal weight F ( y ) F(y) F ( y ) at the final height y y y ; the alternating sum removes the pauses by inclusion–exclusion. Appendix B gives a second proof, directly from W ( N ) = per M W(N)=\operatorname{per} M W ( N ) = per M by a sign-reversing involution. For N = 7 N=7 N = 7 (odd, q = 3 q=3 q = 3 ) we have λ 0 o = 2 \lambda_0^{\mathrm{o}}=2 λ 0 o = 2 , λ 1 o = 12 \lambda_1^{\mathrm{o}}=12 λ 1 o = 12 , t 2 , ⋅ = ( 4 , 14 , 1 ) t_{2,\cdot}=(4,14,1) t 2 , ⋅ = ( 4 , 14 , 1 ) , and W ( 7 ) = 2 ( 4 ⋅ 2 ! − 14 ⋅ 4 ! + 1 ⋅ 6 ! ) = 2 ( 8 − 336 + 720 ) = 784 W(7)=2(4\cdot2!-14\cdot4!+1\cdot6!)=2(8-336+720)=784 W ( 7 ) = 2 ( 4 ⋅ 2 ! − 14 ⋅ 4 ! + 1 ⋅ 6 !) = 2 ( 8 − 336 + 720 ) = 784 . The cancellation grows with N N N : For N = 20 N=20 N = 20 the term of largest absolute value is about 368.5 368.5 368.5 times W ( 20 ) / 2 W(20)/2 W ( 20 ) /2 . Theorem 7.5 computes W ( N ) W(N) W ( N ) with O ( N 2 ) O(N^2) O ( N 2 ) integer operations; the values in Tables 1 and 2 were computed in this way.
Moment representation
Fact 7.6 (Total mass of the continuous dual Hahn weight; Wilson [15 ] , [4 (18.25.2), (18.25.7)–(18.25.8)] ). For α , β , γ > 0 \alpha,\beta,\gamma>0 α , β , γ > 0 ,
1 2 π ∫ 0 ∞ ∣ Γ ( α + i x ) Γ ( β + i x ) Γ ( γ + i x ) Γ ( 2 i x ) ∣ 2 d x = Γ ( α + β ) Γ ( α + γ ) Γ ( β + γ ) . \frac{1}{2\pi}\int_0^\infty\left|\frac{\Gamma(\alpha+ix)\Gamma(\beta+ix)\Gamma(\gamma+ix)}{\Gamma(2ix)}\right|^2\,dx=\Gamma(\alpha+\beta)\Gamma(\alpha+\gamma)\Gamma(\beta+\gamma). 2 π 1 ∫ 0 ∞ Γ ( 2 i x ) Γ ( α + i x ) Γ ( β + i x ) Γ ( γ + i x ) 2 d x = Γ ( α + β ) Γ ( α + γ ) Γ ( β + γ ) .
Let μ α , β , γ \mu_{\alpha,\beta,\gamma} μ α , β , γ be the probability measure on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) whose density is the integrand above divided by 2 π Γ ( α + β ) Γ ( α + γ ) Γ ( β + γ ) 2\pi\Gamma(\alpha+\beta)\Gamma(\alpha+\gamma)\Gamma(\beta+\gamma) 2 π Γ ( α + β ) Γ ( α + γ ) Γ ( β + γ ) , and let ( z ) k : = z ( z + 1 ) ⋯ ( z + k − 1 ) (z)_k:=z(z+1)\cdots(z+k-1) ( z ) k := z ( z + 1 ) ⋯ ( z + k − 1 ) .
Lemma 7.7. E μ α , β , γ [ ( α + i x ) k ( α − i x ) k ] = ( α + β ) k ( α + γ ) k \mathbb{E}_{\mu_{\alpha,\beta,\gamma}}[(\alpha+ix)_k(\alpha-ix)_k]=(\alpha+\beta)_k(\alpha+\gamma)_k E μ α , β , γ [( α + i x ) k ( α − i x ) k ] = ( α + β ) k ( α + γ ) k ; in particular all moments are finite.
Proof. ∣ Γ ( α + i x ) ∣ 2 ( α + i x ) k ( α − i x ) k = ∣ Γ ( α + k + i x ) ∣ 2 |\Gamma(\alpha+ix)|^2(\alpha+ix)_k(\alpha-ix)_k=|\Gamma(\alpha+k+ix)|^2 ∣Γ ( α + i x ) ∣ 2 ( α + i x ) k ( α − i x ) k = ∣Γ ( α + k + i x ) ∣ 2 , so the left side is the total mass with α \alpha α replaced by α + k \alpha+k α + k divided by the original total mass, which by Fact 7.6 is the right side. Moreover ( α + i x ) k ( α − i x ) k = ∏ j < k ( ( α + j ) 2 + x 2 ) ≥ x 2 k (\alpha+ix)_k(\alpha-ix)_k=\prod_{j<k}((\alpha+j)^2+x^2)\ge x^{2k} ( α + i x ) k ( α − i x ) k = ∏ j < k (( α + j ) 2 + x 2 ) ≥ x 2 k .
Theorem 7.8 (Moment representation). Let ω : = 4 ( x 2 + 1 16 ) = 4 ∣ x + i 4 ∣ 2 \omega:=4\left(x^2+\frac{1}{16}\right)=4\left|x+\frac{i}{4}\right|^2 ω := 4 ( x 2 + 16 1 ) = 4 x + 4 i 2 , μ o : = μ 3 / 4 , 3 / 4 , 5 / 4 \mu_{\mathrm{o}}:=\mu_{3/4,3/4,5/4} μ o := μ 3/4 , 3/4 , 5/4 and μ e : = μ 1 / 4 , 3 / 4 , 5 / 4 \mu_{\mathrm{e}}:=\mu_{1/4,3/4,5/4} μ e := μ 1/4 , 3/4 , 5/4 . For every polynomial Q Q Q ,
( Q ( T ) x 3 ) ( 1 ) = E μ o [ Q ( ω ) ] , ( Q ( T ) x 2 ) ( 1 ) = E μ e [ Q ( ω ) ] . (Q(T)x^3)(1)=\mathbb{E}_{\mu_{\mathrm{o}}}[Q(\omega)],\qquad(Q(T)x^2)(1)=\mathbb{E}_{\mu_{\mathrm{e}}}[Q(\omega)]. ( Q ( T ) x 3 ) ( 1 ) = E μ o [ Q ( ω )] , ( Q ( T ) x 2 ) ( 1 ) = E μ e [ Q ( ω )] . Consequently W ( 2 q + 1 ) = 4 E μ o [ ω q − 1 ] W(2q+1)=4\mathbb{E}_{\mu_{\mathrm{o}}}[\omega^{q-1}] W ( 2 q + 1 ) = 4 E μ o [ ω q − 1 ] and W ( 2 q + 2 ) = 2 E μ e [ ω q ] W(2q+2)=2\mathbb{E}_{\mu_{\mathrm{e}}}[\omega^q] W ( 2 q + 2 ) = 2 E μ e [ ω q ] .
Proof. Both sides are linear in Q Q Q , so it suffices to take Q = p k Q=p_k Q = p k (with λ = λ o \lambda=\lambda^{\mathrm{o}} λ = λ o in the first identity and λ = λ e \lambda=\lambda^{\mathrm{e}} λ = λ e in the second); the left side is given by Corollary 7.3. For the right side in the odd case, 1 4 + ( 2 j + 2 ) ( 2 j + 1 ) = 4 ( j + 3 4 ) 2 \frac14+(2j+2)(2j+1)=4\left(j+\frac34\right)^2 4 1 + ( 2 j + 2 ) ( 2 j + 1 ) = 4 ( j + 4 3 ) 2 , so ω + λ j o = 4 ( 3 4 + j + i x ) ( 3 4 + j − i x ) \omega+\lambda_j^{\mathrm{o}}=4\left(\frac34+j+ix\right)\left(\frac34+j-ix\right) ω + λ j o = 4 ( 4 3 + j + i x ) ( 4 3 + j − i x ) and p k ( ω ) = 4 k ( 3 4 + i x ) k ( 3 4 − i x ) k p_k(\omega)=4^k\left(\frac34+ix\right)_k\left(\frac34-ix\right)_k p k ( ω ) = 4 k ( 4 3 + i x ) k ( 4 3 − i x ) k . Lemma 7.7 with ( 3 4 , 3 4 , 5 4 ) \left(\frac34,\frac34,\frac54\right) ( 4 3 , 4 3 , 4 5 ) gives E μ o p k = 4 k ( 3 2 ) k ( 2 ) k = ( 2 k + 2 ) ! 2 \mathbb{E}_{\mu_{\mathrm{o}}}p_k=4^k\left(\frac32\right)_k(2)_k=\frac{(2k+2)!}{2} E μ o p k = 4 k ( 2 3 ) k ( 2 ) k = 2 ( 2 k + 2 )! . In the even case 1 4 + ( 2 j + 1 ) ( 2 j ) = 4 ( j + 1 4 ) 2 \frac14+(2j+1)(2j)=4\left(j+\frac14\right)^2 4 1 + ( 2 j + 1 ) ( 2 j ) = 4 ( j + 4 1 ) 2 , p k ( ω ) = 4 k ( 1 4 + i x ) k ( 1 4 − i x ) k p_k(\omega)=4^k\left(\frac14+ix\right)_k\left(\frac14-ix\right)_k p k ( ω ) = 4 k ( 4 1 + i x ) k ( 4 1 − i x ) k , and ( 1 4 , 3 4 , 5 4 ) \left(\frac14,\frac34,\frac54\right) ( 4 1 , 4 3 , 4 5 ) gives E μ e p k = 4 k ( 1 ) k ( 3 2 ) k = ( 2 k + 1 ) ! \mathbb{E}_{\mu_{\mathrm{e}}}p_k=4^k(1)_k\left(\frac32\right)_k=(2k+1)! E μ e p k = 4 k ( 1 ) k ( 2 3 ) k = ( 2 k + 1 )! . Finally use Lemma 7.1.
For N = 7 N=7 N = 7 , Lemma 7.4 gives ω 2 = p 2 − 14 p 1 + 4 p 0 \omega^2=p_2-14p_1+4p_0 ω 2 = p 2 − 14 p 1 + 4 p 0 , so E μ o ω 2 = 360 − 168 + 4 = 196 \mathbb{E}_{\mu_{\mathrm{o}}}\omega^2=360-168+4=196 E μ o ω 2 = 360 − 168 + 4 = 196 and W ( 7 ) = 4 ⋅ 196 = 784 W(7)=4\cdot196=784 W ( 7 ) = 4 ⋅ 196 = 784 ; the number 196 is the integral of a positive function.
A unified formula. In the odd case one factor ω \omega ω can be absorbed: The densities of μ o \mu_{\mathrm{o}} μ o and μ ∗ : = μ 1 / 4 , 3 / 4 , 3 / 4 \mu^*:=\mu_{1/4,3/4,3/4} μ ∗ := μ 1/4 , 3/4 , 3/4 have ratio proportional to ∣ Γ ( 5 4 + i x ) ∣ 2 / ∣ Γ ( 1 4 + i x ) ∣ 2 = x 2 + 1 16 = ω / 4 |\Gamma(\frac54+ix)|^2/|\Gamma(\frac14+ix)|^2=x^2+\frac1{16}=\omega/4 ∣Γ ( 4 5 + i x ) ∣ 2 /∣Γ ( 4 1 + i x ) ∣ 2 = x 2 + 16 1 = ω /4 , and E μ ∗ [ ω / 4 ] = 1 \mathbb{E}_{\mu^*}[\omega/4]=1 E μ ∗ [ ω /4 ] = 1 by Lemma 7.7 with k = 1 k=1 k = 1 ; so d μ o = ω 4 d μ ∗ d\mu_{\mathrm{o}}=\frac{\omega}{4}d\mu^* d μ o = 4 ω d μ ∗ and
W ( 2 s + 1 ) = E μ 1 / 4 , 3 / 4 , 3 / 4 [ ω s ] , W ( 2 s + 2 ) = 2 E μ 1 / 4 , 3 / 4 , 5 / 4 [ ω s ] ( s ≥ 0 ) . W(2s+1)=\mathbb{E}_{\mu_{1/4,3/4,3/4}}[\omega^s],\qquad W(2s+2)=2\mathbb{E}_{\mu_{1/4,3/4,5/4}}[\omega^s]\qquad(s\ge0). W ( 2 s + 1 ) = E μ 1/4 , 3/4 , 3/4 [ ω s ] , W ( 2 s + 2 ) = 2 E μ 1/4 , 3/4 , 5/4 [ ω s ] ( s ≥ 0 ) .
(for s = 0 s = 0 s = 0 these read W ( 1 ) = 1 W(1) = 1 W ( 1 ) = 1 and W ( 2 ) = 2 W(2) = 2 W ( 2 ) = 2 ). Both parities use μ 1 / 4 , 3 / 4 , γ \mu_{1/4,3/4,\gamma} μ 1/4 , 3/4 , γ , with γ = 3 4 \gamma= \frac{3}{4} γ = 4 3 or 5 4 \frac{5}{4} 4 5 . The parameters 1 4 \frac{1}{4} 4 1 and 3 4 \frac{3}{4} 4 3 are related by the reflection formula Γ ( z ) Γ ( 1 − z ) = π / sin π z \Gamma(z)\Gamma(1-z) = \pi/\sin\pi z Γ ( z ) Γ ( 1 − z ) = π / sin π z ; with the duplication formula it gives
∣ Γ ( 1 4 + i x ) Γ ( 3 4 + i x ) ∣ 2 ∣ Γ ( 2 i x ) ∣ 2 = 4 π x tanh ( 2 π x ) \frac{\left|\Gamma\left(\frac{1}{4}+ix\right)\Gamma\left(\frac{3}{4}+ix\right)\right|^2}{|\Gamma(2ix)|^2} = 4\pi x\tanh(2\pi x) ∣Γ ( 2 i x ) ∣ 2 Γ ( 4 1 + i x ) Γ ( 4 3 + i x ) 2 = 4 π x tanh ( 2 π x )
(see the proof of Lemma 7.10), so μ 1 / 4 , 3 / 4 , γ \mu_{1/4,3/4,\gamma} μ 1/4 , 3/4 , γ has density 4 π x tanh ( 2 π x ) ∣ Γ ( γ + i x ) ∣ 2 \frac{4}{\sqrt{\pi}}x\tanh(2\pi x)|\Gamma(\gamma+ix)|^2 π 4 x tanh ( 2 π x ) ∣Γ ( γ + i x ) ∣ 2 . Substituting ∣ Γ ( 5 4 + i x ) ∣ 2 = ( x 2 + 1 16 ) ∣ Γ ( 1 4 + i x ) ∣ 2 \left|\Gamma\left(\frac{5}{4}+ix\right)\right|^2 = \left(x^2+\frac{1}{16}\right)\left|\Gamma\left(\frac{1}{4}+ix\right)\right|^2 Γ ( 4 5 + i x ) 2 = ( x 2 + 16 1 ) Γ ( 4 1 + i x ) 2 combines the two parities:
W ( N ) = 2 N + 1 π ∫ 0 ∞ x tanh ( 2 π x ) ( x 2 + 1 16 ) ⌊ N / 2 ⌋ ∣ Γ ( 1 4 + { N 2 } + i x ) ∣ 2 d x ( N ≥ 1 ) , (3) W(N) = \frac{2^{N+1}}{\sqrt{\pi}}\int_0^\infty x\tanh(2\pi x)\left(x^2+\frac{1}{16}\right)^{\lfloor N/2\rfloor}\left|\Gamma\left(\frac{1}{4}+\left\{\frac{N}{2}\right\}+ix\right)\right|^2\,dx \qquad(N\ge1), \tag*{(3)} W ( N ) = π 2 N + 1 ∫ 0 ∞ x tanh ( 2 π x ) ( x 2 + 16 1 ) ⌊ N /2 ⌋ Γ ( 4 1 + { 2 N } + i x ) 2 d x ( N ≥ 1 ) , (3)
where { ⋅ } \{\cdot\} { ⋅ } denotes the fractional part. The reflection formula is used only to turn the common pair ( 1 4 , 3 4 ) \left(\frac{1}{4},\frac{3}{4}\right) ( 4 1 , 4 3 ) into the elementary factor x tanh ( 2 π x ) x\tanh(2\pi x) x tanh ( 2 π x ) ; the parity sits entirely in the third parameter.
The Genocchi family
By the theory of Flajolet [5 ] and Viennot [13 ] , the weights of Motzkin paths are the coefficients of a J-fraction. In the variable u = x 2 + α 2 u=x^2+\alpha^2 u = x 2 + α 2 , the monic orthogonal polynomials P n P_n P n of μ α , β , γ \mu_{\alpha,\beta,\gamma} μ α , β , γ (the continuous dual Hahn polynomials [8 §9.3] ) satisfy u P n = P n + 1 + ( A n + C n ) P n + A n − 1 C n P n − 1 uP_n=P_{n+1}+(A_n+C_n)P_n+A_{n-1}C_nP_{n-1} u P n = P n + 1 + ( A n + C n ) P n + A n − 1 C n P n − 1 (P − 1 = 0 P_{-1}=0 P − 1 = 0 , P 0 = 1 P_0=1 P 0 = 1 ) with A n = ( n + α + β ) ( n + α + γ ) A_n=(n+\alpha+\beta)(n+\alpha+\gamma) A n = ( n + α + β ) ( n + α + γ ) and C n = n ( n + β + γ − 1 ) C_n=n(n+\beta+\gamma-1) C n = n ( n + β + γ − 1 ) . This J-fraction is the even contraction of the S-fraction with θ 2 k − 1 = A k − 1 \theta_{2k-1}=A_{k-1} θ 2 k − 1 = A k − 1 and θ 2 k = C k \theta_{2k}=C_k θ 2 k = C k (with θ 0 : = 0 \theta_0:=0 θ 0 := 0 ; indeed C 0 = 0 C_0=0 C 0 = 0 , A n + C n = θ 2 n + θ 2 n + 1 A_n+C_n=\theta_{2n}+\theta_{2n+1} A n + C n = θ 2 n + θ 2 n + 1 and A n − 1 C n = θ 2 n − 1 θ 2 n A_{n-1}C_n=\theta_{2n-1}\theta_{2n} A n − 1 C n = θ 2 n − 1 θ 2 n ). The definition of μ α , β , γ \mu_{\alpha,\beta,\gamma} μ α , β , γ extends to α = 0 \alpha=0 α = 0 , and Fact 7.6 and Lemma 7.7 remain valid by dominated convergence as α → 0 + \alpha\to0^+ α → 0 + : For 0 < α ≤ 1 0<\alpha\le1 0 < α ≤ 1 , Fact 7.11 gives ∣ Γ ( α + i x ) ∣ 2 = ∣ Γ ( 1 + α + i x ) ∣ 2 / ( α 2 + x 2 ) ≤ Γ ( 1 + α ) 2 ∣ Γ ( 2 + i x ) ∣ 2 / ( α 2 + x 2 ) |\Gamma(\alpha+ix)|^2=|\Gamma(1+\alpha+ix)|^2/(\alpha^2+x^2)\le\Gamma(1+\alpha)^2|\Gamma(2+ix)|^2/(\alpha^2+x^2) ∣Γ ( α + i x ) ∣ 2 = ∣Γ ( 1 + α + i x ) ∣ 2 / ( α 2 + x 2 ) ≤ Γ ( 1 + α ) 2 ∣Γ ( 2 + i x ) ∣ 2 / ( α 2 + x 2 ) . With ∣ Γ ( 2 i x ) ∣ − 2 = 2 x sinh ( 2 π x ) / π |\Gamma(2ix)|^{-2}=2x\sinh(2\pi x)/\pi ∣Γ ( 2 i x ) ∣ − 2 = 2 x sinh ( 2 π x ) / π , the integrand of Fact 7.6, times any fixed polynomial in x 2 x^2 x 2 , is therefore bounded on ( 0 , 1 ] (0,1] ( 0 , 1 ] uniformly in α \alpha α , and on [ 1 , ∞ ) [1,\infty) [ 1 , ∞ ) it is at most a constant times the same integrand with α \alpha α replaced by 2 2 2 , which is integrable; for example d μ 0 , 1 , 1 = 2 π x 2 cosh ( π x ) sinh − 2 ( π x ) d x d\mu_{0,1,1}=2\pi x^2\cosh(\pi x)\sinh^{-2}(\pi x)\,dx d μ 0 , 1 , 1 = 2 π x 2 cosh ( π x ) sinh − 2 ( π x ) d x . For the four measures below, θ 2 k − 1 = k ( k + a ′ ) \theta_{2k-1}=k(k+a') θ 2 k − 1 = k ( k + a ′ ) and θ 2 k = k ( k + b ′ ) \theta_{2k}=k(k+b') θ 2 k = k ( k + b ′ ) :
Table 1 (PDF p. 20).
In the variable ω \omega ω itself the S-fractions of W W W have integer coefficients. The number W ( 2 s + 1 ) W(2s+1) W ( 2 s + 1 ) is the total weight of the Dyck paths of length 2 s 2s 2 s in which a down step from height h h h has weight θ h \theta_h θ h , where θ 2 k − 1 = ( 2 k ) 2 \theta_{2k-1}=(2k)^2 θ 2 k − 1 = ( 2 k ) 2 and θ 2 k = 2 k ( 2 k + 1 ) \theta_{2k}=2k(2k+1) θ 2 k = 2 k ( 2 k + 1 ) ( 4 , 6 , 16 , 20 , 36 , 42 , … ) (4,6,16,20,36,42,\ldots) ( 4 , 6 , 16 , 20 , 36 , 42 , … ) ; for W ( 2 s + 2 ) / 2 W(2s+2)/2 W ( 2 s + 2 ) /2 the weights are 2 k ( 2 k + 1 ) 2k(2k+1) 2 k ( 2 k + 1 ) and 2 k ( 2 k + 2 ) 2k(2k+2) 2 k ( 2 k + 2 ) ( 6 , 8 , 20 , 24 , … ) (6,8,20,24,\ldots) ( 6 , 8 , 20 , 24 , … ) . The median Genocchi numbers also occur directly among rainbow maps:
Corollary 7.9. The number of rainbow maps of order N = 2 q + 1 N=2q+1 N = 2 q + 1 with exactly q q q arcs pointing to the nearer end is the median Genocchi number H 2 q + 3 H_{2q+3} H 2 q + 3 ( 2 , 8 , 56 , 608 , 9440 , … (2,8,56,608,9440,\ldots ( 2 , 8 , 56 , 608 , 9440 , … for q = 1 , 2 , … ) q=1,2,\ldots) q = 1 , 2 , … ) , the number of D D D -permutations of [ 2 q ] [2q] [ 2 q ] [3 ] , that is, of permutations π \pi π of { 1 , … , 2 q } \{1,\ldots,2q\} { 1 , … , 2 q } with π ( i ) ≥ i \pi(i)\ge i π ( i ) ≥ i for odd i i i and π ( i ) ≤ i \pi(i)\le i π ( i ) ≤ i for even i i i .
Proof. Exactly q q q arcs point to the nearer end if and only if S q = q S_q=q S q = q , that is, x q + 1 = 1 x_{q+1}=1 x q + 1 = 1 . So the count is the total weight of the paths of § 3.1 from height 1 back to height 1. With height y = x − 1 y=x-1 y = x − 1 , this is the q q q th moment of the J-fraction with level weights 2 ( y + 1 ) 2 2(y+1)^2 2 ( y + 1 ) 2 and products of up and down weights y 2 ( y + 1 ) 2 y^2(y+1)^2 y 2 ( y + 1 ) 2 , which is the even contraction of the S-fraction θ 2 k − 1 = θ 2 k = k ( k + 1 ) \theta_{2k-1}=\theta_{2k}=k(k+1) θ 2 k − 1 = θ 2 k = k ( k + 1 ) of the shifted median Genocchi numbers [3 (2.38)–(2.39)] . □
We do not know a bijection between these rainbow maps and D-permutations, nor models of the same kind for the integer sequences W ( 2 s + 1 ) W(2s+1) W ( 2 s + 1 ) and W ( 2 s + 2 ) / 2 W(2s+2)/2 W ( 2 s + 2 ) /2 .
Asymptotics
It remains to estimate the moments E [ ω s ] = ∫ 4 s ( x 2 + 1 16 ) s d μ \mathbb{E}[\omega^s]=\int4^s(x^2+\frac{1}{16})^s\,d\mu E [ ω s ] = ∫ 4 s ( x 2 + 16 1 ) s d μ , where μ \mu μ is μ o \mu_o μ o or μ e \mu_e μ e , up to a polynomial factor in s s s . For this it suffices to bound the density above and below by functions of the form polynomial × e − π x \times e^{-\pi x} × e − π x . The s s s th moment of x 2 s x^{2s} x 2 s is then Γ ( 2 s + O ( 1 ) ) π − 2 s \Gamma(2s+O(1))\pi^{-2s} Γ ( 2 s + O ( 1 )) π − 2 s , and multiplying by 4 s 4^s 4 s gives ( 2 / π ) 2 s ( 2 s ) ! (2/\pi)^{2s}(2s)! ( 2/ π ) 2 s ( 2 s )! up to a polynomial factor. A finer asymptotic formula is given in Appendix A; it is not needed for the main theorem.
Lemma 7.10 (Density). Let α = 3 4 \alpha=\frac{3}{4} α = 4 3 (for μ o \mu_o μ o ) or 1 4 \frac{1}{4} 4 1 (for μ e \mu_e μ e ). The density of the measure is ψ α ( x ) = π − 3 / 2 ⋅ 4 π x ( x 2 + 1 16 ) tanh ( 2 π x ) ∣ Γ ( α + i x ) ∣ 2 \psi_\alpha(x)=\pi^{-3/2}\cdot4\pi x(x^2+\frac{1}{16})\tanh(2\pi x)|\Gamma(\alpha+ix)|^2 ψ α ( x ) = π − 3/2 ⋅ 4 π x ( x 2 + 16 1 ) tanh ( 2 π x ) ∣Γ ( α + i x ) ∣ 2 for x > 0 x>0 x > 0 .
Proof. We use three standard identities [4 (5.4.3), (5.4.4), (5.5.5)] : ∣ Γ ( i y ) ∣ 2 = π y sinh π y |\Gamma(iy)|^2=\frac{\pi}{y\sinh\pi y} ∣Γ ( i y ) ∣ 2 = y s i n h π y π , ∣ Γ ( 1 2 + i y ) ∣ 2 = π cosh π y |\Gamma(\frac{1}{2}+iy)|^2=\frac{\pi}{\cosh\pi y} ∣Γ ( 2 1 + i y ) ∣ 2 = c o s h π y π , and Γ ( 2 z ) = π − 1 / 2 2 2 z − 1 Γ ( z ) Γ ( z + 1 2 ) \Gamma(2z)=\pi^{-1/2}2^{2z-1}\Gamma(z)\Gamma(z+\frac{1}{2}) Γ ( 2 z ) = π − 1/2 2 2 z − 1 Γ ( z ) Γ ( z + 2 1 ) . The first gives ∣ Γ ( 2 i x ) ∣ − 2 = 2 x sinh 2 π x π |\Gamma(2ix)|^{-2}=\frac{2x\sinh2\pi x}{\pi} ∣Γ ( 2 i x ) ∣ − 2 = π 2 x s i n h 2 π x . The third with z = 1 4 + i x z=\frac{1}{4}+ix z = 4 1 + i x (so that ∣ 2 2 z − 1 ∣ 2 = 1 2 |2^{2z-1}|^2=\frac{1}{2} ∣ 2 2 z − 1 ∣ 2 = 2 1 ), together with the second, gives ∣ Γ ( 1 4 + i x ) Γ ( 3 4 + i x ) ∣ 2 = 2 π ∣ Γ ( 1 2 + 2 i x ) ∣ 2 cosh 2 π x = 2 π 2 cosh 2 2 π x |\Gamma(\frac{1}{4}+ix)\Gamma(\frac{3}{4}+ix)|^2=\frac{2\pi|\Gamma(\frac{1}{2}+2ix)|^2}{\cosh2\pi x}=\frac{2\pi^2}{\cosh^2 2\pi x} ∣Γ ( 4 1 + i x ) Γ ( 4 3 + i x ) ∣ 2 = c o s h 2 π x 2 π ∣Γ ( 2 1 + 2 i x ) ∣ 2 = c o s h 2 2 π x 2 π 2 . Also ∣ Γ ( 5 4 + i x ) ∣ 2 = ( x 2 + 1 16 ) ∣ Γ ( 1 4 + i x ) ∣ 2 |\Gamma(\frac{5}{4}+ix)|^2=(x^2+\frac{1}{16})|\Gamma(\frac{1}{4}+ix)|^2 ∣Γ ( 4 5 + i x ) ∣ 2 = ( x 2 + 16 1 ) ∣Γ ( 4 1 + i x ) ∣ 2 . In both cases the product of the three squared Gamma moduli is therefore 2 π 2 cosh 2 π x ( x 2 + 1 16 ) ∣ Γ ( α + i x ) ∣ 2 \frac{2\pi^2}{\cosh2\pi x}(x^2+\frac{1}{16})|\Gamma(\alpha+ix)|^2 c o s h 2 π x 2 π 2 ( x 2 + 16 1 ) ∣Γ ( α + i x ) ∣ 2 ; for ( 3 4 , 3 4 , 5 4 ) (\frac{3}{4},\frac{3}{4},\frac{5}{4}) ( 4 3 , 4 3 , 4 5 ) , pair one factor ∣ Γ ( 3 4 + i x ) ∣ 2 |\Gamma(\frac{3}{4}+ix)|^2 ∣Γ ( 4 3 + i x ) ∣ 2 with ∣ Γ ( 5 4 + i x ) ∣ 2 = ( x 2 + 1 16 ) ∣ Γ ( 1 4 + i x ) ∣ 2 |\Gamma(\frac{5}{4}+ix)|^2=(x^2+\frac{1}{16})|\Gamma(\frac{1}{4}+ix)|^2 ∣Γ ( 4 5 + i x ) ∣ 2 = ( x 2 + 16 1 ) ∣Γ ( 4 1 + i x ) ∣ 2 . Multiplying by ∣ Γ ( 2 i x ) ∣ − 2 |\Gamma(2ix)|^{-2} ∣Γ ( 2 i x ) ∣ − 2 gives 4 π x ( x 2 + 1 16 ) tanh ( 2 π x ) ∣ Γ ( α + i x ) ∣ 2 4\pi x(x^2+\frac{1}{16})\tanh(2\pi x)|\Gamma(\alpha+ix)|^2 4 π x ( x 2 + 16 1 ) tanh ( 2 π x ) ∣Γ ( α + i x ) ∣ 2 , and the normalization 2 π 2\pi 2 π times the right side of Fact 7.6 is 2 π Γ ( 3 2 ) Γ ( 2 ) Γ ( 2 ) = π 3 / 2 2\pi\Gamma(\frac{3}{2})\Gamma(2)\Gamma(2)=\pi^{3/2} 2 π Γ ( 2 3 ) Γ ( 2 ) Γ ( 2 ) = π 3/2 for μ o \mu_o μ o and 2 π Γ ( 1 ) Γ ( 3 2 ) Γ ( 2 ) = π 3 / 2 2\pi\Gamma(1)\Gamma(\frac{3}{2})\Gamma(2)=\pi^{3/2} 2 π Γ ( 1 ) Γ ( 2 3 ) Γ ( 2 ) = π 3/2 for μ e \mu_e μ e .
Fact 7.11 ([4 (5.8.3)] ). For real a > 0 a>0 a > 0 and real x x x ,
Γ ( a ) 2 ∣ Γ ( a + i x ) ∣ 2 = ∏ k = 0 ∞ ( 1 + x 2 ( a + k ) 2 ) . \frac{\Gamma(a)^2}{|\Gamma(a+ix)|^2}=\prod_{k=0}^{\infty}\left(1+\frac{x^2}{(a+k)^2}\right). ∣Γ ( a + i x ) ∣ 2 Γ ( a ) 2 = k = 0 ∏ ∞ ( 1 + ( a + k ) 2 x 2 ) . In particular, for fixed x x x , ∣ Γ ( a + i x ) ∣ 2 / Γ ( a ) 2 |\Gamma(a+ix)|^2/\Gamma(a)^2 ∣Γ ( a + i x ) ∣ 2 /Γ ( a ) 2 is nondecreasing in a a a .
Lemma 7.12 (Elementary bounds for the density). In both cases, ψ α ( x ) ≤ 60 ( x + 1 ) 4 e − π x \psi_\alpha(x)\le60(x+1)^4e^{-\pi x} ψ α ( x ) ≤ 60 ( x + 1 ) 4 e − π x for x > 0 x>0 x > 0 and ψ α ( x ) ≥ 3 x 2 e − π x \psi_\alpha(x)\ge3x^2e^{-\pi x} ψ α ( x ) ≥ 3 x 2 e − π x for x ≥ 1 x\ge1 x ≥ 1 .
Proof. We have ∣ Γ ( 1 2 + i x ) ∣ 2 = π cosh π x |\Gamma(\frac{1}{2}+ix)|^2=\frac{\pi}{\cosh\pi x} ∣Γ ( 2 1 + i x ) ∣ 2 = c o s h π x π and, from Γ ( 1 + i x ) = i x Γ ( i x ) \Gamma(1+ix)=ix\Gamma(ix) Γ ( 1 + i x ) = i x Γ ( i x ) , ∣ Γ ( 1 + i x ) ∣ 2 = π x sinh π x |\Gamma(1+ix)|^2=\frac{\pi x}{\sinh\pi x} ∣Γ ( 1 + i x ) ∣ 2 = s i n h π x π x . Moreover, for x > 0 x>0 x > 0 ,
e − π x ≤ 1 cosh π x ≤ 2 e − π x , 2 x e − π x ≤ x sinh π x ≤ 2 ( x + 1 ) e − π x . e^{-\pi x}\le\frac{1}{\cosh\pi x}\le2e^{-\pi x},\qquad2xe^{-\pi x}\le\frac{x}{\sinh\pi x}\le2(x+1)e^{-\pi x}. e − π x ≤ cosh π x 1 ≤ 2 e − π x , 2 x e − π x ≤ sinh π x x ≤ 2 ( x + 1 ) e − π x .
the last inequality is equivalent to ( x + 1 ) e − 2 π x ≤ 1 (x+1)e^{-2\pi x}\le1 ( x + 1 ) e − 2 π x ≤ 1 .
Upper bound. By the monotonicity in Fact 7.11 (comparing a = 3 4 a=\frac{3}{4} a = 4 3 with 1 1 1 , and a = 1 4 a=\frac{1}{4} a = 4 1 with 1 2 \frac{1}{2} 2 1 ),
∣ Γ ( 3 4 + i x ) ∣ 2 ≤ Γ ( 3 4 ) 2 ∣ Γ ( 1 + i x ) ∣ 2 ≤ 2 π Γ ( 3 4 ) 2 ( x + 1 ) e − π x , |\Gamma(\tfrac{3}{4}+ix)|^2\le\Gamma(\tfrac{3}{4})^2|\Gamma(1+ix)|^2\le2\pi\Gamma(\tfrac{3}{4})^2(x+1)e^{-\pi x}, ∣Γ ( 4 3 + i x ) ∣ 2 ≤ Γ ( 4 3 ) 2 ∣Γ ( 1 + i x ) ∣ 2 ≤ 2 π Γ ( 4 3 ) 2 ( x + 1 ) e − π x ,
∣ Γ ( 1 4 + i x ) ∣ 2 ≤ Γ ( 1 4 ) 2 Γ ( 1 2 ) 2 ∣ Γ ( 1 2 + i x ) ∣ 2 ≤ 2 Γ ( 1 4 ) 2 e − π x . |\Gamma(\tfrac{1}{4}+ix)|^2\le\frac{\Gamma(\tfrac{1}{4})^2}{\Gamma(\tfrac{1}{2})^2}|\Gamma(\tfrac{1}{2}+ix)|^2\le2\Gamma(\tfrac{1}{4})^2e^{-\pi x}. ∣Γ ( 4 1 + i x ) ∣ 2 ≤ Γ ( 2 1 ) 2 Γ ( 4 1 ) 2 ∣Γ ( 2 1 + i x ) ∣ 2 ≤ 2Γ ( 4 1 ) 2 e − π x .
With tanh ≤ 1 \tanh\le1 tanh ≤ 1 and x ( x 2 + 1 16 ) ≤ ( x + 1 ) 3 x(x^2+\frac{1}{16})\le(x+1)^3 x ( x 2 + 16 1 ) ≤ ( x + 1 ) 3 , Lemma 7.10 gives ψ 3 / 4 ≤ 8 π Γ ( 3 4 ) 2 ( x + 1 ) 4 e − π x \psi_{3/4}\le8\sqrt{\pi}\,\Gamma(\frac{3}{4})^2(x+1)^4e^{-\pi x} ψ 3/4 ≤ 8 π Γ ( 4 3 ) 2 ( x + 1 ) 4 e − π x and ψ 1 / 4 ≤ 8 π Γ ( 1 4 ) 2 ( x + 1 ) 3 e − π x \psi_{1/4}\le\frac{8}{\sqrt{\pi}}\Gamma(\frac{1}{4})^2(x+1)^3e^{-\pi x} ψ 1/4 ≤ π 8 Γ ( 4 1 ) 2 ( x + 1 ) 3 e − π x . Since Γ ( 1 4 ) = 3.62560 … \Gamma(\frac{1}{4})=3.62560\ldots Γ ( 4 1 ) = 3.62560 … and Γ ( 3 4 ) = 1.22541 … \Gamma(\frac{3}{4})=1.22541\ldots Γ ( 4 3 ) = 1.22541 … , we have 8 π Γ ( 3 4 ) 2 < 21.3 8\sqrt{\pi}\,\Gamma(\frac{3}{4})^2<21.3 8 π Γ ( 4 3 ) 2 < 21.3 and 8 π Γ ( 1 4 ) 2 < 59.34 \frac{8}{\sqrt{\pi}}\Gamma(\frac{1}{4})^2<59.34 π 8 Γ ( 4 1 ) 2 < 59.34 .
Lower bound (x ≥ 1 x \ge1 x ≥ 1 ). Again by monotonicity (comparing a = 3 4 a=\frac{3}{4} a = 4 3 with 1 2 \frac{1}{2} 2 1 , and a = 5 4 a=\frac{5}{4} a = 4 5 with 1 1 1 ),
∣ Γ ( 3 4 + i x ) ∣ 2 ≥ Γ ( 3 4 ) 2 Γ ( 1 2 ) 2 ∣ Γ ( 1 2 + i x ) ∣ 2 ≥ Γ ( 3 4 ) 2 e − π x . \left|\Gamma\left(\frac{3}{4}+ix\right)\right|^2 \ge\frac{\Gamma\left(\frac{3}{4}\right)^2}{\Gamma\left(\frac{1}{2}\right)^2}\left|\Gamma\left(\frac{1}{2}+ix\right)\right|^2 \ge\Gamma\left(\frac{3}{4}\right)^2e^{-\pi x}. Γ ( 4 3 + i x ) 2 ≥ Γ ( 2 1 ) 2 Γ ( 4 3 ) 2 Γ ( 2 1 + i x ) 2 ≥ Γ ( 4 3 ) 2 e − π x .
∣ Γ ( 1 4 + i x ) ∣ 2 = ∣ Γ ( 5 4 + i x ) ∣ 2 x 2 + 1 16 ≥ Γ ( 5 4 ) 2 ∣ Γ ( 1 + i x ) ∣ 2 x 2 + 1 16 ≥ 2 π Γ ( 5 4 ) 2 x e − π x x 2 + 1 16 . \left|\Gamma\left(\frac{1}{4}+ix\right)\right|^2=\frac{\left|\Gamma\left(\frac{5}{4}+ix\right)\right|^2}{x^2+\frac{1}{16}}\ge\frac{\Gamma\left(\frac{5}{4}\right)^2\left|\Gamma(1+ix)\right|^2}{x^2+\frac{1}{16}}\ge\frac{2\pi\Gamma\left(\frac{5}{4}\right)^2x e^{-\pi x}}{x^2+\frac{1}{16}}. Γ ( 4 1 + i x ) 2 = x 2 + 16 1 Γ ( 4 5 + i x ) 2 ≥ x 2 + 16 1 Γ ( 4 5 ) 2 ∣ Γ ( 1 + i x ) ∣ 2 ≥ x 2 + 16 1 2 π Γ ( 4 5 ) 2 x e − π x .
For x ≥ 1 x\ge1 x ≥ 1 , tanh 2 π x > 0.99 \tanh2\pi x>0.99 tanh 2 π x > 0.99 and x ( x 2 + 1 16 ) ≥ x 2 x\left(x^2+\frac{1}{16}\right)\ge x^2 x ( x 2 + 16 1 ) ≥ x 2 , so ψ 3 / 4 ≥ 0.99 ⋅ 4 π Γ ( 3 4 ) 2 x 2 e − π x \psi_{3/4}\ge0.99\cdot\frac{4}{\sqrt{\pi}}\Gamma\left(\frac{3}{4}\right)^2x^2e^{-\pi x} ψ 3/4 ≥ 0.99 ⋅ π 4 Γ ( 4 3 ) 2 x 2 e − π x and ψ 1 / 4 ≥ 0.99 ⋅ 8 π Γ ( 5 4 ) 2 x 2 e − π x \psi_{1/4}\ge0.99\cdot8\sqrt{\pi}\,\Gamma\left(\frac{5}{4}\right)^2x^2e^{-\pi x} ψ 1/4 ≥ 0.99 ⋅ 8 π Γ ( 4 5 ) 2 x 2 e − π x ; the two coefficients exceed 3.35 3.35 3.35 and 11.5 11.5 11.5 .
Proof of Theorem 1.2 . Since log n ! = ∑ k = 2 n log k \log n!=\sum_{k=2}^{n}\log k log n ! = ∑ k = 2 n log k lies between ∫ 1 n log x d x \int_1^n\log x\,dx ∫ 1 n log x d x and ∫ 1 n log x d x + log n \int_1^n\log x\,dx+\log n ∫ 1 n log x d x + log n ,
n log n − n + 1 ≤ log n ! ≤ n log n − n + 1 + log n ( n ≥ 1 ) . (4) n\log n-n+1\le\log n!\le n\log n-n+1+\log n\qquad(n\ge1). \tag*{(4)} n log n − n + 1 ≤ log n ! ≤ n log n − n + 1 + log n ( n ≥ 1 ) . (4)
We also use ∫ 0 ∞ x n e − π x d x = n ! π − ( n + 1 ) \int_0^\infty x^n e^{-\pi x}\,dx=n!\,\pi^{-(n+1)} ∫ 0 ∞ x n e − π x d x = n ! π − ( n + 1 ) .
Upper bound for the moments. By x 2 + 1 16 ≤ ( x + 1 ) 2 x^2+\frac{1}{16}\le(x+1)^2 x 2 + 16 1 ≤ ( x + 1 ) 2 and Lemma 7.12 , for integers s ≥ 0 s\ge0 s ≥ 0 ,
E [ ω s ] ≤ 60 ⋅ 4 s ∫ 0 ∞ ( x + 1 ) 2 s + 4 e − π x d x ≤ 60 e π 4 s ∫ 0 ∞ u 2 s + 4 e − π u d u = 60 e π 4 s ( 2 s + 4 ) ! π 2 s + 5 . \mathbb{E}[\omega^s]\le60\cdot4^s\int_0^\infty(x+1)^{2s+4}e^{-\pi x}\,dx\le60e^\pi4^s\int_0^\infty u^{2s+4}e^{-\pi u}\,du=60e^\pi4^s\frac{(2s+4)!}{\pi^{2s+5}}. E [ ω s ] ≤ 60 ⋅ 4 s ∫ 0 ∞ ( x + 1 ) 2 s + 4 e − π x d x ≤ 60 e π 4 s ∫ 0 ∞ u 2 s + 4 e − π u d u = 60 e π 4 s π 2 s + 5 ( 2 s + 4 )! .
Lower bound for the moments. By x 2 + 1 16 ≥ x 2 x^2+\frac{1}{16}\ge x^2 x 2 + 16 1 ≥ x 2 and Lemma 7.12 ,
E [ ω s ] ≥ 3 ⋅ 4 s ∫ 1 ∞ x 2 s + 2 e − π x d x ≥ 3 ⋅ 4 s ( ( 2 s + 2 ) ! π 2 s + 3 − 1 ) ≥ 3 2 ⋅ 4 s ( 2 s + 2 ) ! π 2 s + 3 ( s ≥ 4 ) , \mathbb{E}[\omega^s]\ge3\cdot4^s\int_1^\infty x^{2s+2}e^{-\pi x}\,dx\ge3\cdot4^s\left(\frac{(2s+2)!}{\pi^{2s+3}}-1\right)\ge\frac{3}{2}\cdot4^s\frac{(2s+2)!}{\pi^{2s+3}}\qquad(s\ge4), E [ ω s ] ≥ 3 ⋅ 4 s ∫ 1 ∞ x 2 s + 2 e − π x d x ≥ 3 ⋅ 4 s ( π 2 s + 3 ( 2 s + 2 )! − 1 ) ≥ 2 3 ⋅ 4 s π 2 s + 3 ( 2 s + 2 )! ( s ≥ 4 ) ,
where the last step uses ( 2 s + 2 ) ! ≥ 2 π 2 s + 3 (2s+2)!\ge2\pi^{2s+3} ( 2 s + 2 )! ≥ 2 π 2 s + 3 : For s = 4 s=4 s = 4 , 10 ! / π 11 > 12.3 10!/\pi^{11}>12.3 10 ! / π 11 > 12.3 , and increasing s s s by one multiplies the ratio by ( 2 s + 3 ) ( 2 s + 4 ) / π 2 > 1 (2s+3)(2s+4)/\pi^2>1 ( 2 s + 3 ) ( 2 s + 4 ) / π 2 > 1 .
Substituting. For m = 2 s + 2 m=2s+2 m = 2 s + 2 (N N N odd, W ( N ) = 4 E μ o [ ω s ] W(N)=4\mathbb{E}_{\mu_o}[\omega^s] W ( N ) = 4 E μ o [ ω s ] by Theorem 7.8 ) and for m = 2 s + 1 m=2s+1 m = 2 s + 1 (N N N even, W ( N ) = 2 E μ e [ ω s ] W(N)=2\mathbb{E}_{\mu_e}[\omega^s] W ( N ) = 2 E μ e [ ω s ] ), using 4 s π − 2 s = ( 2 π ) m π 2 4 4^s\pi^{-2s}=\left(\frac{2}{\pi}\right)^m\frac{\pi^2}{4} 4 s π − 2 s = ( π 2 ) m 4 π 2 and ( 2 π ) m π 2 \left(\frac{2}{\pi}\right)^m\frac{\pi}{2} ( π 2 ) m 2 π respectively,
3 2 π ( 2 π ) m m ! ≤ W ( N ) ≤ 60 e π π 3 ( 2 π ) m ( m + 2 ) ! ( N odd , m ≥ 10 ) , \frac{3}{2\pi}\left(\frac{2}{\pi}\right)^m m!\le W(N)\le\frac{60e^\pi}{\pi^3}\left(\frac{2}{\pi}\right)^m(m+2)!\qquad(N\text{ odd},\ m\ge10), 2 π 3 ( π 2 ) m m ! ≤ W ( N ) ≤ π 3 60 e π ( π 2 ) m ( m + 2 )! ( N odd , m ≥ 10 ) ,
3 2 π 2 ( 2 π ) m ( m + 1 ) ! ≤ W ( N ) ≤ 60 e π π 4 ( 2 π ) m ( m + 3 ) ! ( N even , m ≥ 9 ) . \frac{3}{2\pi^2}\left(\frac{2}{\pi}\right)^m(m+1)!\le W(N)\le\frac{60e^\pi}{\pi^4}\left(\frac{2}{\pi}\right)^m(m+3)!\qquad(N\text{ even},\ m\ge9). 2 π 2 3 ( π 2 ) m ( m + 1 )! ≤ W ( N ) ≤ π 4 60 e π ( π 2 ) m ( m + 3 )! ( N even , m ≥ 9 ) .
Since 3 2 π > 0.477 \frac{3}{2\pi}>0.477 2 π 3 > 0.477 , 60 e π π 3 < 44.8 \frac{60e^\pi}{\pi^3}<44.8 π 3 60 e π < 44.8 , 3 2 π 2 > 0.151 \frac{3}{2\pi^2}>0.151 2 π 2 3 > 0.151 and 60 e π π 4 < 14.3 \frac{60e^\pi}{\pi^4}<14.3 π 4 60 e π < 14.3 , the first assertion holds for m ≥ 9 m\ge9 m ≥ 9 . For N = 3 , … , 9 N=3,\ldots,9 N = 3 , … , 9 (m ≤ 8 m\le8 m ≤ 8 ), Table 1 gives W ( N ) / ( ( 2 π ) m m ! ) ≈ 4.93 , 7.75 , 10.15 , 13.39 , 16.36 , 20.00 , 23.44 W(N)/\left(\left(\frac{2}{\pi}\right)^m m!\right)\approx4.93,\ 7.75,\ 10.15,\ 13.39,\ 16.36,\ 20.00,\ 23.44 W ( N ) / ( ( π 2 ) m m ! ) ≈ 4.93 , 7.75 , 10.15 , 13.39 , 16.36 , 20.00 , 23.44 , all between 1 7 \frac{1}{7} 7 1 and 45 45 45 .
Second assertion. Let Θ N : = N log 2 N π − N \Theta_N:=N\log\frac{2N}{\pi}-N Θ N := N log π 2 N − N , and note ( 2 π ) m = π 2 ( 2 π ) N \left(\frac{2}{\pi}\right)^m=\frac{\pi}{2}\left(\frac{2}{\pi}\right)^N ( π 2 ) m = 2 π ( π 2 ) N , m ! = N ! / N m!=N!/N m ! = N ! / N and ( m + 3 ) ! = N ! ( N + 1 ) ( N + 2 ) (m+3)!=N!(N+1)(N+2) ( m + 3 )! = N ! ( N + 1 ) ( N + 2 ) . By (3),
log W ( N ) ≥ − log 7 + log π 2 + N log 2 π + ( N log N − N + 1 ) − log N ≥ Θ N − log N − 0.50 ≥ Θ N − Λ , \begin{aligned}
\log W(N)&\ge-\log7+\log\frac{\pi}{2}+N\log\frac{2}{\pi}+(N\log N-N+1)-\log N\\
&\ge\Theta_N-\log N-0.50\ge\Theta_N-\Lambda,
\end{aligned} log W ( N ) ≥ − log 7 + log 2 π + N log π 2 + ( N log N − N + 1 ) − log N ≥ Θ N − log N − 0.50 ≥ Θ N − Λ ,
log W ( N ) ≤ log 45 + log π 2 + N log 2 π + ( N log N − N + 1 + log N ) + 2 log ( N + 2 ) ≤ Θ N + 3 log ( N + 2 ) + 5.26. \begin{aligned}
\log W(N)&\le\log45+\log\frac{\pi}{2}+N\log\frac{2}{\pi}+(N\log N-N+1+\log N)+2\log(N+2)\\
&\le\Theta_N+3\log(N+2)+5.26.
\end{aligned} log W ( N ) ≤ log 45 + log 2 π + N log π 2 + ( N log N − N + 1 + log N ) + 2 log ( N + 2 ) ≤ Θ N + 3 log ( N + 2 ) + 5.26.
For N ≥ 3 N\ge3 N ≥ 3 , log ( N + 2 ) ≤ log ( N + 1 ) + log 5 4 ≤ Λ − 0.77 \log(N+2)\le\log(N+1)+\log\frac{5}{4}\le\Lambda-0.77 log ( N + 2 ) ≤ log ( N + 1 ) + log 4 5 ≤ Λ − 0.77 and Λ ≥ 2.38 \Lambda\ge2.38 Λ ≥ 2.38 , so log W ( N ) ≤ Θ N + 3 Λ + 2.95 ≤ Θ N + 5 Λ \log W(N)\le\Theta_N+3\Lambda+2.95\le\Theta_N+5\Lambda log W ( N ) ≤ Θ N + 3Λ + 2.95 ≤ Θ N + 5Λ .
Concluding remarks
We have proved log τ ( N ) = N log N − N log e b + O ( log 4 N ) \log\tau(N)=N\log N-N\log\frac{e}{b}+O(\log^{4}N) log τ ( N ) = N log N − N log b e + O ( log 4 N ) with b = 2 / π b=2/\pi b = 2/ π , with the explicit error bound 152 Λ 4 152\Lambda^{4} 152 Λ 4 for every N ≥ 3 N\geq3 N ≥ 3 . The comparison of τ ( N ) \tau(N) τ ( N ) with W ( N ) W(N) W ( N ) (Sections 4–6) uses only an injection, a count of vertex-disjoint cycles, an inequality on words, and an exchange argument; the formulas for W ( N ) W(N) W ( N ) start from the Motzkin paths of Section 3.
Some questions remain open. (1) Anick’s ratio form τ ( N ) / τ ( N − 1 ) = a + b N + ( − 1 ) N c / N + ⋯ \tau(N)/\tau(N-1)=a+bN+(-1)^{N}c/N+\cdots τ ( N ) / τ ( N − 1 ) = a + b N + ( − 1 ) N c / N + ⋯ and the constants a a a , c c c . If the ratio form holds with remainder O ( N − 2 ) O(N^{-2}) O ( N − 2 ) , summing logarithms gives log τ ( N ) = N log N − N log e b + ( a b + 1 2 ) log N + O ( 1 ) \log\tau(N)=N\log N-N\log\frac{e}{b}+\left(\frac{a}{b}+\frac{1}{2}\right)\log N+O(1) log τ ( N ) = N log N − N log b e + ( b a + 2 1 ) log N + O ( 1 ) ; the ratio form alone does not determine b b b , but together with Theorem 1.3 it forces b = 2 / π b=2/\pi b = 2/ π . (2) An improvement of the error O ( log 4 N ) O(\log^{4}N) O ( log 4 N ) to O ( log N ) O(\log N) O ( log N ) , and the polynomial order of τ ( N ) / ( N ! ( 2 / π ) N ) \tau(N)/(N!(2/\pi)^{N}) τ ( N ) / ( N ! ( 2/ π ) N ) . (3) The distribution of the number of cycles of a uniformly random rainbow map, and a combinatorial interpretation of the acyclic probability τ ( N ) / W ( N ) \tau(N)/W(N) τ ( N ) / W ( N ) (which is 0.7297 for N = 30 N=30 N = 30 ).
Acknowledgments
I thank Donald E. Knuth for his detailed comments on an earlier version of this paper. This work was done with extensive use of AI systems directed by the author; the author is responsible for all of its content.
A finer asymptotic formula
Theorem 1.2 determines log W ( N ) \log W(N) log W ( N ) up to O ( log N ) O(\log N) O ( log N ) . The moment representation gives the first terms of the full asymptotic expansion.
Theorem A.1. As N → ∞ N\to\infty N → ∞ , W ( N ) = G N ( 1 + π 2 32 N + O ( N − 2 ) ) W(N)=G_N\left(1+\frac{\pi^2}{32N}+O(N^{-2})\right) W ( N ) = G N ( 1 + 32 N π 2 + O ( N − 2 ) ) with G N : = 4 π ( 2 π ) N Γ ( N + 3 2 ) G_N:=\frac{4}{\pi}\left(\frac{2}{\pi}\right)^N\Gamma\left(N+\frac{3}{2}\right) G N := π 4 ( π 2 ) N Γ ( N + 2 3 ) ; equivalently
log W ( N ) = N log 2 N π − N + log N + log 4 2 π π + ϰ N + O ( N − 2 ) , ϰ = 11 24 + π 2 32 . \log W(N)=N\log\frac{2N}{\pi}-N+\log N+\log\frac{4\sqrt{2\pi}}{\pi}+\frac{\varkappa}{N}+O(N^{-2}),\qquad\varkappa=\frac{11}{24}+\frac{\pi^2}{32}. log W ( N ) = N log π 2 N − N + log N + log π 4 2 π + N ϰ + O ( N − 2 ) , ϰ = 24 11 + 32 π 2 .
Fact A.2 (Stirling’s formula; [4 (5.11.1)] ). As z → ∞ z\to\infty z → ∞ with ∣ arg z ∣ ≤ π − δ |\arg z|\leq\pi-\delta ∣ arg z ∣ ≤ π − δ ,
log Γ ( z ) = ( z − 1 2 ) log z − z + 1 2 log 2 π + 1 12 z + O ( ∣ z ∣ − 3 ) . \log\Gamma(z)=\left(z-\frac{1}{2}\right)\log z-z+\frac{1}{2}\log2\pi+\frac{1}{12z}+O(|z|^{-3}). log Γ ( z ) = ( z − 2 1 ) log z − z + 2 1 log 2 π + 12 z 1 + O ( ∣ z ∣ − 3 ) .
Lemma A.3. As x → ∞ x\to\infty x → ∞ , ψ α ( x ) = 8 π x 2 α + 2 e − π x ( 1 + O ( x − 2 ) ) \psi_{\alpha}(x)=8\sqrt{\pi}x^{2\alpha+2}e^{-\pi x}(1+O(x^{-2})) ψ α ( x ) = 8 π x 2 α + 2 e − π x ( 1 + O ( x − 2 )) .
Proof. Take z = α + i x z=\alpha+ix z = α + i x in Fact A.2 and take real parts. With θ : = arctan α x \theta:=\arctan\frac{\alpha}{x} θ := arctan x α we have arg z = π 2 − θ \arg z=\frac{\pi}{2}-\theta arg z = 2 π − θ , log ∣ z ∣ = log x + O ( x − 2 ) \log|z|=\log x+O(x^{-2}) log ∣ z ∣ = log x + O ( x − 2 ) , x θ = α + O ( x − 2 ) x\theta=\alpha+O(x^{-2}) x θ = α + O ( x − 2 ) and Re 1 12 z = O ( x − 2 ) \operatorname{Re}\frac{1}{12z}=O(x^{-2}) Re 12 z 1 = O ( x − 2 ) , so
log ∣ Γ ( α + i x ) ∣ = ( α − 1 2 ) log ∣ z ∣ − x ( π 2 − θ ) − α + 1 2 log 2 π + O ( x − 2 ) = ( α − 1 2 ) log x − π x 2 + 1 2 log 2 π + O ( x − 2 ) . \begin{aligned}
\log|\Gamma(\alpha+ix)|=\left(\alpha-\frac{1}{2}\right)\log|z|-x\left(\frac{\pi}{2}-\theta\right)-\alpha+\frac{1}{2}\log2\pi+O(x^{-2}) \\
&=\left(\alpha-\frac{1}{2}\right)\log x-\frac{\pi x}{2}+\frac{1}{2}\log2\pi+O(x^{-2}).
\end{aligned} log ∣Γ ( α + i x ) ∣ = ( α − 2 1 ) log ∣ z ∣ − x ( 2 π − θ ) − α + 2 1 log 2 π + O ( x − 2 ) = ( α − 2 1 ) log x − 2 π x + 2 1 log 2 π + O ( x − 2 ) .
Hence ∣ Γ ( α + i x ) ∣ 2 = 2 π x 2 α − 1 e − π x ( 1 + O ( x − 2 ) ) |\Gamma(\alpha+ix)|^2=2\pi x^{2\alpha-1}e^{-\pi x}(1+O(x^{-2})) ∣Γ ( α + i x ) ∣ 2 = 2 π x 2 α − 1 e − π x ( 1 + O ( x − 2 )) . Multiply by x 2 + 1 16 = x 2 ( 1 + O ( x − 2 ) ) x^2+\frac{1}{16}=x^2(1+O(x^{-2})) x 2 + 16 1 = x 2 ( 1 + O ( x − 2 )) and tanh 2 π x = 1 + O ( e − 4 π x ) \tanh2\pi x=1+O(e^{-4\pi x}) tanh 2 π x = 1 + O ( e − 4 π x ) , and note π − 3 / 2 ⋅ 4 π ⋅ 2 π = 8 π \pi^{-3/2}\cdot4\pi\cdot2\pi=8\sqrt{\pi} π − 3/2 ⋅ 4 π ⋅ 2 π = 8 π . □
Lemma A.4 (Asymptotics of moments). Let ψ ( x ) = C x ν e − π x ( 1 + η ( x ) ) \psi(x)=Cx^\nu e^{-\pi x}(1+\eta(x)) ψ ( x ) = C x ν e − π x ( 1 + η ( x )) be a probability density with C , ν > 0 C,\nu>0 C , ν > 0 and ∣ η ( x ) ∣ ≤ K / x 2 |\eta(x)|\leq K/x^2 ∣ η ( x ) ∣ ≤ K / x 2 for x ≥ x 0 x\geq x_0 x ≥ x 0 . Then, as s → ∞ s\to\infty s → ∞ ,
∫ 0 ∞ ( 4 ( x 2 + 1 16 ) ) s ψ ( x ) d x = C 4 s Γ ( 2 s + ν + 1 ) π 2 s + ν + 1 ( 1 + π 2 64 s + O ( s − 2 ) ) . \int_{0}^{\infty}\left(4\left(x^2+\frac{1}{16}\right)\right)^s\psi(x)\,dx=C\,4^s\frac{\Gamma(2s+\nu+1)}{\pi^{2s+\nu+1}}\left(1+\frac{\pi^2}{64s}+O(s^{-2})\right). ∫ 0 ∞ ( 4 ( x 2 + 16 1 ) ) s ψ ( x ) d x = C 4 s π 2 s + ν + 1 Γ ( 2 s + ν + 1 ) ( 1 + 64 s π 2 + O ( s − 2 ) ) .
Proof. Let n : = 2 s + ν n := 2s+\nu n := 2 s + ν and g j : = ∫ 0 ∞ x n − j e − π x d x = Γ ( n − j + 1 ) π − ( n − j + 1 ) g_j := \int_0^\infty x^{n-j}e^{-\pi x}\,dx = \Gamma(n-j+1)\pi^{-(n-j+1)} g j := ∫ 0 ∞ x n − j e − π x d x = Γ ( n − j + 1 ) π − ( n − j + 1 ) , so that g 2 g 0 = π 2 n ( n − 1 ) \frac{g_2}{g_0}=\frac{\pi^2}{n(n-1)} g 0 g 2 = n ( n − 1 ) π 2 and g 4 g 0 = π 4 n ( n − 1 ) ( n − 2 ) ( n − 3 ) \frac{g_4}{g_0}=\frac{\pi^4}{n(n-1)(n-2)(n-3)} g 0 g 4 = n ( n − 1 ) ( n − 2 ) ( n − 3 ) π 4 . Let ξ : = s 2 / 3 \xi:= s^{2/3} ξ := s 2/3 , and let s s s be large enough that ξ ≥ max ( 1 , x 0 ) \xi\geq\max(1,x_0) ξ ≥ max ( 1 , x 0 ) and π ξ ≤ n − 4 \pi\xi\leq n-4 π ξ ≤ n − 4 .
(a) The model integrals have negligible mass on [ 0 , ξ ] [0,\xi] [ 0 , ξ ] . For 0 ≤ j ≤ 4 0\leq j\leq4 0 ≤ j ≤ 4 , x n − j e − π x x^{n-j}e^{-\pi x} x n − j e − π x increases on [ 0 , ( n − j ) / π ] ⊇ [ 0 , ξ ] [0,(n-j)/\pi]\supseteq[0,\xi] [ 0 , ( n − j ) / π ] ⊇ [ 0 , ξ ] , so ∫ 0 ξ x n − j e − π x d x ≤ ξ n + 1 \int_0^\xi x^{n-j}e^{-\pi x}\,dx\leq\xi^{n+1} ∫ 0 ξ x n − j e − π x d x ≤ ξ n + 1 . Since Γ ( n + 1 ) ≥ ∫ n ∞ x n e − x d x ≥ ( n / e ) n \Gamma(n+1)\geq\int_n^\infty x^n e^{-x}\,dx\geq(n/e)^n Γ ( n + 1 ) ≥ ∫ n ∞ x n e − x d x ≥ ( n / e ) n , we have g 0 ≥ π − ( n + 1 ) ( n / e ) n g_0\geq\pi^{-(n+1)}(n/e)^n g 0 ≥ π − ( n + 1 ) ( n / e ) n and
ξ n + 1 g 0 ≤ δ s : = π ξ ( e π ξ n ) n , e π ξ n ≤ e π 2 s − 1 / 3 → 0 , \frac{\xi^{n+1}}{g_0}\leq\delta_s:=\pi\xi\left(\frac{e\pi\xi}{n}\right)^n,\qquad\frac{e\pi\xi}{n}\leq\frac{e\pi}{2}s^{-1/3}\to0, g 0 ξ n + 1 ≤ δ s := π ξ ( n e π ξ ) n , n e π ξ ≤ 2 e π s − 1/3 → 0 ,
so δ s \delta_s δ s is smaller than any negative power of s s s .
(b) The range x ≥ ξ x\geq\xi x ≥ ξ . Let y : = 1 16 x 2 y:=\frac{1}{16x^2} y := 16 x 2 1 ; then ( 4 ( x 2 + 1 16 ) ) s = 4 s x 2 s ( 1 + y ) s \left(4\left(x^2+\frac{1}{16}\right)\right)^s=4^sx^{2s}(1+y)^s ( 4 ( x 2 + 16 1 ) ) s = 4 s x 2 s ( 1 + y ) s and 0 ≤ s y ≤ 1 16 0\leq sy\leq\frac{1}{16} 0 ≤ sy ≤ 16 1 . With u : = s log ( 1 + y ) u:=s\log(1+y) u := s log ( 1 + y ) , the bounds y − y 2 2 ≤ log ( 1 + y ) ≤ y y-\frac{y^2}{2}\leq\log(1+y)\leq y y − 2 y 2 ≤ log ( 1 + y ) ≤ y give s y − s y 2 2 ≤ u ≤ s y ≤ 1 sy-\frac{sy^2}{2}\leq u\leq sy\leq1 sy − 2 s y 2 ≤ u ≤ sy ≤ 1 , and 1 + u ≤ e u ≤ 1 + u + u 2 1+u\leq e^u\leq1+u+u^2 1 + u ≤ e u ≤ 1 + u + u 2 gives ( 1 + y ) s = 1 + s y + R 1 (1+y)^s=1+sy+\mathcal{R}_1 ( 1 + y ) s = 1 + sy + R 1 with ∣ R 1 ∣ ≤ 1 2 s y 2 + s 2 y 2 ≤ 2 s 2 y 2 |\mathcal{R}_1|\leq\frac12 sy^2+s^2y^2\leq2s^2y^2 ∣ R 1 ∣ ≤ 2 1 s y 2 + s 2 y 2 ≤ 2 s 2 y 2 . Including the factor 1 + η ( x ) 1+\eta(x) 1 + η ( x ) , for x ≥ ξ x\geq\xi x ≥ ξ ,
( 4 ( x 2 + 1 16 ) ) s ψ ( x ) = C 4 s x n e − π x [ 1 + s 16 x 2 + R ( x ) ] , ∣ R ( x ) ∣ ≤ K ′ ( s 2 x 4 + 1 x 2 ) , \left(4\left(x^2+\frac{1}{16}\right)\right)^s\psi(x)=C\,4^sx^ne^{-\pi x}\left[1+\frac{s}{16x^2}+\mathcal{R}(x)\right],\qquad|\mathcal{R}(x)|\leq K'\left(\frac{s^2}{x^4}+\frac{1}{x^2}\right), ( 4 ( x 2 + 16 1 ) ) s ψ ( x ) = C 4 s x n e − π x [ 1 + 16 x 2 s + R ( x ) ] , ∣ R ( x ) ∣ ≤ K ′ ( x 4 s 2 + x 2 1 ) ,
with K ′ K' K ′ depending only on K K K . Integrate over [ ξ , ∞ ) [\xi,\infty) [ ξ , ∞ ) ; by (a), replacing ∫ ξ ∞ x n − j e − π x d x \int_\xi^\infty x^{n-j}e^{-\pi x}\,dx ∫ ξ ∞ x n − j e − π x d x by g j g_j g j (j = 0 , 2 , 4 j=0,2,4 j = 0 , 2 , 4 ) costs at most g 0 δ s g_0\delta_s g 0 δ s . Thus
∫ ξ ∞ ( 4 ( x 2 + 1 16 ) ) s ψ d x = C 4 s g 0 [ 1 + s 16 g 2 g 0 + O ( s 2 g 4 g 0 + g 2 g 0 + s 2 δ s ) ] = C 4 s g 0 [ 1 + π 2 64 s + O ( s − 2 ) ] , \int_\xi^\infty\left(4\left(x^2+\frac{1}{16}\right)\right)^s\psi\,dx=C4^sg_0\left[1+\frac{s}{16}\frac{g_2}{g_0}+O\left(\frac{s^2g_4}{g_0}+\frac{g_2}{g_0}+s^2\delta_s\right)\right]=C4^sg_0\left[1+\frac{\pi^2}{64s}+O(s^{-2})\right], ∫ ξ ∞ ( 4 ( x 2 + 16 1 ) ) s ψ d x = C 4 s g 0 [ 1 + 16 s g 0 g 2 + O ( g 0 s 2 g 4 + g 0 g 2 + s 2 δ s ) ] = C 4 s g 0 [ 1 + 64 s π 2 + O ( s − 2 ) ] ,
because s 16 ⋅ π 2 n ( n − 1 ) − π 2 64 s = π 2 16 ⋅ 4 s 2 − n ( n − 1 ) 4 s n ( n − 1 ) = O ( s − 2 ) \frac{s}{16}\cdot\frac{\pi^2}{n(n-1)}-\frac{\pi^2}{64s}=\frac{\pi^2}{16}\cdot\frac{4s^2-n(n-1)}{4sn(n-1)}=O(s^{-2}) 16 s ⋅ n ( n − 1 ) π 2 − 64 s π 2 = 16 π 2 ⋅ 4 s n ( n − 1 ) 4 s 2 − n ( n − 1 ) = O ( s − 2 ) , s 2 g 4 / g 0 = O ( s − 2 ) s^2g_4/g_0=O(s^{-2}) s 2 g 4 / g 0 = O ( s − 2 ) and g 2 / g 0 = O ( s − 2 ) g_2/g_0=O(s^{-2}) g 2 / g 0 = O ( s − 2 ) .
(c) The range x ≤ ξ x\leq\xi x ≤ ξ . Since ψ \psi ψ is a probability density, ∫ 0 ξ ( 4 ( x 2 + 1 16 ) ) s ψ d x ≤ 4 s ξ 2 s ( 1 + 1 16 ξ 2 ) s ≤ e 1 / 16 4 s ξ 2 s ≤ e 1 / 16 4 s g 0 δ s \int_0^\xi\left(4\left(x^2+\frac{1}{16}\right)\right)^s\psi\,dx\leq4^s\xi^{2s}\left(1+\frac{1}{16\xi^2}\right)^s\leq e^{1/16}4^s\xi^{2s}\leq e^{1/16}4^sg_0\delta_s ∫ 0 ξ ( 4 ( x 2 + 16 1 ) ) s ψ d x ≤ 4 s ξ 2 s ( 1 + 16 ξ 2 1 ) s ≤ e 1/16 4 s ξ 2 s ≤ e 1/16 4 s g 0 δ s (as ξ ≥ 1 \xi\geq1 ξ ≥ 1 and 2 s ≤ n + 1 2s\leq n+1 2 s ≤ n + 1 ), which is again negligible. Adding (b) and (c) proves the lemma. □
Proof of Theorem A.1. By Lemma A.3, Lemma A.4 applies with C = 8 π C=8\sqrt{\pi} C = 8 π and ν = 2 α + 2 \nu=2\alpha+2 ν = 2 α + 2 . By Theorem 7.8, for m = 2 s + 2 m=2s+2 m = 2 s + 2 (odd N N N ) W ( N ) = 4 ⋅ 8 π 4 s Γ ( 2 s + 9 2 ) π − ( 2 s + 9 / 2 ) ( 1 + π 2 64 s + O ( s − 2 ) ) W(N)=4\cdot8\sqrt{\pi}\,4^s\Gamma\left(2s+\frac{9}{2}\right)\pi^{-(2s+9/2)}\left(1+\frac{\pi^2}{64s}+O(s^{-2})\right) W ( N ) = 4 ⋅ 8 π 4 s Γ ( 2 s + 2 9 ) π − ( 2 s + 9/2 ) ( 1 + 64 s π 2 + O ( s − 2 ) ) , and for m = 2 s + 1 m=2s+1 m = 2 s + 1 (even N N N ) W ( N ) = 2 ⋅ 8 π 4 s Γ ( 2 s + 7 2 ) π − ( 2 s + 7 / 2 ) ( 1 + π 2 64 s + O ( s − 2 ) ) W(N)=2\cdot8\sqrt{\pi}\,4^s\Gamma\left(2s+\frac{7}{2}\right)\pi^{-(2s+7/2)}\left(1+\frac{\pi^2}{64s}+O(s^{-2})\right) W ( N ) = 2 ⋅ 8 π 4 s Γ ( 2 s + 2 7 ) π − ( 2 s + 7/2 ) ( 1 + 64 s π 2 + O ( s − 2 ) ) . Both equal 8 π 2 ( 2 π ) m Γ ( m + 5 2 ) ( 1 + π 2 64 s + O ( s − 2 ) ) \frac{8}{\pi^2}\left(\frac{2}{\pi}\right)^m\Gamma\left(m+\frac{5}{2}\right)\left(1+\frac{\pi^2}{64s}+O(s^{-2})\right) π 2 8 ( π 2 ) m Γ ( m + 2 5 ) ( 1 + 64 s π 2 + O ( s − 2 ) ) with s = m 2 + O ( 1 ) s=\frac{m}{2}+O(1) s = 2 m + O ( 1 ) ; substituting m = N − 1 m=N-1 m = N − 1 gives the first form. For the second, Fact A.2 gives log Γ ( N + 3 2 ) = ( N + 1 ) log N − N + 1 2 log 2 π + 11 24 N + O ( N − 2 ) \log\Gamma\left(N+\frac{3}{2}\right)=(N+1)\log N-N+\frac{1}{2}\log2\pi+\frac{11}{24N}+O(N^{-2}) log Γ ( N + 2 3 ) = ( N + 1 ) log N − N + 2 1 log 2 π + 24 N 11 + O ( N − 2 ) , because ( N + 1 ) log ( 1 + 3 2 N ) = 3 2 + 3 8 N + O ( N − 2 ) (N+1)\log\left(1+\frac{3}{2N}\right)=\frac{3}{2}+\frac{3}{8N}+O(N^{-2}) ( N + 1 ) log ( 1 + 2 N 3 ) = 2 3 + 8 N 3 + O ( N − 2 ) and 3 8 + 1 12 = 11 24 \frac{3}{8}+\frac{1}{12}=\frac{11}{24} 8 3 + 12 1 = 24 11 . □
A second proof of the alternating sum
This appendix derives the alternating sum directly from W ( N ) = per M W(N)=\operatorname{per}M W ( N ) = per M by a sign-reversing involution, without Motzkin paths. Write M = J + U M=J+U M = J + U , where J J J is the all-ones matrix. For N = 7 N=7 N = 7 (m = 6 m=6 m = 6 ) the ranks of the rows are ( 1 , 2 , 3 , 3 , 2 , 1 ) (1,2,3,3,2,1) ( 1 , 2 , 3 , 3 , 2 , 1 ) and
M = ( 2 1 1 1 1 1 2 2 1 1 1 0 2 2 2 1 0 0 2 2 2 1 0 0 2 2 1 1 1 0 2 1 1 1 1 1 ) , U = ( 1 0 0 0 0 0 1 1 0 0 0 − 1 1 1 1 0 − 1 − 1 1 1 1 0 − 1 − 1 1 1 0 0 0 − 1 1 0 0 0 0 0 ) . M=\begin{pmatrix}
2&1&1&1&1&1\\
2&2&1&1&1&0\\
2&2&2&1&0&0\\
2&2&2&1&0&0\\
2&2&1&1&1&0\\
2&1&1&1&1&1
\end{pmatrix},
\qquad
U=\begin{pmatrix}
1&0&0&0&0&0\\
1&1&0&0&0&-1\\
1&1&1&0&-1&-1\\
1&1&1&0&-1&-1\\
1&1&0&0&0&-1\\
1&0&0&0&0&0
\end{pmatrix}. M = 2 2 2 2 2 2 1 2 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 , U = 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 − 1 − 1 0 0 0 − 1 − 1 − 1 − 1 0 .
Table 2. Numerical check of Theorem A.1 . Here ε N : = log W ( N ) − ( N log 2 N π − N + log N + log 4 2 π π ) \varepsilon_N := \log W(N) - \left(N\log\frac{2N}{\pi} - N + \log N + \log\frac{4\sqrt{2\pi}}{\pi}\right) ε N := log W ( N ) − ( N log π 2 N − N + log N + log π 4 2 π ) ; the theorem implies N ε N → ϰ = 0.766758 … N\varepsilon_N \to\varkappa= 0.766758\ldots N ε N → ϰ = 0.766758 … and N ( log W ( N ) − log G N ) → π 2 32 = 0.308425 … N(\log W(N)-\log G_N) \to\frac{\pi^2}{32}=0.308425\ldots N ( log W ( N ) − log G N ) → 32 π 2 = 0.308425 … , and that the fourth column is bounded. (Computed with 50 decimal digits.)
Column 6 is the negative of column 2, column 5 the negative of column 3, column 4 is zero and column 1 is all ones; the nonzero rows of column 2 form C 2 = { 2 , 3 , 4 , 5 } C_2=\{2,3,4,5\} C 2 = { 2 , 3 , 4 , 5 } , those of column 3 form C 3 = { 3 , 4 } ⊂ C 2 C_3=\{3,4\}\subset C_2 C 3 = { 3 , 4 } ⊂ C 2 . In general:
Lemma B.1. (i) U u , d = [ ρ ( u ) ≥ d ] − [ ρ ( u ) ≥ N + 1 − d ] U_{u,d}=[\rho(u)\ge d]-[\rho(u)\ge N+1-d] U u , d = [ ρ ( u ) ≥ d ] − [ ρ ( u ) ≥ N + 1 − d ] .
(ii) For 2 ≤ d ≤ m 2\le d\le m 2 ≤ d ≤ m , column N + 1 − d N+1-d N + 1 − d is the negative of column d d d . Column 1 is all ones; for odd N N N , column N + 1 2 \frac{N+1}{2} 2 N + 1 is zero.
(iii) For 2 ≤ d ≤ R 2\le d\le R 2 ≤ d ≤ R , U u , d = [ u ∈ C d ] U_{u,d}=[u\in C_d] U u , d = [ u ∈ C d ] with C d : = { d , … , N − d } C_d:=\{d,\ldots,N-d\} C d := { d , … , N − d } , ∣ C d ∣ = N + 1 − 2 d |C_d|=N+1-2d ∣ C d ∣ = N + 1 − 2 d , and C R ⊂ ⋯ ⊂ C 3 ⊂ C 2 C_R\subset\cdots\subset C_3\subset C_2 C R ⊂ ⋯ ⊂ C 3 ⊂ C 2 . So there are R − 1 R-1 R − 1 column pairs { d , N + 1 − d } \{d,N+1-d\} { d , N + 1 − d } (2 ≤ d ≤ R 2\le d\le R 2 ≤ d ≤ R ), whose supports have sizes 2 , 4 , … , m − 2 2,4,\ldots,m-2 2 , 4 , … , m − 2 (m m m even) or 1 , 3 , … , m − 2 1,3,\ldots,m-2 1 , 3 , … , m − 2 (m m m odd).
Proof. (i) { u , N − u } = { ρ , N − ρ } \{u,N-u\}=\{\rho,N-\rho\} { u , N − u } = { ρ , N − ρ } with ρ = ρ ( u ) \rho=\rho(u) ρ = ρ ( u ) , so M u , d = [ d ≤ ρ ] + [ d ≤ N − ρ ] M_{u,d}=[d\le\rho]+[d\le N-\rho] M u , d = [ d ≤ ρ ] + [ d ≤ N − ρ ] , and [ d ≤ N − ρ ] − 1 = − [ ρ ≥ N + 1 − d ] [d\le N-\rho]-1=-[\rho\ge N+1-d] [ d ≤ N − ρ ] − 1 = − [ ρ ≥ N + 1 − d ] . (ii) Replacing d d d by N + 1 − d N+1-d N + 1 − d in (i) exchanges the two brackets. For d = 1 d=1 d = 1 , ρ ≥ 1 \rho\ge1 ρ ≥ 1 always holds and ρ ≥ N \rho\ge N ρ ≥ N never does. If d = N + 1 − d d=N+1-d d = N + 1 − d the column equals its own negative. (iii) For d ≤ R d\le R d ≤ R we have N + 1 − d > N / 2 ≥ ρ N+1-d>N/2\ge\rho N + 1 − d > N /2 ≥ ρ , so the second bracket vanishes, and ρ ( u ) ≥ d \rho(u)\ge d ρ ( u ) ≥ d if and only if d ≤ u ≤ N − d d\le u\le N-d d ≤ u ≤ N − d .
Theorem B.2 (Alternating sum, second form). Let r j r_j r j be the number of ways to choose j j j of the R − 1 R-1 R − 1 column pairs and one row in each of the chosen 2 j 2j 2 j columns, the rows being distinct and both rows chosen for pair d d d lying in C d C_d C d (r 0 = 1 r_0=1 r 0 = 1 ). Then
W ( N ) = 2 ∑ j = 0 R − 1 ( − 1 ) j r j ( m − 2 j ) ! ( N ≥ 2 ) . W(N)=2\sum_{j=0}^{R-1}(-1)^j r_j(m-2j)! \qquad(N\ge2). W ( N ) = 2 j = 0 ∑ R − 1 ( − 1 ) j r j ( m − 2 j )! ( N ≥ 2 ) .
The two forms agree term by term, that is, r j = t R − 1 , R − 1 − j r_j=t_{R-1,R-1-j} r j = t R − 1 , R − 1 − j , where t t t is the triangle of Lemma 7.4 for the parity of N N N , so Theorem B.2 is Theorem 7.5. To see this for odd N N N , let the chosen pairs have supports of sizes 2 a 1 < ⋯ < 2 a j 2a_1<\cdots<2a_j 2 a 1 < ⋯ < 2 a j (1 ≤ a i ≤ R − 1 1\le a_i\le R-1 1 ≤ a i ≤ R − 1 ) and place their rooks in this order. The supports are nested, so when the i i i th pair is placed, its support contains the 2 ( i − 1 ) 2(i-1) 2 ( i − 1 ) rows already used, and there are ( 2 a i − 2 i + 2 ) ( 2 a i − 2 i + 1 ) = λ b i o (2a_i-2i+2)(2a_i-2i+1)=\lambda^o_{b_i} ( 2 a i − 2 i + 2 ) ( 2 a i − 2 i + 1 ) = λ b i o choices, where b i : = a i − i b_i:=a_i-i b i := a i − i . As 0 ≤ b 1 ≤ ⋯ ≤ b j ≤ R − 1 − j 0\le b_1\le\cdots\le b_j\le R-1-j 0 ≤ b 1 ≤ ⋯ ≤ b j ≤ R − 1 − j , summing over the choices gives r j = h j ( λ 0 o , … , λ R − 1 − j o ) = t R − 1 , R − 1 − j o r_j=h_j(\lambda^o_0,\ldots,\lambda^o_{R-1-j})=t^o_{R-1,R-1-j} r j = h j ( λ 0 o , … , λ R − 1 − j o ) = t R − 1 , R − 1 − j o . For even N N N the sizes are 2 a i − 1 2a_i-1 2 a i − 1 and the number of choices is λ b i e \lambda^e_{b_i} λ b i e . Proof. Expansion. Since M = J + U M = J + U M = J + U ,
W ( N ) = ∑ δ ∏ u ( 1 + U u , δ ( u ) ) = ∑ δ ∑ I ′ ∏ u ∈ I ′ U u , δ ( u ) . W(N) = \sum_{\delta}\prod_{u}(1+U_{u,\delta(u)}) = \sum_{\delta}\sum_{I'}\prod_{u\in I'} U_{u,\delta(u)}. W ( N ) = δ ∑ u ∏ ( 1 + U u , δ ( u ) ) = δ ∑ I ′ ∑ u ∈ I ′ ∏ U u , δ ( u ) .
where δ \delta δ runs over the permutations of { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } and I ′ I' I ′ over the sets of rows. The pair ( I ′ , δ ∣ I ′ ) (I',\delta|_{I'}) ( I ′ , δ ∣ I ′ ) is a placement P P P of ∣ P ∣ : = ∣ I ′ ∣ |P|:=|I'| ∣ P ∣ := ∣ I ′ ∣ rooks in distinct rows and columns, with weight wt ( P ) : = ∏ u ∈ I ′ U u , δ ( u ) \operatorname{wt}(P):=\prod_{u\in I'}U_{u,\delta(u)} wt ( P ) := ∏ u ∈ I ′ U u , δ ( u ) . A placement extends to a permutation in ( m − ∣ P ∣ ) ! (m-|P|)! ( m − ∣ P ∣ )! ways, so W ( N ) = ∑ P ( m − ∣ P ∣ ) ! wt ( P ) W(N)=\sum_P(m-|P|)!\operatorname{wt}(P) W ( N ) = ∑ P ( m − ∣ P ∣ )! wt ( P ) over all placements, including the empty one; only placements with all rooks on nonzero entries of U U U contribute.
A sign-reversing involution. A column pair { d , N + 1 − d } \{d,N+1-d\} { d , N + 1 − d } is half used by P P P if P P P uses exactly one of its columns. If P P P has a half-used pair, take the one with smallest d d d and move its rook within its row to the other column of the pair, obtaining P ′ P' P ′ . That column was empty, so P ′ P' P ′ is a placement with the same number of rooks, and wt ( P ′ ) = − wt ( P ) \operatorname{wt}(P')=-\operatorname{wt}(P) wt ( P ′ ) = − wt ( P ) by Lemma B.1 (ii). P ′ P' P ′ has the same half-used pairs as P P P , so the operation is an involution, and these placements cancel in pairs.
The remaining terms. In each remaining placement every column pair is used fully or not at all, and the zero column (for odd N N N ) is not used. Suppose j j j pairs are used. The two rooks of pair { d , N + 1 − d } \{d,N+1-d\} { d , N + 1 − d } , at ( u , d ) (u,d) ( u , d ) and ( u ′ , N + 1 − d ) (u',N+1-d) ( u ′ , N + 1 − d ) , contribute U u , d U u ′ , N + 1 − d = − U u , d U u ′ , d = − [ u , u ′ ∈ C d ] U_{u,d}U_{u',N+1-d}=-U_{u,d}U_{u',d}=-[u,u'\in C_d] U u , d U u ′ , N + 1 − d = − U u , d U u ′ , d = − [ u , u ′ ∈ C d ] by Lemma B.1 (iii). So these 2 j 2j 2 j rooks contribute ( − 1 ) j (-1)^j ( − 1 ) j , and the number of nonzero choices is r j r_j r j by definition.
Column 1. Column 1 belongs to no pair. If it is not used, ∣ P ∣ = 2 j |P|=2j ∣ P ∣ = 2 j and the contribution is ( − 1 ) j r j ( m − 2 j ) ! (-1)^jr_j(m-2j)! ( − 1 ) j r j ( m − 2 j )! . If it is used, its rook is in one of the m − 2 j ≥ 1 m-2j\ge1 m − 2 j ≥ 1 remaining rows, ∣ P ∣ = 2 j + 1 |P|=2j+1 ∣ P ∣ = 2 j + 1 , and the contribution is ( − 1 ) j r j ( m − 2 j ) ( m − 2 j − 1 ) ! (-1)^jr_j(m-2j)(m-2j-1)! ( − 1 ) j r j ( m − 2 j ) ( m − 2 j − 1 )! , the same. This gives the factor 2. ∎