#Please do not post homework
#Jeffrey Tang, 2/2/25, Assignment 3


with(combinat):

#Graphs(n): inputs a non-neg. integer and outputs the set of ALL
#graphs on {1,...,n} 
Graphs:=proc(n) local i,j,S,E,s:
E:={seq(seq({i,j},j=i+1..n),   i=1..n)};
S:=powerset(E):
{seq([n,s],s in S)}:
end:

#LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p
LC:=proc(p) local a,b,ra:
if not (type(p,fraction) and p>=0 and p<=1) then
 RETURN(FAIL):
fi:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b)():
if ra<=a then
 true:
else
 false:
fi:
end:

RG:=proc(n,p) local E,i,j:
E:={}:
for i from 1 to n do
 for j from i+1 to n do
   if LC(p) then
    E:=E union {{i,j}}:
   fi:
 od:
od:
[n,E]:
end:

#Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of
#k-cliques
Cliques:=proc(G,k) local n, E,S,i,c,C:
n:=G[1]:
E:=G[2]:
S:={}:
C:=choose({seq(i,i=1..n)},k):
for c in C do
 if choose(c,2) minus E={} then
  S:=S union {c}:
 fi:
od:
S:
end:

#Neis(G): inputs a graph G=[n,E] and outputs a list of length n, N, such that
#N[i] is the set of neighbors of vertexi
Neis:=proc(G) local n,E,N,i,e:
n:=G[1]: 
E:=G[2]:
for i from 1 to n do
 N[i]:={}:
od:
for e in E do
N[e[1]]:=N[e[1]] union {e[2]}:
N[e[2]]:=N[e[2]] union {e[1]}:
od:
[seq(N[i],i=1..n)]:
end:

#C(G,i): The connected component of vertex i
CC:=proc(G,i) local n,C1,C2,C3,N,i1:
if not (type(G,list) and nops(G)=2 and type(G[1],integer) and G[1]>=0 and type(G[2],set)) then
  RETURN(FAIL):
fi:
n:=G[1]:
N:=Neis(G):

C1:={i}:
C2:=C1 union { seq(op(N[i1]), i1 in C1)}:
while C1<>C2 do
 C3:=C2 union { seq(op(N[i1]), i1 in C2)}:
C1:=C2:
C2:=C3:
od:
C2:
end:

#IsCo(G): Is the graph G connected?
IsCo:=proc(G): evalb(nops(CC(G,1))=G[1]):end:

#NuCG(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices
#OEIS A001187  
NuCG:=proc(n) local i,g:
[seq(coeff(add(IsCo(g), g in Graphs(i)),true,1),i=1..n)]:
end:

NuCGc:=proc(n) local f,z,i:
#The number of labeled graphs on n vertices is 2^binomial(n,2)
f:=log(add(2^binomial(i,2)*z^i/i!,i=0..n)):
f:=taylor(f,z=0,n+1):
[seq(i!*coeff(f,z,i),i=1..n)]:
end:

#NuCGx(n,x): inputs pos integer n and a variable x and outputs a list of length n whose i-th entry is P_i[x]
NuCGx := proc(n, x) local f, z, i:
    f := log(add((1+x)^binomial(i,2) * z^i / i!, i = 0 .. n)):
    f := taylor(f, z = 0, n+1):
    [seq(i! * coeff(f, z, i), i = 1 .. n)]:
end:

#NuCGk(n,k): inputs pos integer n, nonneg integer k and outputs the sequence of coefficients of x^{n-1+k}
NuCGk := proc(n, k) local Pn, x;
    Pn := NuCGx(n, x)[n]: 
    coeff(Pn, x, n-1+k): 
end:

#NuCGk(n,0) is OEIS A001187
#NuCGk(n,1) did not have an OEIS number
#Largest k found was 0.