\magnification=\magstep1
\centerline{MATH 357 -- Combinatorics}
\centerline{Review Sheet for Exam 1}
\centerline{February 17, 2017}
\bigskip
\noindent
{\it General Information and Groundrules}
\bigskip
The first midterm exam in Combinatorics this semester will be given (as announced
in the course syllabus) in class on Friday, February 24.  This will be a closed-book, 
individual exam.  You may use a basic calculator if you like, but even that should not be
necessary, since it will be OK (preferred, in fact!) to leave answers expressed in terms of 
the numbers $P(n,k), {n \choose k}, s(n,k)$, etc.  
\bigskip
\noindent
{\it What might be covered}
\bigskip
The exam will cover all of the material we have studied so far this semester, though 
the material from section 3.5 on ``dividers'' (a.k.a. ``stars and bars'') and 
3.6 on multinomial coefficients.  Note that this is slightly beyond the sections covered
on Problem Set 3.  Specifically this means:
\bigskip
\item{0)} Mathematical sets, unions, intersections, functions, etc.
\item{1)} The game {\it Set} and the structure of ``sets'' in the 81-card {\it Set} deck
\item{2)} The Multiplication and Addition Principles
\item{3)} The Pigeonhole Principle
\item{4)} Permutations, cycle decompositions, counting permutations by cycle type or
cycle index, the Stirling numbers of the first kind (Know the proof of the recurrence
relation $s(n+1,k) = n s(n,k) + s(n, k-1)$.)
\item{5)} Legendre's theorem on divisiblity of $n!$ by a primes $p$.  
\item{6)} Numbers of permutations $P(n,k)$ and binomial coefficients ${n \choose k}$ and
the counting problems they solve.
\item{7)} Poker hands and related counting problems
\item{8)} Binomial coefficient identities (Know algebraic and combinatorial proofs of the 
``Pascal's triangle'' 
identity ${n + 1\choose k} = {n \choose k} + {n \choose k - 1}$ and be ready to 
prove other identities by either approach.) 
\item{9)} The ``dividers'' method and applications
\item{10)}  Multinomial coefficients.
\bigskip
\noindent
{\it Some practice problems}
\bigskip
\noindent
{\it Disclaimer:}  These problems are only intended to give you an idea of the range
of topics and the possible ways questions might be phrased.  The actual exam questions
might not be exactly like these!  This list is also quite a bit longer than the actual exam
will be.  
\bigskip
\noindent
I.  
\item{A)} How many bit strings of length $9$ are there?
\item{B)} How many bit strings of length $9$ are there which start with a $0$ and which have at least one
other $0$?
\item{C)} How many bit strings of length 9 are there, such that every 1 is followed immediately by a
zero?  (Hint: Break this one into cases depending on how many $1$'s there are.)
\bigskip
\noindent
II.  
\item{A)} You are in a city with rectangular blocks. You want to walk from point $A$
five blocks north and three blocks east to point B, while walking north or east 
for every block.  In how many ways can you get from A to B?
\item{B)} Same question but supposing you start out by heading north from point A?
\bigskip
\noindent
III.  
\item{A)}  In the card game {\it Set}, suppose you deal $5$ cards and place them face up
on a table.  What is the {\it largest} number of 3-card ``sets'' that could be contained 
in that collection of cards?  Give an example and explain why some other set of $5$
cards could not contain any more ``sets'' than your $5$ cards.
\item{B}  Same question as A, but with 6 cards.  
\bigskip
\noindent
IV.  How many numbers must you pick to ensure that at least three of them have the same 
remainder when divided by 11?
\bigskip
\noindent
V.  How many functions are there from the set
$X=\{1,2,3\}$ to the set
$$Y = \{A, B, C, D, E, F, G\}?$$  How many of these are one-to-one (injective)?
\bigskip
\noindent
VI.  
\item{A)}  How many permutations are there in $S_{17}$ with cycle type $[3,3,3,3,2,2,1]$?
\item{B)}  State and prove the recurrence relation for the Stirling numbers of the
first kind.  
\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(5,3)$.
\bigskip
\noindent
VII.  What is the largest power of $6$ that divides $100!$?
\bigskip
\noindent
VIII. 
\item{A)} A store sells 8 kinds of balloons and they have at least 30 balloons of each kind
in stock. How many different
combinations of 30 balloons can be chosen?  
\item{B)} What if the store has only 10 red balloons, but at
least 30 of every other kind of balloon?
\bigskip
\noindent
IX.  A pool of available computer programmers has 13 members--six men and seven women.
\item{A)} In how many ways can you choose a team of five from the pool?
\item{B)} In how many ways can you choose a team of five, with two men and three women?
\item{C)} In how many ways can you choose a team of five, with at most three men?
\item{D)} Give a {\it combinatorial} proof that 
$${13 \choose 5} = \sum_{m=0}^5 {7\choose m}{6 \choose 5-m}$$
(Note:  Generalizing this gives:  If $1 \le \ell \le n - 1$, then 
$${n \choose k} = \sum_{m=0}^k {\ell \choose m}{n-\ell \choose k-m}$$
called the {\it Vandermonde convolution identity}.)
\item{E)}  Suppose that one of the men and one of the women are a divorced couple, and they 
refuse to work together. In how many ways can you choose a team of five, with two men and 
three women, respecting the wishes of the divorced couple?
\bigskip
\noindent
X.  
\item{A)}  What is the coefficient of $x^4 y^2$ in $(3x + 5y)^6$?
\item{B)}  What is the coefficient of $x^3 y^2 z$ in $(x + 2y + 3z)^6$?
\bye
