\documentclass{article}
\usepackage{amssymb,graphics}
%\usepackage{logic}
%\graphicspath{{teaching/}{Discstr2007/}}

\begin{document}
\begin{center}
{\Large
MATH 2113/CSCI 2113, Discrete Structures II

Winter 2008

Toby Kenney

\large Homework Sheet 2

Due in: Wednesday 23rd January, 1:30 PM}
\end{center}



\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] Show that ${2n\choose n}=\sum_{k=0}^{n}{n\choose k}^2$.

\item[2] (a) Show that ${n\choose a}{n-a\choose b}={n\choose a+b}{a+b\choose a}$.

(b) What is $\sum_{k=1}^{n} {n\choose k}k^2$? [Hint: $k^2=2{k\choose2}+{k\choose1}$.]

\item[3] How many subsets of $\{1,2,\ldots,17\}$ contain at most two multiples of 3?

\item[4] (a) How many solutions are there to $x_1+x_2+x_3+x_4=18$ where $x_1$, $x_2$, 
$x_3$ and $x_4$ are natural numbers ($\{0,1,2,3,\ldots\}$)?

(b) How many solutions are there to $x_1+2x_2+3x_3=10$ for $x_1$, $x_2$ and $x_3$ 
natural numbers?

\item[5] (a) In a class with 13 students, there are 5 mathematicians and 8 computer 
scientists. How many subsets of the students in the class contain the same number 
of mathematicians and computer scientists? [Hint: The easy way to answer this question 
involves considering a different set from the set to be chosen (but related to it).]

\subsection*{Bonus question}

(b) How many contain at least as many mathematicians as computer scientists? [Hint: 
This question will be a lot easier if you can find a simple explanation for why the 
solution to part (a) is what it is.]

%\item[6] 

\end{list}

\end{document}