#OK to post homework #Joseph Koutsoutis, 02-16-2025, Assignment 7 read `C7.txt`: #1 #RandSeq(n) outputs a sequence of length n-2 with entries in [n] RandSeq := proc(n) local ra,i: ra := rand(1..n): [seq(ra(), i=1..n-2)]: end: #TestAntiPC(n, K) creates K random sequences of length n-2 and checks if PC(AntiPC(P)) = P TestAntiPC := proc(n, K) local i, P: for i from 1 to K do: P := RandSeq(n): if P <> PC(AntiPC(P)) then return FAIL: fi: od: end: #2 NumberOfLeaves := proc(T) local e,V,v,N,n: V := {seq(op(e), e in T)}: for v in V do: N[v] := 0: od: for e in T do: N[e[1]]++: N[e[2]]++: od: n := 0: for v in V do: if N[v] = 1 then n++: fi: od: n: end: #3 RandomTree := proc(n): AntiPC(RandSeq(n)): end: #4 EstimateAverageNumberOfLeaves := proc(n, K) local i,c: c := 0: for i from 1 to K do: c += NumberOfLeaves(RandomTree(n)): od: c / K: end: #EstimateAverageNumberOfLeaves(100, 1000) outputted 37.34200000 and EstimateAverageNumberOfLeaves(100, 10000) outputted 37.34440000, which are close. #5 #We will follow parts (d) and (e) of exercise 4.18 in Wilf's generatingfunctionology. #4.18(d) Use the sieve method to show that if e_k is the number of vertex labeled trees on n vertices of which k are endpoints, #then sum(e_k * x^k) = sum(binomial(n, r) * r^(n-2) * (x-1)^(n-r)). #The set of objects is the set of labeled trees on n vertices. For each i in [n], we say that a tree T has property i if i is a leaf of T. #Let S be a set of properties. Then S is a subset of [n] and is a set of vertices, and we want to know the number of labeled trees #that have at least the vertices of S as leaves. Since the remaining n - |S| must form a tree and our |S| vertices can attach to any of the n-|S| vertices, #we compute by Cayley's formula that N(\supseteq S) = (n - |S|)^(|S|) * (n - |S|)^(n-|S|-2) = (n - |S|)^(n-2). #Now for each r >= 0, we compute N_r = binomial(n, r) * (n - r)^(n-2) #Finally, we have by the sieve method that sum(e_k * x^k) = N(x-1) = sum(N_r (x-1)^r) = sum(binomial(n, r) * r^(n-2) * (x-1)^(n-r)). #4.18(e) Show that the average number of endpoints that trees of n vertices have is n(1 - 1/n)^(n-2) ~ n/e (n -> infinity). #We observe that when using the sieve method, the average number of properties that an object has is N_1 / N. #Hence the average number of leaves is n * (n - 1)^(n-2) / n^(n-2) = n(1 - 1/n)^(n-2). #By 4.18(e), it follows that the probability of being a leaf converges to 1/e.