> #Weiji Zheng, Assignment 21, 11/22/2020
;
> #OK TO POST HOMEWORK
;
> 
;
> #Q1
;
> #How many labeled connected graphs with 50 vertices and 70 edges are?
;
> 
;
> #coeff(WtEdConGclever(50,a)[50],a,70) =#557570125262936299552095051452832858951958306952392379552719516748979534894703561052813706583449695070191616000000

;
> #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.
;
> 
;
> #i=2
;
> #f1:=taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^2/2!, x = 0, 51)

;
> #coeff(expand(coeff(f1, x, 50)*50!), a, 70) = 2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000
;
> 
;
> #i=3
;
> #f2:=taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^3/3!, x = 0, 51)
;
> #coeff(expand(coeff(f2, x, 50)*50!), a, 70) = 
;
> #4084614615513849564059280183743190588234377301848961646892154560205839868330317696952259164363869748482983526400000
;
> 
;
> #i=4
;
> #coeff(expand(coeff(taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^4/4!, x = 0, 51), x, 50)*50!), a, 70)
;
> #4336520950646656327224993268880264842114984745013581637572959168612209444462829083123209142308423023328834795520000
;
> 
;
> #i=5
;
> #coeff(expand(coeff(taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^5/5!, x = 0, 51), x, 50)*50!), a, 70)
;
> #3046643850794698885807347271650949921058341236747610399052555568087884858386903803880100124793197196674954096998400
;
> 
;
> #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)
;
> 
;
> AveNuCC:=proc(n,K,M) local i, total, res:
> total := 0:
>  
> for i from 1 to M do
> total := total + nops(CCs(RandGr(n,K))):
> od:
> 
> res := s/M:
> res:
> end:
> EstimateCutOff:=proc(n,M) local i:
> for i from 1 to 100 do
>     if AveNuCC(n,i,M) < 1.05 then
>        return(i):
>     fi
> od:
> 
> return "BAD RESULT":
>  
> end:
> #EstimateCutOff(30,1000) = 84
;
> #FindCutOff(30,1.05) = 84
;
> #GOOD
;
> 
;
> #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(30, 1.05)/40) = 3.000000000
;
> #evalf(FindCutOff(50, 1.05)/50) = 3.160000000
;
> #evalf(FindCutOff(60, 1.05)/60) = 3.300000000
;
> 
;
> #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, s,res:
> s := 0:
> for i to N do 
>     if nops(CCs(RandGr(n, m))) = k then 
>         s := s + 1:
>     fi:
> od:
> res := evalf(s/N):
> res:
> 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)?
;
> 
;
> 
;