\documentclass[12pt]{amsart}

\usepackage[margin=1in]{geometry}

\newcommand{\bF}{\mathbf{F}}
\newcommand{\bZ}{\mathbf{Z}}

\begin{document}

Math 188, Spring 2021

Homework 8

Due: May 28, 2021 11:59PM via Gradescope

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points. 
    
\begin{enumerate}

\item How many ways are there to list the letters of the word MATTDAMON so that no two consecutive letters are the same?

\item Let $n > 1$ be an integer. We have $n$ married couples ($2n$ people in total).
  \begin{enumerate}
  \item How many ways can we have the $2n$ people stand in a line so that no person is standing next to their spouse?
    
  \item Same as (a), but replace line by circle.
  \end{enumerate}
\item Let $q$ be a prime power and $n$ a positive integer. Let $V$ be an $n$-dimensional $\bF_q$-vector space and let $P$ be the poset whose elements are linear subspaces of $V$ with the ordering $X \le Y$ if $X$ is contained in $Y$. Show that the M\"obius function of $P$ is given by
  \[
    \mu(X,Y) = (-1)^d q^{\binom{d}{2}}
  \]
  where $d = \dim Y - \dim X$. Hint at end.
  
\item For a positive integer $n$, define
  \[
    f(n) = |\{i \in \bZ \mid 1 \le i \le n, \ \gcd(n,i)=1\}|.
  \]
  \begin{enumerate}
  \item Show that
    \[
      n = \sum_{d |n} f(d)
    \]
    where the sum is over all positive integers $d$ that divide $n$.
  \item Use M\"obius inversion to show that
    \[
      f(n) = n\prod_{p|n} \left(1 - \frac1p \right) 
    \]
    where the product is over the primes $p$ that divide $n$.
  \end{enumerate}

\item Let $\Pi_n$ be the poset of set partitions of $[n]$ and let $\mu$ be its M\"obius function. Write a formula for the number of connected labeled graphs with vertex set $[n]$ using $\mu$ (a formula for $\mu$ is given in the book, but you don't need to look it up).
  
  \section{Optional problems (don't turn in)}
  
\item A derangement of a set $S$ is a bijection $f \colon S \to S$ such that $f(i) \ne i$ for $i \in S$. Let $d_n$ be the number of derangements of $[n]$, and let 
\[
D(x) = \sum_{n \ge 0} \frac{d_n}{n!} x^n.
\]
\begin{enumerate}

\item Using the structure interpretation for products of EGF, show that
\[
D(x) e^x = \frac{1}{1-x}.
\]

\item Show how this implies the formula we previously obtained:
\[
d_n = \sum_{i=0}^n (-1)^i \frac{n!}{i!}.
\]
\end{enumerate}

\item There are $n$ people sitting at a circular table. How many ways can they rearrange seats so that no one sits next to someone they were sitting next to before?
  
\item Let $q$ be a prime power and let $N_n$ be the number of monic irreducible polynomials of degree $n$ with coefficients in $\bF_q$.
  \begin{enumerate}
    
  \item Using that polynomials over a field satisfy unique factorization, show that
    \[
      (1-qx)^{-1} = \prod_{d \ge 1} (1-x^d)^{-N_d}.
    \]
  \item Take the logarithmic derivative of (a) and compare the coefficient of $x^{n-1}$ to get $q^n = \sum_{d|n} dN_d$.
    
  \item Use M\"obius inversion to get a formula for $N_n$.
    
  \end{enumerate}
  
\end{enumerate}

  \section{Hints}

  (3) For subspaces $X \subseteq Y$, the set of $r$-dimensional subspaces $Z$ such that $X \subseteq Z \subseteq Y$ are in bijection with $(r-\dim X)$-dimensional subspaces in the quotient space $Y/X$, and $\dim(Y/X) = \dim Y - \dim X$.  

\end{document}
