# OK to post homework
# Aurora Hiveley, 4/29/25, Assignment 26

Help := proc(): print(``): end:

with(combinat):

### project update 
# generalized previous procedure to generate the initial spanning tree so that now it generates a 
# spanning forest of rooted trees from the "residual blob" in each iteration. 
# also updated the overleaf paper with a description of how this works and what the syntax is. 
# other group members have been writing/coding in parallel.


### cemetery trip 
# i'll be there! 


# 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.

# subs({seq(x[i]=2,i=1..binomial(13,2))},CIPknC(13,x));
# output: 50502031367952


# 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 unlabelled graphs are there with 13 vertices and 30 edges?

# f := expand(subs({seq(x[i]=1+t^i,i=1..binomial(13,2))},CIPknC(13,x)));
# coeff(f,t,30);
# output: 584089835857





# What are the OEIS numbers (if they exist) for
# The sequence enumerating unlabeld graphs with n vertices and n-1 edges?
# seq( coeff(expand(subs({seq(x[i]=1+t^i,i=1..binomial(n,2))},CIPknC(n,x))),t,n-1),n=1..9);
#                1, 1, 1, 3, 6, 15, 41, 115, 345
# OEIS: A001433

# The sequence enumerating unlabeld graphs with n vertices and n edges?
# seq( coeff(expand(subs({seq(x[i]=1+t^i,i=1..binomial(n,2))},CIPknC(n,x))),t,n),n=1..9);
#                0, 0, 1, 2, 6, 21, 65, 221, 771
# OEIS: A001434

# The sequence enumerating unlabelled graphs with n+1 vertices and n+1 edges?
#                0, 1, 2, 6, 21, 65, 221, 771
# same as before, OEIS A001434 

# n vertices and n+1 edges is an all zeros sequence since this graph would not be simple








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

read `AGT.txt`:

#MultP(pi,sig): the product of the permutation pi and sig
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,i,s,g1,n,G2,G3:
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 to 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]:
od:
[seq(T[i],i=1..n)]:
end:

#IndPer(pi): inputs a permuation pi on the set of VERTICES of K_n
#outputs the member of S_binomial(n,2) , a certaion permutation on the
#set of edges INDUCED by pi
IndPer:=proc(pi) local n, Ed, i,j,T,r,T1:
n:=nops(pi):
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
#A88
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 partion P of an integer n (a member of Pars1(n,n)) outputs the "canononical permuation" 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:=Pars1(n,n):
 add(Mult(s)*WtP(IndPer(ParToPer(s)),x),s in S)/n!:
end: