\documentclass[12pt]{amsart}
\usepackage[margin=1in]{geometry}
\newcommand{\fS}{\mathfrak{S}}
\DeclareMathOperator{\Aut}{Aut}

\begin{document}

Math 188, Spring 2021

Homework 9

Due: June 4, 2021 11:59PM via Gradescope

{\bf Reminder}: Final draft of your project is due June 11. The optional presentation is also due June 11. If you want your HW score to be used for the presentation, submit a single sheet that says: ``Use HW score''. Otherwise, submit a Google drive link so that I can download the video.

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points. 
\begin{enumerate}
\item Let $G_n$ be the graph from HW6 \#1. Describe all of the elements of $\Aut(G_n)$ (a complete solution includes why all of the elements you described are actually distinct). You may use without proof that $|\Aut(G_n)|=2^nn!$.
\item Do the case of general $n$ of Example 7.11, i.e., give a formula for the number of necklaces (considered equivalent up to reflection) of length $n$ using an alphabet of size $k$.

\item Consider assigning one of $k$ colors to each of the entries of a $3 \times 3$ matrix.
  \begin{enumerate}
  \item How many ways are there to do this if we consider two colorings the same if they differ by rotation?
  \item How many ways are there to do this if we consider two colorings the same if they differ by a combination of rotations or reflections?
  \item In both cases, how many colorings (up to equivalence) are there that use 3 different colors, each used to color 3 entries?
  \end{enumerate}

\item In Theorem 7.9, take $X = [n]$, $Y = [d]$, and $G = \fS_n$ with the natural action on $X$.
  \begin{enumerate}
  \item Find a bijection between $G$-orbits on $Y^X$ and weak compositions; give a closed formula for their number using this interpretation.

  \item By varying $d$, explain how the equality between the expression in Theorem 7.9 and your answer to (a) gives a new proof for Corollary 3.30.
  \end{enumerate}

\item Let $p$ be a prime and $n \ge p$. Use the method of \S 7.4 for the following:
  \begin{enumerate}
  \item Show that
    \[
      S(n,k) \equiv S(n-p, k-p) + S(n-p+1,k) \pmod p.
    \]
  \item Show that
    \[
      c(n,k) \equiv c(n-p,k-p) - c(n-p,k-1) \pmod p.
    \]
  \end{enumerate}

\end{enumerate}

\end{document}
