\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amssymb,graphicx,enumitem,color,txfonts,picins}
\def\full{n}
\def\fullcut{\if\full y \newpage\null \fi}

%\topmargin -1.3in
%\textheight 9.9in

\newcommand{\bbQ}{{\mathbb{Q}}}
\newcommand{\bbR}{{\mathbb R}}

\def\red{\color{red}\footnotesize}

\begin{document}

%\noindent Name: $\underline{\hspace{2.5in}}$ \hfill Student ID: $\underline{\hspace{1.5in}}$

\vfil

\begin{center}
  {\Large UNIVERSITY OF TORONTO}\\
  \vskip 2mm
  {\large Faculty of Arts and Sciences}\\
  \vskip 2mm
  {\Large DECEMBER EXAMINATIONS 2015}\\
  \vskip 2mm
  {\Large Math 344H1 Combinatorics --- Final Exam}

  \vskip 2mm

  Dror Bar-Natan\par
  December 17, 2015\par
\end{center}

\vfil

{\bf Solve 5 of the following 7 questions.} If you solve more than 5 questions indicate very clearly below which are the ones that you want marked, or else a random one will be left out. The questions are of equal value of 20 points each.

\vfil

\noindent{\bf Duration. } You have 3 hours to write this exam.

\vskip 2mm

\noindent{\bf Allowed Material. } None.

\vfil

\centerline{{\bf \large Good Luck!}}

\vfil

\begin{center}
  {\red I should have not put this table here.}
  \newline
  Circle the 5 questions that you want marked --- otherwise some arbitrary 5 will be marked:\par\bigskip
  \renewcommand{\arraystretch}{3}
  %\newcommand{\mybox}{\vbox to 0.1in{\vfill\hbox to 1.5in{\hfil}}}
  \newcommand{\mybox}{\hbox to 1.0in{\hfil}}
  \begin{tabular}{|c|r|c|r|}
  \hline
  \hspace{5mm}1\hspace{5mm}\quad & \mybox /20 &
  \hspace{5mm}5\hspace{5mm} & \mybox /20 \\ \hline
  2 & \mybox /20 &
  6 & \mybox /20 \\ \hline
  3 & \mybox /20 &
  7 & \mybox /20 \\ \hline
  4 & \mybox /20 &
   &  \\ \hline\hline
  Total & \multicolumn{3}{|r|}{\mybox /100} \\ \hline
  \end{tabular}
\end{center}

\newpage

\noindent{\bf Solve 5 of the following 7 problems. } Each problem is worth
20 points. You have three hours.

