\magnification=\magstep1
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Review Sheet Practice Problems for Exam 1}
\centerline{February 17, 2017}
\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{} {\it Solution:}  There are $2^9$ such strings by the Multiplication Principle (2 choices
for each of the 9 bits).
\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{} {\it Solution:}  There are $2^8 - 1$ such strings.  After the leading $0$, we can 
have any of the $2^8$ strings of length $8$, {\it except} for $11111111$.
\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.)
\item{} {\it Solution:}  Since there are 9 bits in all, the largest number of 1's that you can
have is 4.  
\itemitem{$\bullet$} If there are no ones, you have the all-$0$ string, so $1$ of those
\itemitem{$\bullet$} If there is exactly one one, then it can only come in positions 1 through 8
in the string because there must be (at least one) zero after it.  There are $8$ of these.
\itemitem{$\bullet$} If there are exactly two ones, then they can come in positions 
$$(1,3), (1,4), \ldots, (1,8)$$ 
or 
$$(2, 4), (2, 5), \ldots (2, 8)$$ 
or 
$$(3, 5), (3, 6), (3, 7), (3, 8)$$ 
or 
$$(4,6), (4,7), (4,8)$$
 or $(5,7), (5,8)$, or $(6,8)$, so $21$ of these.  
\itemitem{$\bullet$} If there are exactly three ones, then can come in positions 
$$(1,3,5), (1,3,6), (1,3,7), (1,3,8)$$ or 
$$(1,4,6), (1,4,7), (1,4,8),$$ or 
$$(1,5,7), (1,5,8)$$ 
or $(1,6,8)$, or 
$$(2,4,6), (2,4,7), (2,4,8)$$ or 
$(2,5,7), (2,5,8)$, or $(2,6,8)$, or $(3,5,7), (3,5,8)$, or 
$(3,6,8)$, or $(4,6,8)$, so $20$ of these.
\itemitem{$\bullet$} Finally, if there are exactly four ones, they can come in positions
$$(1,3,5,7), (1,3,5,8), (1,3,6,8), (1,4,6,8),$$ or $(2,4,6,8)$, so $5$ of these.
The total is $1 + 8 + 21 + 20 + 5 = 55$.  (Note:  There are other ways to do these counts
as well that are less ``brute force'' in nature!)
\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{} {\it Solution:}  By the ``dividers'' or ``stars and bars'' method, the 
number is ${8\choose 5} = {8 \choose 3} = {8\cdot 7\cdot 6 \over 3\cdot 2\cdot 1} = 56$.  
\item{B)} Same question but supposing you start out by heading north from point A?
if you must start out heading north from point A, there are 7 remaining blocks to 
travel east or north, and you must do 4 more north blocks and 3 east blocks.  
The number if ${7 \choose 4} = {7\choose 3} = {7\cdot 6\cdot 5\over 3\cdot 2\cdot 1} = 35$.
\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{} {\it Solution:}  In that collection of $5$ cards, there are ${5\choose 3} = 10$ triples.
However, recall that any two cards in a ``set'' determine the third card uniquely.  Hence
if the five cards are $a,b,c,d,e$ and we stipulate that $\{a,b,c\}$ {\it is a ``set,''} then the 
six triples $\{a,b,d\}, \{a,b,e\}, \{a,c,d\},
\{a,c,e\},\{b,c,d\},\{b,c,e\}$ {\it cannot be ``sets''} because they each share
two cards with the triple that is a ``set.''  However, one of the cards in the 
first set, say $a$, can be in a second ``set'' $\{a,d,e\}$ with the two remaining cards, $d,e$.
If we now rule out other sets containing exactly two of these cards, we must conclude
$\{a,d,b\},\{a,d,c\},\{a,e,b\},\{a,e,c\},\{d,e,b\},\{d,e,c\}$ are not ``sets'' either.
The first four of these were already ruled out from before with the ``set'' $\{a,b,c\}$, but the last two
are not.   Of the 10 possible triples, we have 2 that we have claimed are ``sets,'' and
the remaining 8 triples are all ruled out.  Therefore, the largest number of ``sets''
we could have is {\it two}(!)  An example:  Take the five cards to be 
$$a,b,c,d,e = [0,0,0,0],[1,1,1,1],[2,2,2,2],[1,2,1,2],[2,1,2,1]$$
There are exactly two ``sets'' in this collection $\{a,b,c\}$ and $\{a,d,e\}$. Our
argument shows there cannot be any more than two.  
\item{B)}  Same question   Proceed as in part A.  There are ${6 \choose 3} = 20$ triples.
 If the cards $a,b,c$ do form a 
``set,'' then the ${3\choose 2}\cdot 3 = 9$ triples 
$$\{a,b,d\},\{a,b,e\},\{a,b,f\}, \{a,c,d\},\{a,c,e\},\{a,c,f\}, \{b,c,d\}, \{b,c,e\}, \{b,c,f\}$$
cannot be ``sets.''   Any remaining triples that are ``sets'' must have either one
card in common with the first set or no cards in common with the first one.

