#Written by Kellen Myers, Feb. 12, 2009 # This file contains the procedures needed to make lots of trees of same height # For help, you can type HELP(); HELP:=proc() print(` DisplayTree(T) , AllTrees(h) , NumTrees(h) , ShowTrees(h) ` ); end: with(plots): DT:=proc(T,a,b,i) local v,pic: v:=[ (a+b)/2 , i ]; pic:=plot({v},style=point,axes=none,symbol=solidbox,symbolsize=20); if T[1]<>{} then pic:=display(pic,DT(T[1],a,(a+b)/2,i+1)); pic:=display(pic,plot( { v , [ (3*a+b)/4,i+1 ] } ) ); fi: if T[2]<>{} then pic:=display(pic,DT(T[2],(a+b)/2,b,i+1)); pic:=display(pic,plot( { v , [ (a+3*b)/4,i+1 ] } ) ); fi: pic; end: DisplayTree:=proc(T) DT(T,0,1,0) end: #let's get all the trees! -- also I wrote this one on my own! AllTrees:=proc(k) local S,Sk,i,j,Trees: option remember: if k=0 then RETURN( { {} } ) fi: Sk:=AllTrees(k-1); S:={}; for j from 0 to k-1 do S:=S union AllTrees(j): end: Trees:={}: for j from 1 to nops(S) do for i from 1 to nops(Sk) do Trees:=Trees union { [Sk[i],S[j]] , [S[j],Sk[i]] }: end: end: RETURN(Trees): end: #plots a sequence of plots in a nice rectangular format (not great for <4 plots). plotseq:=proc(plts) local n,i,a,b,plts2: n:=nops(plts): a:=floor(sqrt(n)): b:=ceil(n/a): plts2:=array(0..a-1,0..b-1): for i from 0 to n-1 do plts2[iquo(i,b),irem(i,b)]:=display(plts[i+1]): end: for i from n to a*b-1 do plts2[iquo(i,b),irem(i,b)]:=plot(0,x=0..1,axes=none,color=white): end: display(plts2): end: #Let's count them, using the shell of the recursion in AllTrees: NumTrees:=proc(k) local S,Sk: option remember: if k=0 then RETURN(1) fi: Sk:=NumTrees(k-1); S:=add(NumTrees(j),j=0..k-1): # Trees:=Trees union { [Sk[i],S[j]] , [S[j],Sk[i]] }: # In this line, we get two trees for each pair EXCEPT when they are the same (thus both lenght k), we double count, so subtract: RETURN(2*Sk*S-Sk^2): end: #Show them all of a specific height ShowTrees:=proc(n) plotseq([seq(DisplayTree(AllTrees(n)[i]),i=1..nops(AllTrees(n)))]) end: # The p will stand for a leaf of the tree, making it a bit easier to make sense of it. # You can check out NumTrees(i) in the online encyclopedia of integer sequences # Try the following lines: # read `W:\\kellenstrees.txt`; # p:=[ {} , {} ]: # DisplayTree([[p,p],[[p,p],p]]); # ShowTrees(3); # seq(nops(AllTrees(i)),i=0..4); # seq(NumTrees(i),i=0..8);