\vfill\par\noindent{\small {\bf Tip. } Don't start working! Read the whole exam first. You may wish to start with the questions that are easiest for you.}

\vfill\par\noindent{\small {\bf Tip. } Neatness, cleanliness and organization count, here and everywhere else!}

\vfill

\parpic[r]{\includegraphics[scale=0.75]{Tesseract.pdf}}\picskip{1}
\noindent\parbox{4.5in}{{\bf Problem 1.} Let $G$ be an arbitrary graph, and for a natural number $n$ let $C_n$ denote the graph of vertices and edges of the $n$ dimensional cube (the case $n=4$ is depicted on the right).
\begin{enumerate}
\item (6 points) Define ``an Euler circuit'' and ``a Hamilton circuit'' in $G$.
\item (7 points) Prove that {\red for $n>1$,} $C_n$ always has a Hamilton circuit.
\item (7 points) For which values of $n$ does $C_n$ have an Euler circuit?
\end{enumerate}}

\vfill\par\noindent{\small {\bf Tip. } Quote any theorem you use!}

\vfill

\noindent{\bf Problem 2.} {\red (Should have started ``define a spanning tree''.)} Prove: If $G$ is a connected graph and $T$ and $T'$ are spanning trees in $G$, then there exists a sequence $T_0$, $T_1$, $T_2$, \ldots, $T_n$ of spanning trees in $G$ such that $T_0=T$, $T_n=T'$, and for every $1\leq k\leq n$, the tree $T_k$ is obtained from $T_{k-1}$ by adding one edge and removing one edge.

\noindent{\red Evaluation. $3/20$. Reasonable writeup of something else.
\hfill $3/20$. Understood what's a ``spanning tree''.
\newline $5/20$. Construction that does not make the  intermediate steps be spanning trees.
\newline $-6$. No proof that intermediate steps are spanning trees.
\hfill $-6$. Moves are not ``directed towards goal''.
\newline $-5$. Correct, but very loose writeup.
\hfill $-3$. Described a process but not why it terminates.
}

\vfill

% Section 5.3 P28.
\noindent{\bf Problem 3.} How many ways are there to place 9 rings on the four fingers of your right hand (excluding the thumb) if
\begin{enumerate}
\item (6 points) the rings are identical? {\red Ans. $\binom{9+3}{3}$.}
\item (6 points) the rings are different and the order of the rings on a finger does not matter? {\red A. $4^9$.}
\newline{\red Evaluation. $-4$ for $9^4$.}
\item (8 points) the rings are different and the order of rings on a finger does matter? {\red  $9!\binom{9+3}{3}=\frac{12!}{3!}$.}
\end{enumerate}

\vfill\par\noindent{\small {\bf Tip. } Answers in the form ``$\binom{7}{3}\cdot9\cdot 7\cdot 5$'' are acceptable (if correct) --- there is no need to find the numerical value of such an expression.}

\vfill

\noindent{\bf Problem 4.} Let $C_n$ be the number of ``soccer histories'' that start at $(0,0)$, end in $(n,n)$, and in which the first team is never behind. Show by whatever means you wish that $C_n=\frac{1}{n+1}\binom{2n}{n}$.

\noindent{\red Evaluation. $4/20$. Built the ``Catalan triangle'' and nothing more.
\hfill $-12$. No justification for bad-path formula.
\newline $-8$. Referred correctly to ``Andr\'e's reflection'' without explaining what it is.
\newline $-6$. So specification of what part of the path to reflect; not clear why comes to $(n-1,n+1)$.
\newline $-4$. ``Reflect about a diagonal'' without specifying which one.
\newline $-4$. Correct reflection but no statement of what it proves.
}

\vfill\par\noindent{\small {\bf Tip. } In math-talk, ``show'' means ``prove''.}

\newpage

\noindent{\bf Problem 5.}
\begin{enumerate}
\item (5 points) Show that if $f$ is the generating function of a sequence $a_k$, namely $f(x)=\sum_{k=0}^\infty a_kx^k$, then $xf'$ is the generating function of the sequence $ka_k$.
\item (5 points) For some fixed natural number $n$, find the generating function of the sequence $k\binom{n}{k}$.
\par\noindent{\red Answer. $nx(1+x)^{n-1}$.
\newline Evaluation. $-2$ incorrect/no differentiation.
}
\item (5 points) Likewise find the generating function of the sequence $k^2\binom{n}{k}$.
\par\noindent{\red Answer. $nx\left((1+x)^{n-1}+x(n-1)(1+x)^{n-2}\right) = nx(1+nx)(1+x)^{n-2}$
\newline Evaluation. $-2$ incorrect/no differentiation.
}
\item (5 points) Compute the sum $\sum_{k=0}^n k^2\binom{n}{k}$. {\red Answer. $n(n+1)2^{n-2}$}
\end{enumerate}

\vfill

\parpic[r]{\includegraphics[scale=0.7]{Pascal.pdf}}\picskip{1}
\noindent\parbox{4.87in}{{\bf Problem 6.} Consider Pascal's triangle PT, as {\red partially} depicted on the right.
\begin{enumerate}
\item (10 points) Show that the sum of every vertical column of numbers in PT {\red (should have: ``\ldots which starts at the 1 at the top of a column'')} is the number below it and to the right. (For example, for the column surrounded by a rectangle on the right, the sum is $1+5+15+35=56$, as underlined below it and to the right).
\end{enumerate}
}

\par\noindent{\red Evaluation.
$3/10$ Checked all possible sub-examples for the displayed PT; $5/20$ if for both parts.
\newline $-2$. Column did not start at top, then correct solution for as if it did.
\newline $-5$. Derived correct algebraic formula, but did not prove it.
}
\begin{enumerate}\setcounter{enumi}{1}
\item (10 points) Show that the sum of every ``upwards and to the right'' diagonal chain of numbers in PT is a Fibonacci number. (For example, for the diagonal surrounded by an ellipse on the right, the sum is $1+5+6+1=13$, which is $F_6$).
\end{enumerate}
\par\noindent{\red Evaluation.
$4/10$. Meant the right thing, completely deficient writeup.
}

\vfill

\noindent{\bf Problem 7.}
\begin{enumerate}
\item (15 points) Let $F_n$ be the Fibonacci sequence, defined by $F_0=F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq 2$ (so $F_n=(1,1,2,3,5,8,13,\ldots)$). Using whatever means you wish, find an explicit formula for the generating function of this sequence, $f(x)\coloneqq \sum_{n=0}^\infty F_nx^n$.
\end{enumerate}
\par\noindent{\red Evaluation.
$5/15$. Found formula for $F_n$, but not for $f(x)$.
\hfill $-3$ wrong numerator, right denominator.
}
\begin{enumerate}\setcounter{enumi}{1}
\item (5 points) Let $G_n$ be the sequence defined by $G_0=G_1=1$, $G_2=2$, and $G_n=G_{n-1}+G_{n-2}+G_{n-3}$ for $n\geq 3$ (so $G_n=(1,1,2,4,7,13,24,\ldots)$). Using whatever means you wish, find an explicit formula for the generating function of this sequence, $g(x)\coloneqq \sum_{n=0}^\infty G_nx^n$.
\end{enumerate}

\vfill\par\noindent{\small {\bf Tip. } In math exams, ``find'' means ``find and explain how you found''.}

\par\noindent{\red Evaluation.
$10/20$. Wrote $(x+x^2)^k$ and $(x+x^2+x^3)^k$, no summation.
}

\vfill \label{goodluck}\centerline{\bf \large Good Luck!}\vfill

\end{document}