#OK to post homework
#Tianyi Liu, Dec6, Assignment 23
1.
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}}

By hand:5, 2, 4, 2, 10, 8, 11, 3, 9, 10, 13, 13
Pruffer(T)
[5, 2, 4, 2, 10, 8, 11, 3, 9, 10, 13, 13]

2.
RandF(15)
[14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]


           
                  >6 
                 /   \>
8->12-> 1->14->13  -   10
          / ^   
        7   |   
        4->15  

3->11  2  9
 

2  6  9  10  11  13
2 10  9  13  11  

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

Joyal(f)
{{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.
T := {{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}}
evalb(InvPruffer(Pruffer(T))=T)
true

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

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

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

time(RandTree(2000));
.218
.250
.234
.125

time(RandTree1(2000));
1.953
1.890
1.875
1.828

Joyal output trees by find cycles but invpruffer has to go through for loop to find b[i]

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

evalf(99/exp(1))
36.42006468

evalf(EstAveLeaves(100,1000))
37.46800000
37.28200000
37.40200000
37.42300000

It is within 1 unit of difference

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

b:=4:
e:=6:
R(e,b)
400000
b*(b+e)^(e-1)
400000

b:=10:
e:=25:
R(e,b)
114191312420705803871750831604003906250
b*(b+e)^(e-1)
114191312420705803871750831604003906250

b:=23:
e:=78:
R(e,b)
494850048631107852277317801652235522139578818261222321303434746810789149409808258435676718416924755554407614583326539276932501603842570226136351665623157123
b*(b+e)^(e-1)
494850048631107852277317801652235522139578818261222321303434746810789149409808258435676718416924755554407614583326539276932501603842570226136351665623157123

It satisfies.