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

#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 := proc(N, k) local n1:
[seq(nops(AllKcomponentsGraphs(n1, k)), n1 = 1 .. N)]:
end:

NuKcomponentsGraphs(5, 1);
 [1, 1, 4, 38, 728]

seq(evalb(NuKcomponentsGraphs(i, 1) = NuConG(i)), i = 1 .. 5);
 true, true, true, true, true

NuKcomponentsGraphs(5, 2);
 [0, 1, 3, 19, 230]
#Yes, the sequence [0,1,3,19,230] is in the OEIS. The A number is A323875.

NuKcomponentsGraphs(5, 3);
 [0, 0, 1, 6, 55]
#Yes, the sequence [0,0,1,6,55] is in the OEIS. The A number is A323876.



#2.
AveNuCC := proc(n, k, m):
evalf(sum(nops(CCs(RandGr(n, k))), i = 1 .. m)/m):
end:

seq(AveNuCC(30, k, 1000), k = 1 .. 30);
29., 28., 27., 26., 25., 24., 23., 22., 21., 20., 19., 18., 18., 17., 15., 14., 13., 13., 11., 10., 10., 9., 9., 8., 6., 6., 5., 6., 5., 3.

seq(AveNuCC(30, k, 1000), k = 1 .. 30);
29., 28., 27., 26., 25., 24., 23., 22., 21., 20., 19., 18., 17., 16., 15., 14., 14., 12., 11., 12., 10., 10., 10., 8., 8., 9., 5., 7., 7., 6.

seq(AveNuCC(30, k, 1000), k = 1 .. 30);
29., 28., 27., 26., 25., 24., 23., 22., 21., 20., 19., 18., 17., 16., 15., 14., 13., 13., 11., 10., 10., 9., 9., 8., 6., 7., 6., 5., 7., 8.



#3.
SingleEstimate := proc(n, M) local k, i:
k := 0:
for i while 1.05 < AveNuCC(n, i, M) do
 k++:
od:
k:
end:

EstimateCutOff := proc(n, M) local i:
round(evalf(1/30*add(SingleEstimate(n, M), i = 1 .. 30))):
end:

seq(EstimateCutOff(k, 1000), k = 2 .. 30);
0, 1, 2, 3, 4, 6, 8, 9, 11, 11, 13, 15, 15, 18, 18, 20, 23, 22, 25, 26, 28, 30, 32, 32, 36, 37, 36, 39, 42