#OK to post homework
#Hari Amoor, December 6, 2020, Homework Assn. #23

# Question 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}}
# is the following graph:

		3-10
		  |
	    2-6-7-13-4-9       
		|		  
    1-5-11-12-8-14         
	
# 1 => [5]
# 3 => [5,10]
# 5 => [5,10,11]
# 9 => [5,10,11,4]
# 4 => [5,10,11,4,13]
# 10 => [5,10,11,4,13,6]

# The tree is now as follows:

	    2-6-7-13       
		|		  
        11-12-8-14      

# 13 => [5,10,11,4,13,6,7]
# 7 => [5,10,11,4,13,6,7,6]
# 6 => [5,10,11,4,13,6,7,6,2]
# 2 => [5,10,11,4,13,6,7,6,2,11]
# 11 => [5,10,11,4,13,6,7,6,2,11,12]
# 12 => [5,10,11,4,13,6,7,6,2,11,12,8]

# This is isomorphic to the result of  Pruffer(myT).

# Question 2

# RandF(15) = [14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]
# The graph is as follows (roughly drawn):

		4->15
           |
		   v
        7->14<-1<-12<-8<-5
	       |
		   v
    1 <=== 13->6->10 
           ^      |
		   |______v

	
   
	3->11(self)      2(self)	9(self)

# The cycles are as follows: 2 10 9 13 11 6
# The tree is drawn as follows:

               3
	           |
*2->10->9->13->11->6**
           |
	     7-14-1-12-8-5
		   |
		 4-15
    
# This is isomorphic to the result of Joyal(myf).

# Question 3

# T:=RandTree(100): evalb(InvPruffer(Pruffer(T))=T) gives true for many different values T

# Question 4

RandTree1:=proc(n) local C:

if n=2 then
    return({{1,2}}):
fi:
if n=1 then
    return({}):
fi:
    
C:=RandF(n-2):
InvPruffer(C):

end:

# RandTree [.156,.484,.218] seems to be faster than RandTree1 [1.875,1.812,1.734].  RandTree might be faster due to how it
# primarily uses edges, and the RandF already creates such a relationship of 'edges' for Joyal to use when finding cycles
# and getting the result, where as RandTree1 needs InvPruffer, which performs mex in its own for loop roughly n-2 times
# while mex has the worst-case of going all the way from i to n-1 before returning i, which is a lot more looping
# in the long run.

# RandTree seems to be faster than RandTree1, mostly because it uses edges to find cycles as opposed tfo InvPruffer. We see that
# the mathematical time-complexity of the latter is an order of magnitude lesser than that of the former.

# Question 5

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

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

res:=evalf(sum/K):

return(res):
end:

# Running it with (100,1000) supplied values within a single unit of 36.42006468.

# Question 6

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

if e=0 then return(1): fi:

res:=0:
for s from 1 to e do:
res:=res+binomial(e,s)*b^s*R(e-s,s):
od:

return(res):

end:

# evalb(R(e,b)=b*(b+e)^(e-1)) returns true for different values of e,b