\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 December 11, 2017 \vspace{-4mm}\\
\noindent \small \textit{There are only patterns, patterns on top of patterns, patterns that affect other patterns. Patterns hidden by patterns. Patterns within patterns.
If you watch close, history does nothing but repeat itself.
What we call chaos is just patterns we haven't recognized. What we call random is just patterns we can't decipher.
}\\\vspace{1mm} \hfill--- Chuck Palahniuk
\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in the following:}
\vspace{5mm}
\bigskip
\begin{enumerate}
\item Let $g_n$ be the number of ways in which $n$ people can sit down around an unspecified number of tables that are arranged in a line, so that if $k$ tables have people around them, then those will be the first $k$ tables in the line. Two seating arrangements are considered identical if each person has the same left neighbour in both of them, and each person sits at the same table in both of them. Find the exponential generating function $G(x)$ of the sequence $g_n$.
\item Find the exponential generating function for the number of ways that $n$ people can be divided into any number of non-empty committees where each committee has a designated chairperson.
\item Describe, for arbitrary $n$ a permutation of length $n^2$ which contains all $n!$ patterns of length $n$.
\item Describe the permutations that avoid both of the patterns 312 and 213 (Hint: Think about where $1$ can go, and then where $2$ can go, etc. ) How many such permutations are there of length $n$?
\item Suppose you have two stacks in series, meaning that items of the input can be pushed to the first stack, popped from the first stack and immediately pushed onto the second stack, or popped from the second stack to the output. Show the operations that can be used to sort 231 using two stacks in series, and find a permutation that cannot be sorted using two stacks in series.
\end{enumerate}
\end{document}