\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,graphicx}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Discussion 3 -- Polya's Theorem}
\centerline{April 24 and 28, 2017}
\vskip 10pt
\noindent
{\it Background}
\vskip 10pt
\noindent
Last Friday, we stated the Polya Counting Theorem and did a first example using it.
Here's the statement again:
\vskip 10pt
\noindent
{\bf Polya's Theorem}. Let a finite group $G$ act on a set $S$ and hence on the
set $X$ of $m$-colorings of $S$.  The number of distinguishable colorings
using color $i$ the number $\ell_i$ times (where $\sum_{i = 1}^m \ell_i = |S|$)
is given by the coefficient of $c_1^{\ell_1}\cdots c_m^{\ell_m}$ in 
$$Z_G(c_1 + \cdots + c_m, c_1^2 + \cdots + c_m^2, \ldots, c_1^{|S|} + \cdots c_m^{|S|}).$$
\par
\noindent
Here $Z_G(x_1,\ldots,x_{|S|})$ is the {\it cycle index polynomial} of $G$ acting on $S$:
$$Z_G(x_1,\ldots,x_{|S|}) = \frac{1}{|G|} \sum_{g \in G} {\rm cim}(g)$$
and ${\rm cim}(g)$ is the {\it cycle index monomial}
$${\rm cim}(g) = \prod_{i = 1} x_i^{k_i(g)}.$$
The variables are $x_1,x_2,\ldots,x_{|S|}$ and $k_i(g) = $ the number of cycles of length
$i$ in the permutation representation of $g$ acting on $S$ (using some labeling of the 
elements of $|S|$ by the integers in $[|S|]$).  Usually there will not be cycles of every
possible length $1,2,3,\ldots,|S|$.  If so, we usually just ignore those variables.  
\vskip 10pt
Recall the idea -- colorings are not distinguishable if there is some group element
that takes one to the other.  They are distinguishable if and only if they are in
different orbits under the action of $G$ on the set $X$ of colorings.  
\vskip 10pt
\noindent
To finish off the semester before the final project presentations, we will 
work through an interesting and complicated example using this!  All of the 
calculations will be do-able by hand (although somewhat tedious). 
You may also use Maple to compute the relevant cycle index polynomial and
apply the Polya Theorem if you prefer.  
\vskip 10pt
\noindent
{\it Questions}
\vskip 10pt
\begin{figure}
\begin{center}
\includegraphics[width=5in]{CubeS4.png}
\caption{The symmetries of the nodes ($=$ vertices) of a cube}
\end{center}
\end{figure}
\begin{itemize}
\item[(A)]  The group acting on the nodes ($=$ vertices) of a cube
is a group of order $24$.  As permutations of the
vertices, the elements are listed in the table on the back of this sheet.
For each element, find ${\rm Inv}(g)$, ${\rm cyc}(g)$ and ${\rm cim}(g)$.
\item[(B)]  How many distinct colorings of the vertices are there if
we have $m = 4$ colorings to use?  
\item[(C)]  How many distinguishable colorings are there if each of the 4 colors is
used exactly twice?
\item[(D)]  How many if three of the colors are used once each and the
other is used five times?
\item[(E)]  {\bf Extra Credit} The group you are working with here is 
isomorphic to $S_4$.  However, it shouldn't be immediately obvious
what four things are being permuted to produce the isomorphism.  Find
such a set of four things (related to the geometry of the cube), such that
the group $G$ is acting as the set of all permutations of those four objects.
\end{itemize}
\end{document}
