# Ok to post homework
# Lucy Martinez, 05-01-2025, Assignment 26

read `AGT.txt`:

######################
#Problem 1: Briefly describe the progress on your team's project
# We have now written up some of the introduction, background
# and some of the overview of the algorithm that we aim to implement



#Problem 2: Let me know whether you are coming
# to the Annual Princeton Cemetery tour, Sat., May 10, 2025, 6:00pm,
# followed by a free dinner at a restaurant tbd.
# We meet Outside the Princeton Public Library. More details later.

#ANSWER: Yes, I will be coming to the tour and dinner



#Problem 3: A graph may be viewed as a way of coloring the edges
# of the complete graph with two colors.
# By Polya's theorem, to obtain the number of ways
# of coloring unlabeled objects with c colors is to plug-in x[i]=c
# into the cycle index polynomial for all x[i].
# Use CIPknC(13,x) to find the exact number of unlabelled graphs
# on 13 vertices.

#Answer: 50502031367952
# I did the following:
# P:=CIPknC(13,x);
# subs(seq({x[i]=2},i=1..42),P);


#Problem 4: According to Polya theory, in order to find
# the weight-enumerator, according to the weight, t^NumberOfEdges,
# for the set of unlabeled graphs on n vertices,
# you replace x[i] by 1+t^i, in CIPknC(n,x) for every x[i] that shows up,
# and expand. 
# How many unlabeled graphs are there with 13 vertices and 30 edges?
# Answer: 584089835857

#UGVE(n,x,e): inputs the number of vertices n and the number of edges edges
# and outputs the number of unlabeled graphs with n vertices and e edges
UGVE:=proc(n,x,e) local P,vars,i1,v,poly,i,t:
P:=CIPknC(n,x):
vars:=indets(P, name):
i1:=max([seq(op(1, v), v in vars)]):
poly:=expand(subs(seq({x[i]=1+t^(i)},i=1..i1),P)):
coeff(poly,t,e):
end:
 

#Problem 5: What are the OEIS numbers (if they exist) for
#The sequence enumerating unlabeled graphs with n vertices and n-1 edges?
# Answer: A001433 Number of graphs with n nodes and n-1 edges.

#The sequence enumerating unlabeled graphs with n vertices and n edges?
# Answer: A001434 Number of graphs with n nodes and n edges.

#The sequence enumerating unlabeled graphs with n+1 vertices and n+1 edges?



####################################from previous classes:
#C26.txt: April 28, 2025
Help26:=proc():
print(`MultP(pi,sig), GenGp(S), CtoP(C), IndPer(pi),CIPkn(n,x)`):
print(`ParToPer(P),CIPknC(n,x)`):
end:


#MultP(pi,sig): the produce of the permutations pi and sig (sigma)
#MultP([3,1,2],[2,1,3])=[1,3,2] 
#i.e. reading from right to left: 1->2->1, 2->1->3, 3->3->2
MultP:=proc(pi,sig) local i:
[seq(pi[sig[i]],i=1..nops(pi))]:
end:



#GenGp(S): inputs a set of permutations (all of the same length, nops(S[1]))
# outputs the subset of S_n generated by S
GenGp:=proc(S) local n,G1,G2,G3,i,s,g1:
if S={} then
 return(FAIL):
fi:

n:=nops(S[1]):
G1:={[seq(i,i=1..n)]}:
G2:=G1 union {seq(seq(MultP(g1,s),g1 in G1),s in S)}:
while G1<>G2 do
 G3:=G2 union {seq(seq(MultP(g1,s),g1 in G2),s in S)}:
 G1:=G2:
 G2:=G3:
od:
G2:
end:


#CtoP(C): Given a permutation in CYCLE notation (a set of list)
# converts it in one-line notation
CtoP:=proc(C) local i,T,j,n,c:
n:=add(nops(c),c in C):
for i from 1 to nops(C) do
 c:=C[i]:
 for j from 1 to nops(c)-1 do
  T[c[j]]:=c[j+1]:
 od:
T[c[nops(c)]]:=c[1]:
end:
[seq(T[i],i=1..n)]:
end:



#IndPer(pi): inputs a permutation pi on the set of VERTICES of K_n
# outputs the member of S_binomial(n,2), a certain permutation on the
# set of edges INDUCED by pi
IndPer:=proc(pi) local n,Ed,i,j,T,r,T1:
n:=nops(pi):
#Ed:=edges
Ed:=[seq(seq({i,j},j=i+1..n),i=1..n)]:
for r from 1 to nops(Ed) do
 T1[Ed[r]]:=r:
od:

for r from 1 to nops(Ed) do
 T[Ed[r]]:={pi[Ed[r][1]],pi[Ed[r][2]]}:
od:
[seq(T1[T[Ed[r]]],r=1..nops(Ed))]:
end:



#CIPkn(n,x): the cycle-index polynomial for K_n
#A000088
CIPkn:=proc(n,x) local S,pi:
S:=permute(n):
 add(WtP(IndPer(pi),x),pi in S)/n!:
end:

#added after class

#ParToPer(P): Given a partition P of an integer n (a member of Pars1(n,n))
# outputs the "canonical permutation" of that type
ParToPer:=proc(P) local n,cu,i,j,r,C,c:
n:=nops(P):
C:={}:
cu:=1:
for i from 1 to n do
 for j from 1 to P[i] do
 c:=[seq(r,r=cu..cu+i-1)]:
 C:=C union {c}:
  cu:=cu+i:
 od:
od:
CtoP(C):
end:


#CIPknC(n,x): the cycle-index polynomial for K_n done cleverly
CIPknC:=proc(n,x) local S,pi,s:
S:=Pars1(n,n):
add(Mult(s)*WtP(IndPer(ParToPer(s)),x),s in S)/n!:
end: