> #ok to post 
;
> #Yifan Zhang, 12/2/2020
;
> 
;
> #Q1.
;
> #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);
> read `M23.txt`;
> RandTree(14);
{{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}}
;
> #[5,2,4,2,10,8,11,3,9,10,13,13];
> Pruffer({{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}});
[5, 2, 4, 2, 10, 8, 11, 3, 9, 10, 13, 13]
;
> 
;
> #Q2.
;
> #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).
;
> RandF(15);
[14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]
;
> 
;
> #cycle: (13,6,10),(11),(2),(9)
;
> #2 6  9 10 11 13
;
> #2 10 9 13 11 6
> 
> 
> #              3 
> #              |
;
> #2*->10->9->13->11->6**
;
> #           |  
;
> #        7-14-1-12-8-5
;
> #           |
;
> #          15
;
> #           |
;
> #           4
;
> Joyal([14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]);
{{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}}, [2, 6]
;
> 
;
> #Q3.
;
> #Read and understand procedure Pruffer(T) and InvPruffer(C). Check empirically, for several choices of RandTree(100), that InvPruffer(Pruffer(T))=T
;
> g:=RandTree(100):
> evalb(InvPruffer(Pruffer(g))=g);
true
;
> #The procedure of Pruffer is to add the code one by one. If the number of edges is more than 1, it will choose the minimum value of leaves, and add its neighbor to the result list, and re-size the tree. Once the number of edges is 1. Return the result list. 
;
> 
;
> #Q4.
;
> #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?
> 
;
> RandTree1:=proc(n) local f:
> f:=RandF(n):
> InvPruffer(f);
> end:
> 
> 
;
> time(RandTree1(2000));
1.718
;
> time(RandTree(2000));
.203
;
> #Using Joyal(f) is faster. Joyal algorithm does not has cycle which can save time.
;
> 
;
> #Q5.
;
> #Write a procedure: EstAveLeaves(n,K), that inputs a posive integer n and a large positive ineger 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)
;
> 
;
> EstAveLeaves:=proc(n,K) local i, g,s:
> s:=0:
> for i from 1 to K do
> g:=RandTree(n);
> s:=s+nops(Leaves(g));
> od:
> 
> s/K;
> 
> end:
> 
;
> 
;
> evalf(EstAveLeaves(100,1000));
37.44600000
;
> evalf(99/exp(1));
36.42006468
;
> 
;
> #Q6.
;
> #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
;
> with(combinat):
> R:=proc(e,b) local s, r:
> option remember:
> if e=0 then
> RETURN(1):
> fi:
> 
> r:=0;
> 
> for s from 1 to e do
> 
> r:=r+nops(choose(e,s))*(b^s)*R(e-s,s);
> 
> od:
> 
> r:
> 
> end:
> R(5,2);
4802
;
> b:=2: e:=5:
> b*(b+e)^(e-1);
4802
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;