\documentclass[11pt, reqno]{amsart}
\usepackage[margin=1in]{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath}
\usepackage{pdfsync}%leaves makers for tex searching
\usepackage{enumerate}

\numberwithin{equation}{section}

%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}[section]
	\newtheorem{lemma}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
	\newtheorem*{defn}{Definition}
	\newtheorem{remark}[thm]{Remark}
	\newtheorem{example}{Example}
	\newtheorem{try}{In-class Exercise}
	\newtheorem*{warmup}{Warmup}


%%% Environments %%%--------------------------------------------------------- 
\newenvironment{ans}{\medskip \paragraph*{\emph{Answer}.}}{\hfill \break  $~\!\!$ \dotfill \medskip }
\newenvironment{summary}{\medskip \paragraph*{\emph{Summary}.}}{\hfill \break  $~\!\!$ \dotfill \medskip }


%%% Pictures %%%--------------------------------------------------------- 
%\usepackage{etex} %fixes the fight that pictex has with every other drawing package
%\usepackage{pictexwd}
\usepackage{tikz}
%\usepackage{graphicx}
%\usepackage{epstopdf}
%\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[pdftex,bookmarks]{hyperref}


\usetikzlibrary{scopes}
\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=2pt]
\tikzstyle{bV}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]
\tikzstyle{C}=[draw, thick, fill =white, circle, inner sep=0pt, minimum size=6pt]
\tikzstyle{blV}=[draw, white, fill =black, circle, inner sep=1pt, minimum size=4pt]
\tikzstyle{gV}=[draw, fill =black!40!white, circle, inner sep=1pt, minimum size=4pt]
\tikzstyle{wV}=[draw, fill =white, circle, inner sep=1pt, minimum size=4pt]



\newcommand{\TikZ}[1]{
\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}
}

\newcounter{r}
\newcommand\Part[1]{
        \setcounter{r}{1}
	 \foreach \x in {#1}{
 	{\ifnum\value{r}=1
		\draw (0,\value{r}-1)--(\x,\value{r}-1); 
		\fi}
	\draw (0,\value{r}) to (\x,\value{r});
   	\foreach \y in {0, ..., \x} {\draw (\y,\value{r})--(\y,\value{r}-1);}
	\addtocounter{r}{1}
 }}
 \def\PartUNIT{.175}
