#M21.txt: Maple code for Lecture 21 of Dr. Z.'s Combinatorics class

Help21:=proc(): print(`   WtEdConG(N,a), WtEdConGclever(N,a), ProbConn(n,m),  EstProbConn(n,m,N), NuKcomp, AvCCseq(n) ,  ,FindCutOff(n,co)`):
print(` LT(n) , LTseq(N) LTseqC(N)  `):
end:

###Stuff from M18.txt
#M18.txt: Maple code for Lecture 18 of Dr. Z.'s Combinatorics class
#
#
Help18:=proc():print(` CF(E,n) , AllGraphs(n) RandGr(n,K) , CC(G,i), CCs(G) , AllConGraphs(n), AllConGraphs(n) `): 
print(`AllGraphsK(n,K) , AllConGraphsK(n,K), NuConG(N), NuConGclever(N)`):
end:

with(combinat):

#CF(E,n): inputs a graph G on {1, ...,n} as a set of edges outputs it in canonical form as a list of
#sets of length n such that G[i] is the set of neighbors of i. Try:
#CF({{1,2},{1,3}},3);
CF:=proc(E,n) local T,i,e:

 for i from 1 to n do
  T[i]:={}:
 od:

for e in E do
 #For every e={i,j} we include j in the set of neigbors of i and  i in the set of neighbors of j
 T[e[1]]:=T[e[1]] union {e[2]}:
 T[e[2]]:=T[e[2]] union {e[1]}:
od:

[seq(T[i],i=1..n)]:
end:



#AllGraphs(n): All the (labeled) graphs on {1,...n}
AllGraphs:=proc(n) local S,s,i:
S:=powerset(choose({seq(i,i=1..n)},2)):
{seq(CF(s,n), s in S)}:
end:


#AllGraphsK(n,K): All the (labeled) graphs on {1,...n} with K edges
AllGraphsK:=proc(n,K) local S,s,i:
if not (K>=0 and K<=binomial(n,2)) then
 print(K, `must be between 0 and `, binomila(n,2)):
 RETURN(FAIL):
fi:

S:=choose(choose({seq(i,i=1..n)},2),K):
{seq(CF(s,n), s in S)}:
end:

#RandGr(n,K): a random  (labeled) graph on n vertices and K edges
RandGr:=proc(n,K) local i:
if not (K>=0 and K<=binomial(n,2)) then
 print(K, `must be between 0 and `, binomila(n,2)):
 RETURN(FAIL):
fi:

CF(randcomb(choose({seq(i,i=1..n)},2),K),n):
end:

#CC(G,i): The connected component of vertex i in the graph G
CC:=proc(G,i) local S1,S2,S3,s:

if not (1<=i and i<=nops(G)) then
 print(`bad input`):
 RETURN(FAIL):
fi:

S1:={i}:

S2:=S1 union {seq(op(G[s]), s  in S1)}:

while S1<>S2 do

S3:=S2 union {seq(op(G[s]), s  in S2)}:

S1:=S2:
S2:=S3:
od:
S2:
end:

#CCs(G): Inputs a graph G in canonical form  on {1,...,n} where n=nops(G), outputs the set partition of {1,...,n}
#consisting of its connected components. Try
#CCs([{},{},{}]);
#The set of connected components of G. Inputs the set partition of {1,
CCs:=proc(G) local n,i,StillToDo,ConComps,v:

n:=nops(G):

StillToDo:={seq(i,i=1..n)}:

ConComps:={}:

while StillToDo<>{} do
 v:=StillToDo[1]:
 ConComps:=ConComps union {CC(G,v)}:
 StillToDo:=StillToDo minus CC(G,v):
od:
ConComps:
end:


#AllConGraphs(n): The set of all connected (labeled) graphs on {1,..,n}
AllConGraphs:=proc(n) local S,s,C:
S:=AllGraphs(n):
C:={}:

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

C:
end:


#AllConGraphsK(n,K): The set of all connected (labeled) graphs on {1,..,n} with K edges
AllConGraphsK:=proc(n,K) local S,s,C:
S:=AllGraphsK(n,K):
C:={}:

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

C:
end:

#NuConG(N): The first N terms of the sequence "number of connected (labeled) graphs with n vertices", by BRUTE force
#Try:
#NuConG(5);
NuConG:=proc(N) local n1:
[seq( nops(AllConGraphs(n1)),n1=1..N)]:
end:


#NuConGclever(N): The first N terms of the sequence "number of connected (labeled) graphs with n vertices", done via
#Exonenital Generating functions. Try
#Try:
#NuConGclever(30);
NuConGclever:=proc(N) local f,i,x:
f:=log(add(2^binomial(i,2)*x^i/i!,i=0..N+1)):
f:=taylor(f,x=0,N+1):
[seq(coeff(f,x,i)*i!,i=1..N)]:
end:


