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