###################################################################### ##BinaryTrees: Save this file as BinaryTrees # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read BinaryTrees # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: Sept. 2012 print(`Created: Sept. 2012`): print(` This is BinaryTrees `): print(`It is one of the packages that accompany the article `): print(`Pick up sticks`): print(`by Larry Shepp, Doron Zeilberger, and Cun-Hui Zhang`): print(`available from Zeilberger's website and from arxiv.org`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: BhzN, BTs, fnr, Fnt, `): print(` FntDirect, FntSeqSlow`): print(` HeightT, LeavesT, MishkalT, phir, phirN, RollLD `): print(` wnr, Wnt, WntDirect, WntSeqSlow `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: AvF, AvW, FntSeq, RBT, RwBT, Simu,`): print(` SimuW, Stat, WntSeq `): print(` `): elif nops([args])=1 and op(1,[args])=AvF then print(`AvF(N): the list of expected height of complete binary trees`): print(`with n leaves`): print(` for n=1 to N`): elif nops([args])=1 and op(1,[args])=AvW then print(`AvW(N): the list of expected durations of the stick game of `): print(`length n for n=1 to N`): elif nops([args])=1 and op(1,[args])=BhzN then print(`BhzN(h,z,N): B^[h](z) in Eq. (3) of Flajolet-Odlyzko`): print(`J. Comp.Sys.Sci. v.25 (1982),171-213`): print(`Try: BhzN(10,z,8);`): elif nops([args])=1 and op(1,[args])=BTs then print(`BTs(n): all the complete binary trees on n leaves, try`): print(`BTs(5);`): elif nops([args])=1 and op(1,[args])=fnr then print(`fnr(n,r): the number of complete binary trees with`): print(`n leaves whose depth is r. Try:`): print(`fnr(10,3);`): elif nops([args])=1 and op(1,[args])=Fnt then print(`Fnt(n,t)`): print(`The polynomial in t whose coefficient of t^r is the`): print(`number of complete binary trees whose height is r`): print(`[Not as fast as doing FntSeq]`): print(`Try: Fnt(10,t);`): elif nops([args])=1 and op(1,[args])=FntDirect then print(`FntDirect(n,t):Fnt(n,t) done directly. ONLY FOR CHECKING`): print(`VERY SLOW`): print(`try FntDirect(5,t);`): elif nops([args])=1 and op(1,[args])=FntSeq then print(`FntSeq(N,t): the list of length N whose n-th entry is the`): print(`polynomial in t whose coeff. of t^r is the number`): print(`of complete binary trees with n leaves and height r`): print(`Try:`): print(`FntSeq(10,t);`): elif nops([args])=1 and op(1,[args])=FntSeqSlow then print(`FntSeqSlow(N,t): a slow version of FntSeq(N,t);`): print(`For checking purposes only`): print(`Try:`): print(`FntSeqSlow(N,t);`): elif nops([args])=1 and op(1,[args])=HeightT then print(`HeightT(T): the height of the binary tree T, try:`): print(`HeightT([[],[]]);`): elif nops([args])=1 and op(1,[args])=LeavesT then print(`LeavesT(T): the number of leaves of the complete binary tree T, try`): print(`LeavesT([[],[]]);`) elif nops([args])=1 and op(1,[args])=MishkalT then print(`MishkalT(T): the weight of a complete binary tree,`): print(`try: MishkalT([[],[]]);`): elif nops([args])=1 and op(1,[args])=phir then print(`phir(r,x): the generating function of all complete binary trees`): print(`of depth r, try phir(3,x), according to the weight x^(#leaves)`): elif nops([args])=1 and op(1,[args])=phirN then print(`phirN(r,x,N): the generating function of all complete binary trees`): print(`of depth r, truncated to N leaves try phirN(3,x,100);`): elif nops([args])=1 and op(1,[args])=psirN then print(`psirN(r,x,N): the generating function for the weight of`): print(`all complete binary trees`): print(`of depth r, truncated to N leaves try psirN(3,x,100);`): elif nops([args])=1 and op(1,[args])=RBT then print(`RBT(n): a uniformly-at-random complete binary tree with n leaves`): print(`Try RBT(10);`): elif nops([args])=1 and op(1,[args])=RwBT then print(`RwBT(n): a weight-W-random complete binary tree with n leaves`): print(`Try RwBT(10);`): elif nops([args])=1 and op(1,[args])=RollLD then print(`RollLD(L): Given a Loaded die, L, rolls it, try:`): print(`RollLD([1,3,2]);`): elif nops([args])=1 and op(1,[args])=Simu then print(`Simu(n,K,N): takes K random complete binary trees of n leaves`): print(`and finds the statistics up to the N-th moment.`): print(`Try: Simu(5,100,6);`): elif nops([args])=1 and op(1,[args])=SimuW then print(`SimuW(n,K,N): takes K W-weight `): print(`random complete binary trees of n leaves`): print(`and finds the statistics up to the N-th moment.`): print(`Try: SimuW(5,100,6);`): elif nops([args])=1 and op(1,[args])=Stat then print(`Stat(P,t,N): given a polynomial P of the variable t`): print(`representing the generating function (or prob. gen. function)`): print(`outputs a list whose `): print(` (i) first entry is the expectation `): print(` (ii) second entry is the variance `): print(` (iii) third entry is the square of the skewness `): print(` (iiii) 4th entry is the kurtosis (the fourth-moment about the mean `): print(`divided by the square of the variance)`): print(`(iv) for k>4, the alpha_k coefficient if k is even`): print(`and (alpha_k)^2 if k is odd. Try`): print(`Stat((1+t)^1000,t,20);`): elif nops([args])=1 and op(1,[args])=wnr then print(`wnr(n,r): the weight of the set of complete binary trees with`): print(`n leaves whose depth is r`): elif nops([args])=1 and op(1,[args])=Wnt then print(`Wnt(n,t): the polynomial in t whose coeff. of t^r is`): print(`the probability (in the stick distribution)`): print(`of a complete binary tree of having depth r`): elif nops([args])=1 and op(1,[args])=WntDirect then print(`WntDirect(n,t):Fnt(n,t) done directly. ONLY FOR CHECKING`): print(`VERY SLOW`): print(`try WntDirect(5,t);`): elif nops([args])=1 and op(1,[args])=WntSeq then print(`WntSeq(N,t): the list of length N whose n-th entry is the`): print(`prob. gen. functions of the random variable`): print(`height(T) over all complete binary trees with n leaves`): print(`according to the Shepp-stick prob. dist.`): print(`Try:`): print(`WntSeq(10,t);`): elif nops([args])=1 and op(1,[args])=WntSeqSlow then print(`WntSeqSlow(N,t): a slow version of WntSeq(N,t);`): print(`For checking purposes only`): print(`Try:`): print(`WntSeqSlow(N,t);`): else print(`There is no ezra for`,args): fi: end: #fnr(n,r): the number of complete binary trees with #n leaves whose depth is r. Try: #fnr(10,3); fnr:=proc(n,r) local a,s: option remember: if n=1 then if r=0 then RETURN(1): else RETURN(0): fi: fi: add(add(fnr(a,s)*fnr(n-a,r-1),s=0..r-2),a=1..n-1)+ add(add(fnr(a,r-1)*fnr(n-a,s),s=0..r-2),a=1..n-1)+ add(fnr(a,r-1)*fnr(n-a,r-1),a=1..n-1): end: #Fnt(n,t): #the polynomial in t whose coefficient of t^r is the #number of complete binary trees whose depth is r #try Fnt(5,t); Fnt:=proc(n,t) local r: add(fnr(n,r)*t^r,r=0..n-1): end: #wnr(n,r): the weight of the set of complete binary trees with #n leaves whose depth is r wnr:=proc(n,r) local a,s: option remember: if n=1 then if r=0 then RETURN(1): else RETURN(0): fi: fi: add(add(wnr(a,s)*wnr(n-a,r-1)/(n-1),s=0..r-2),a=1..n-1)+ add(add(wnr(a,r-1)*wnr(n-a,s)/(n-1),s=0..r-2),a=1..n-1)+ add(wnr(a,r-1)*wnr(n-a,r-1)/(n-1),a=1..n-1): end: #Wnt(n,t): the polynomial in t whose coeff. of t^r is #the probability (in the stick distribution) #of a complete binary tree of having depth r Wnt:=proc(n,t) local r: sort(add(wnr(n,r)*t^r,r=0..n-1)): end: #AvWslow(N): the list of expected durations of the stick game of length n # for n=1 to N AvWslow:=proc(N) local n,t: [seq(subs(t=1,diff(Wnt(n,t),t)),n=1..N)]: end: #phir(r,x): the generating function of all complete binary trees #of depth r, try phir(3,x), according to the weight x^(#leaves) phir:=proc(r,x) local s: option remember: if r=0 then RETURN(x): else expand(phir(r-1,x)^2+2*phir(r-1,x)*add(phir(s,x),s=0..r-2)): fi: end: #phirNold(r,x,N): the generating function of all complete binary trees #of depth r, truncated to N leaves try phirNold(3,x,100); phirNold:=proc(r,x,N) local s,gu,i: option remember: if r=0 then RETURN(x): else gu:=expand(phirNold(r-1,x,N)^2+2*phirNold(r-1,x,N)*add(phirNold(s,x,N),s=0..r-2)): RETURN(add(coeff(gu,x,i)*x^i,i=0..N)): fi: end: #psirN(r,x,N): the generating function for the weight of #all complete binary trees #of depth r, truncated to N leaves try phirN(3,x,100); psirN:=proc(r,x,N) local s,gu,i,t: option remember: if r=0 then RETURN(x): else gu:=expand(psirN(r-1,x,N)^2+2*psirN(r-1,x,N)*add(psirN(s,x,N),s=0..r-2)): gu:=normal(subs(x=x*t,gu)/t^2): gu:=int(gu,t=0..1): RETURN(add(coeff(gu,x,i)*x^i,i=0..N)): fi: end: #WntSeq(N,t): the list of length N whose n-th entry is the #prob. gen. functions of the random variable #height(T) over all complete binary trees with n leaves #according to the Shepp-stick prob. dist. #Try: #WntSeq(N,t); WntSeq:=proc(N,t) local gu,r,x,i: gu:=expand(add(psirN(r,x,N)*t^r,r=0..N)): [seq(sort(coeff(gu,x,i)),i=1..N)]: end: #WntSeqSlow(N,t): a slow version of WntSeq(N,t); #For checking purposes only #Try: #WntSeqSlow(N,t); WntSeqSlow:=proc(N,t) local n: [seq(Wnt(n,t),n=1..N)]: end: #AvW(N): the list of expected durations of the stick game of length n # for n=1 to N AvW:=proc(N) local t: subs(t=1,diff(WntSeq(N,t),t)): end: #FntSeq(N,t): the list of length N whose n-th entry is the #polynomial in t whose coeff. of t^r is the number #of complete binary trees with n leaves and height r #Try: #FntSeq(N,t); FntSeq:=proc(N,t) local gu,r,x,i: gu:=expand(add(phirN(r,x,N)*t^r,r=0..N)): [seq(sort(coeff(gu,x,i)),i=1..N)]: end: #FntSeqSlow(N,t): a slow version of FntSeq(N,t); #For checking purposes only #Try: #FntSeqSlow(N,t); FntSeqSlow:=proc(N,t) local n: [seq(Fnt(n,t),n=1..N)]: end: #AvF(N): the list of expected height of complete binary trees #with n leaves # for n=1 to N AvF:=proc(N) local t,gu,i: gu:=FntSeq(N,t): [seq(subs(t=1,diff(gu[i],t))/subs(t=1,gu[i]),i=1..N)]: end: #Stat(P,t,N): given a polynomial P of the variable t #representing the generating function (or prob. gen. function) #outputs a list whose #(i) first entry is the expectation #(ii) second entry is the variance #(iii) third entry is the square of the skewness #(iiii) 4th entry is the kurtosis (the fourth-moment about the mean #divided by the square of the variance) #(iv) for k>4, the alpha_k coefficient if k is even #and (alpha_k)^2 if k is odd. Try #Sta((1+t)^1000,t,20); Stat:=proc(P,t,N) local gu,P1,ka,ave,mo,k,var: ka:=subs(t=1,P): if ka=0 then RETURN(FAIL): fi: P1:=P/ka: ave:=subs(t=1,diff(P1,t)): P1:=P1/t^ave: P1:=t*diff(P1,t): P1:=t*diff(P1,t): var:=subs(t=1,P1): gu:=[ave,var]: for k from 3 to N do P1:=t*diff(P1,t): mo:=subs(t=1,P1): if k mod 2=1 then gu:=[op(gu),mo^2/var^k]: else gu:=[op(gu),mo/var^(k/2)]: fi: od: gu: end: Die:=proc(n) local k: option remember: [seq(binomial(2*k-2,k-1)/k*binomial(2*(n-k)-2,n-k-1)/(n-k),k=1..n-1)]: end: #RollLD(L): Given a Loaded die, L, rolls it, try: #RollLD([1,3,2]); RollLD:=proc(L) local i,r,N: N:=convert(L,`+`): r:=rand(1..N)(): for i from 1 to nops(L) while convert([op(1..i,L)],`+`)