# Ross Berkowitz hw12.txt #Permission to post granted Help12:=proc(): print("Tn(n),C3(n),C3Fast(n),RandTT(n),RandBGT(n,a)"): end: #### 1 ############################################### #Tn returns the Hecke Operator giving all sublattices of index n. Tn:=proc(n) local S,S1,S2,S3,t1,t2,t3,k,j: option remember: if n=0 then RETURN({}): elif n=1 then RETURN({[]}): fi: S:={}: for k from 1 to n-2 do for j from 1 to n-k-1 do S1:=Tn(k): S2:=Tn(j): S3:=Tn(n-k-j): S:=S union {seq(seq(seq([t1,t2,t3],t3 in S3), t2 in S2), t1 in S1)}: od: od: S: end: ############### 2 ################################## C3:=proc(n) local k,j: option remember: if n=1 then RETURN(1): fi: add(add(C3(k)*C3(j)*C3(n-k-j), j=1..n-k-1),k=1..n-2): end: ## After plugging the resulting sequence into OEIS the following formula will also work, #and be much faster C3Fast:=proc(n) local m: if 0=n mod 2 then RETURN(0): fi: m:=(n-1)/2: 1/(2*m+1)*binomial(3*m,m): end: ####################### 3 ################################# RandTT:=proc(n) local j,k,j1,k1: if n=1 then RETURN([]): fi: if n=3 then RETURN([[],[],[]]) fi: if 0=n mod 2 then RETURN(FAIL) fi: k1:=RollLD([seq(add(C3(k)*C3(j)*C3(n-k-j), j=1..n-k-1),k=1..n-2)]): j1:=RollLD([seq(C3(j)*C3(n-k1-j), j=1..(n-k1-1))]): [RandTT(k1),RandTT(j1),RandTT(n-k1-j1)]: end: ######################## 4 ############################ RandBGT:=proc(n,a) local T,L,i: T:=RandBT(n): for i from 1 to n do L[i]:=rand(1..a)(): od: DressUp(T,[seq(L[i],i=1..n)]): end: ###### From class Code ########### #March 4, 2013 Gambling (binary trees) Help:=proc(): print(` BT(n) , NuL(T) , DressUp(T,L) `): print(` C(n), RollLD(L) , RandBT(n) `): end: #BT(n): The set of all fulll binary trees #every vertex has either TWO children or ZERO children #(then it is called a leaf) #with n leaves, in the format #Tree=[] or [T1,T2] (T1 and T2 are smaller trees) BT:=proc(n) local k, S, S1,S2,t1,t2: option remember: if n=0 then RETURN({}): fi: if n=1 then RETURN({ [ ] }): fi: S:={}: for k from 1 to n-1 do S1:=BT(k): S2:=BT(n-k): S:=S union {seq(seq([t1,t2], t1 in S1), t2 in S2)}: od: S: end: #NuL(T): the number of leaves of T NuL:=proc(T) option remember: if T=[] then 1: else NuL(T[1])+NuL(T[2]): fi: end: #DressUp(T,L): inputs a "naked" binary tree with #n (say) leaves and a list of numbers and #sticks the numbers in order from left to right #For example #DressUp([[],[[],[]]],[4,1,3]); #should be [[4],[[1],[3]]] DressUp:=proc(T,L) local k, T1, T2: if nops(L)<>NuL(T) then RETURN(FAIL): fi: if nops(L)=1 then RETURN([L[1]]): #wise-guy Jacob Baron claims (mathematically correctly #but morally incorrectly) that [L[1]] is the same L fi: k:=NuL(T[1]): T1:=DressUp(T[1],[op(1..k,L)]): T2:=DressUp(T[2],[op(k+1..nops(L),L)]): [ T1, T2]: end: #C(n): the number of full binary trees with n leaves C:=proc(n) local k: option remember: if n=1 then 1: else add(C(k)*C(n-k), k=1..n-1): fi: end: #RollLD(L): inputs a list of NON-NEGATIVE #integers and outputs an integer from 1 #nops(L) such that the prob. of getting i #is L[i]/convert(L,`+`): RollLD:=proc(L) local Tot,ra,j,i,m : Tot:=convert(L,`+`): j:=rand(1..Tot)(): for i from 1 to nops(L) while add(L[m],m=1..i)