#OK to post homework
#Hari Amoor, November 15, 2020, Assignment HW #18

with(combinat):

# Question 1

AllKcomponentsGraphs:=proc(n,K) local S,s,C:
S:=AllGraphs(n):
C:={}:

for s in S do
 if nops(CCs(s))=K then
  C:=C union {s}:
 fi:
od:

C:
end:

#NuKcomponentsGraphs(N,K): outputs first N terms of the seq of the number of labeled graphs on N vertices with 
#K components
NuKcomponentsGraphs:=proc(N,K) local n1:
[seq( nops(AllKcomponentsGraphs(n1,K)),n1=1..N)]:
end:

# NuKcomponentsGraphs(5,2) = [0, 1, 3, 19, 230];  OEIS-value of A323875
# NuKcomponentsGraphs(5,3) = [0, 0, 1, 6, 55];  OEIS-value of A323876

# Question 2

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

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

return(evalf(sum/M)):
end:

# Question 3

EstimateCutOff:=proc(n,M) local K:
K:=0:
do
    K:=K+1:
until(AveNuCC(n,K,M) < 1.05):
K:
end: