\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}}

\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}
  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 $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.} 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.

\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?
\item (6 points) the rings are different and the order of the rings on a finger does not matter?
\item (8 points) the rings are different and the order of rings on a finger does matter? 
\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}$.

\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}$.
\item (5 points) Likewise find the generating function of the sequence $k^2\binom{n}{k}$.
\item (5 points) Compute the sum $\sum_{k=0}^n k^2\binom{n}{k}$.
\end{enumerate}

\vfill

\parpic[r]{\includegraphics[scale=0.8]{Pascal.pdf}}
\noindent\parbox{4.5in}{{\bf Problem 6.} Consider Pascal's triangle PT, as depicted on the right.
\begin{enumerate}
\item (10 points) Show that the sum of every vertical column of numbers in PT 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).
\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}
}

\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$.
\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''.}

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

\end{document}