#OK to post homework
#Tianyi Liu, Nov22, Assignment 21

1.
557570125262936299552095051452832858951958306952392379552719516748979534894703561052813706583449695070191616000000

2.
WtEdConGedgeclever:=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))^k/k!:
f:=taylor(f,x=0,N+1):
[seq(expand(coeff(f,x,i)*i!),i=1..N)]:
end:

i=2:2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000
i=3:4084614615513849564059280183743190588234377301848961646892154560205839868330317696952259164363869748482983526400000
i=4:4336520950646656327224993268880264842114984745013581637572959168612209444462829083123209142308423023328834795520000
i=5:3046643850794698885807347271650949921058341236747610399052555568087884858386903803880100124793197196674954096998400

3.
EstimateCutOff:=proc(n,M) local i:
for i from 1 to binomial(n,2) do
 if AveNuCC(n,i,M) <= 1.05 then
  RETURN(i):
 fi:
od:
end:

FindCutOff(30,1.05)
84
EstimateCutOff(30,1000)
84
They are the same but my procedure is extremely slow.

4.
evalf(FindCutOff(20,1.05)/20)
2.450000000
evalf(FindCutOff(30,1.05)/30)
2.800000000
evalf(FindCutOff(40,1.05)/40)
3.
evalf(FindCutOff(50,1.05)/50)
3.160000000
evalf(FindCutOff(60,1.05)/60)
3.300000000
As n increases, the rate of increase in cutoff decreases.

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:

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

ProbKcomponents(40,50,2)
0.9801230118e-1
EstProbKcomps(40,50,2,300)
0.9333333333e-1
 They are very close.