%Self-contained tikz images for \Part above. 
\newcommand{\PART}[1]{
\begin{matrix}
\begin{tikzpicture}[xscale=\PartUNIT, yscale=-\PartUNIT] 
	\Part{#1}
\end{tikzpicture}
\end{matrix}
}



%%% Color  %%%--------------------------------------------------------------
\usepackage{color}

%%% Alphabets %%%--------------------------------------------------------
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  


\def\ii{\mathbf{i}}\def\jj{\mathbf{j}}\def\kk{\mathbf{k}}\def\uu{\mathbf{u}}\def\vv{\mathbf{v}}\def\ww{\mathbf{w}}




\usepackage{fancyhdr}
 
\pagestyle{empty}



\newcommand{\SOL}[1]
{
$\quad$\hfill
\begin{tikzpicture}
\node[above right] at (0,0) {\bf \small  Answer:};
\draw[thick] (0,0) rectangle (#1,-1.5);
\end{tikzpicture}
}

\begin{document}
\thispagestyle{empty}



\centerline {\bf \huge Exam \#2 Extra Credit }
\medskip

\centerline{\bf \Large {Math 365} -- Daugherty}

%\centerline{(In class part)}
\smallskip

\centerline{Due in class May 1, 2019}

\vskip .4in

\noindent{\bf Name: \underline{ \hspace{4.5in}}}

\vfill

\noindent
{\bf Instructions:}

\begin{enumerate}[$\bullet$]
\item Your answers \textbf{must be typed}, with the exception that you may fill in pictures or equations by hand as necessary. You are highly encouraged to use \LaTeX, but you may use other word-processing programs like Word if you prefer. Either way, please follow these three formatting requirements:
\begin{enumerate}[i.]
\item include this page as a cover page of your document;
\item include the question prompts before your answers;\\
{\footnotesize(Tip: even if you're not using \LaTeX, you can download the .tex file to copy and paste the wording.)} 
\item start each of the four problems on a new page. {\footnotesize(For example, you can use your own discretion about whether or not part (b) of problem 1 needs to be started on a new page, but problem 2 should definitely start at the top of a new page; generally avoid splitting a proof across two pages if possible)}.
\end{enumerate} 

\medskip

\item Your answers must be written in \textbf{complete sentences}. The point is to explain your understanding, not to complete computations alone. Revisit the handout ``Guidelines for Good Mathematical Writing'' if necessary. Your grade will depend on the \emph{quality} of your exposition, not just its validity. 

\medskip

\item Your \textbf{audience} for this assignment is a math major who has not taken 365. In other words, you may assume general mathematical fluency of your reader, but not that they already know what you're talking about. Think about explaining  what 365 is about to a classmate in a different course.  

\medskip


\item You may talk to your professor or classmates when working some of these out, but \textbf{your answers must be your own}. In particular, it is strongly suggested that you do not collaborate on your examples. If you take an example out of the book or any other resource, \textbf{cite your source}.

\medskip


\item Your \textbf{total grade} on Exam 2 will be an average of your score on this assignment and your original Exam 2 grade, with the following exceptions---your total grade will not exceed 80\%, nor will it decrease as a result of a low grade on this assignment.
\end{enumerate}


\vfill

\centerline{\Large\def\arraystretch{1.5}
\begin{tabular}{|c|c|@{\quad}c@{\quad}|}\hline
Problem \# & Out of & Score\\\hline\hline
\bf 1 & 20  & \\\hline
\bf 2 & 50 & \\\hline
\bf 3 & 10 & \\\hline
\bf 4 & 20 &  \\\hline\hline
\bf total& 100 &\\\hline
\end{tabular}
}


\pagebreak



\begin{enumerate}[\bf 1.]
\item \emph{Counting.}
\begin{enumerate}
\item Give the combinatorial meaning of each of the following functions, and give an example of a word problem where it would arise. 
\begin{enumerate}
\item $\binom{n}{k}$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}

\item $S(n,k)$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\item $P(n,k)$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\item $p_k(n)$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\end{enumerate}

\bigskip

\item Summarize the content of Sections 6.1, 3, and 5. In your summary, be sure to explain the big picture, give the major kinds of problems in general terms, and include illustrative examples. You may refer to part (a).


%\begin{summary}
%YOUR ANSWER HERE
%\end{summary}

\bigskip

\end{enumerate}
\item \emph{Combinatorial proofs.} (For example, see Section 6.4, proofs of Theorems 2, 3, and 4.)

\bigskip

\begin{enumerate}
\item Explain the general format of a combinatorial proof.

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}

\bigskip


\item Adapt the  proof of Theorem 3 in Section 6.4 to prove the identity in Corollary 4, 
$$\binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2.$$
{[Namely, they prove an identity for general $m, n$, and $r$ in Theorem 3 and then say if you set $m = n = r$, you get Corollary 4 for free. I want you to rewrite the proof of Theorem 3, adapting it to just prove Corollary 4 instead.]}

%\begin{proof}
%YOUR PROOF HERE
%\end{proof}

\bigskip


\item Give a combinatorial proof of the following identity:
$$n 2^{n-1} = \sum_{k=1}^n \binom{n}{k}k.$$
{[Hint: Think about picking a club and its president.]}

%\begin{proof}
%YOUR PROOF HERE
%\end{proof}

\bigskip


\item A \emph{graph coloring} (with $k$ colors) is a way to color the vertices of a graph so that adjacent vertices get colored differently. For example, if I have three colors, 
$$\TikZ{\node[blV, label=above:{\tiny black}] at (0,0) {\tiny\bf1};}, \quad \TikZ{\node[gV, label=above:{\tiny gray}] at (0,0) {\tiny\bf2};},  \quad \text{ and } \quad \TikZ{\node[wV, label=above:{\tiny white}] at (0,0) {\tiny\bf3};},$$
then 
$$\begin{matrix}
\text{this is a valid coloring:}\\
\TikZ{
\node[blV, label=above:{\tiny$a$}] (a) at (0,0) {\tiny\bf1};
\node[wV, label=above:{\tiny$b$}] (b) at (1,0) {\tiny\bf3};
\node[wV, label=left:{\tiny$c$}] (c) at (0,-1) {\tiny\bf3};
\node[gV, label=right:{\tiny$d$}] (d) at (1,-1) {\tiny\bf2};
\node[blV, label=below:{\tiny$e$}] (e) at (.5,-1.5) {\tiny\bf1};
\draw (a) to (b) to (d) to (c) to (a) to (d) to (e) to (c);}
\end{matrix}
\qquad\qquad\qquad 
\begin{matrix}
\text{but this is \emph{not} a valid coloring:}\\
\TikZ{
\node[blV, label=above:{\tiny$a$}] (a) at (0,0) {{\tiny\bf1}};
\node[wV, label=above:{\tiny$b$}] (b) at (1,0) {{\tiny\bf3}};
\node[blV, label=left:{\tiny$c$}] (c) at (0,-1) {{\tiny\bf1}};
\node[gV, label=right:{\tiny$d$}] (d) at (1,-1) {{\tiny\bf2}};
\node[wV, label=below:{\tiny$e$}] (e) at (.5,-1.5) {{\tiny\bf3}};
\draw (a) to (b) to (d) to (c) to (a) to (d) to (e) to (c);}
\end{matrix}
$$
since $a$ and $c$ are adjacent and both colored black. Let $c_n$ be the number of ways to color the $n$-vertex path 
$$P_n = \TikZ{\foreach \x in {1,2,3}{\node[bV, label=above:{\small$v_\x$}] (\x) at (\x,0) {};}
		\node[bV, label=above:{\small$v_{n}$}] (n) at (5,0) {};
		\draw (1) to (2) to (3) to (3.5,0) (n) to (4.5,0);
		\node at (4,0) {$\cdots$};}$$
with $k$ colors. Give a combinatorial proof of the recursive identity
$$c_n = (k-1) c_{n-1}.$$

%\begin{proof}
%YOUR PROOF HERE
%\end{proof}

\bigskip


\item Let $\sigma_m(n)$ be the number of surjective functions from $\{1, \dots, m\}$ to $\{1, \dots, n\}$. Assuming $m \ge n > 1$, give a combinatorial proof of the recursive identity 
$$\sigma_m(n) = n^m - \sum_{k=1}^{n-1} \binom{n}{k} \sigma_m(k).$$

%\begin{proof}
%YOUR PROOF HERE
%\end{proof}

\bigskip


\item Explain the big-picture idea of what Section 8.1 is about. 

%\begin{summary}
%YOUR ANSWER HERE
%\end{summary}

\end{enumerate}


\bigskip


\item Summarize the content of Section 8.2, including both a big-picture explanation and a  brief guide to solving recurrences of various types. Include examples.

%\begin{summary}
%YOUR ANSWER HERE
%\end{summary}

\bigskip


\item \emph{Generating functions.} 
\begin{enumerate}
\item  Summarize the content of Section 8.4,  including a big-picture explanation (what's a generating function and why do we care) and examples of the various ways we encounter generating functions. 

%\begin{summary}
%YOUR ANSWER HERE
%\end{summary}

\bigskip

\item Explain why each of the following generating functions model the corresponding counting problem (i.e.\ justify the answers to the last problem on the exam). 




\begin{enumerate}
\item The number of integer partitions of $n$ has the generating function 
$$\prod_{k=1}^\infty \frac{1}{1-x^k}.$$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}



\item The number of integer partitions of $n$ with at most one part of each length has the generating function 
$$\prod_{k=1}^\infty (1 + x^k).$$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\item The number of ways to make change for \$$n$ with \$1's, \$5's, and \$10's has the generating function 
$$\left(\frac{1}{1-x}\right)\left(\frac{1}{1-x^5}\right)\left(\frac{1}{1-x^{10}}\right).$$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\item The number of non-negative integer solutions to the equation $x_1 + x_2 + x_3 = n$, where $x_1, x_2, x_3 \le 5$, has the generating function 
$$\left(1+x+x^2 + x^3 + x^4 + x^5\right)^3.$$

%\begin{ans}
%YOUR ANSWER HERE
%\end{ans}


\end{enumerate}



\end{enumerate}



\end{enumerate}
\end{document}

