Exploring Werner Krandick's Sum of Jump Distances 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 of lower depth. We are interested in the sum of these distances ove\ r all jumps. Let's call it NJD(T). Let , JD[n](q), be the weight-enumerator of the set of full binary trees wi\ th n internal vertices according to the sum of jump distances, in other \ words: JD[n](q)=Sum(q^NJD(T), T running over all full binary trees with n internal \ vertices) Also let, JD(q, x), be the grand generating function infinity ----- \ n JD(x, q) = ) JD[n](q) x / ----- n = 0 Theorem 1: 2 q JD(x, q) = ------------------------- 1/2 (-4 q x + 1) - 1 + 2 q and in Maple notation JD(x,q) = 2*q/((-4*q*x+1)^(1/2)-1+2*q) Let R[n](t) be the weight enumerator of the set of full binary trees with n \ internal vertices according to the weigth t^DepthOfRightmostLeaf(T) and let R(x,t) be the grand generating function Obviously, it satisfies the simple functional equation R(x, t) = 1 + x t R(x, 1) R(x, t) Hence 1 R(x, t) = --------------- 1 - x t R(x, 1) But R(x,1) is the good old generating function for the Catalan numbers, 1/2 1 - (1 - 4 x) ---------------- 2 x hence 1 R(x, t) = ------------------------ 1/2 t (1 - (1 - 4 x) ) 1 - -------------------- 2 Because JD(T)+DepthOfRightmostLeaf(T)=n, JD(x,q)=R(x*q,1/q) hence indeed 2 q JD(x, q) = ------------------------- 1/2 (-4 q x + 1) - 1 + 2 q Let's conclude with the first , 10, moments of the sum of Jumps statistics The expected number of jumps in the set of full binary trees with n internal\ vertices is: n (n - 1) --------- n + 2 and in Maple notation n*(n-1)/(n+2) giving a new proof of Krandick's result. But we can do much more! The variance is 2 2 n (2 n - n - 1) --------------------- 3 2 n + 7 n + 16 n + 12 note that this tends to, 4, as n goes to infinity, hence the coefficient of v\ ariation tends to 0 and the statistics is highly concentrated and in Maple notation 2*n*(2*n^2-n-1)/(n^3+7*n^2+16*n+12) The scaled, 3, -th moment is / 3 2 \1/2 1/2 | (n - n - 8 n + 12) n | 3 2 |--------------------------------| | 4 3 2 | \2 n + 15 n + 23 n - 24 n - 16/ -------------------------------------------- 2 and in Maple notation 3/2*2^(1/2)*((n^3-n^2-8*n+12)*n/(2*n^4+15*n^3+23*n^2-24*n-16))^(1/2) The limit has n goes to infinity is 3/2 The scaled, 4, -th moment is 5 4 3 2 25 n + 58 n - 45 n - 34 n - 172 n - 48 ------------------------------------------ 4 3 2 2 (2 n + 17 n + 30 n - 29 n - 20) n and in Maple notation 1/2*(25*n^5+58*n^4-45*n^3-34*n^2-172*n-48)/(2*n^4+17*n^3+30*n^2-29*n-20)/n The limit has n goes to infinity is 25/4 The scaled, 5, -th moment is 1/2 / 13 12 11 10 9 8 3 2 |(4225 n + 24635 n - 12986 n - 286502 n - 284479 n + 994219 n \ 7 6 5 4 3 + 2084536 n - 188320 n - 4867712 n - 4244832 n + 1752192 n 2 / 12 11 10 + 5833728 n + 3297024 n + 559872) / ((8 n + 228 n + 2618 n / 9 8 7 6 5 4 + 15035 n + 41183 n + 22598 n - 124288 n - 173293 n + 128435 n 3 2 \1/2 + 181992 n - 19156 n - 60960 n - 14400) n)| /4 / and in Maple notation 3/4*2^(1/2)*((4225*n^13+24635*n^12-12986*n^11-286502*n^10-284479*n^9+994219*n^8 +2084536*n^7-188320*n^6-4867712*n^5-4244832*n^4+1752192*n^3+5833728*n^2+3297024 *n+559872)/(8*n^12+228*n^11+2618*n^10+15035*n^9+41183*n^8+22598*n^7-124288*n^6-\ 173293*n^5+128435*n^4+181992*n^3-19156*n^2-60960*n-14400)/n)^(1/2) The limit has n goes to infinity is 195/8 The scaled, 6, -th moment is 10 9 8 7 6 5 4 (1921 n + 8226 n - 5972 n - 48226 n - 10949 n + 56672 n + 44712 n 3 2 / + 21776 n + 130848 n + 94752 n + 17280) / (4 ( / 8 7 6 5 4 3 2 4 n + 84 n + 625 n + 1772 n + 316 n - 4894 n - 1065 n + 2318 n + 840 2 ) n ) and in Maple notation 1/4*(1921*n^10+8226*n^9-5972*n^8-48226*n^7-10949*n^6+56672*n^5+44712*n^4+21776* n^3+130848*n^2+94752*n+17280)/(4*n^8+84*n^7+625*n^6+1772*n^5+316*n^4-4894*n^3-\ 1065*n^2+2318*n+840)/n^2 The limit has n goes to infinity is 1921 ---- 16 The scaled, 7, -th moment is 1/2 / 23 22 21 20 9 2 |(5697769 n + 60641735 n + 134015792 n - 696733232 n \ 19 18 17 16 - 3442333038 n - 498098634 n + 22948889696 n + 40306812616 n 15 14 13 12 - 33185969699 n - 199153017941 n - 234163379336 n + 172792134208 n 11 10 9 + 921714126752 n + 1106655041280 n - 203058193920 n 8 7 6 - 2343379822976 n - 3195738586624 n - 1352083093504 n 5 4 3 + 2109172590592 n + 4294051012608 n + 3623441854464 n 2 / 20 19 + 1660305420288 n + 400387276800 n + 39813120000) / ((32 n + 1840 n / 18 17 16 15 14 + 46720 n + 685400 n + 6359586 n + 38095239 n + 140884135 n 13 12 11 10 + 258033200 n - 118611328 n - 1502753218 n - 1831974586 n 9 8 7 6 + 2398055960 n + 5500886650 n - 1386315021 n - 6006429333 n 5 4 3 2 - 611343400 n + 2918191660 n + 1009612960 n - 462588736 n 3 \1/2 - 305679360 n - 45158400) n )| /8 / and in Maple notation 9/8*2^(1/2)*((5697769*n^23+60641735*n^22+134015792*n^21-696733232*n^20-\ 3442333038*n^19-498098634*n^18+22948889696*n^17+40306812616*n^16-33185969699*n^ 15-199153017941*n^14-234163379336*n^13+172792134208*n^12+921714126752*n^11+ 1106655041280*n^10-203058193920*n^9-2343379822976*n^8-3195738586624*n^7-\ 1352083093504*n^6+2109172590592*n^5+4294051012608*n^4+3623441854464*n^3+ 1660305420288*n^2+400387276800*n+39813120000)/(32*n^20+1840*n^19+46720*n^18+ 685400*n^17+6359586*n^16+38095239*n^15+140884135*n^14+258033200*n^13-118611328* n^12-1502753218*n^11-1831974586*n^10+2398055960*n^9+5500886650*n^8-1386315021*n ^7-6006429333*n^6-611343400*n^5+2918191660*n^4+1009612960*n^3-462588736*n^2-\ 305679360*n-45158400)/n^3)^(1/2) The limit has n goes to infinity is 21483 ----- 32 The scaled, 8, -th moment is 15 14 13 12 11 (272665 n + 1740750 n + 12727 n - 18736748 n - 26418689 n 10 9 8 7 6 + 55010542 n + 158466505 n + 79691200 n - 210040760 n - 374904528 n 5 4 3 2 - 186822752 n - 55809984 n - 299154816 n - 361286784 n - 151994880 n / 12 11 10 9 8 - 20901888) / (8 (8 n + 300 n + 4526 n + 34397 n + 130094 n / 7 6 5 4 3 2 + 162239 n - 326524 n - 802861 n + 356798 n + 766941 n - 23782 n 3 - 241656 n - 60480) n ) and in Maple notation 1/8*(272665*n^15+1740750*n^14+12727*n^13-18736748*n^12-26418689*n^11+55010542*n ^10+158466505*n^9+79691200*n^8-210040760*n^7-374904528*n^6-186822752*n^5-\ 55809984*n^4-299154816*n^3-361286784*n^2-151994880*n-20901888)/(8*n^12+300*n^11 +4526*n^10+34397*n^9+130094*n^8+162239*n^7-326524*n^6-802861*n^5+356798*n^4+ 766941*n^3-23782*n^2-241656*n-60480)/n^3 The limit has n goes to infinity is 272665 ------ 64 The scaled, 9, -th moment is 1/2 / 33 32 31 3 2 |(1655198037025 n + 24442989975755 n + 99325948967454 n \ 30 29 28 - 247349482198842 n - 2944463347579053 n - 4537669108889919 n 27 26 25 + 25095469506765772 n + 98853949400276720 n - 6787419512712585 n 24 23 - 674887772490430339 n - 1172313096157590434 n 22 21 + 1193338990146748446 n + 6986987133633964597 n 20 19 + 7947796270833853847 n - 8558888939606375976 n 18 17 - 39295831721854069876 n - 50974934033705462336 n 16 15 + 3328309294067192064 n + 135012387307267964928 n 14 13 + 259774761669826268160 n + 200671640686556542464 n 12 11 - 160163942990397713920 n - 678376882486616944640 n 10 9 - 961785424654611879936 n - 663534085840842424320 n 8 7 + 218936429150635229184 n + 1275182260431867740160 n 6 5 + 1902163307858545213440 n + 1768701823065766821888 n 4 3 + 1120268627006509744128 n + 482169709000102772736 n 2 + 134842017539955621888 n + 22080548153138872320 n + 1605566788219699200) / 28 27 26 25 24 / ((128 n + 12096 n + 523488 n + 13717648 n + 242270952 n / 23 22 21 20 + 3033634044 n + 27519736058 n + 180740846355 n + 835182719343 n 19 18 17 + 2480871584870 n + 3217881131136 n - 6568286136783 n 16 15 14 - 34781326332023 n - 37439672538000 n + 77342106178938 n 13 12 11 + 201528041283989 n - 32547868210767 n - 410293335028626 n 10 9 8 - 107387069560876 n + 425052260407431 n + 205031551689183 n 7 6 5 - 228510720003104 n - 163480031758344 n + 48672609530160 n 4 3 2 + 63194867798384 n + 6149543003520 n - 8980362835200 n 5 \1/2 - 3362010624000 n - 365783040000) n )| /16 / and in Maple notation 3/16*2^(1/2)*((1655198037025*n^33+24442989975755*n^32+99325948967454*n^31-\ 247349482198842*n^30-2944463347579053*n^29-4537669108889919*n^28+ 25095469506765772*n^27+98853949400276720*n^26-6787419512712585*n^25-\ 674887772490430339*n^24-1172313096157590434*n^23+1193338990146748446*n^22+ 6986987133633964597*n^21+7947796270833853847*n^20-8558888939606375976*n^19-\ 39295831721854069876*n^18-50974934033705462336*n^17+3328309294067192064*n^16+ 135012387307267964928*n^15+259774761669826268160*n^14+200671640686556542464*n^ 13-160163942990397713920*n^12-678376882486616944640*n^11-961785424654611879936* n^10-663534085840842424320*n^9+218936429150635229184*n^8+1275182260431867740160 *n^7+1902163307858545213440*n^6+1768701823065766821888*n^5+ 1120268627006509744128*n^4+482169709000102772736*n^3+134842017539955621888*n^2+ 22080548153138872320*n+1605566788219699200)/(128*n^28+12096*n^27+523488*n^26+ 13717648*n^25+242270952*n^24+3033634044*n^23+27519736058*n^22+180740846355*n^21 +835182719343*n^20+2480871584870*n^19+3217881131136*n^18-6568286136783*n^17-\ 34781326332023*n^16-37439672538000*n^15+77342106178938*n^14+201528041283989*n^ 13-32547868210767*n^12-410293335028626*n^11-107387069560876*n^10+ 425052260407431*n^9+205031551689183*n^8-228510720003104*n^7-163480031758344*n^6 +48672609530160*n^5+63194867798384*n^4+6149543003520*n^3-8980362835200*n^2-\ 3362010624000*n-365783040000)/n^5)^(1/2) The limit has n goes to infinity is 3859635 ------- 128 The scaled, 10, -th moment is 20 19 18 17 (60293041 n + 502892158 n + 358118476 n - 7458033428 n 16 15 14 13 - 19244546522 n + 27491268112 n + 164220751188 n + 142292552004 n 12 11 10 - 377851504383 n - 1106465764126 n - 966143685880 n 9 8 7 6 + 762199057760 n + 3102125164160 n + 3751578901760 n + 1982389829120 n 5 4 3 2 + 643225365504 n + 1802709909504 n + 2834653764096 n + 1874825450496 n / 16 15 14 + 563300904960 n + 62705664000) / (16 (16 n + 928 n + 22936 n / 13 12 11 10 9 + 312712 n + 2526433 n + 11843032 n + 26753496 n - 3695868 n 8 7 6 5 4 - 132419106 n - 117875524 n + 243135452 n + 191970116 n - 154454743 n 3 2 4 - 131575636 n + 22297916 n + 34505040 n + 6652800) n ) and in Maple notation 1/16*(60293041*n^20+502892158*n^19+358118476*n^18-7458033428*n^17-19244546522*n ^16+27491268112*n^15+164220751188*n^14+142292552004*n^13-377851504383*n^12-\ 1106465764126*n^11-966143685880*n^10+762199057760*n^9+3102125164160*n^8+ 3751578901760*n^7+1982389829120*n^6+643225365504*n^5+1802709909504*n^4+ 2834653764096*n^3+1874825450496*n^2+563300904960*n+62705664000)/(16*n^16+928*n^ 15+22936*n^14+312712*n^13+2526433*n^12+11843032*n^11+26753496*n^10-3695868*n^9-\ 132419106*n^8-117875524*n^7+243135452*n^6+191970116*n^5-154454743*n^4-131575636 *n^3+22297916*n^2+34505040*n+6652800)/n^4 The limit has n goes to infinity is 60293041 -------- 256 To sum up the limits of the scaled moments from the second up to the , 10, th are 1921 21483 272665 3859635 60293041 [1, 3/2, 25/4, 195/8, ----, -----, ------, -------, --------] 16 32 64 128 256 and in Maple notation [1, 3/2, 25/4, 195/8, 1921/16, 21483/32, 272665/64, 3859635/128, 60293041/256]