Help:=proc(): print(`CBT(k), cbt(k), LC(p), RCBT(p,k,Sad, Happy)`): print(`RCBTH(k)`): end: #CBT(k): the set of complete binary trees with k leaves #(and k-1 inernal vertices) CBT:=proc(k) local S,i,S1,S2,s1,s2: option remember: if k=1 then RETURN({ []}): fi: S:={}: for i from 1 to k-1 do S1:=CBT(i): S2:=CBT(k-i): S:= S union {seq(seq( [s1 , s2], s1 in S1), s2 in S2)}: od: S: end: #cbt(k): the set of complete binary trees with k leaves #(and k-1 inernal vertices) cbt:=proc(k) local i: option remember: if k=1 then RETURN(1): fi: add(cbt(i)*cbt(k-i),i=1..k-1): end: #LC(p): a loaded coin prob. p of success(1) , 1-p failure (0) LC:=proc(p) local a,b,ra,r: a:=numer(p): b:=denom(p): ra:=rand(1..b): r:=ra(): if r<=a then 1: else 0: fi: end: #RCBT(p,k,Sad, Happy) : a random complete binary tree with prob. of having kids #=p, with <=k leaves RCBT:=proc(p,k,Sad,Happy) local IV,LL,DL,c,leaf,g: LL:={1}: c:=1: DL:={}: IV:={}: while (LL<>{} and nops(DL)+nops(LL)<=k) do leaf:=LL[1]: g:=LC(p): LL:=LL minus {leaf}: if g=0 then DL:=DL union {leaf}: else IV:=IV union {[leaf, [c+1,c+2 ] ] }: LL:=LL union {c+2,c+1}: c:=c+2: fi: od: if LL={} then RETURN(Sad): else RETURN(Happy): fi: end: #RCBTH(k) : a random complete binary tree with prob. of having kids #=p, with <=k leaves RCBTH:=proc(k) local IV,LL,DL,c,leaf,g,p: p:=1/2: LL:={1}: c:=1: DL:={}: IV:={}: while (LL<>{} and nops(DL)+nops(LL)<=k) do leaf:=LL[1]: g:=LC(p): LL:=LL minus {leaf}: if g=0 then DL:=DL union {leaf}: else IV:=IV union {[leaf, [c+1,c+2 ] ] }: LL:=LL union {c+2,c+1}: c:=c+2: fi: od: if LL={} then RETURN(nops(DL)): else RETURN(FAIL): fi: end: