\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{graphicx}

\usepackage{enumitem}
\setenumerate[0]{label=(\alph*)}

\addtolength{\topmargin}{-0.95in}
\addtolength{\textheight}{1.8in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\textwidth}{1.0in}
\pagestyle{empty}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\bF}{\,\overline{\!\mathcal{F}}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\tD}{\tilde{\mathcal{D}}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\NN}{\mathcal{N}}
\newcommand{\Flat}{\mathrm{Flat}}
\renewcommand{\S}{\mathcal S}
\renewcommand{\SS}{\mathfrak S}
\newcommand{\surj}{\mathrm{surj}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\cyc}{\mathrm{cyc}}
\newcommand{\wt}{\mathrm{wt}}

\newcommand{\lam}{\lambda}

%\newcommand{\multi}[2]{\left(\!\binom{#1}{#2}\!\right)}
%\newcommand{\multi}[2] { \genfrac {(} {)} {0em} {} {#1} {#2} }
\newcommand{\multi}[2]{\left(\!\left(\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right)\!\right)}

\newcommand{\stirling}[2]{\left\{\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right\}}

\newcommand{\cycle}[2]
{\left[
\genfrac{}{}{0pt}{}{#1}{#2}
\right]}

\newcommand{\form}[1]{[[#1]]}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf Homework 4}\hfill Fall 2025}
\vspace{1em}      

\noindent  Feel free to discuss homework problems with other students, and to learn from references, but please do not look up specific answers.
Write out solutions in your own words, and give explicit credit for any significant help. 
\\[.5em]
{\bf 1.}  Show that the number $e_{2k}$ of permutations in $\mathfrak S_{2k}$ which have only even-length cycles is $(1\cdot 3\cdot 5\cdots (2k{-}1))^2$. For example, $e_4=(1\cdot 3)^2=9$
counts the permutations: 
$$(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23).$$
 {\it Hint:} The even part of a function $f(x)$ is $\frac12(f(x)+f(-x))$.        \\
{\it Extra Credit:} Give a bijective transformation proof of this formula.
\\[1em]
 {\bf 2.}  Writing permutations as sets of cycles, 
we computed the bivariate generating function:
$$
\tilde S(x,y) \ =\  \sum_{k,n\geq 0} \cycle kn y^n \frac{x^k}{k!}
\ =\  \exp\!\left( y\log\tfrac{1}{1-x}\right) \ =\  \frac{1}{(1-x)^y}\,,
$$
% giving  $S_k(y) \ =\ \sum_{n=1}^k \cycle kn y^n \ =\ y^{\overline{k}}\ =\ y(y{+}1)\cdots (y{+}k{-}1)$
% and $S^{(n)}(x) \ =\ \sum_{k\geq 0} \cycle kn y^n \ =\ (\log\!\frac 1{1-x})^n$.
%
Consider the average or expected number of cycles in a permutation $w\in \SS_k$:
$$
a_k \,=\, %\mathbb{E}(\text{cyc}) \,=\, 
\frac{1}{k!} \sum_{w\in S_k}  \text{cyc}(w)
\,=\,\frac{1}{k!}\,\sum_{n=1}^k \cycle kn n.
$$
Show that the generating function of $a_k$ is a partial derivative of $\tilde S(x,y)$:
$$
A(x) \,=\, \sum_{k\geq 0} a_k x^k \,=\,  \left[\frac{\partial}{\partial y} \tilde S(x,y)\,\right]_{y=1}.
$$
Compute $A(x)$, and  find a simple asymptotic approximation $a_k\sim f(k)$:
what is the approximate number of cycles expected for a permutation $w\in \SS_k$?
{\it Hint:} Harmonic series.

\hrulefill

\vspace{.5em}

\noindent
{\it Burnside Lemma:} For $G$ acting on a finite class $\F$,
the number of orbits is equal to the average number of fixed points:
$\#\bar\F \ =\ \frac{1}{\#G}\sum_{g\in G} \#\F^g$, 
where $\F^g = \{f\in \F \mid g(f) = f\}$.
\\[.5em]
{\it Pattern inventory generating function:} 
For fixed $k,n$, and the finite class of functions $\F = \{f:[k]\to [n]\}$, 
define the multi-variable generating function:
$$
F(\vec y) = F(y_1,\ldots,y_n) 
= \sum_{f\in \F} y_1^{\wt_1(f)} \cdots y_n^{\wt_n(f)}
= \sum_{m_1,\ldots, m_n\geq 0} F_{m_1,\ldots, m_n} y_1^{m_1}\cdots y_n^{m_n},
$$
where $\wt_i(f) = \#f^{-1}(i)$ and $\F_{\vec m} =F_{m_1,\ldots, m_n}=\#\{f \mid 
\wt_1(f)=m_1, \ldots, \wt_n(f)=m_n\}$.
\\[.5em]
{\it Cycle index polynomial:} 
For a permutation group $G\subset \SS_k$ define:
$$
Z_G(z_1,\ldots,z_k) = \sum_{w\in G} z_1^{\cyc_1(w)}\cdots z_k^{\cyc_k(w)}
= \sum_{c_1,\ldots, c_k\geq 0} G_{c_1,\ldots, c_n} z_1^{c_1}\cdots z_k^{c_k},
$$
where $\cyc_i(w)=\#$ $i$-cycles in $w\in\SS_k$ and
$G_{c_1,\ldots, c_k}
=\#\{w\in G \mid \cyc_i(w)=c_i\text{ for all }i\}$.

\pagebreak

\noindent
{\bf 3.} {\it Polya formula:} Let $G\subset \SS_k$ act on $\F = \{f:[k]\to [n]\}$,
with orbits $\bar\F=\F / G$. Then:
$$
\bar F(\vec y) = \tfrac1{\# G}Z_G(p_1(\vec y),\ldots, p_k(\vec y)),
$$
where $p_i(\vec y) = y_1^i+\cdots+y_n^i$.
Prove this as follows:
\begin{itemize}

\item[{\bf a.}] 
Show $\bar F(\vec y) = \tfrac1{\# G} S(\vec y)$, where $S(\vec y)$ 
is the multi-variable generating function of:
$$
\S = \{(w,f)\in G\times \F \mid f(w(i)) = f(i) \text{ for all } i\},
$$
with $\wt_i(w,f) = \wt_i(f) = \#f^{-1}(i)$.
{\it Hint:} Apply Burnside to each weight set $\F_{\vec m}$.

\item[{\bf b.}] For the multi-graded class $\NN = [n]$ with pattern inventory 
$N(\vec y) = y_1+\cdots+y_n$, give a multi-graded bijection:
$$
\S \ \cong\ \coprod_{w\in G} 
(\Delta^1\NN)^{\cyc_1(w)}\!\times \cdots\times (\Delta^k\NN)^{\cyc_k(w)},
$$
where $\Delta^i \NN$ is the diagonal class $\{(j,\ldots, j) \in \NN^i\}$.
Use this to prove Polya's formula.

\end{itemize}

\noindent
{\bf 4.} Let $G$ be the rotational symmetry group of the 3-dimensional cube, 
containing $\frac14$ \& $\frac12$ rotations around opposite pairs of square faces,
$\frac13$ rotations around opposite pairs of vertices, and $\frac12$ rotations of opposite pairs of edges.
(You may rely on pictures, no need to codify the representation in matrices.)
\begin{itemize}

\item[{\bf a.}]  Show $G$ is isomorphic to $\SS_4$. 
{\it Hint:} Find 4 isometric structures inside the cube, permuted by $G$,
so that certain rotations induce the generators 
$(12), (23), (34)\in \SS_4$.

\item[{\bf b.}] Count the possible designs for dice, 
ways to label the 6 square faces with every element of $1, \ldots , 6$, 
up to rotational symmetry: that is, count the physically distinct designs.

\item[{\bf c.}] Consider the permutation representation 
$G\subset \SS_6$ induced by the rotations permuting the 6 faces.  
Determine the cycle index polynomial $Z_G(z_1,\ldots,z_6)$.

\item[{\bf d.}] Let $\F = \{f:[6]\to[n]\}$ be the class of 
labelings of the 6 faces with $n$ available colors. 
Use Burnside to compute the number of physically distinct labelings 
in $\bar\F=\F/G$.

\item[{\bf e.}] Use Polya to determine
the pattern inventory polynomial $\overline{\! F}(y_1,\ldots,y_n)$. 
Expand this by computer for $n=3$, and find how many colorings of the 6 faces use the labels $1,1,2, 2,3,3$.

\end{itemize}

\noindent
{\bf 5.} Define the {\it Euler phi-function} $\varphi(k)=\#\{j\leq k \mid \gcd(j,k)=1\}$,
the number of integers in $[k]$ which are relatively prime to $k$. For
example, $\varphi(p)=p{-}1$ for $p$ prime.
\begin{itemize}

\item[{\bf a.}]  Use the Principle of Inclusion-Exclusion to prove that if $k$ has prime factorization $k=p_1^{\ell_1} p_2^{\ell_2}\cdots$, then $\varphi(k) =\prod_{i}\, p_i^{\ell_i-1} (p_i{-}1)$.

\item[{\bf b.}]  Determine the cycle index $Z_G(z_1,\ldots, z_k)$ for the cyclic group
$G=C_k$ generated by $(12\cdots k)\in S_k$. 
The answer will involve the phi-function.

\item[{\bf c.}]  For a graded unlabeled class $\B$, 
consider the class $\bar\F=\text{\sc Cyc}_k\,\B$ consisting
of all cyclic arrangements of $k$ elements of $\B$, 
up to rotation symmetry.
Use the previous problems to find the generating function 
$\bar F(y)$ in terms of 
the ordinary generating function $B(y)$. 
% 
% $\bar F(x)\ =\ \frac1k \sum_{d|k} \phi(d) B(x^d)^{k/d}$}
%
%
\end{itemize}

\end{document}

*********************************************************************************************

{\bf 3.} A labeled signed graded class is split into positive and negative elements 
$\tilde \A^\pm_k=\tilde A_k^+\cup \tilde \A_k^-$,
and has the signed generating function:
$$
\tilde A^{\pm}(x) 
\ =\  \sum_{k\geq 0} (A_k^+{-}A_k^-)\frac{x^k}{k!}.
$$
{\bf a.} The  {\it Labeled Graded Product Principle} states that a 
labeled Cartesian product $\tilde\A\star\tilde\B$
has generating function $\tilde A(x)\tilde B(x)$.
\\[.5em]
 {\it Problem:} Prove that this also holds for the Cartesian product of 
{\it signed} labeled graded classes (with an appropriate definition of $\sgn$).
\\[1em]
{\bf b.} The  {\it Involution Priniciple} assumes a sign-reversing bijection 
$I:\tilde\A_k^\pm\to\tilde\A_k^\pm$ with $I^{-1}=I$ and $\mathrm{sgn}(I(a))=-\mathrm{sgn}(a)$,
except on the fixed-point set $\tilde\F_k^\pm=\{a\in \tilde\A_k^\pm\mid I(a)=a\}$.
Cancelation implies the equality of signed generating functions:
 $
 \tilde F^\pm(x)=\tilde A^\pm(x).
 $
 {\it Problem:} Prove the equation:
 $$
\tilde D(x) \ = \ 
\frac{1}{1-x}\cdot e^{-x}
$$
by interpreting the right side as the product of signed exponential generating functions for two simple signed labeled graded classes.
Then find an involution whose fixed points (all positive) are in bijection with derangements:
$$
\tilde\F^{\pm}\ =\ \tilde\F^{+} \ \cong\ \tD_k.
$$

*********************************************************************************************
