#OK to post homework
#Kent Mei, 11/22/20, Assignment 21

#---------------------------------
#Part 1

#coeff(WtEdConGclever(50,a)[50],a,70);
#557570125262936299552095051452832858951958306952392379552719516748979534894703561052813706583449695070191616000000
#labeled connected graphs have 50 vertices and 70 edges.

#---------------------------------
#Part 2

#The answers can be found with the help of this alternate procedure which does taylor(f^k/k!,x=0,N+1) where k = 2, 3, 4, 5.

WtEdConGcleverAlt:=proc(N,a,k) local f,i,x:
option remember:
f:=log(add((1+a)^binomial(i,2)*x^i/i!,i=0..N+1)):
f:=taylor(f^k/k!,x=0,N+1):
[seq(expand(coeff(f,x,i)*i!),i=1..N)]:
end:


#i = 2:
#coeff(WtEdConGcleverAlt(50,a,2)[50],a,70);
#2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000

#i = 3:
#coeff(WtEdConGcleverAlt(50,a,3)[50],a,70);
#4084614615513849564059280183743190588234377301848961646892154560205839868330317696952259164363869748482983526400000

#i = 4:
#coeff(WtEdConGcleverAlt(50,a,4)[50],a,70);
#4336520950646656327224993268880264842114984745013581637572959168612209444462829083123209142308423023328834795520000

#i = 5:
#coeff(WtEdConGcleverAlt(50,a,5)[50],a,70);
#3046643850794698885807347271650949921058341236747610399052555568087884858386903803880100124793197196674954096998400

#---------------------------------
#Part 3

AveNuCC:=proc(n,K,M) local i, L, sum:

sum:=0:

for i from 1 to M do
	sum := sum + nops(CCs(RandGr(n,K))):
od:

evalf(sum / M):

end:

EstimateCutOff:=proc(n,M) local ave, K:

K := n-2:
ave := 2:

while ave > 1.05 do
	K := K + 1:
	ave := AveNuCC(n,K,M):
od:

K:

end:

#EstimateCutOff(30,1000);
#82

#FindCutOff(30,1.05);
#84

#The output of the simulated procedure with the exact one are fairly close. The simulated one tends to be smaller because it just accepts the first cutoff under the threshold.

#---------------------------------
#Part 4

#evalf(FindCutOff(20,1.05)/20)
#2.45

#evalf(FindCutOff(30,1.05)/30)
#2.8

#evalf(FindCutOff(40,1.05)/40)
#3

#evalf(FindCutOff(50,1.05)/50)
#3.16

#evalf(FindCutOff(60,1.05)/60)
#3.3

#As n increases, the cutoff/n seems to be increasing about logarithmically. It's a bit difficult to deduce an exact trend from these values though.

#---------------------------------
#Part 5

EstProbKcomps:=proc(n,m,k,N) local i,co, G:

co:=0:

for i from 1 to N do

G:=RandGr(n,m):

if nops(CCs(G))=k then
 co:=co+1:
fi:

od:

evalf(co/N):
end:

#---------------------------------
#Part 6

#Using the WtEdConGcleverAlt procedure from part 2:

ProbKcomponents:=proc(n,m,k)  local a:
evalf(coeff(WtEdConGcleverAlt(n,a,k)[n],a,m)/binomial(n*(n-1)/2,m)):
end:

#EstProbKcomps(40,50,2,300) = 0.8666666667e-1
#ProbKcomponents(40,50,2) = 0.9801230118e-1

#They are relatively close to each other, within a few percent of one another. The EstProbKcomps value is less than the exact ProbKcomponents value which mimics the situation with the Cutoff procedures.