\magnification=\magstep1
\overfullrule=0pt
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Solutions for Midterm Examination 1}
\centerline{February 24, 2017}
\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.$$
\bigskip
%\item{A)} (5) Show that if we have a subset $S\subset L$ with
%$|S| = 8$, then there are two points in $S$ on the same 
%vertical line $x = c$ for some $0 \le c \le 6$.
%\item{} {\it Solution:}  Let the ``pigeon holes'' be the $7$ vertical lines and
%the pigeons be the $8$ points in $S$.  By the Pigeonhole Principle, some
%line will contain two of the points. 
\item{A)}  What is the smallest number $n$ such that if
 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{} {\it Solution:}  (This one should ``smell like'' the Pigeonhole Principle
if you're thinking the right way!  Think:  ``pigeons'' $=$ the points in $S$;
``pigeonholes'' $=$ the 7 horizontal lines containing points in $L$.  A pigeon goes
in a pigeonhole if the point lies on that line.)  The smallest such number is $15$.  By 
the Generalized Pigeonhole Principle, if we have $15$ points, then
some horizontal line must contain strictly more than $\lfloor {15 - 1\over 7} \rfloor = 2$
points.  (A subset of $14$ points equally distributed with 2 on each horizontal
line shows that $|S| = 14$ is not large enough.) 
\item{B)} 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? 
\item{} {\it Solution:}  By ``dividers'' or ``stars and bars,''
the number is ${6 + 6 \choose 6} = {12\choose 6} = 924$.  
\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)}  How many of these functions are not 
surjective (not onto)?
\item{} {\it Solution:}  Since $|X| = |Y|$, $f: X \to Y$ is not 
surjective if and only it is not injective.  There are $5! = 120$ injective functions, 
so $3125 - 5! = 3005$ of the functions are not injective and hence not surjective.
\item{B)}  How many of the functions in part A
satisfy $|f(X)| = 2$?
\item{} {\it Solution:}  The statement $|f(X)|$ means that the range or image of the
function consists of just two of the elements of $Y$.
There are ${5\choose 2} = 10$ choices for the image as a 
subset of $Y$.  Then for each image, there are $30$ different ways to construct mappings
with that image.  For instance, if the image is $\{1,2\}$, then 
\itemitem{$\bullet$}  There are ${5 \choose 1} = 5$ 
different functions with one element in $X$ mapping to $1$ and four elements in $X$ mapping to $2$, or
equivalently $|f^{-1}(\{1\})| = 1$ and $|f^{-1}(\{2\})| = 4$.  The element mapping to $1$ can
be any one of the 5 elements of $X$, and then the other four elements in $X$ map to $2$.
\itemitem{$\bullet$} Similarly, there  ${5\choose 2} = 10$ 
different functions with $|f^{-1}(\{1\})| = 2$ and $|f^{-1}(\{2\})| = 3$
\itemitem{$\bullet$}  ${5\choose 3} = 10$ 
different functions with $|f^{-1}(\{1\})| = 3$ and $|f^{-1}(\{2\})| = 2$
\itemitem{$\bullet$}  ${5 \choose 4} = 5$ 
different functions with $|f^{-1}(\{1\})| = 4$ and $|f^{-1}(\{2\})| = 1$.
(Note that we cannot have either $|f^{-1}(\{1\})| = 0$ or $|f^{-1}(\{1\})| = 5$
since then we would not be ``hitting'' one of the elements of $\{1,2\}$ in
the image.)
By the Multiplication and Addition Principles, then the total number is
$${5\choose 2}\cdot \left({5\choose 1} + {5\choose 2} + {5\choose 3} + {5\choose 4}\right) = 
10 \cdot (5 + 10 + 10 + 5) = 300.$$
\bigskip 
\noindent
III. $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
{\it Solution:}  If we choose the cars first, then there are ${n \choose k}$
different $k$-subsets of the $n$ cars on the lot.  For each of them, we
have $2$ choices for the flyer, either the pizzeria flier or the car wash flier.
Hence the total number of choices of cars and assignments of fliers is $2^k{n\choose k}$
by the Multiplication Principle.  On the other hand, if we assign the fliers as we select
the cars, then the number of selections where
\medskip
\item{$\bullet$} all chosen cars get car wash fliers is ${n\choose 0}{n \choose k}$
\item{$\bullet$} one chosen car gets a pizzeria flier and the other $k - 1$ chosen get
car wash fliers is ${n\choose 1} {n-1\choose k - 1}$
\item{$\bullet$} two chosen cars get a pizzeria flier and the other $k - 2$ chosen get
car wash fliers is ${n\choose 2} {n-2\choose k - 2}$.  
\item{$\bullet$}  Similarly, for each $\ell$, $0 \le \ell \le k$, the term 
$${n \choose \ell} {n - \ell \choose k - \ell}$$
represents the number of ways of picking $\ell$ cars to get pizzeria fliers, and then
picking $k - \ell$ cars from the remaining $n - \ell$ cars to get the 
car wash fliers.
\medskip
\noindent
By the Addition Principle we have 
$$\sum_{\ell = 0}^k {n \choose \ell} {n - \ell \choose k - \ell} = 2^k {n \choose k}.$$
\bigskip
\noindent
IV.    A professor makes up a review sheet for an exam 
including 15 practice questions, subdivided
into parts I,II,III, each with 5 questions.  The actual exam 
will consist of exactly $8$ different problems out of the 15 practice questions.
\bigskip
\item{A)}  Taking the ordering of the problems on the actual
exam into account, how many different possible exams are there?
\item{}  {\it Solution:} (Note: The subdivision of the review sheet into parts I,II,III
is irrelevant for this part.)
The total number of exams (ordered) is 
$$P(15,8) = 15\cdot 14\cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9 \cdot 8 = 259459200.$$
\item{B)}  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?
\item{}  {\it Solution:} We can start by considering the number of ways of writing $8 = a_1 + a_2 + a_3$
where $2 \le a_i \le 5$ is the number of problems taken from part $i = I,II,III$.  
If we write $a_i = 2 + b_i$, then $2 = b_1 + b_2 + b_3$ and $0 \le b_i \le 3$.  
There are clearly only $6$ ways to choose the $b_i$: 
$$(b_1,b_2,b_3) \in \{(2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)\}$$
which correspond to breakdowns of questions between the three parts of the review sheet like this:
$$\{(4,2,2),(2,4,2),(2,2,4),(3,3,2),(3,2,3),(2,3,3)\}$$
Then taking into account the actual questions chosen from each part, we have that
the total number of exams is 
$$3\cdot {5\choose 4}\cdot {5\choose 2}\cdot {5\choose 2} + 
3 \cdot {5\choose 3}\cdot {5\choose 3} \cdot {5\choose 2}.$$
\bigskip
\noindent
V.  
\item{A)}  How many permutations are there in $S_{16}$ with cycle type $[4,4,3,3,2]$?
\item{} {\it Solution:}  The number is
$${1\over 2!} \left( {P(16,4)\over 4}\cdot {P(12,4)\over 4} \right)\cdot 
{1\over 2!} \left( { P(8,3)\over 3 }\cdot { P(5,3)\over 3} \right) \cdot {P(2,2)\over 2}$$
\item{B)}  State and prove the recurrence relation for the Stirling numbers of the
first kind.  
\item{} {\it Solution:} The recurrence is 
$$s(n+1,k) = n\cdot s(n,k) + s(n,k-1).$$
The proof is as follows:
$s(n+1,k)$ counts the number of permutations in $S_{n+1}$ with cycle index $k$.  This 
collection of permutations is the disjoint union of two subsets:  The permutations with cycle
index $k$ that satisfy $\sigma(n+1) = n+1$ and the ones with $\sigma(n+1) \ne n+1$.  
In the first case, $(n+1)$ will be a cycle of length 1 in the disjoint cycle decomposition. The
remainder then consists of $k - 1$ cycles not containing $n+1$.  Hence these permutations
are in 1-1 correspondence with the permutations in $S_n$ with cycle index $k-1$, and 
that number of such is $s(n,k-1)$.   The permutations of the second type are all formed by 
inserting $n+1$ in one location in a permutation in $S_n$ with cycle index $k$.  There are 
exactly $n$ possible ways to insert the $n+1$, so there are $n\cdot s(n,k)$ of these by the 
Multiplication Principle.  The recurrence relation then follows by the Addition Principle.
\item{C)} 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)$.
\item{} {\it Solution:} We have, since $s(n,1) = (n - 1)!$ and $s(3,2) = 3$:
$$\eqalign{
s(6,2) &= 5\cdot s(5,2) + s(5,1)\cr
&= 5\cdot (4\cdot s(4,2) + s(4,1)) + 24\cr
&= 20 \cdot(3 \cdot s(3,2) + s(3,1)) + 30 + 24\cr
&= 60\cdot 3 + 40 + 30 + 24\cr
&= 274.\cr}$$
\bye
