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