\item{} If there are no cards in common, then the second ``set'' is $\{d,e,f\}$ and as before this
means that none of 
$$\{a,d,e\},\{b,d,e\},\{c,d,e\},\{a,d,f\},\{b,d,f\},\{c,d,f\},\{a,e,f\},\{b,e,f\},\{c,e,f\}$$
can be ``sets.''  We have 2 disjoint ``sets'' and $9 + 9$ different distinct triples that
cannot be ``sets,'' and that accounts for all $20$ of the triples.  So there cannot be any 
more than $2$ ``sets'' in this case.  

\item{} The remaining case to consider is where the second ``set'' does have one card, say $a$, 
in common with the first ``set.''  For instance, 
if $\{a,d,e\}$ is a ``set,'' then that rules out additional triples (but some of 
these have been listed before):
$$\{a,b,d\},\{a,c,d\},\{a,d,f\},\{a,b,e\},\{a,c,e\},\{a,e,f\}, \{b,d,e\},\{c,d,e\},\{d,e,f\}.$$
Five of these did not appear in the first excluded list, so 
there are now two ``sets'' and $9 + 5 = 14$ different triples that cannot be ``sets.''  In this
case it is possible for a third ``set'' to exist.  One of the triples that has not been
excluded as a ``set'' is $\{b,d,f\}$ (and up to the naming of the elements this is essentially
the only case!)  If that triple is also a ``set'' then 
we must rule out
$$\{a,b,d\},\{b,c,d\},\{b,d,e\},\{a,b,f\},\{b,c,f\},\{b,e,f\},\{a,d,f\},\{c,d,f\},\{d,e,f\}$$
Now we have $3$ ``sets'' and $9 + 5 + 2 = 16$ triples that cannot be ``sets.''  It looks as though
there might be ``room'' for one more ``set'' in the sense that $\{c,e,f\}$ has not been ruled out.  
But you can check that that one remaining triple can never satisfy the 
algebraic condition that would produce a set (the sums of the entries of the 4-tuples cannot
all be 0 mod 3).  This is because we know $a + b + c \equiv 0 \bmod 3$, $a + d + e \equiv 0 \bmod 3$
and $b + d + f \equiv 0 \bmod 3$.  But then $c \equiv 2a + 2b \bmod 3$, $e \equiv 2a + 2d \bmod 3$
and $f \equiv 2b + 2d \bmod 3$.  So $a + c + f \equiv 2a + 2b + 2a + 2d + 2b + 2d \equiv a + b + d \bmod 3$.
But the triple $\{a,b,d\}$ was one of the ones we ruled out and that means $a + b + d \bmod 3$
cannot equal $0$.  

\item{} Thus the largest number of ``sets'' in $6$ cards is actually $3$(!)  I'll let you cook up such a 
collection of cards as actual 4-tuples of integers mod 3.   
\bigskip
\item{}
(Comment:  This is too hard for an in-class exam question, so if you 
did not see how to finish it, don't worry!  I just wanted to get your problem-solving
``juices'' flowing!)
\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
{\it Solution:}  By the Generalized Pigeonhole Principle, if you have $23$ numbers (the ``pigeons'')
and you place them into the 11 ``pigeonholes'' of their congruence classes $\bmod 11$, then 
some pigeonhole must have strictly more than $\lfloor {23 - 1\over 11} \rfloor = 2$ pigeons.  
On the other hand you could have $22$ numbers where there are exactly two in each of the
congruence classes $\bmod 11$.  So $23$ is the smallest number of numbers where this
is guaranteed to happen.  
\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
{\it Solution:}  There are $7$ choices for $f(1)$, $7$ choices for $f(2)$, and $7$ choices
for $f(3)$.  So by the Multiplication Principle, there are $7^3 = 343$ functions in all.
Of these the injective functions are the ones where $f(1) \ne f(2)$, $f(1) \ne f(3)$, and
$f(2) \ne f(3)$.  There are $P(7,3) = 7\cdot 6\cdot 5 = 210$ injective functions.  
\bigskip
\noindent
VI.  
\item{A)}  How many permutations are there in $S_{17}$ with cycle type $[3,3,3,3,2,2,1]$?
\item{} {\it Solution:}  As in examples from class and Problem Set 2, the number of 
permutations with this cycle type is 
$${1\over 4!}\left({P(17,3)\over 3}\cdot {P(14,3)\over 3} \cdot {P(11,3)\over 3}\cdot {P(8,3)\over 3}\right)\cdot {1\over 2!} \left({P(5,2)\over 2}\cdot {P(3,2)\over 2}\right) \cdot 1.$$
\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$.  

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

\item{} 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.

