\documentclass[11pt]{amsart}
\usepackage{graphicx}
\usepackage{amssymb}

\textwidth = 6.5 in
\textheight = 8.5 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.5 in
\headsep = 0.2 in
\parskip = 0.2in
\parindent = 0.0in

\newcommand{\pchoose}[2]{{{#1} \choose {#2}}}
\newcommand{\bchoose}[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}


\title{Homework \#3 - Math 4160}
\author{Assigned: Oct 29, 2019 Due: Nov 13, 2019}
\begin{document}
\maketitle


\LaTeX ~your homework solutions neatly and clearly.  Provide full
explanations and justify all of your answers.

\begin{enumerate}
\item Give a proof of the following identity by counting
two sets of partitions in two different ways.
$$\prod_{i\geq1} \frac{1}{1-x^i} = \frac{1}{1-x} + \sum_{r \geq 1} \frac{x^{r(r+1)}}{1-x^{r+1}}
\prod_{j=1}^r \frac{1}{(1-x^j)^2}~.$$
Hint: Look for the largest $r \times (r+1)$ rectangle in the partition.\\
\item Find the exponential
generating function for the number of words of length $n$ using letters $a,b,c,d$ such
that
\begin{enumerate}
\item all 5 letters occur without restriction
\item at least three $a$'s occur and at least four $b$'s occur and the total number of $a$'s and $c$'s is even.
\item the letters $a,b$ each appear an even number of times and $c,d$ together appear an even number of times
\item the letters $a,b$ together appear even number of times and $a,c,d$ together appear an even number of times
\end{enumerate}
Use your generating function to find the number of number of words of length 20
with the restrictions above.\\
\item Show that the exponential generating function for the sequence
$1,2,3,4,\ldots$ is $(1+x)e^x$.  What is the sequence corresponding to the
exponential generating function $\frac{1}{1+x}$?
Take the coefficient of $\frac{x^n}{n!}$ in the expression
$$\frac{1}{1+x}\cdot(1+x)e^x = e^x$$
(using the multiplication principle of exponential generating functions on the left hand side)
and state the combinatorial identity proved by taking this coefficient.
\item Let $B'(n,k)$ be the coefficient of $x^k$ in $(x+1)(x+3)\cdots(x+(2n-1))$.
Find a formula for the generating function
$$\sum_{n\geq0} \sum_{k\ge0} B'(n,k) q^k \frac{x^n}{n!}
= e^{-\frac{1}{2}(1+q) log(1-2x)}$$
\end{enumerate}


\end{document}
