#OK to post
#Sam Minkin, 12/06, Assignment 23

QUESTION #1:

Our Tree:

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		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14
	      ^     ^
	      |     |   
	      4<-9  10<-3
				
	
Find the Pruffer code:


		1->5->11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5]
	      ^     ^
	      |     |   
	      4<-9  10<-3



		   5->11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10]
	      ^     ^
	      |     |   
	      4<-9  10<-3


		   5->11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10, 11]
	      ^     ^
	      |     |   
	      4<-9  10


		      11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10, 11, 4]
	      ^     ^
	      |     |   
	      4<-9  10


		      11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10, 11, 4, 13]
	      ^     ^
	      |     |   
	      4    10


		      11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10, 11, 4, 13, 6]
	            ^
	            |   
	           10


		      11->12		
		       ^   ^
		       |   |
	     13->7->6->2   8<-14	Code so far: [5, 10, 11, 4, 13, 6, 7]
	       

		      11->12		
		       ^   ^
		       |   |
	         7->6->2   8<-14	Code so far: [5, 10, 11, 4, 13, 6, 7, 6]


		      11->12		
		       ^   ^
		       |   |
	            6->2   8<-14	Code so far: [5, 10, 11, 4, 13, 6, 7, 6, 2]


		      11->12		
		       ^   ^
		       |   |
	               2   8<-14	Code so far: [5, 10, 11, 4, 13, 6, 7, 6, 2, 11]



	     11->12		
                  ^
	          |
	          8<-14	     Code so far: [5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12]


	         12		
                  ^
	          |
	          8<-14	     Code so far: [5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]



	          8<-14	     Code so far: [5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]




QUESTION #2:

Our function is:

RandF(14);
      F:=[14, 2, 11, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14]

This generates the following graph:

		       6<-12<-7
		       |	
		       v
             3->11->1->14(<-)    2(<-)
		^
		|
	        10<-5           

		4->8->9->13(<-)  5->10

The cycles in this graph are: (2), (13), (14)
The permutation is: Pi(2) = 2, Pi(13) = 13, Pi(14) = 14

The doubly rooted-tree is given by

	
		        6<-12<-7
			|
			v
        	2*->13->14**
                    ^   ^
		    |   |
	      4->8->9	1<-11<-3
                            ^
	               	    |
	                   10<-5  
				
Calling Joyal(F), we get:
{{1, 11}, {1, 14}, {2, 13}, {3, 11}, {4, 8}, {5, 10}, {6, 12}, {6, 14}, {7, 12}, {8, 9}, {9, 13}, {10, 11}, {13, 14}}, [2, 14]

This agrees with our doubly rooted-tree. It has the same roots and connections.


QUESTION #3:

checkPrufferInvPruffer:=proc(n) local i,C,T:

C:={}:

for i from 1 to n do:
	T:=RandTree(100):
	C:=C union {evalb(T = InvPruffer(Pruffer(T)))}:
od:

C:
end:

Running checkPrufferInvPruffer(5); we get {true}
Running checkPrufferInvPruffer(10); we get {true}

QUESTION #4:

Write a competitor to RandTree, Call it RandTree1(n), that inputs a positive integer n and outputs a random tree with n vertices, but that uses procedure InvPruffer(C) rather than Joyal(f). First generated a random list of length n-2, whose entries are from {1, ..., n}, and then apply InvPruffer to it.

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

end:

Running [seq(time(RandTree(2000)), i = 1 .. 5)];
              [0.328, 0.140, 0.296, 0.187, 0.203]

Running [seq(time(RandTree1(2000)), i = 1 .. 5)];
              [1.859, 1.765, 1.781, 1.734, 1.984]

We see that RandTree is consistently a magnitude faster than RandTree1. The major difference between these functions is how they obtain the random tree - Joyal(f) in the case of RandTree and InvPruffer(C) in the case of RandTree1. Calculating InvPruffer requires a nested loop which is time intensive and while Joyal also requires a nested operation, the space of which Joyal draws its values is a much smaller subset than that of InvPruffer. Typically, the number of cycles needed in Joyal will be much smaller than the number of vertices which are needed in InvPruffer. Hence, RandTree will run faster.

QUESTION #5:

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

c:=0:

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

c/K:

end:

Running [seq(evalf(EstAveLeaves(100, 1000)), i = 1 .. 5)] we get:
[37.41400000, 37.34600000, 37.43800000, 37.36100000, 37.38900000]

99/exp(1) = 36.42006468

The differences are:
 [0.99393532, 0.92593532, 1.01793532, 0.94093532, 0.96893532]

The differences are between 0.9-1.02, which is not negligible. 


QUESTION #6:

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

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

add(binomial(e,i)*b^i*R(e-i,i), i=1..e):

end:

To verify, we will check several cases of number of labelled trees on n vertices:

{seq(evalb(R(i-1,1) = i^(i-2)), i=2..100)} returns {true}.

Empirically it seems to work.

For other values of b and a, we have:
In the case of b=4:
{seq(evalb(R(i - 1, 4) = 4*((4 + i) - 1)^(i - 2)), i = 10 .. 100)};
                             {true}

It seems to work for many cases.