#OK to post homework
#Nick Belov, Feb 16nd 2025, Assignment 7
read "C7.txt";
read "C6.txt";

NumberOfLeaves := proc(T)
    local ans,n,e,deg,i;
    n := 1;
    ans:=0;
    for e in T do
        n := max(n,max(e));
    od;
    deg:=[seq(0,i=1..n)];
    for e in T do
        deg[e[1]]++;
        deg[e[2]]++;
    od;
    for i from 1 to n do
        if deg[i]=1 then 
            ans++;
        fi;
    od;
    return ans;
end:

RandomTree := proc(n)
    local ra,i;
    ra:=rand(1..n);
    return AntiPC([seq(ra(),i=1..n-2)]);
end:

EstimateAverageNumberOfLeaves := proc(n,K)
    local count,i;
    count:=add(NumberOfLeaves(RandomTree(n)),i=1..K);
    return count / K;
end:
#evalf(EstimateAverageNumberOfLeaves(100, 1000)) = 37.39400000
#evalf(EstimateAverageNumberOfLeaves(100, 10000)) = 37.37150000
#very close !

#[Optional theoretical challenge, "open book" and "open internet", 5 dollars]. Find the exact expression for the average number of leaves in a random tree with n vertices. Call it an. After you found it, prove that
limit(an/n, n goes to infinity) exists, and find its value.

#to find the expected number of leaves we can sum over each node and its probability of being a leaf 
#a node is a leaf exactly when it does not appear in the prufer code 
#for some fixed node then, the probability is ((n-1)/n)^(n-2)
#then we can multiply that by n for each node giving 
#EV[n] = n * ((n-1) / n) ^ (n-2)

#EV[100] = 37.3464280454, pretty resonable given the results of the experiment!

# a_n / n = EV[n] / n = (n * ((n-1) / n) ^ (n-2)) / n = ((n-1) / n) ^ (n-2)
#which is back to the probability a single node is a leaf, cute!

#lim a_n / n  = 1/e !!!!!!!!!
#proof:
#rewrite ((n-1) / n) ^ (n-2) = (1 - 1/n)^(n-2)
#then recall that lim (1 - 1/n)^n = 1/e 
#we can again rewrite (1 - 1/n)^(n-2) = (1 - 1/n)^n * (1 - 1/n)^(-2)

#meaning i can express the sequence a_n/n as the product of 2 sequences
#one being (1 - 1/n)^n and the second being (1 - 1/n)^(-2)
#the first is known to limit to 1/e so its sufficient to show the second sequence limits to 1 

#to show that (1 - 1/n)^(-2) limits to 1 again write it as the product of 2 sequences 
# (1 / (1 - 1/n)) times (1 / (1 - 1/n))
#which both limit to 1 so their product limits to 1 as needed !!