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

Help := proc(): print(`NuEqC(n,C)`): end:

with(combinat):

### project update 
# see hw24


# The number of sequences of length n with entries in {1,...,c} up to the action of the symmetric group 
# (i.e. the number of equivalence classes) is obtained by plugging in x[i]=c for all i=1..n. 


# NuEqC(n,c): uses CIPsn(n,x) to find that number.

NuEqC := proc(n,c) local f,i: 
f := CIPsn(n,x):
subs([seq(x[i]=c,i=1..n)],f):
end: 



# What is
# [seq(NuEqC(i,2),i=1..12)]
# [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
# [seq(NuEqC(i,3),i=1..12)]
# [3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91]
# [seq(NuEqC(i,4),i=1..12)]
# [4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455]

# conjecture: NuEqC(i,c) = NuEqC(i-1,c) + NuEqC(i,c-1)
# with NuEqC(0,c) = NuEqC(i,0) = 1









### copied from C25.txt 

#C25.txt: April 24, 2025
Help25:=proc(): print(` EC(pi,i), PtoC(pi), WtP(pi,x), CIP(G,x), Mult(a) ,  Pars1(n,m), CIPsn(n,x): `):end:
with(combinat):
#YOU HAVE A SET S OF OBJECTS on n "points", WITH A NATURAL ACTION OF A GROUP OF PERMUTATIONS
#(subset of S_n) and you want to count the number of isomorphim classes
#for each s in S, Images(s)={g(s), g in G}, you want to count how many such isomorphism classes
#Def: For a permutation pi decompose into cycles
#pi=C1*C2*...*Ck, X is a formal variable
#Wt(pi)=X[nops(C1)]*X[nops(C2)]*...*X[nops(Ck)]
#Cycle-Index Polynomial of a group of permutaions G (a subset of S-n) is
#Sum(Wt(pi), pi in G)/nops(G)

#EC(pi,i): inputs a permutation pi and finds the cycle that belongs to i
EC:=proc(pi,i) local a,C,m,j:
C:=[i]:
a:=pi[i]:
while a<>i do
C:=[op(C),a]:
a:=pi[a]:
od:
m:=min(C):
for j from 1 to nops(C) while C[j]<>m do od:
[op(j..nops(C),C),op(1..j-1,C)]:
end:

#Mult(a): inputs an integer partion p in frequency-notation 
#1^a1...n^an [a1, ...,an] of non-negative integers 
#n=add(i*a[i],i=1..nops(p)):
Mult:=proc(a) local n,i:
n:=nops(a):
if n<>add(a[i]*i,i=1..n) then
  RETURN(FAIL):
fi:

#n!/(1!^a1*2!^a2*...*n!^an)/(a1*a2!*..*an!)*0!^a1*1!^a2*...(n-1)!^an
n!/mul(i!^a[i],i=1..n)/mul(a[i]!,i=1..n)*mul((i-1)!^a[i],i=1..n):
end:


#PtoC(pi): inputs a per. in one-line notation outputs its cycle decomposition
#
PtoC:=proc(pi) local S, C,c:
C:={}:
S:={op(pi)}:
while S<>{} do
 c:=EC(pi,S[1]):
 S:=S minus {op(c)}:
  C:=C union {c}:
 od:
C:
end:

#WtP(pi,x): The weight of the permutation pi according to
#x[1]^NumberOfOneCycles*x[2]^NumberOfTwoCycles...*x[n]^NumberOf n cycles
WtP:=proc(pi,x) local C,c:
C:=PtoC(pi):
mul( x[nops(c)], c in C):
end:

#CIP(G,x): The Polya cycle-index polynomial of the gp G of permutations of length n
CIP:=proc(G,x) local g: add(WtP(g,x),g in G)/nops(G):end:

#Added after class

#Pars1(n,m): The set of [a1,a2,...,an] such that 1*a1+...+n*an=m
Pars1:=proc(n,m) local S,s1,i,S1:
option remember:
if m=0 then
 RETURN({[0$n]}):
fi:

if n=0 then
 if m=0 then
   RETURN({[]}):
else
  RETURN({}):
fi:
fi:

S:={}:

for i from 0 to trunc(m/n) do
S1:=Pars1(n-1,m-i*n):
S:=S union {seq([op(s1),i], s1 in S1)}:
od:
S:
end:

#CIPsn(n,x):CIP(permute(n),x), done cleverly, using Mult(a):
CIPsn:=proc(n,x) local S,s,i:
S:=Pars1(n,n):
add(Mult(s)*mul(x[i]^s[i],i=1..n), s in S)/n!:
end: