#OK to post homework
#William Wang, 12/3/2020, Assignment 23

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

What this tree looks like:
        7 1  12
        | |   |        
4-8-11-10-5-3-2-9-13
        | |
        6 14

By hand: 5,8,10,10,11,10,5,2,9,2,3,5

Pruffer(rt);
  [5, 8, 10, 10, 11, 10, 5, 2, 9, 2, 3, 5]

#They agree!



#2.
f := RandF(15);
  f := [7, 8, 9, 1, 10, 2, 11, 4, 7, 13, 8, 1, 6, 4, 1]

Two line notation:
1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
7   8   9   1   10  2   11  4   7   13  8   1   6   4   1

What this tree looks like:
           3
           |
           v
     15    9
      |    |
      v    v
12 -> 1 -> 7 -> 11
      ^        / 
       \      v    
        4 <- 8 <- 2 <- 6 <- 13 <- 10 <- 5
        ^
	|
       14

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

#They are the same



#3.
test1 := RandTree(100);
test2 := RandTree(100);
test3 := RandTree(100);
test4 := RandTree(100);
test5 := RandTree(100);
evalb(InvPruffer(Pruffer(test1)) = test1);
  true

evalb(InvPruffer(Pruffer(test2)) = test2);
  true

evalb(InvPruffer(Pruffer(test3)) = test3);
  true

evalb(InvPruffer(Pruffer(test4)) = test4);
  true

evalb(InvPruffer(Pruffer(test5)) = test5);
  true



#4.
RandTree1 := proc(n) local f:
f := RandF(n):
InvPruffer(F):
end:

seq(time(RandTree(2000)), i = 1 .. 5);
  0.546, 0.140, 0.375, 0.171, 0.453

seq(time(RandTree1(2000)), i = 1 .. 5);
  0., 0., 0., 0., 0.

#RandTree1 is faster, since it is more efficient to invert the Pruffer code (get the tree from the Pruffer code).



#5.
EstAveLeaves := proc(n, K) local i:
add(nops(Leaves(RandTree(n))), i = 1 .. K)/K:
end:

seq(evalf(EstAveLeaves(100, 100)), i = 1 .. 5);
  38.07000000, 36.66000000, 37.20000000, 37.80000000, 37.82000000

evalf(99/exp(1));
  36.42006468

#Pretty close, off slightly.



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

B := proc(e, b):
b*(e + b)^(e - 1):
end:

{seq(seq(evalb(R(e, b) = B(e, b)), b = 1 .. 10), e = 1 .. 10)};
  {true}