#OK to post homework
#William Wang, 11/19/2020, Assignment 2020

#1. How many labeled connected graphs with 50 vertices and 70 edges are there?
WtEdConGclever(50, a)[50];
coeff(%, a, 70);
  557570125262936299552095051452832858951958306952392379552719516748979534894703561052813706583449695070191616000000



#2. 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
coeff(expand(coeff(taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^2/2!, x = 0, 51), x, 50)*50!), a, 70);
  2267762282072205271778791270680596849921516338574571823883456519281730035101965414722739023408444177334403072000000
#i=3
coeff(expand(coeff(taylor(log(add((1 + a)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^3/3!, x = 0, 51), 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

#We replace 2 with 1+a to keep track of the edges, then we raise log(...) to the ith power and divide by i! for i=2,3,4,5.  The expand command will make it easier to find the coefficient and then we take the coefficient of a^(70), which represents the number of connected components with i connected components with 50 vertices and 70 edges.



#3.
AveNuCC := proc(n, K, M) local i, numComps, G:
numComps := 0:
for i to M do
 G := RandGr(n, K):
 numComps := numComps + nops(CCs(G));
od:
numComps/M:
end:

EstimateCutOff := proc(n, M) local i:
for i to 1/2*n*(n - 1) do
 if evalf(AveNuCC(n, i, M)) <= 1.05 then
  return i:
 fi:
od:
1/2*n*(n - 1):
end:

FindCutOff(30, 1.05);
  84
EstimateCutOff(30, 1000);
  83

#EstimateCutOff(30,1000) seems to be close to FindCutOff(30,1.05)



#4.
evalf(FindCutOff(20, 1.05)/20), evalf(FindCutOff(30, 1.05)/30), evalf(FindCutOff(40, 1.05)/40), evalf(FindCutOff(50, 1.05)/50), evalf(FindCutOff(60, 1.05)/60), evalf(FindCutOff(70, 1.05)/70);
  2.450000000, 2.800000000, 3., 3.160000000, 3.300000000, 3.400000000

with(plots):
pointplot([[20, 2.45], [30, 2.8], [40, 3], [50, 3.16], [60, 3.3], [70, 3.4]]);

with(gfun);
guessgf([2.45, 2.8, 3, 3.16, 3.3, 3.4], x);
  FAIL

#The trend should satisfy a logarithmic relationship



#5.
EstProbKcomps := proc(n, m, k, N) local i, co, G:
co := 0:
for i to N do
 G := RandGr(n, m):
 if nops(CCs(G)) = k then
  co := co + 1:
 fi:
od:
evalf(co/N):
end:

EstProbKcomps(6, 6, 1, 1000);
  0.7390000000
EstProbConn(6, 6, 1000);
  0.7320000000



#6.
ProbKcomponents := proc(n, m, k) local a, i:
evalf(coeff(expand(coeff(taylor(log(add((a + 1)^binomial(i, 2)*x^i/i!, i = 0 .. 51))^k/k!, x = 0, n + 1), x, n)*n!), a, m)/binomial(1/2*n*(n - 1), m)):
end:

ProbConn(6, 6, 1);
                          0.7312687313
ProbKcomponents(6, 6, 1);
                          0.7312687313