\item{} By the Addition Principle, $s(n+1,k) = n\cdot s(n,k) + s(n,k-1)$ as claimed.  
\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)$.
\item{} {\it Solution:}  We use the recurrence relation three times and collect like terms:
$$\eqalign{
s(5,3) &= 4\cdot s(4,3) + s(4,2)\cr
       &= 4\cdot (3s(3,3) + s(3,2)) + 3s(3,2) + s(3,1)\cr
       &= 12\cdot s(3,3) + 7\cdot s(3,2) + s(3,1)\cr
}$$
We can stop here since we recall $s(3,3) = 1$, $s(3,2) = 3$, and $s(3,1) = 2$.  So
$$s(5,3) = 12\cdot 1 + 7\cdot 3 + 2 = 35.$$
\bigskip
\noindent
VII.  What is the largest power of $6$ that divides $100!$?
\bigskip
\noindent
{\it Solution:} By the Legendre formula the highest power of the prime $2$ that divides $100!$ is
$$\sum_{k\ge 1}\lfloor {100\over 2^k}\rfloor = 50 + 25 + 12 + 6 + 3 + 1 = 97$$
Similarly the highest power of the prime $3$ that divides $100!$ is 
$$\sum_{k\ge 1}\lfloor {100\over 3^k}\rfloor = 33 + 11 + 3 + 1 = 48$$
Since $6 = 2\cdot 3$, the largest power of $6$ that divides $100!$ is $6^{48}$.
\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{} {\it Solution:}  By the ``dividers'' method. This is the same as finding
the number of ways of writing $30 = a_1 + \cdots + a_8$ with $0 \le a_i \le 30$ for all $i$.
This number is ${30 + 7 \choose 7} = {37\choose 7}$.  
\item{B)} What if the store has only 10 red balloons, but at
least 30 of every other kind of balloon?  
\item{} {\it Solution 1:}  Say $a_1$ is the number of red balloons.  There is a restriction
now because $0 \le a_1 \le 10$ (we cannot have any more than 10 of them).  The most direct
way to count now is to use the Addition Principle and break things down by how many 
red balloons are included in the 30.  The terms below are the numbers with $0,1,2,\ldots,10$
red balloons, respectively:
$${36 \choose 6} + {35 \choose 6} + \cdots + {26 \choose 6}$$
\item{} {\it Solution 2:} 
An alternate way to think about it:  If we could buy at least 11 red balloons, then we would
be getting ${19 + 7\choose 7} = {26\choose 7}$ out of the ${37 \choose 7}$ total ways to 
make up 30 balloons from part A.  So the number here should be ${37 \choose 7} - {26\choose 7}$
(by the Addition Principle).  Good additional exercise:  Convince yourself that
$${36 \choose 6} + {35 \choose 6} + \cdots + {26 \choose 6} = {37\choose 7} - {26\choose 7}.$$
\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{} {\it Solution:}  There are ${13\choose 5}$ ways.
\item{B)} In how many ways can you choose a team of five, with two men and three women?
\item{} {\it Solution:} There are ${6\choose 2}\cdot {7\choose 3}$ ways.
\item{C)} In how many ways can you choose a team of five, with at most three men?
\item{} {\it Solution:}  We can have either $0,1,2$, or $3$ men, so by the Addition Principle
there are 
$${7\choose 5}{6\choose 0} + {7\choose 4}{6\choose 1} + {7\choose 3}{6 \choose 2} + {7\choose 2}{6\choose 3}$$
ways
\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:
$${n \choose k} = \sum_{m=0}^k {\ell \choose m}{n-\ell \choose k-m}$$
called the {\it Vandermonde convolution identity}.)
\item{} {\it Solution:}  The left hand side gives the total number of ways to 
pick a 5-person team from the pool of 13 programmers.  The right hand side gives
the same number but broken down into the different possible gender make-ups of the
team.  The term for each $m$, $0 \le m\le 5$ gives the number of teams with
exactly $m$ women and $5 - m$ men.
\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?
\item{} {\it Solution 1:} 
There are ${6\choose 3}\cdot {5\choose 2}$ teams that contain neither of the two divorced
people, ${6\choose 2}\cdot {5\choose 2}$ teams that contain the woman but not the man,  and
${6\choose 3}\cdot {5\choose 1}$ that contain the man, but not the woman.  By the Addition
Principle, the total number is the sum
$${6\choose 3}\cdot {5\choose 2} + {6\choose 2}\cdot {5\choose 2} + {6\choose 3}\cdot {5\choose 1}.$$
\item{} {\it Solution 2:}  Another way to do this is to count the number of teams containing
both of the people from the divorced couple and subtract that from the total number of teams from part B:
$${7\choose 3}\cdot {6\choose 2} - {6\choose 2}\cdot {5\choose 1}.$$
(You should check that these two ways of looking at the problem give the same result!)
\bigskip
\noindent
X.  
\item{A)}  What is the coefficient of $x^4 y^2$ in $(3x + 5y)^6$?
\item{} {\it Solution:}  The coefficient is ${6\choose 4}\cdot 3^4 \cdot 5^2$.
\item{B)}  What is the coefficient of $x^3 y^2 z$ in $(x + 2y + 3z)^6$? 
\item{} {\it Solution:}  This involves a multinomial coefficient:  ${6\choose 3,2,1}\cdot 2^2\cdot 3$.  
\bye
