#Ok to post homework
#Tifany Tong, December 6th, 2020, HW #23

# Question 1

# Random Tree: {{1, 6}, {2, 12}, {2, 14}, {3, 11}, {4, 7}, {4, 9}, {4, 12}, {5, 7}, {6, 14}, {8, 14}, {9, 13}, {10, 14}, {11, 12}}


# 3 - 11 - 12 - 4 - 7 - 5
#          |    | 
#          2    9 - 13
#          |
#  1 - 6 - 14 - 8
#          |
#          10

# Pruffer Code: [6, 11, 7, 14, 4, 14, 14, 12, 9, 4, 12, 2]

# It agrees with Pruffer(T). 

# Question 2

# f := [5, 6, 14, 3, 3, 14, 6, 5, 14, 15, 7, 11, 9, 15, 12]

# 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
# 5  6  14 3  3  14 6  5  14 15   7  11  9   15  12

#           13
#           |
#    8  4   9   10
#    |  |   |   |
# 1->5->3->14->15->12->11->7->6->2
#           ^_________________|

# Loops: [14,15,12,11,7,6] 

# pi(14) = 15, pi(15) = 12, pi(12) = 11, pi(11) = 7, pi(7) = 6, pi(6) = 14.

# 6  7  11  12  14  15
# 14 6  7   11  15  12

#     13
#      |
#      9   2            10
#      |   |             |
# 1  *14 - 6 - 7 - 11 - 15 - 12**
# |    |
# 5 -  3 - 4
# |
# 8 

# The doubly-rooted tree that I get with Joyal's mapping is the same as Joyal(f). 

# Question 3

L := RandTree(100);
L := {{1, 49}, {2, 13}, {2, 48}, {2, 92}, {3, 50}, {3, 53}, 
  {4, 30}, {4, 98}, {5, 11}, {5, 95}, {6, 48}, {7, 29}, {8, 50}, 
  {9, 21}, {9, 28}, {10, 20}, {10, 40}, {10, 45}, {11, 33}, 
  {11, 59}, {12, 89}, {13, 35}, {14, 41}, {14, 92}, {15, 96}, 
  {16, 32}, {16, 87}, {16, 98}, {16, 99}, {17, 72}, {18, 64}, 
  {19, 22}, {19, 88}, {19, 98}, {20, 26}, {20, 33}, {21, 79}, 
  {21, 100}, {22, 52}, {23, 70}, {23, 75}, {23, 81}, {23, 91}, 
  {24, 36}, {24, 43}, {25, 43}, {25, 71}, {27, 91}, {29, 84}, 
  {29, 97}, {30, 63}, {31, 74}, {33, 47}, {34, 82}, {35, 80}, 
  {36, 39}, {36, 58}, {37, 45}, {37, 46}, {38, 83}, {38, 85}, 
  {39, 42}, {39, 64}, {40, 78}, {40, 86}, {40, 89}, {43, 90}, 
  {44, 50}, {47, 51}, {48, 69}, {49, 58}, {51, 99}, {52, 57}, 
  {53, 57}, {54, 61}, {55, 65}, {55, 94}, {56, 97}, {58, 92}, 
  {60, 74}, {61, 76}, {61, 77}, {61, 85}, {62, 73}, {62, 83}, 
  {63, 77}, {66, 97}, {67, 79}, {68, 91}, {71, 93}, {72, 73}, 
  {74, 86}, {75, 94}, {77, 82}, {78, 91}, {78, 96}, {79, 90}, 
  {80, 83}, {83, 84}}

L := RandTree(100);
L := {{1, 6}, {2, 36}, {3, 42}, {3, 52}, {3, 90}, {4, 42}, 
  {5, 69}, {6, 60}, {6, 73}, {7, 31}, {7, 59}, {7, 91}, {8, 44}, 
  {8, 54}, {8, 62}, {9, 44}, {10, 25}, {10, 63}, {10, 71}, 
  {11, 37}, {11, 90}, {12, 37}, {13, 66}, {14, 100}, {15, 61}, 
  {15, 69}, {16, 44}, {17, 45}, {17, 57}, {18, 75}, {19, 99}, 
  {20, 39}, {20, 70}, {20, 88}, {21, 81}, {22, 35}, {22, 52}, 
  {23, 77}, {23, 80}, {23, 91}, {24, 41}, {25, 34}, {25, 85}, 
  {26, 48}, {27, 44}, {27, 47}, {27, 75}, {28, 74}, {29, 86}, 
  {29, 93}, {30, 92}, {32, 75}, {32, 92}, {33, 36}, {33, 64}, 
  {34, 84}, {37, 60}, {38, 85}, {40, 64}, {41, 45}, {41, 99}, 
  {43, 58}, {43, 65}, {44, 78}, {45, 72}, {46, 82}, {47, 53}, 
  {48, 98}, {49, 51}, {49, 89}, {50, 58}, {51, 75}, {51, 77}, 
  {52, 76}, {54, 68}, {55, 70}, {55, 73}, {56, 99}, {58, 74}, 
  {60, 96}, {60, 97}, {61, 86}, {64, 68}, {65, 66}, {65, 94}, 
  {67, 74}, {69, 85}, {72, 73}, {74, 82}, {76, 100}, {79, 80}, 
  {81, 96}, {82, 95}, {83, 85}, {87, 95}, {90, 98}, {91, 95}, 
  {93, 95}, {95, 99}}

