Question 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);

Answer 1: 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}}

[5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]

Question 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 := [14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]

Answer 2:
With roots 2, 6
{{1, 12}, {1, 14}, {2, 10}, {3, 11}, {4, 15}, {5, 8}, {6, 11}, {7, 14}, {8, 12}, {9, 10}, {9, 13}, {11, 13}, {13, 14}, {14, 15}}

Question 3:
Read and understand procedure Pruffer(T) and InvPruffer(C). Check empirically, for several choices of RandTree(100), that InvPruffer(Pruffer(T))=T

Answer 3:
I ran the following code often and it came out to be true every time
T:=RandTree(100):
evalb(InvPruffer(Pruffer(T))=T)
                              true


Question 4:
Write a competitor to RandTree, Call it RandTree1(n), that inputs a positive integer n and outputs a random tree with n vertices, but that uses procedure InvPruffer(C) rather than Joyal(f). First generated a random list of length n-2, whose entries are from {1, ..., n}, and then apply InvPruffer to it.
By typing
time(RandTree(2000));
several times, and your own
time(RandTree1(2000));
the same number of times, find out who is faster. Can you explain why?

Answer 4
RandTree1:=proc(n) local a, b, c:
option remember:
a:=[seq(rand(1..n)(), i=1..n-2)]:
b:=InvPruffer(a)
end proc:

Rand tree is faster. 

Question 5:
Write a procedure: EstAveLeaves(n,K), that inputs a positive integer n and a large positive integer K, and outputs an ESTIMATE for the average number of leaves in a labelled tree on n vertices.
[Hint: use RandTree(T), K times, finding the number of leaves (using nops(Leaves(T))]

Run EstAveLeaves(100,1000) several times. How close is it to 99/exp(1)? (that we got exactly in Lecture 22)


Answer 5:
EstAveLeaves:=proc(n, K) local ans, i:
ans:=0:
for i from 0 to K do:
ans:=ans + nops(Leaves(RandTree(n))):
od:
ans/K
end proc:

Running it a few times and we get a pretty close answer to 99/e

Question 6:
Read and understand this gem, for yet another proof of Cayley's formula. Implement in Maple the function R(e,b) given by equation (*) (Remember to use "option remember"), and verify empirically that it equals indeed b(b+e)e-1

Answer 6
R:=proc(e, b) local s, fin, l:
option remember:
print(e):
if e = 1 then:
return 1:
fi:
for s from 1 to e do:
l:=R(e-s, s):
fin:=fin+binomial(e, s)*b^3*l:
od:
fin
end proc: