Exploring Werner Krandick's Jump statistics for Full Binay Trees By Shalosh B. Ekhad For any full binary tree with n internal vertices, a jump occurs when its la\ belling according to Depth First Search a vertex jumps to a vertex closer to the root, it can be defined recursively as follows If T has zero internal vertices (i.e. it is the trivail tree consisting of \ one vertex) its value is 0 Otherwise it has a left subtree and right subtrees, let's call them T1 and T\ 2 If T1 is the trivial tree, then NJ(T)=NJ(T2), otherwise MJ(T)=NJ(T1)+NJ(T2)+\ 1 Let , J[n](q), be the weight-enumerator of the set of full binary trees wit\ h n internal vertices according to the numbre of jumps Sum(q^NJ(T), T running over all full binary trees with n internal vertices Also let, J(q, x), be the grand generating function infinity ----- \ n J(x, q) = ) J[n](q) x / ----- n = 0 Theorem 1: 2 2 2 2 1/2 -q x + (q x - 2 q x - 2 q x + x - 2 x + 1) + x - 1 J(x, q) = - --------------------------------------------------------- 2 q x and in Maple notation J(x,q) = -1/2*(-q*x+(q^2*x^2-2*q*x^2-2*q*x+x^2-2*x+1)^(1/2)+x-1)/q/x In order to prove it we need a more general theorem that also talks about th\ e statistics "depth of rightmost leaf" Let , H[n](t, q), be the weight-enumerator of the set of full binary trees \ with n internal vertices according to the numbre of jumps and depth of r\ ightmost leaf Sum(q^NJ(T)*t^DepthOfRightmostLeaf, T running over all full binary trees wit\ h n internal vertices Also let, H(x, t, q), be the grand generating function infinity ----- \ n H(x, t, q) = ) H[n](t, q) x / ----- n = 0 Theorem 2: H(x, q, t) = 2 4 2 3 2 3 2 2 2 2 1/2 -t x + t x + (t x - 2 t x - 2 t x + t x - 2 t x + t ) + t - 2 - ------------------------------------------------------------------------- 2 2 (2 t x - t x - t + 1) and in Maple notation H(x,t,q) = -1/2*(-q*t*x+t*x+(q^2*t^2*x^2-2*q*t^2*x^2-2*q*t^2*x+t^2*x^2-2*t^2*x+ t^2)^(1/2)+t-2)/(q*t*x+t^2*x-t*x-t+1) Note that K(x,q)=H(x,1,q), so Theorem 2 implies Theorem 1 Before proving Thereom 2, we need a lemma, that follows easily from the recu\ srive definition of NJ(T) Lemma: H(x,t,q) satisfies the functional equation H(x, t, q) = 1 + x t H(x, 0, q) H(t, x, q) + x t q (H(x, 1, q) - H(x, 0, q)) H(x, t, q) and in Maple notation: H(x,t,q) = 1+x*t*H(x,0,q)*H(t,x,q)+x*t*q*(H(x,1,q)-H(x,0,q))*H(x,t,q) Note that this functional equation uniquely determines K(x,t,q), so in orde\ r to prove it rigorously, all we need is to check that the expression on\ the right of Theorem 2 also satisfies it Maple is happy to do it for us, and indeed using procedure ProveJxtq() in ou\ r Maple package, we get that it is true This proves Theorem 2 and hence, by plugging-in t=1, Theorem 1 Let's conclude with the first , 10, moments of the Jump statistics The expected number of jumps in the set of full binary trees with n internal\ vertices is: n/2 - 1/2 and in Maple notation 1/2*n-1/2 giving a new proof of Krandick's result. But we can do much more! The variance is 2 n - 1 ----------- 4 (2 n - 1) and in Maple notation 1/4*(n^2-1)/(2*n-1) The scaled, 4, -th moment is 3 2 6 n - 11 n - 2 n + 3 ---------------------- 3 2 2 n - 3 n - 2 n + 3 and in Maple notation (6*n^3-11*n^2-2*n+3)/(2*n^3-3*n^2-2*n+3) The limit has n goes to infinity is 3 The scaled, 6, -th moment is 6 5 4 3 2 60 n - 300 n + 391 n - 20 n - 82 n - 16 n + 15 --------------------------------------------------- 6 5 4 3 2 4 n - 16 n + 7 n + 32 n - 26 n - 16 n + 15 and in Maple notation (60*n^6-300*n^5+391*n^4-20*n^3-82*n^2-16*n+15)/(4*n^6-16*n^5+7*n^4+32*n^3-26*n^ 2-16*n+15) The limit has n goes to infinity is 15 The scaled, 8, -th moment is 9 8 7 6 5 4 3 (840 n - 7980 n + 27006 n - 38933 n + 23070 n - 6937 n + 3178 n 2 / 9 8 7 6 5 - 1167 n - 142 n + 105) / (8 n - 60 n + 118 n + 75 n - 402 n / 4 3 2 + 135 n + 418 n - 255 n - 142 n + 105) and in Maple notation (840*n^9-7980*n^8+27006*n^7-38933*n^6+23070*n^5-6937*n^4+3178*n^3-1167*n^2-142* n+105)/(8*n^9-60*n^8+118*n^7+75*n^6-402*n^5+135*n^4+418*n^3-255*n^2-142*n+105) The limit has n goes to infinity is 105 The scaled, 10, -th moment is 12 11 10 9 8 7 (15120 n - 231840 n + 1413720 n - 4430280 n + 7833841 n - 8407064 n 6 5 4 3 2 + 6060092 n - 3082632 n + 1016374 n - 162856 n + 2948 n - 1488 n / 12 11 10 9 8 7 + 945) / (16 n - 192 n + 760 n - 720 n - 2255 n + 4800 n / 6 5 4 3 2 + 1100 n - 8160 n + 2390 n + 5760 n - 2956 n - 1488 n + 945) and in Maple notation (15120*n^12-231840*n^11+1413720*n^10-4430280*n^9+7833841*n^8-8407064*n^7+ 6060092*n^6-3082632*n^5+1016374*n^4-162856*n^3+2948*n^2-1488*n+945)/(16*n^12-\ 192*n^11+760*n^10-720*n^9-2255*n^8+4800*n^7+1100*n^6-8160*n^5+2390*n^4+5760*n^3 -2956*n^2-1488*n+945) The limit has n goes to infinity is 945 The odd moments are trivially 0