#OK to post homework
#Ariana Yousafzai, 12/06/2020, Assignment 23
1. [5, 2, 4, 2, 10, 8, 11, 3, 9, 10, 13, 13]
2. {{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]
3.  
RandTree(100);
{{1, 39}, {2, 72}, {2, 85}, {2, 100}, {3, 5}, {3, 13}, {3, 61}, 


  {4, 27}, {4, 67}, {4, 76}, {5, 37}, {6, 11}, {6, 96}, {7, 53}, 


  {8, 12}, {9, 18}, {9, 34}, {9, 83}, {10, 31}, {10, 59}, 


  {10, 63}, {11, 22}, {11, 73}, {11, 91}, {12, 35}, {12, 90}, 


  {13, 29}, {14, 49}, {15, 32}, {15, 49}, {16, 63}, {16, 67}, 


  {17, 44}, {17, 74}, {18, 25}, {19, 30}, {19, 40}, {19, 51}, 


  {20, 27}, {21, 98}, {22, 75}, {23, 67}, {23, 96}, {24, 73}, 


  {24, 88}, {25, 85}, {26, 41}, {28, 44}, {28, 69}, {30, 84}, 


  {32, 86}, {33, 64}, {34, 49}, {36, 52}, {36, 57}, {36, 58}, 


  {37, 75}, {38, 72}, {39, 90}, {40, 43}, {40, 60}, {40, 79}, 


  {40, 87}, {40, 90}, {41, 43}, {41, 93}, {42, 55}, {43, 65}, 


  {45, 70}, {46, 52}, {47, 68}, {47, 81}, {48, 87}, {50, 85}, 


  {51, 78}, {52, 68}, {52, 94}, {53, 61}, {53, 66}, {54, 63}, 


  {55, 100}, {56, 70}, {58, 80}, {58, 95}, {62, 87}, {64, 98}, 


  {65, 98}, {66, 83}, {69, 99}, {70, 75}, {71, 78}, {71, 92}, 


  {72, 74}, {74, 90}, {77, 91}, {80, 89}, {81, 93}, {81, 97}, 


  {82, 98}}




InvPruffer(Pruffer(%));
{{1, 39}, {2, 72}, {2, 85}, {2, 100}, {3, 5}, {3, 13}, {3, 61}, 


  {4, 27}, {4, 67}, {4, 76}, {5, 37}, {6, 11}, {6, 96}, {7, 53}, 


  {8, 12}, {9, 18}, {9, 34}, {9, 83}, {10, 31}, {10, 59}, 


  {10, 63}, {11, 22}, {11, 73}, {11, 91}, {12, 35}, {12, 90}, 


  {13, 29}, {14, 49}, {15, 32}, {15, 49}, {16, 63}, {16, 67}, 


  {17, 44}, {17, 74}, {18, 25}, {19, 30}, {19, 40}, {19, 51}, 


  {20, 27}, {21, 98}, {22, 75}, {23, 67}, {23, 96}, {24, 73}, 


  {24, 88}, {25, 85}, {26, 41}, {28, 44}, {28, 69}, {30, 84}, 


  {32, 86}, {33, 64}, {34, 49}, {36, 52}, {36, 57}, {36, 58}, 


  {37, 75}, {38, 72}, {39, 90}, {40, 43}, {40, 60}, {40, 79}, 


  {40, 87}, {40, 90}, {41, 43}, {41, 93}, {42, 55}, {43, 65}, 


  {45, 70}, {46, 52}, {47, 68}, {47, 81}, {48, 87}, {50, 85}, 


  {51, 78}, {52, 68}, {52, 94}, {53, 61}, {53, 66}, {54, 63}, 


  {55, 100}, {56, 70}, {58, 80}, {58, 95}, {62, 87}, {64, 98}, 


  {65, 98}, {66, 83}, {69, 99}, {70, 75}, {71, 78}, {71, 92}, 


  {72, 74}, {74, 90}, {77, 91}, {80, 89}, {81, 93}, {81, 97}, 


  {82, 98}}
4.  
#RandTree1(n):  inputs a positive integer n and outputs a random tree with n vertices using  #InvPruffer(C)
RandTree1:=proc(n) local f:
f:=RandF(n):
InvPruffer(f)[1]:
End:
RandTree is faster than RandTree1 because it only executes 2 functions, while RandTree executes 3 to get the final answer. 
5.  
tree:= RandTree(100) for K while K>100 do leaves:=(RandTree(100))end do tree;
6. By the binomial theorem, the recurrence may be rewritten as b(b+e)^e-1.