\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 4}
\author{Mary Radcliffe}
\date{due 7 Oct 2016}
\maketitle

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

\begin{enumerate}

\item (*) Define a Motzkin path to be a lattice path from $(0,0)$ to $(n,0)$ where steps are of the form $(1,0)$, $(1,1)$, and $(1, -1)$, such that the path never crosses below the line $y=0$. Let $M_n$ denote the number of such paths, known as the $n^{\textrm{th}}$ Motzkin number. Find the ordinary generating function $\sum_{n\geq 0} M_nx^n$.

\item Find an explicit formula for $a_n$ if $a_0=0$ and $a_{n+1}=a_n+2^n$.

\item (*) A certain insect multiplies in such a way that at the end of each year, the number of insects is double the number from the previous year, plus 1000 more. Suppose we initially release 50 insects of this type. How many will we have at the end of the $n^{\textrm{th}}$ year?

\item (*) A semester at Awesome University has $n$ days. Semesters are arranged as follows: for some $1\leq k\leq n-2$, the first $k$ days are theoretical, and the remaining $n-k$ days are lab days. Further, there is one holiday in the first part, and two holidays scheduled in the second part. 

\begin{enumerate}
\item Show, directly, that the number of ways to design such a semester is $\sum_{k=1}^{n-2} k{n-k\choose 2}$.
\item Use ordinary generating functions to count the number of ways to design the semester, and use this to find a simple formula for $\sum_{k=1}^{n-2} k{n-k\choose 2}$.
\end{enumerate}

\item Recall from the previous homework set, that you found a recurrence on the number of derangements of $[n]$. Use an exponential generating function to find a formula for the number of derangements of $[n]$.

\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}


\end{enumerate}

\end{document}