# Jike Liu
# HomeWork #26

read "C26.txt":

# Problem 1: Cube colorings up to rotational symmetry


# CubeGp(): rotational symmetry group of the cube acting on its 6 faces.
# Face labels: [U,L,F,R,B,D]=[1,2,3,4,5,6].
# The original C26 version had X=Y, so I use three different quarter-turns.
CubeGp:=proc() local X,Y,Z;
X:=[5,2,1,4,6,3]:
Y:=[4,1,3,6,5,2]:
Z:=[1,5,2,3,4,6]:
GenGp({X,Y,Z}):
end:

# Check: the rotation group of the cube has order 24.
Gcube:=CubeGp():
nops(Gcube);

# Unnormalized cycle index polynomial.
CIPcube:=expand(CIP(Gcube,x));
CIPcube;

# Number of ways to color the faces of a cube with c colors, up to rotations.
CubeColoring:=proc(c) local G,x;
G:=CubeGp():
expand(subs({seq(x[i]=c,i=1..6)},CIP(G,x))/nops(G)):
end:

CubeColoring(c);
seq(CubeColoring(i),i=0..10);

# This sequence is OEIS A047780.


# Problem 2: Necklaces without clasp


# Necklace(n,c): number of ways to color a necklace without clasp of n beads
# using c colors, where necklaces are considered up to rotation.
Necklace:=proc(n,c) local R,G,x;
R:=[seq(i,i=2..n),1]:
G:=GenGp({R}):
expand(subs({seq(x[i]=c,i=1..n)},CIP(G,x))/nops(G)):
end:

seq(Necklace(n,c),n=1..10);