Help:=proc(): print(` A81(N), A55(N), Wt(pi,s) ,CIP(G,s), NuCol(G,c) `): print(`Cn(n) , WtCol(G,c,x) `): end: with(combinat): with(group): ###From C23.txt #Counting unlabelled rooted trees #A[n]=number of rooted unalabelled trees with n vertices #A[1]=1, A[2]=1, A[3]=2, #Removing the root, leads to a MULTISET of smaller rooted trees #HOW MANY with one vertex? 1/(1-x)^A[1] #HOW MANY with two vertices 1/(1-x^2)^A[2] #... #How MANY with i vertices? 1/(1-x^i)^A[i] #A[1]*x+A[2]*x^2+A[3]*x^3+A[4]*x^4+...= #x/(1-x)^A[1]/(1-x^2)^A[2]/(1-x^3)^A[3]/..... #A81(N): the first N terms of the enumerating #sequence for the numnber of UNLABELLED rooted trees #with n vertices A81:=proc(N) local A,f,n,x,i: A:=[1]: for n from 2 to N do f:=x*mul(1/(1-x^i)^A[i],i=1..nops(A)): f:=taylor(f,x=0,n+1): A:=[op(A),coeff(f,x,n)]: od: A: end: ###end from C23.txt #Let R(x) be the (ORDINARY) generating function for #Unlabelled rooted trees (counted by URT(N)) #R(x)=add(URT(infinity)[i]*x^i,i=0..infinity); #Let A(x) be the generating function for unlabelled trees #A(x)=R(x)-R(x)^2/2+R(x^2)/2 #A55(N): the first N terms in OEIS A000055, Neil Sloane's #favorite sequence (default, viewed April 23, 2012 and many #years before, possibly from the start) #the number of unlabelled trees A55:=proc(N) local R,A,L,x,i: L:=A81(N): R:=add(L[i]*x^i,i=1..N): A:=expand(R-R^2/2+subs(x=x^2,R)/2): [seq(coeff(A,x,i), i=1..N)]: end: #Wt(pi,s): the weight (according to Polya) of #the permutation pi #For example : Wt([1,2,3],s)=s[1]^3 Wt:=proc(pi,s) local L,n,i,y,W: n:=nops(pi): L:=convert(pi, `disjcyc`); W:=mul( s[ nops(L[i])], i=1..nops(L)): W*s[1]^n/subs({seq(s[i]=s[1]^i,i=2..n)},W): end: #CIP(G,s): inputs a group (or even a set) of permutations #and outputs the Polya Cycle-index polynomial #1/|G| *( Sum of the weights of all pi in G) #weight(pi)=prod(s[i]^(#of cycles of length i) #s is a letter #For example, #wt([2,1,4,5,3])=s[2]^1*s[3]^1=s[2]*s[3] #wt([1,2,3,4,5,6])=s[1]^6 #wt([2,3,4,5,6,1])=s[6] CIP:=proc(G,s) local pi: add(Wt(pi,s), pi in G)/nops(G): end: #NuCol(G,c): the number of ways of coloring a combinatorial #object (up to equivalence) with the group being G #with c colors #For example #NuCol(permute(4),c); NuCol:=proc(G,c) local s,P,n: n:=nops(G[1]): P:=CIP(G,s): factor(subs( { seq( s[i]=c, i=1..n)}, P)): end: #Cn(n): the group of rotations of a circle with n beads Cn:=proc(n) local i,j: #[i,i+1,...,n,1,..., i-1] { seq( [seq(j,j=i..n), seq(j,j=1..i-1)], i=1..n)}: end: ##WtCol(G,c,x): The generating function of all colorings #with the weigt #x[1]^NumberOFBeadsColoredColor1* #x[2]^NumberOFBeadsColoredColor2* .... WtCol:=proc(G,c,x) local i,n,P: n:=nops(G[1]): P:=CIP(G,s): #s[1]=x[1]+...+x[c] #s[2]=x[1]^2+ ...+x[c]^2 #.... expand(subs({seq( s[i]=add(x[j]^i,j=1..c),i=1..n)},P)): end: