> #ok to post
> #Yifan Zhang, 11/19/2020
> 
> #Q1.
> #How many labeled connected graphs with 50 vertices and 70 edges are?
> read `M21.txt`;
> coeff(WtEdConGclever(50,a)[50],a,70);

55757012526293629955209505145283285895195830695239237955271951674897953489470356
1052813706583449695070191616000000
> 
> #Q2.
> #How many labeled graphs with i connected components with 50 vertices and 70
> edges are for i=2,3,4,5? Explain how you do it, by using the taylor command in
> Maple.
> f:=(log(add((1+a)^binomial(i,2)*x^i/i!,i=0..51)))^2/2!:
> f:=taylor(f,x=0,51):
> coeff(expand(coeff(f,x,50)*50!),a,70);

22677622820722052717787912706805968499215163385745718238834565192817300351019654
14722739023408444177334403072000000
> #for i = 2, there are
> 226776228207220527177879127068059684992151633857457182388345651928173003510196
> 5414722739023408444177334403072000000 labeled graphs.
> 
> f:=(log(add((1+a)^binomial(i,2)*x^i/i!,i=0..51)))^3/3!:
> f:=taylor(f,x=0,51):
> coeff(expand(coeff(f,x,50)*50!),a,70);

40846146155138495640592801837431905882343773018489616468921545602058398683303176
96952259164363869748482983526400000
> #for i=3, there are
> 408461461551384956405928018374319058823437730184896164689215456020583986833031
> 7696952259164363869748482983526400000 labeled graphs.
> 
> f:=(log(add((1+a)^binomial(i,2)*x^i/i!,i=0..51)))^4/4!:
> f:=taylor(f,x=0,51):
> coeff(expand(coeff(f,x,50)*50!),a,70);

43365209506466563272249932688802648421149847450135816375729591686122094444628290
83123209142308423023328834795520000
> #for i=4, there are
> 433652095064665632722499326888026484211498474501358163757295916861220944446282
> 9083123209142308423023328834795520000 labeled graphs.
> 
> f:=(log(add((1+a)^binomial(i,2)*x^i/i!,i=0..51)))^5/5!:
> f:=taylor(f,x=0,51):
> coeff(expand(coeff(f,x,50)*50!),a,70);

30466438507946988858073472716509499210583412367476103990525555680878848583869038
03880100124793197196674954096998400
> #for i=5, there are
> 304664385079469888580734727165094992105834123674761039905255556808788485838690
> 3803880100124793197196674954096998400 labeled graphs.
> 
> #Q3.
> #In the homework assigment for Lecture 18 you were asked to write a procedure
> #EstimateCutOff(n,M)
> 
> #by simulating it M times, and using as cutoff 1.05. Procedure
> FindCutOff(n,co) in
> 
> #M21.txt
> 
> #does it EXACTLY, for an arbitrary parameter co (foremerly I asked you to take
> 1.05).
> 
> #Comparee the output of the simulated procedure with the exact one, i.e.
> compare your EstimateCutOff(30,1000) with my exact FindCutOff(30,1.05)
> read `M18.txt`;
> AveNuCC:=proc(n,K,M) local i, s:
> s:=0:
> 
> for i from 1 to M do
> s:=s+nops(CCs(RandGr(n,K))):
> od:
> 
> s/M:
> 
> end:
> EstimateCutOff:=proc(n,M) local K:
> 
> for K from 1 to 100 do
> if AveNuCC(n,K,M)<1.05 then
> return(K);
> fi
> od:
> 
> return "NOT FOUND SUCH K or K is larger than 100":
> 
> end:
> EstimateCutOff(30,1000);
84
> FindCutOff(30,1.05);
84
> #same
> 
> #Q4.
> #Try to do the optional challenge from the homework of Lecture 18 exactly,
> using evalf(FindCutOff(n,1.05)/n), for n= 20,30,40,50,60. Do you see a trend?
> 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
> 
> with(plots):
> v1:=<20,30,40,50,60>:
> v2:=<2.45,2.8,3,3.16,3.3>:
> plot(v1,v2,color=blue,symbol=diamond);

> pointplot(v1,v2,color=blue,symbol=diamond);

> 
> #Q5.
> #Generalize procedure
> #EstProbConn(n,m,N):
> 
> #and write a procedure
> 
> #EstProbKcomps(n,m,k,N):
> 
> #that estimates the probability that a random graph with n vertices and m
> edges has exactly k components, by sampling N such random graphs.
> 
> #Note that EstProbKcomps(n,m,1,N) is exactly the same as EstProbConn(n,m,N)
> (except, since we are doing simulations, you get different answers each time)
> 
> 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:
> 
> 
> #Q6.
> #Generalize procedure
> #ProbConn(n,m):
> 
> #To write a procedure
> 
> #ProbKcomponents(n,m,k)
> 
> #that uses the method of exponential generating functions to find the EXACT
> probability that a random graph with n vertices and m edges has k components.
> Note that ProbKcomponents(n,m,1) is EXACTLY the same as ProbConn(m,m,1)
> 
> #[Hints: (i) you may need to write another procedure generalizing one of those
> that I wrote and that was used in ProbConn(n,m). (ii) the egf of labeled
> graphs with n vertices and k components with keeping track of the number of
> edges (i.e. the weight-enumerator according to the weight anumber of edges) is
> 
> #(log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^k/k!
> 
> #How does ProbKcomponents(40,50,2) differ from EstProbKcomps(40,50,2,300)?
> 
> 
> ProbConn:=proc(n,m) local a:
> evalf(coeff(WtEdConGclever(n,a)[n],a,m)/binomial(n*(n-1)/2,m)):
> end:
> 
> WtEdConGcleverK:=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:
> 
> ProbKcomponents:=proc(n,m,k) local a:
> evalf(coeff(WtEdConGcleverK(n,a,k)[n],a,m)/binomial(n*(n-1)/2,m)):
> end:
> 
> ProbKcomponents(5,5,1);
.8809523810
> ProbConn(5,5);
.8809523810
> 
> 
> 
> 
> 
> 
> 
>