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

\textwidth = 6.5 in
%\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
%\topmargin = 0.0 in
%\headheight = 0.0 in
%\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newcommand{\binomial}[2]{{#1\choose #2}}


\title{Midterm - Take Home - Math 4160}
\author{Assigned: October 31, 2019 \hskip .4in Due: November 4, 2019 at 11:59pm}
\begin{document}
\maketitle

Write your solutions neatly and clearly.  Provide full
explanations and justify all of your answers.  DO NOT DISCUSS THESE
PROBLEMS WITH OTHERS.  You must do this
work alone and I will ask you to sign the statement below which
states that you have not discussed these problems with others or
received help on these problems (when you hand the paper to me).
Note that in certain circumstances I am giving you the answer, and it is your job
{\it explain} it.  This means that you should write grammatically correct
sentences, tell me why two things are equal, and make your calculations clear and easy to follow.

\begin{minipage}{5in} If you have any questions about the problems you may
e-mail me at {\tt zabrocki@mathstat.yorku.ca}.
\end{minipage}
\begin{tabular}{c|c}
1 (8 pts)&{\hskip .2in.}\cr
2 (10 pts)&\cr
3 (7 pts)&\cr
\hline
total(25 pts)&\cr
\end{tabular}

\begin{enumerate}
\item Use generating functions to determine the
number of ways of putting 100 red, blue and green balls into two bins
such that there are an even number of red and blue balls in the first bin
and there are at most 30 green balls.
\item 
Define for $n\geq1$, $(x)^{\{n\}} = (x+1)(x+3)\cdots(x+(2n-1))$.  Let $B'(n,k)$
be the coefficient of $x^k$ in $(x)^{\{n\}}$, that is,
$$(x)^{\{n\}} = \sum_{k=0}^n B'(n,k) x^k~.$$
Recall that a cycle of a permutation $\pi$ is an ordered list of numbers $(a_1, a_2, \ldots, a_r)$
such that $\pi(a_i) = a_{i+1}$ for $1 \leq i < r$ and $\pi(a_r) = a_1$ (with
$a_1$ the the smallest entry in the cycle so that the representation of the cycle is unique).
In the homework I asked you to show that the coefficient
$x^k$ in $x(x+1)(x+2)\cdots(x+(n-1))$ was equal to the
number of permutations $\pi$ of $\{1,2,\ldots,n\}$ with exactly $k$ cycles.
I'm going to ask you to prove the analogous interpretation for $B'(n,k)$.
\begin{enumerate}
\item (1 pt) Make a table of $B'(n,k)$ for $1 \leq n \leq 3$ and $0 \leq k \leq n$.
\item (1 pt) Prove that $\sum_{k=0}^n B'(n,k) = 2^n n!=$ the number of pairs
$(S,\pi)$ where $S$ is a subset of $\{1,2,\ldots, n\}$ and $\pi$ is a permutation
of $\{1,2,\ldots, n\}$.\footnote{note that I'm asking you to show two equalities in this problem}
\item (1 pt) Give an explicit formula for $B'(n,0)$ and $B'(n,n)$ for all $n\geq1$.
\item (2 pts) Give a recurrence for $B'(n,k)$ for $n \geq 2$ and $0<k<n$
\item (5 pts) We will say that
a list of numbers $(a_1, a_2, \ldots, a_r)$ is an even cycle of $(S, \pi)$ if
$(a_1, a_2, \ldots, a_r)$ is a cycle of $\pi$ and 
the number of elements in $\{a_1, a_2, \ldots, a_r\} \cap S$ is even.
Show that $B'(n,k)$ is equal to the number of pairs $(S,\pi)$ with
exactly $k$ even cycles.\footnote{For example $(\{1\},(1)(2)(3))$, $(\{2\},(1)(2)(3))$, $(\{3\},(1)(2)(3))$,
$(\emptyset, (12)(3))$, $(\emptyset, (1)(23))$, $(\emptyset, (2)(13))$, $(\{1,2\},(12)(3))$
$(\{2,3\},(1)(23))$, $(\{1,3\},(2)(13))$ are $9$ pairs that have two even cycles}
\end{enumerate}
\item Prove the following identity using a combinatorial argument
$$\binom{m}{2}^2 = 6 \binom{m}{4} + 6 \binom{m}{3} + \binom{m}{2}$$
\end{enumerate}

WHEN YOU SUBMIT THIS EXAM please sign the following statement and fill out the information below.

I attest that I have completed this exam myself without help
from anyone else (besides the professor)
and I have not discussed the problems on this
exam with other students in the class.
\vskip .2in

------------------------------------------------------------------

This exam is open book, open notes, and other sources, but I expect you
to not ask other people how to complete the assignment.  You should list
books and websites that you consulted below.  Your solutions should refer to
precise pages in the notes and reference that I can consult.
If you cannot sign the above statement truthfully, I would prefer if
you just explain to me the situation rather than perjure yourself.
Please detail below
the sources you consulted, the  that you have obtained 
on this exam or who you have discussed these
problems with:
\newpage
Some people have asked for clarifications on this exam.  I will answer them here
in case they are useful for everyone.

\vskip .2in
{\bf For ``an even number of red and blue balls,'' do you mean an even number of
red and blue balls together, or an even number of red and an even number of blue?}
\vskip .1in

I mean an even number of red and blue balls together.

\vskip .2in
{\bf Is it 100 balls total, of which some are red/blue/green or is it 100 red, 100 blue, 100 green? }

\vskip .1in
100 balls in total.

\vskip .2in
{\bf Should it be: ``there are at most 30 green balls in the second bin?'' }

\vskip .1in
It�s at most 30 balls in total.
\end{document}