L := RandTree(100);
L := {{1, 15}, {1, 59}, {1, 79}, {2, 19}, {2, 62}, {2, 68}, 
  {2, 71}, {3, 18}, {4, 31}, {4, 74}, {5, 41}, {6, 89}, {7, 63}, 
  {8, 13}, {8, 14}, {8, 85}, {9, 49}, {10, 79}, {11, 20}, 
  {12, 28}, {12, 92}, {14, 20}, {14, 55}, {14, 100}, {15, 36}, 
  {16, 56}, {16, 96}, {17, 47}, {18, 43}, {18, 60}, {19, 79}, 
  {20, 29}, {20, 36}, {20, 90}, {21, 81}, {22, 77}, {22, 82}, 
  {22, 91}, {23, 55}, {23, 66}, {24, 42}, {24, 70}, {25, 45}, 
  {25, 80}, {25, 94}, {26, 37}, {26, 43}, {27, 55}, {28, 85}, 
  {29, 95}, {30, 60}, {31, 36}, {32, 63}, {32, 86}, {33, 52}, 
  {33, 75}, {34, 67}, {34, 99}, {35, 39}, {35, 49}, {35, 72}, 
  {35, 98}, {37, 91}, {38, 55}, {39, 66}, {40, 49}, {41, 69}, 
  {43, 93}, {44, 51}, {45, 78}, {45, 96}, {46, 63}, {47, 66}, 
  {48, 88}, {50, 53}, {50, 57}, {50, 70}, {51, 66}, {52, 80}, 
  {53, 97}, {54, 68}, {54, 86}, {56, 99}, {57, 73}, {58, 61}, 
  {58, 73}, {60, 73}, {60, 89}, {62, 81}, {63, 82}, {63, 84}, 
  {64, 73}, {65, 67}, {65, 91}, {69, 73}, {69, 87}, {76, 88}, 
  {79, 83}, {88, 100}}

# With these 3 random trees, InvPruffer(Pruffer(T)) = T. 

# Question 4

RandTree1 := proc(n) local i, curr, ra, ans:
ra := rand(1 .. n):
curr := [seq(ra(), i = 1 .. n - 2)]:
return InvPruffer(curr):
end:

checkRandTree := proc() local i, ans, sum:
sum := 0:
for i to 20 do 
    sum := sum + time(RandTree(2000)):
od: 
1/20*sum:
end:

checkRandTree1 := proc() local i, ans, sum:
sum := 0:
for i to 20 do 
    sum := sum + time(RandTree1(2000)):
od: 
1/20*sum:
end:

# checkRandTree() = 0.2614000000 
# checkRandTree1() = 1.873000000

# Random Tree appears to be faster, and this seems to be because InvPruffer is O(n^2) in 
# time complexity whereas Joyal is only O(n) in time complexity. 

# Question 5

EstAveLeaves := proc(n, K) local i, T, sum, ans:
sum := 0:
for i to K do 
    T := RandTree(n):
    sum := sum + nops(Leaves(T)):
od: 
sum := sum/K:
return sum:
end:

# evalf(EstAveLeaves(100, 1000)) = 37.26000000

# evalf(99/exp(1)) = 36.42006468

# EstAveLeaves(100,1000) is quite close to 99/exp(1). 

# Question 6

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

# R(5,1) = 1296 = 1(1+5)^4
# R(6,2) = 65536 = 2(2+6)^5 
# R(6,3) = 177147 = 3(3+6)^5
# R(5,3) = 12288 = 3(3+5)^4

# Empirically, R(e,b) seems to indeed equal b(b+e)^(e-1).