\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Midterm Examination 1}
\centerline{February 24, 2017}
\bigskip
\noindent
{\it Directions}
\bigskip
Do any combination of parts of the following 5 problems in the 
blue exam book.  (The exam will be scored out of 100 points, but
you have the possibility of accumulating up to 110 points if you do all the 
parts.)
Explain your reasoning fully and do not place any work on the exam sheet.  
{\it Relax, and read each question carefully before starting to work!}
\bigskip
\noindent
I.  Consider a rectangular $7\times 7$ grid $L$ of integer
lattice points:
$$L = \{(i,j) : 0 \le i \le 6, 0 \le j \le 6\} \subset {\bf R}^2.$$
\item{A)} (10)  What is the smallest number $n$ such that
 we have $S \subset L$ with
$|S| = n$, then some three  points in $S$ must lie
on the same horizontal line $y = c$ for some $0 \le c \le 6$.   
\item{B)} (10) How many lattice paths are there from $(0,0)$ 
to $(6,6)$ made up of segments moving either up one unit or 
right one unit in the lattice? 
\bigskip
\noindent
II. Let
$X=\{a,b,c,d,e\}$ and $Y = \{1,2,3,4,5\}$.
There are $5^5 = 3125$ functions $f: X \to Y$ by the Multiplication
Principle (5 choices for $f(a)$, 5 choices for $f(b)$, etc.)
\item{A)} (10) How many of these functions are not 
surjective (not onto)?
\item{B)}  (10) How many of the functions in part A 
satisfy $|f(X)| = 2$?
\bigskip 
\noindent
III.  (15) $k$ out of $n$ cars in a lot are selected 
and each one of those gets an advertising flier for either a 
pizzeria or a car wash.  
By counting the ways the selection and distribution of the ads
can be done in two ways, give a combinatorial argument 
establishing:
$${n\choose 0}{n\choose k} + {n\choose 1}{n-1\choose k-1} + {n \choose 2}{n - 2 \choose k - 2} + \cdots 
+ {n\choose k}{n-k\choose 0} = 2^k {n\choose k}$$
\bigskip
\noindent
IV.    A professor makes up a review sheet for an exam 
including 15 practice questions, grouped
into parts I,II,III, each with 5 questions.  The actual exam 
will consist of exactly 8 of the 15 practice questions.
\bigskip
\item{A)} (10)  Taking the ordering of the problems on the actual
exam into account, how many different possible exams are there?
\item{B)} (10) How many possible exams are there
containing at least two questions from each part, if we 
ignore the order in which the problems are listed?
\bigskip
\noindent
V.  
\item{A)} (10)  How many permutations are there in $S_{16}$ with cycle type $[4,4,3,3,2]$?
\item{B)} (15) State and prove the recurrence relation for the Stirling numbers of the
first kind.  
\item{C)} (10) Using part B and the base cases for the $s(n,1), s(n,n)$
(or other methods as appropriate), compute the Stirling number of the first kind $s(6,2)$.
\bye
