#OK to post
#Soham Palande, Assignment 23, 12/06/2020



#PART 1

#Pick a random tree, T, using RandTree(14); of M23.txt and find its Pruffer Code, BY HAND! Check that it agrees with #Pruffer(T);


T:=RandTree(14)
T := {{1, 5}, {2, 6}, {2, 11}, {3, 10}, {4, 9}, {4, 13}, {5, 11}, {6, 7}, {6, 10}, {7, 13}, {8, 12}, {8, 14}, {11, 12}}

Pruffer(T)
[5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]

#The code agrees with my drawing 



#PART 2

#Pick a random function from {1,2,..., 15} to itself, using RandF(15), call it f, and find, BY HAND, the doubly-rooted #tree that you get with Joyal's mapping. Check that it is the same as Joyal(f).


f:=RandF(15)
f := [5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 14]

Joyal(f)
{{1, 5}, {2, 4}, {2, 5}, {2, 10}, {3, 9}, {3, 11}, {4, 6}, {7, 8}, {8, 11}, {9, 10}, {10, 13}, {12, 13}, {13, 14}, {14, 15}}, [11, 12]

#The code agrees with my drawing 



#PART 3

#Running the following pair of statements several times gives true each time

T:=RandTree(100):

evalb(T=InvPruffer(Pruffer(T)))
true


#PART 4

#RandTree1(n): A random tree on n vertices using InvPruffer(C). Try:
#RandTree1(30);

RandTree1:=proc(n) local f,s:
f:=RandF(n):
s:=[]:
s:=[seq(f[i],i=1..nops(f)-2)]:
InvPruffer(s):
end:

#Running the following statements several times:

time(RandTree1(2000))
1.562

time(RandTree(2000))
.328


#RandTree() is much faster than RandTree1() which uses InvPruffer(C).


#PART 5

EstAveLeaves:=proc(n,K) local sum,leaves,T,est,i:
sum:=0:
leaves:=0:
est=0:
for i from 1 to K do
   T:=RandTree(n): 
   leaves:=nops(Leaves(T)):
   sum:=sum+leaves:
od:
est:=sum/K:
evalf(est)
end proc:

#Running EstAveLeaves(100,1000) several times, we get

EstAveLeaves(100,1000)
37.42200000

#The value is pretty close to 99/e (the value derived in lecture)

evalf(99/exp(1))
36.42006468


#PART 6

R:=proc(e,b) local s,sum1:
option remember:
if e=0 then
 RETURN(1)
fi:
sum1:=add(binomial(e,s)*(b^s)*R(e-s,s),s=1..e):
sum1:
end proc:

#Evaluating empirically using the formula b(b+e)^(e-1)

#R(e,b) = b(b+e)^(e-1)

R(7,5)
14929920

(12^6)*5
14929920