#OK to post homework
#Karnaa Mistry, 12/6/20, Assignment HW #23

with(combinat):

# 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}}
# looks like:

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

# tree now looks like:

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

# 13 --> code so far [5,10,11,4,13,6,7]
# 7 --> code so far [5,10,11,4,13,6,7,6]
# 6 --> code so far [5,10,11,4,13,6,7,6,2]
# 2 --> code so far [5,10,11,4,13,6,7,6,2,11]
# 11 --> code so far [5,10,11,4,13,6,7,6,2,11,12]

# 12 --> code is [5,10,11,4,13,6,7,6,2,11,12,8]

# This is the same as Pruffer(myT);




# 2.

# RandF(15) = [14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]
# graph looks like:

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

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

# Cycles = (13,6,10) ; (11) ; (2) ; (9)

# One line notation: 2 10 9 13 11 6

# tree:

               3
	           |
*2->10->9->13->11->6**
           |
	     7-14-1-12-8-5
		   |
		 4-15
    
# This is the same as Joyal(myf)




# 3.

# T:=RandTree(100): evalb(InvPruffer(Pruffer(T))=T) gives true for many T's




# 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.




# 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) gave values like 37.384, 37.476, 37.351, ...  Which are close to 36.42006468 (within 1.05 or so)




# 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