\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]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 301 Homework}
\author{Mary Radcliffe}
\date{Due 25 September 2017}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item A group of $n$ people is to be divided into committees. From each committee, an even number of people will be chosen to serve on a subcommittee. Find the exponential generating function for the number of ways to do this.

\item For even $n$, let $e_n$ be the number of permutations with all cycles even, $o_n$ the number of permutations with all cycles odd, and $p_n=n!$ the total number of permutations. Let $E(x), O(x)$, and $P(x)$ denote the corresponding exponential generating functions. Prove the following:
\begin{enumerate}
\item $P(t)=(1-t^2)^{-1}$

\item $E(t)=(1-t^2)^{-1/2}$ (A suggested strategy: first, show that the number of matchings in a graph on $2n$ vertices is $\frac{(2n)!}{2^nn!}$ (compare to problem 1 from Homework 2). Show, also that $e_n$ is equal to the number of {\textit pairs} of matchings in a graph on $2n$ vertices, and use this to show the desired result.)


\item $E(t)O(t)=P(t)$


\item $e_n=o_n$ for all even $n$.
\end{enumerate}

\item Prove the following theorem for exponential generating functions.

\begin{quote}
Let $a_n$ be the number of ways to build a structure of type $A$ on an $n$-element set, where $a_0=0$, and $b_n$ the number of ways to build a structure of type $B$ on an $n$-element set, where $b_0=1$. Let $c_n$ denote the number of ways to partition the set $[n]$ into an unspecified number of nonempty subsets, build a structure of type $A$ on each subset, and then a structure of type $B$ on the set of subsets themselves. 

If $A(x)=\displaystyle\sum_{n\geq 1}\frac{a_n}{n!}x^n$, $B(x)=\displaystyle\sum_{n\geq 0}\frac{b_n}{n!}x^n$, and $C(x)=\displaystyle\sum_{n\geq 0}\frac{c_n}{n!}x^n$, then \[C(x)=B(A(x)).\] 
\end{quote}

\end{enumerate}
\end{document}