> #Weiji Zheng, Homework 23, 2020/12/10
;
> #OK TO POST HOMEWORK
;
> 
;
> #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);
> 
;
> #RandTree(14)
> #{{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]
;
> 
;
> #Pruffer({{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]

;
> 
;
> #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)
> #[5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 14]

;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> #Joyal([5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 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}, {14, 15}}, [11, 12]
> 

;
> #Q3
;
> #Read and understand procedure Pruffer(T) and InvPruffer(C). Check empirically, for several choices of RandTree(100), that InvPruffer(Pruffer(T))=T
;
> 
;
> #t:=RandTree(50)
> #t := {{1, 28}, {2, 7}, {2, 24}, {3, 11}, {3, 14}, {3, 37}, {4, 14}, {4, 29}, {5, 47}, {6, 47}, {6, 48}, {7, 12}, {8, 19}, {8, 22}, {8, 39}, {9, 25}, {9, 35}, {9, 40}, {10, 17}, {10, 19}, {10, 26}, {10, 33}, {12, 36}, {12, 49}, {13, 31}, {13, 49}, {15, 21}, {15, 43}, {16, 37}, {17, 47}, {17, 49}, {18, 43}, {18, 45}, {19, 32}, {20, 27}, {21, 34}, {23, 47}, {23, 50}, {25, 38}, {26, 34}, {26, 37}, {26, 42}, {27, 41}, {28, 39}, {30, 44}, {40, 41}, {40, 46}, {41, 49}, {43, 44}}
> #evalb(InvPruffer(Pruffer(t))=t)
> #true

;
> #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):
> InvPruffer(RandF(n));
> end:

> #time(RandTree1(2000))
> #1.656
> #time(RandTree(2000))
> #.250
> 
;
> #Joyal is faster since it use no cycle.
;
> 
;
> #Q5
;
> #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.
> #[Hin#t: 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,r,s:
> s:=0:
> r:=0:
> for i from 1 to K do:
>     r := nops(Leaves(RandTree(n)));
>     s := s + r;
> od:
> 
> s/K:
> 
> end:

> #evalf(EstAveLeaves(100,1000))
> #37.37400000
> #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
;
> 
;
> R:=proc(e,b) local s:
> option remember:
> add(binomial(e,s)*b^s*R(e-s,s),s=1..e):
> end:
> 
;