%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #4 (added by Ivan)
\problem \points{15} %F96 Q2 p6

\bparts 

\ppart\points{5} Prove, by direct calculation, that 
for $1 \leq r \leq n$,
\[\binom{n}{ r} = \frac{(n-r+1)}{r} \binom{n}{ r-1}.\]

%\vspace{2.5in}

\solution{
\textbf{Solution:}
\begin{eqnarray*}
\binom{n}{r} / \binom{n}{r-1}
 & = & \frac{n!}{r!(n-r)!} \times \frac{(r-1)!(n-(r-1))!}{n!} \\
&=& \frac{1}{r\cdot (r-1)! (n-r)!} \times (r-1)!(n-r+1)! \\
&=& \frac{1}{r (n-r)!} \times (n-r+1) \cdot (n-r)! \\
&=& (n-r+1)/r.
\end {eqnarray*}
}

\ppart\points{10} Now prove the same identity combinatorially by comparing
two procedures for choosing a committee of $r$ members out of $n$ people
and also choosing a committee member to be chairman.


\medskip
\solution{
\textbf{Solution:}  Straight from Recitation 8:

Consider the number of ways of choosing a committee of $r$ members
out of $n$ people, and  also choose a chairman for the committee.
There are $\binom{n}{r}$ ways of choosing the committee, and for each
such committee there are $r$ choices for the chair.
Alternatively, there are $\binom{n}{r-1}$ ways of choosing all the
members but the chair, and then $n-r+1$ ways to choose the chair among
the remaining people. It follows that
\[ r \binom{n}{r} = (n-r+1) \binom{n}{r-1} \]
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #5 (added by Ivan) %formerly from S97 Q2
\problem \points{10}
Prove that the number of sequences of eleven letters which can be
made from the letters in MISSISSIPPI is not divisible by four.

\medskip
\solution{
\textbf{Solution:}
11 letters: 4 S's, 4 I's, 2 P's, 1 M.
After some cancelling, 
\[\binom{11}{4,4,2,1} = 11 * 10 * 9 * 7 * 5,\]
which is divisible by 2 but not 4.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #6 (added by Ivan)
\problem\points{20}

Prove that there are 16,800 permutations of the letters
$\set{a,b,c,d,e,f,g,h}$ such that neither the letters $\set{a,b,c}$ nor
the letters $\set{d,e}$ occur in order.  For example, $fbgadceh$ is not
allowed because $d$ occurs before $e$, and $fagbecdh$ is not allowed
because $a$ occurs before $b$ and $b$ occurs before $c$, but $fbgaedch$ is
OK.

\medskip
\solution{
\textbf{Solution:}

One way is to find three positions for $a$, $b$, and $c$, then two other
positions for $d$ and $e$, and count the number of ways $a$, $b$, and
$c$, can be out of order (namely, 5), the number of ways for $de$ (namely,
1), and the permutations of remaining 3 elements (namely, 3!):
\begin{eqnarray*}
\binom{8}{3}\binom{5}{2}3!5 & = &
      \frac{8*7*6}{3*2} \frac{5*4}{2} 3 * 2 * 5\\
& = & (8*7)(5*2)30 = 56*300 = 16800.
\end{eqnarray*}

Inclusion-exclusion is another way: let ALL be the $8!$ permutations of
all eight letters, let ABC be those permutations with $a,b,c$ appearing in
order, and DE those permutations with $d,e$ in order.  So
$\card{\mbox{ABC}} = P(8,5) ::= 8\cdot 7\cdot 6\cdot 5\cdot 4$, since a
permutation in ABC is uniquely determined by the 5 out of 8 positions of
the 5 letters besides $a,b,c$.  Likewise $\card{\mbox{DE}} = P(8,6)$.
Also, $\card{\mbox{ABC} \intersect \mbox{DE}}$ is determined by the
$P(8,3)$ positions of $f,g,h$ and then the $\binom{5}{2}$ places to put
$d$ and $e$ in order, that is $\card{\mbox{ABC} \intersect \mbox{DE}} =
P(8,3)\binom{5}{2}$.  Then the number of allowed permutations is
\begin{eqnarray*}
\card{\mbox{ALL}} - \card{\mbox{ABC} \union \mbox{DE}} & = & 8! -
\card{\mbox{ABC}} - \card{\mbox{DE}} + \card{\mbox{ABC} \intersect
\mbox{DE}}\\
& = & 8! - P(8,5) - P(8,6) + P(8,3)\binom{5}{2}\\
& = & 8*7*6[5! - 5*4 - 5*4*3 + 5*4/2]\\
& = & 8*7*6[120-20-60+10] = 8*7*6*50 = 16,800.
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \pts{45} \textbf {Rearranging the Alphabet}

For this problem you do not need to evaluate an expression fully: you
may leave it in terms of binomial coefficients, powers of numbers,
factorials, and so on.  For this problem we consider the alphabet to
consist only of capital letters.

\problempart {\bf (15 points)} How many different strings are there
of 10 letters such that no letter is used more than once?

\solution{\bigskip
{\bf Solution:}

This is just asking for a permutation of 10 out of 26 objects.  Thus,
the answer is $P(26,10) = \frac{26!}{(26-10)!} = \frac{26!}{16!}$.  
}
\mediumspace

\problempart {\bf (15 points)} How many ways can you rearrange the
alphabet (using each letter only once) so that none of the words ``TEST,''
``EXAM,'' and ``STUDY'' appear as consecutive letters in your arrangement?


\solution{\bigskip
{\bf Solution:}

We proceed by using the inclusion/exclusion principle.  It makes our
job slightly easier that the word ``TEST'' can never appear in a
rearrangement of the alphabet, since ``TEST'' contains the letter T
twice.  The number of valid arrangements is equal to $A-E-S+B$ where
$A$ is the number of ways we can rearrange the alphabet, $E$ is the
number of ways we can rearrange the alphabet so that ``EXAM'' appears,
$S$ is the number of ways we can rearrange the alphabet so that
``STUDY'' appears, and $B$ is the number of ways we can rearrange the
alphabet so that both ``EXAM'' and ``STUDY'' appear.

$A = 26!$, since there are $26!$ ways of putting 26 distinct elements in order.

$E = 23!$. since there are $23!$ ways of ordering 23 objects: the string 
``EXAM'' and the 22 other letters in the alphabet.

$S = 22\cdot 21! = 22!$ by the same reasoning.

$B = 19!$ by the same reasoning; this time there are two strings, ``EXAM'' 
and ``STUDY'' and 17 letters.

So the final answer is $26! - 23! - 22! + 19!$.
}

\nextproblem

\problempart {\bf (15 points)} How many ways are there to choose a
collection of 30 letters such that none of the words ``EXAM,'' ``STUDY,''
and ``TEST'' can be formed using the letters in the collection?

\solution{\bigskip
{\bf Solution:}

Again, we prooced by inclusion/exclusion.  A collection is not an ordered
object, and we are obviously allowed to use letters more than once, so we 
use the formula for combinations with repetitions.  Thus,
the number of ways to choose a collection of 30 letters is
$\binom{30+26-1}{30} = \binom{55}{30}$.

The number of ways to make a collection of 30 letters with $k$ specified
letters is the number of ways to make a collection of $30-k$ letters (to
which we add the specified letters).  Thus, it is $\binom{30+26-1-k}{30-k}
= \binom{55-k}{30-k}$.  

Let $A$ be the set of all collections which contain the letters `E', `X',
`A', and `M'.  Let $B$ be the set of all collections which contain the
letters `S', `T', `U', `D', and `Y'.  Let $C$ be the set of all
collections which contain the letters `S', `E', and which contains the
letter `T' at least twice.  What we want is

$$| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B
\cap
C| + |A \cap B \cap C|$$

Now we note that $A \cap B$ has 9 fixed letters, $A \cap C$ and $B \cap C$
have 7, and $A \cap B \cap C$ has 10 fixed letters.  (For instance,
``EXAM'' and ``TEST'' overlap so we only have to have the `E' once to form
both words).  Thus, 

$$|A \cup B \cup C| = \binom{51}{26} + \binom{50}{25} + \binom{51}{26} -
\binom{46}{21} -
\binom{48}{23} - \binom{48}{23} + \binom{45}{20}$$

So our answer is

$$ \binom{55}{30} - 2\binom{51}{26} - \binom{50}{25} + 2\binom{48}{23}
+ \binom{46}{21} - \binom{45}{20}.$$


which, if you're curious, evaluates to about 2.5 quadrillion.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} The following identity holds for non-negative
integers $n$, $j$, and $k$ such that $n \geq j + k$.

\begin{eqnarray*}
\binom{n}{j} \binom{n-j}{k}
    & = &   \binom{n}{j+k} \binom{j+k}{k}
\end{eqnarray*}

\begin{problemparts}
\problempart {\bf (5 points)} Prove the identity algebraically.

\examonly{\vspace{3in}}

\solution{
\begin{eqnarray*}
\binom{n}{j} \binom{n-j}{k}
    & = &   \frac{n!}{j! \ (n-j)!} \cdot
        \frac{(n-j)!}{k! \ (n-j-k)!} \\
    & = &   \frac{n!}{j! \ k! \ (n-j-k!)} \\
    & = &   \frac{n!}{(j+k)! \ (n-j-k)!} \cdot
        \frac{(j+k)!}{k! \ j!} \\
    & = &   \binom{n}{j+k} \binom{j+k}{k}
\end{eqnarray*}
}

\problempart {\bf (5 points)} Prove the identity combinatorially.

\solution{Both sides of the equation count the number of ways to
choose distinguishable, disjoint subsets of sizes $j$ and $k$ from a
set of $n$ elements.  On the left side, we first choose the
$j$-element subset from the whole $n$-element set, and then choose the
$k$-element subset from the remaining $n-j$ elements.  On the right
side, we first choose $j+k$ elements from the whole set.  From these
$j+k$ elements, we then choose the $k$-element set; the remainders
form the $j$-element set.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (20 points)} Solve the following counting problems.
Simplified answers are not required.

\begin{problemparts}

\problempart {\bf (4 points)} In how many ways can the letters in
BOOKKEEPER be arranged?

\examonly{\vspace{1in}}

\solution{
\[
\frac{10!}{2! \ 2! \ 3!}
\]
}

\problempart {\bf (4 points)} In how many ways can 160 distinguishable
students be assigned to 8 indistinguishable recitations so that every
recitation has 20 students?

\examonly{\vspace{1in}}

\solution{If the recitations were distinguishable, then the answer
would be $\frac{160!}{20!^8}$ by the multinomial formula.  Since the
recitations are identical, the answer is $\frac{160!}{20!^8 \ 8!}$ by
the quotient rule.
}

\problempart {\bf (4 points)} In how many ways can 6.042 TA John Dunagan assign
the following objects to three desk drawers,

\begin{itemize}
\item 7 tasty treats,
\item 27 thumb tacks, and
\item 1 can of theoretically-enriched Spam,
\end{itemize}

so that the Spam shares a drawer with no tasty treats and at least 19
thumb tacks?  (Desk drawers are distinguishable, but tasty treats and
thumbtacks are not.)

\examonly{\vspace{1in}}

\solution{Theory Pig (R. I. P.) and the tacks can be assigned to a
drawer in 3 ways.  The treats can be divided between the other two
drawers in $\binom{7+1}{1} = 8$ ways.  The 8 remaining tacks can be
divided among the three drawers in $\binom{8+2}{2} = 45$ ways.
Overall, there are $3 \cdot 8 \cdot 45$ assignments.}

\problempart {\bf (4 points)} How many ways can 100 identical balls be
placed in 10 distinguishable bins so that every bin contains an odd
number of balls?

\examonly{\vspace{1in}}

\solution{First, we put 1 ball into each bin.  Then we pair up the 90
remaining balls into 45 pairs.  Then we assign the 45 pairs to bins.
This can be done in $\binom{45 + 9}{9}$ ways.}

\problempart {\bf (4 points)} How many paths are there from $(0, 0)$
to $(4, 4)$ consisting of 10 steps, each of which is either north,
south, east, or west?

\examonly{\vspace{1in}}

\solution{Either there are 5 north steps, 1 south step, and 4 east
steps, or else there are 5 east steps, 1 west step, and 4 north
steps.  Thus, there are

\[
2 \cdot \frac{10!}{5! \ 1! \ 4!}
\]

paths in total.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Combinatorics}
Let $S$ be the set $\{a, b, c, d, e\}$ and let $T$ be the set $\{1,
2, 3, 4\}$. {\bf (2 points each)}

\problempart What is the number of binary relations from $S$ to $T$?

\solution{\bigskip{\bf Solution:} 
The set of all binary relations is
$\mathcal{P}(S \times T)$.  Since $|S \times T| = 20$, the number of
binary relations between $S$ and $T$ is $2^{20}$.
}

\smallspace

\problempart What is the number of functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} To make a function from $T$ to $S$,
we must assign an element of $S$ to each element of $T$.  Thus, for
each of the 4 elements in $T$ we must make one of 5 choices.  Therefore
the number of functions from $T$ to $S$ is $5^4$.}

\smallspace

\problempart What is the number of injective functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} We must choose a permutation of 4
out of 5 elements.  Thus, $5!$ is the number of injective functions.
(We must make a choice of which of the 5 elements of $S$ is mapped to
from the first element of $T$, then a choice of which of the remaining
4 elements of $S$ is mapped to from the second element of $T$, et
cetera.}

\smallspace

\problempart What is the number of surjective functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} 
0.  $T$ is smaller than $S$ so there cannot be a surjection from $T$ to $S$.
}

\smallspace

\problempart What is the number of surjective functions from $S$ to $T$?

\solution{\bigskip{\bf Solution:} To form a surjective function, we
first take an injective function from $T$ to $S$ (this takes care of
the surjective requirement), and then choose which element of $T$ is
the image of the remaining element of $S$ which hasn't been paired up
yet.  There are $5! \cdot 4$ ways of doing this.

However, we have double-counted everything.  For example, if the
function is $(1, 2, 3, 4, 1)$, we have counted this by choosing the
injection $(a, b, c, d)$ and then the element 1, AND by choosing the
injection $(e, b, c, d)$ and then the element 1.  So, we must divide 
by 2 to take care of this; this leaves $2 \cdot 5!$ as the final answer.}
