### Kristen Lew, Homework 26
### ExpMath, Spring 2012
## Post if you wish.

### Problem 1
## How many necklaces are there with 
# 15 beads colored Red, 23 beads colored Blue, and 12 beads colored Green?

Necklaces:=proc() local G,n,c,x:
	n:=15+23+12:
	G:=Cn(n):
	coeff(coeff(coeff(WtCol(G,3,x), x[1]^15), x[2]^23),x[3]^12):
end:

## Necklaces();
## 37564175809042384320

		## WtCol(G,c,x): the generating function of all colorings with the weight 
		# x[1]^(num of beads colored color 1)*x[2]^(num of beads colored color 2)*..
		WtCol:=proc(G,c,x) local i,n,P:
			n:=nops(G[1]):
			P:=CIP(G,s):
			expand(subs({seq(s[i]=add(x[j]^i,j=1..c),i=1..n)},P)):
		end:
		CIP:=proc(G,s) local pi: 
			add(Wt(pi,s), pi in G)/nops(G):
		end:
		Wt:=proc(pi,s) local L,n,i,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:
		Cn:=proc(n) local i,j:
			{seq([seq(j,j=i..n),seq(j,j=1..i-1)],i=1..n)}:
		end:


### Problem 2
## In how many ways can you color the faces of a cube (up to rotational symmetry) 
# with 3 faces colored Red, 2 faces colored Blue, and one face colored Green?
Cubes:=proc() local G,x:
	G:=Gp({[1,4,2,5,3,6],[4,2,1,6,5,3],[2,6,3,4,1,5]}):
	coeff(coeff(coeff(WtCol(G,3,x), x[1]^3), x[2]^2), x[3]):
end:

## Cubes();
## 3 
		Gp:=proc(S) local length, i, Done, ToDo, T, new:
			if not type(S,set) then
				return `FAIL`:
			fi:
			if nops(S)=0 then
				return `FAIL: S should be nonempty`:
			fi:
			length:=nops(S[1]):
			for i from 2 to nops(S) do
				if nops(S[i])<>length then
					return `FAIL`:
				fi:
			od:
			Done:={}:
			ToDo:={[seq(i,i=1..length)]}:
			while ToDo<>{} do
				T:=ToDo[1]:
				Done:=Done union {T}:
				ToDo:=ToDo minus {T}:
				new:=map2(Mul,T,S):
				ToDo:=ToDo union (new minus Done):
			od:
			return Done:
		end:
		Mul:=proc(P,Q) local perm,k:
			if nops( P) <> nops(Q) then
				RETURN(FAIL):
			fi:
			perm:=[seq(Q[P[k]],k=1..nops(Q))]:
		end: