\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 5}
\author{Mary Radcliffe}
\date{due 19 Oct 2016}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

\begin{enumerate}

\item (*) Let $\pi$ be a permutation of $[n]$. We define a cycle of length $k$ in $\pi$ to be a sequence $a_1, a_2, \dots, a_k$ such that $\pi(a_i)=a_{i+1}$ for all $i<k$, and $\pi(a_k)=a_1$. Note that every permutation can be written as a collection of cycles.
\begin{enumerate}
\item Fix $k$. Find the exponential generating function $F(x)$ for the number of permutations having all cycles of length $k$.
\item Determine the number of permutations of $[n]$ that have all cycles of length at most 4.

\end{enumerate}


\item (*) Suppose you wanted to count permutations that had all their cycles of length divisible by $k$. Define an exponential family $\mathcal{F}$ that will generate these permutations. Use the theorems from class to find an exponential generating function for the number of such permutations.


\item \label{Problem2} Suppose you have an exponential family $\mathcal{F}=\{D_1, D_2, D_3, \dots\}$, with corresponding generating functions \[D(x)=\sum_{n\geq 1} \frac{d_n}{n!}x^n\hbox{ and }H(x)=\sum_{n\geq 0} \frac{h_n}{n!}x^n,\]
where $d_n=|D_n|$ and $h_n$ is the total number of hands of weight $n$ in $\mathcal{F}$.

For $n\geq 1$, put $h_n = \sum_{k=1}^n h(n, k)$. Prove that $nh_n = \sum_{k=1}^{n-1} {n\choose k}kd_kh_{n-k}$.

(Hint: Use the corollary from class to write $H(x)$ in terms of $D(x)$. Take a logarithm of both sides, then take a derivative and solve for the desired coefficients.)


\item Let $G$ be a graph. Show that $G$ must have at least two vertices of the same degree.

\item (*) Prove that the distances in a graph $G$ satisfy the triangle inequality; that is, if $u, v, w\in V(G)$ then $d(u, w)\leq d(u, v)+d(v, w)$.

\newpage
\item (*) A labelled graph is a graph together with a labeling on the vertices. For example, the two graphs shown below are the same as unlabelled graphs, but are different as labelled graphs:
\begin{figure}[htp]
\centering
\includegraphics[scale=.5]{Problem3.pdf}
\end{figure}

\begin{enumerate}
\item Explain why there are $2^{{n\choose 2}}$ labelled graphs on $n$ vertices.
\item Use the result of problem \ref{Problem2} to find a recurrence for calculating the number of connected labelled graphs on $n$ vertices.
\item Determine the number of connected labelled graphs on $n$ vertices for $n=1, 2, 3, 4, 5$.
\end{enumerate}


\end{enumerate}

\end{document}