\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{Math 184 Homework 4}
\date{Fall 2022}
\begin{document}
\maketitle
This homework is due on gradescope Friday October 28th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.
\begin{ques}[Distinct Parts Partitions, 20 points]
Show that the number of partitions of $n$ into exactly $k$ distinct parts is
$$
p_k(n-k(k-1)/2).
$$
\end{ques}
\begin{ques}[Permutation Orders, 20 points]
Let $\pi$ be a permutation of $[n]$. Show that $\pi^{n!}$ is the identity permutation (i.e. the permutation $\sigma$ of $[n]$ where $\sigma(i)=i$ for all $1\leq i\leq n$).
\end{ques}
\begin{ques}[Ambiguous Permutations, 30 points]
We have discussed two ways to encode a permutation $\pi$ of $[n]$ as an ordered list of the numbers from $1$ to $n$: either by listing the values $\pi(1),\pi(2),\ldots,\pi(n)$ in order or by writing $\pi$ in canonical cycle notation and removing the parentheses. Call a permutation $\pi$ \emph{ambiguous} if each of these representations gives rise to the same sequence of numbers. Show that the number of ambiguous permutations of $[n]$ is given by the Fibonacci number $F_n$ where $F_1=1, F_2=2,$ and $F_n = F_{n-1}+F_{n-2}$ for all $n > 2.$
\end{ques}
\begin{ques}[Random Permutations and Coin Flips, 30 points]
Consider the following two random processes:
\begin{enumerate}
\item Pick a uniform random permutation $\pi$ of $[n]$ and count the number of cycles in $\pi$.
\item Flip $n$ coins $C_1,C_2,\ldots,C_n$ where $C_i$ has a probability $1/i$ of coming up heads, independently of the other coins and count the total number of heads.
\end{enumerate}
Show that these processes give rise to the same distribution over outcomes.
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}