#OK to post homework
#Kent Mei, 12/06/20, Assignment 23

#---------------------------------
#Part 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}}

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

#Leaf 1 : [5]
#Leaf 3 : [5,10]
#Leaf 5 : [5,10,11]
#Leaf 9 : [5,10,11,4]
#Leaf 4 : [5,10,11,4,13]
#Leaf 10: [5,10,11,4,13,6]
#Leaf 13: [5,10,11,4,13,6,7]
#Leaf 7 : [5,10,11,4,13,6,7,6]
#Leaf 6 : [5,10,11,4,13,6,7,6,2]
#Leaf 2 : [5,10,11,4,13,6,7,6,2,11]
#Leaf 11: [5,10,11,4,13,6,7,6,2,11,12]
#Leaf 12: [5,10,11,4,13,6,7,6,2,11,12,8]

#Pruffer(T);
#[5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]

#---------------------------------
#Part 2

#      1   2   3  4  5  6  7   8  9 10  11  12  13  14  15
#f := [5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 14]
#

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

#Cycles: (3,11,10,9)(12,13)
# 3  9  10  11  12  13
# 11 3   9  10  13  12


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

#Doubly-Rooted Tree:
#{{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]

#Joyal(f);
#{{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]

#They match.


#---------------------------------
#Part 3

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

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

#It continues to be true for various choices of RandTree(100).

#---------------------------------
#Part 4

RandTree1:=proc(n) local i,ra, C:

ra:= rand(1..n);
C := [seq(ra(), i = 1..n-2)]:

InvPruffer(C):

end:

#[seq(time(RandTree(2000)),i = 1..5)];
#[.156, .203, .187, .218, .218]

#[seq(time(RandTree1(2000)),i = 1..5)];
#[1.750, 1.562, 1.546, 1.578, 1.578]

#The regular RandTree procedure is faster than the RandTree1 procedure.
#It seems to me that the mex procedure in the InvPruffer procedure might be causing the longer runtime. For really large n, finding the smallest integer not in S can take O(n) runtime and doing that procedure n times would make InvPruffer run in O(n^2). Meanwhile, the Joyal procedure in RandTree seems to only take O(n) time meaning RandTree would be faster.

#---------------------------------
#Part 5

EstAveLeaves:=proc(n,K) local sum, i, T:

sum := 0:
for i from 1 to K do
	T := RandTree(n):
	sum := sum + nops(Leaves(T)):
od:

sum / K:

end:

#[seq(evalf(EstAveLeaves(100,1000)),i = 1..5)]
#[37.25400000, 37.36700000, 37.34700000, 37.54600000, 37.36500000]

#evalf(99/exp(1)) = 36.42006468
#The estimate is fairly close, but I think 

#---------------------------------
#Part 6

R:=proc(e,b) local s: 
option remember:

if e = 0 then:
	return 1:
fi:

add(binomial(e,s) * b^s * R(e-s,s), s = 1..e);

end:

#L1 := [seq(seq(R(e,b),e = 1..10),b = 1..10)]
#L2 := [seq(seq(b*(b+e)^(e-1),e = 1..10), b = 1..10)]

#evalb(L1 = L2) = true as desired.

#---------------------------------
#Part 7

#Optional challenge, did not have the chance to do it.