\documentclass[12pt]{amsart}
% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}
\usepackage{tikz}
% Set the title, author, and date information.
% Formally begin the document and make the title.
\begin{document}
\noindent \textbf{Math 315 - Fall 2017 \\
Homework 7} \\
Due November 15, 2017 \vspace{-4mm}\\
\noindent \small \textit{In mathematics you don't understand things. You just get used to them.}\\\vspace{1mm} \hfill---
John Von Neumann
\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in one of the following:} (You can turn in more for extra credit.)
\vspace{5mm}
\bigskip
\begin{enumerate}
\item Let $B(x)$ be the generating function for the collection of all lattice paths with Up/Down steps which stay above the x-axis and have no peaks of height 1. (i.e., in a ballot sequence, a point where Alice and Bob are tied, after which Alice gets a vote followed by a vote for Bob.) For example, paths such as
\begin{center}
\begin{tikzpicture}[scale=0.4]
\def\U{-- ++(1,1) [fill] circle(1.6pt)}
\def\D{-- ++(1,-1) [fill] circle(1.6pt)}
\begin{scope}[shift = {(0,0)}, scale=1]
\draw[line width = .4mm] (0,0) circle(1.3pt)\U\D;
\draw[line width = .2mm] (0,0) -- (2,0);
\end{scope}
\begin{scope}[shift = {(4,0)}, scale=1]
\draw[line width = .4mm] (0,0) circle(1.3pt)\U\U\D\D\U\D\U\D\U\U\D\D;
\draw[line width = .2mm] (0,0) -- (12,0);
\end{scope}
\end{tikzpicture}
\end{center}
are \textbf{NOT} permitted. Find the generating function $B(x)$ using the same ideas as we looked at in class.
\item Find a generating function for sequences of integers $\{a_1,a_2,\ldots a_n$ where $1\leq a_1\leq a_2\leq \cdots \leq a_n$ and $a_i\leq i$. Note: the empty sequence is considered such a sequence!
\item Let $a_0 =0$ and define $a_{n} = 2n\cdot a_{n-1} + n!$ for $n\geq 1$. Find an explicit formula for $a_n$ by using the EGF for the sequence $a_0,a_1,a_2,\ldots$. (Hint: Find a functional equation involving the EGF for $a_n$.)
\item A permutation $\pi$ of $[n]$ is said to be an \textbf{involution} if its cycle decomposition consists of only 1- or 2-cycles. Let $\mathcal{I}$ be the collection of all involutions (for all $n\geq 0$.) Find the EGF for $\mathcal{I}$.
\end{enumerate}
\end{document}