##End from M18.txt



#NuKcomp(N,k): The first N terms of the sequence "number  (labeled) graphs with exactly k components, with n vertices", done via
#Exonenital Generating functions. Try
#Try:
#NuKcomp(30,3);
NuKcomp:=proc(N,k) local f,i,x:
f:=(log(add(2^binomial(i,2)*x^i/i!,i=0..N+1)))^k/k!:
f:=taylor(f,x=0,N+1):
[seq(coeff(f,x,i)*i!,i=1..N)]:
end:


#WtEdConG(N,a): The first N terms of the sequence of
#generating functios of the set "connected (labeled) graphs with n vertices" according to the weight a^number of edges,
#In other words, the list, of length N, whose n-th entry is a polynomial in a whose coefficient of a^m
#is the exact number of connected graphs with n vertices and m edges (recall that the total number of such graphs is
#binomial(binomial(n,2),a)
#It is done by brute force. For checking purposes only
WtEdConG:=proc(N,a) local K,n:
[seq(add(nops(AllConGraphsK(n,K))*a^K,K=0..binomial(n,2)),n=1..N)]:
end:

#WtEdConGclever(N,a): The first N terms of the sequence of
#generating functios of the set "connected (labeled) graphs with n vertices" according to the weight a^number of edges,
#In other words, the list, of length N, whose n-th entry is a polynomial in a whose coefficient of a^m
#is the exact number of connected graphs with n vertices and m edges (recall that the total number of such graphs is
#binomial(binomial(n,2),a)

#It is done via Exonenital Generating functions. Try
#Try:
#WtEdConGclever(30);
WtEdConGclever:=proc(N,a) local f,i,x:
option remember:
f:=log(add((1+a)^binomial(i,2)*x^i/i!,i=0..N+1)):
f:=taylor(f,x=0,N+1):
[seq(expand(coeff(f,x,i)*i!),i=1..N)]:
end:

#ProbConn(n,m): The probability that a random labeled graph on n vertices and m edges is connected.
#Try:
#ProbConn(30,100):
ProbConn:=proc(n,m)  local a:
evalf(coeff(WtEdConGclever(n,a)[n],a,m)/binomial(n*(n-1)/2,m)):
end:

#EstProbConn(n,m,N): estimates that the probability that a random  graph on n vertices with m edges is connected
#by simulating N times. Try:
#EstProbConn(30,70,100);
EstProbConn:=proc(n,m,N) local i,co, G:

co:=0:

for i from 1 to N do

G:=RandGr(n,m):

if nops(CCs(G))=1 then
 co:=co+1:
fi:

od:

evalf(co/N):
end:

#AvCCseq(n): The list of length binomial(n,2)
#of whose m-th entry is the expected number of connected components in a graph with n vertices and m edges. Try
#AvCCseq(20,12);
AvCCseq:=proc(n) local m,f,i,x,a:
f:=add((1+a)^binomial(i,2)*x^i/i!,i=0..n+1):
f:=taylor(f*log(f),x=0,n+1):
f:=expand(coeff(f,x,n)*n!):
[seq(evalf(coeff(f,a,m)/binomial(n*(n-1)/2,m)),m=1..binomial(n,2))];
end:


#FindCutOff(n,co): inputs a positive integer n and a cutoff co, finds the first m such that the
#expected number of connected components in a graph with n vertices and m edges is less than co.
#Try:
#FindCutOff(20,1.05);
FindCutOff:=proc(n,co) local L,m:
L:=AvCCseq(n):

for m from 1 to nops(L) while L[m]>co do od:
m:
end:

#LT(n): The set of labelled trees
LT:=proc(n) local S1,S2,G:
S1:=AllGraphsK(n,n-1):
S2:={}:

for G in S1 do
 if nops(CCs(G))=1 then
  S2:=S2 union {G}:
fi:
od:

S2:

end:


#LTseq(N): The first N terms of the sequence for counting labeled trees by brute force
LTseq:=proc(N) local n:
[seq(nops(LT(n)),n=1..N)]:
end:


#LTseqC(N): The first N terms of the sequence for counting labeled trees by the clever way
#iterating the functional equation T(x)=x*exp(T(x))
LTseqC:=proc(N) local n,f,x,i:
f:=x:
for n from 1 to N do
f:=x*exp(f):
f:=add(coeff(taylor(f,x=0,N+1),x,i)*x^i,i=1..N):
od:
[seq(coeff(f,x,i)*i!/i,i=1..N)]:
end: