#John Kim
#Use whatever you like

#read "C:/Users/John Y. Kim/Documents/Maple/hw25.txt":

Help:=proc(): print(`Edges(n), Graphs(n), Neis(G,i), CC(G,Erdos) `):
print(`IsCon(G,n), ConG(n) , NuCCSeqSlow(N) , NuCCSeqFast(N)`):
print(`LabTrees(n) , NuLabTreesSlow(N) , NuLabTreesSeqFast(N)`):
end:

with(combinat):

#Edges(n): the set of all edges of K_n
Edges:=proc(n) local i,j:

 {seq(seq({i,j},i=1..j-1),j=2..n)}:
end:

#Graphs(n): ALL graphs on {1, ..., n}
Graphs:=proc(n): powerset(Edges(n)):end:


#Neis(G,i): inputs a graph G (given as a set of edges,
#and every edge is given a 2-set) and outputs all
#the vertices adjacent to it (i.e. all j such that
#{i,j} is in G
Neis:=proc(G,i) local N,e:
option remember:
N:={}:

for e in G do 
 if member(i,e) then
  N:=N union (e minus {i}):
 fi:
od:

N:

end:


#CC(G,Erdos): the connected component of vertex Erdos in graph G
CC:=proc(G,Erdos) local C1,NewF,v:

C1:={Erdos}:
NewF:=Neis(G,Erdos):

while NewF minus C1<>{} do

C1:=C1 union NewF:

NewF:= `union`(seq(Neis(G,v), v in NewF)): 
od:

C1:

end:

#IsCon(G,n): Is the graph G on {1, ..., n} connected?
IsCon:=proc(G,n): evalb(nops(CC(G,1))=n): end:

#the set of all connected labelled graphs  on {1, ..., n}
ConG:=proc(n) local ConGraphs, AllGraphs, G:

AllGraphs:=Graphs(n):

ConGraphs:={}:


for G in AllGraphs do
 if IsCon(G,n) then
    ConGraphs:=ConGraphs union {G}:
 fi:
od:

ConGraphs:

end:


#The first N terms of sequence A001187 by the SLOW way
#(But slow is not always stupid)
NuCCSeqSlow:=proc(N) local i:
[seq(nops(ConG(i)),i=1..N)]:
end:

# NuCCSeqFast(N):
#The first N terms of sequence A001187 by the FAST way
#(using exponential generatingfunctionology)

NuCCSeqFast:=proc(N) local i,x,F:

F:=taylor(log(add(x^i*2^(binomial(i,2))/i!,i=0..N)), x=0, N+1):

[ seq(coeff(F,x,i)*i!,i=1..N)]:

end:


#the set of all labelled trees  on {1, ..., n}
LabTrees:=proc(n) local ConGraphs, AllGraphs, G:

AllGraphs:=choose(Edges(n),n-1) :

ConGraphs:={}:


for G in AllGraphs do
 if IsCon(G,n) then
    ConGraphs:=ConGraphs union {G}:
 fi:
od:

ConGraphs:

end:

#The first N terms of the number of labelled trees 
#sequence by the SLOW way
#(But slow is not always stupid)
NuLabTreesSlow:=proc(N) local i:
[seq(nops(LabTrees(i)),i=1..N)]:
end:

# WtCCSeqFast(N,y):
#The first N terms of the weight-enumerator of
#all connected graphs according to the weight
#y^(#edges) the FAST way
#(using exponential generatingfunctionology)

WtCCSeqFast:=proc(N,y) local i,x,F:

F:=taylor(log(add(x^i*(1+y)^(binomial(i,2))/i!,i=0..N)), x=0, N+1):

[ seq(coeff(F,x,i)*i!,i=1..N)]:

end:




#the set of all labelled connected graphs  on {1, ..., n}
#with exactly n-1+a edges
AlmostTrees:=proc(n,a) local ConGraphs, AllGraphs, G:

AllGraphs:=choose(Edges(n),n-1+a) :

ConGraphs:={}:


for G in AllGraphs do
 if IsCon(G,n) then
    ConGraphs:=ConGraphs union {G}:
 fi:
od:

ConGraphs:

end:

#The first N terms of the number of labelled trees 
#sequence by the SLOW way
#(But slow is not always stupid)
NuLabAlmostTreesSlow:=proc(N,a) local i:
[seq(nops(AlmostTrees(i,a)),i=1..N)]:
end:


#The first N terms of the number of labelled trees 
#sequence by the SLOW way
#(But slow is not always stupid)
NuLabAlmostTreesFast:=proc(N,a) local i:
[seq(coeff(WtCCSeqFast(N,y)[i],y,i-1+a),i=1..N)]:
end:




#NuLabAlmostTreesFast(10,1); 
# [0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840]
#A057500 Number of connected labeled graphs with n edges and n nodes.

#NuLabAlmostTreesFast(10,2); 
#[0, 0, 0, 6, 205, 5700, 156555, 4483360, 136368414, 4432075200]
#A061540 Number of connected labeled graphs with n nodes and n+1 edges. 

#NuLabAlmostTreesFast(10,3); 
#[0, 0, 0, 1, 120, 6165, 258125, 10230360, 405918324, 16530124800]
#A061541 Number of connected labeled graphs with n nodes and n+2 edges. 

#Up to a=9 in Sloane
#a=10 not in Sloane



#Image(G,n,pi): inputs a simple labelled graph G (in our notation)
# of {1, ...,n}, a pos. integer n, and a permutation pi of 
#{1, ...,n} and outputs the image under pi, in other words, 
#the graph where label i goes to label pi[i] for i=1,2, ,... n
Image:=proc(G,N,pi) local e,PG:

PG:={}:
for e in G do
 PG:=PG union {{pi[e[1]],pi[e[2]]}}:
od:

PG:

end:



#ConULG(n): inputs a pos. integer n, and outputs ONE 
#representative from each equivalence class.
ConULG:=proc(n) local perms,CULG,CG,pi,PG,G:

CG:=ConG(n):
perms:=permute(n):
CULG:={}:

while CG<>{} do
 G:=CG[1]:
 CULG:=CULG union {G}:
 
 for pi in perms do
  PG:=Image(G,n,pi):
  CG:=CG minus {PG}:
 od:
od:

CULG:

end:


#NuConULSeqSlow(N): counts, the number of connected unlabelled 
#graph (alias equivalence class under permuting labels) on n 
#vertices for n from 1 to N. 
NuConULSeqSlow:=proc(N) local n:

[seq(nops(ConULG(n)),n=1..N)]:

end:

#A001349 Number of connected graphs with n nodes. 



#ConULT(n): inputs a pos. integer n, and outputs ONE 
#representative from each equivalence class of trees.
ConULT:=proc(n) local perms,CULG,CG,pi,PG,G:

CG:=LabTrees(n):
perms:=permute(n):
CULG:={}:

while CG<>{} do
 G:=CG[1]:
 CULG:=CULG union {G}:
 
 for pi in perms do
  PG:=Image(G,n,pi):
  CG:=CG minus {PG}:
 od:
od:

CULG:

end:


#NuULTreesSeqSlow(N): counts, the number of connected unlabelled 
#graph (alias equivalence class under permuting labels) on n 
#vertices for n from 1 to N. 
NuULTreesSeqSlow:=proc(N) local n:

[seq(nops(ConULT(n)),n=1..N)]:

end:

#This does in fact yield Sloane's favorite sequence.



#ConULAT(n,a): inputs a pos. integer n, and outputs ONE 
#representative from each equivalence class of almost trees.
ConULAT:=proc(n,a) local perms,CULG,CG,pi,PG,G:

CG:=AlmostTrees(n,a):
perms:=permute(n):
CULG:={}:

while CG<>{} do
 G:=CG[1]:
 CULG:=CULG union {G}:
 
 for pi in perms do
  PG:=Image(G,n,pi):
  CG:=CG minus {PG}:
 od:
od:

CULG:

end:


#NuULATreesSeqSlow(N,a): counts, the number of connected unlabelled 
#graph (alias equivalence class under permuting labels) on n 
#vertices for n from 1 to N. 
NuULATreesSeqSlow:=proc(N,a) local n:

[seq(nops(ConULAT(n,a)),n=1..N)]:

end: