\documentclass[12pt]{article}
\pagestyle{empty} 
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}
\topmargin=0pt
\textheight=9in
\oddsidemargin=0pt
\textwidth=6.5in



\begin{document}
Mathmatics 239 solutions to Homework for Chapter 3

\bigskip


\S 14.6 Let us say that two integers are near to one another provided their difference is 2 or smaller.  Let $R$ stand for this is-near-to relation.  

(a) Write down $R$ as a set of ordered pairs.
 
The easiest way to do this is $R = \{(x, y) : \mid x - y \mid \leq 2\}$.  (There are many other ways.  
The better your choice on this part the easier the rest of the problem becomes.) 

(b) Prove or disprove:  $R$ is reflexive. 

This is true.  Proof:  Let $x \in \mathbb{Z}.  \mid x -x\mid = \mid0\mid = 0 \leq 2$.  Therefore $(x, x) \in R$.   Since 
there was nothing assumed about $x$, we have $\forall x \in \mathbb{Z}, (x, x) \in R$.  This is what it means for $R$ to be reflexive. 

(c) Prove or disprove:  $R$ is irreflexive.
 
This is false (in fact very false; any example is a counterexample).  Counterexample:  
Consider 0.  $\mid0 - 0\mid= 0 \leq 2$.  Therefore $(0, 0) \in R$.  Therefore it is not the case that                      $\forall 
x \in Z, (x, x) \notin R$.  Therefore $R$ is not irreflexive. 

(d) Prove or disprove:  $R$ is symmetric. 

This is true.  Proof:  Suppose $x, y \in \mathbb{Z}$ such that $(x, y) \in R$.  By the definition of $R$ we 
then have $\mid x  - y\mid \leq 2$.  But $\mid x - y\mid = \mid y - x\mid$, so we have $\mid y - x\mid \leq 2$.  Therefore $(y, x) \in R$.  
We have shown if $(x, y) \in R$ then $(y, x) \in R$.  Therefore $R$ is symmetric.
 
(e) Prove or disprove:   $R$ is antisymmetric.
 
This is false.  $\mid2 - 1\mid = 1 \leq 2$.  Therefore $(2, 1) \in R$.  By (d) we know that $R$ is 
symmetric, therefore $(1, 2) \in R$.  However $1 \ne 2$.  Therefore $(2, 1)$ is a counterexample to antisymmetry which asserts that if $(x, y) \in R$ and $(y, x) \in R$ then $x = y$.  Therefore $R$ is not 
antisymmetric.
 
(f) Prove or disprove:  R is transitive. 

This is false.  $\mid7 - 5\mid \leq 2$ and $\mid5 - 3\mid \leq 2$.  Therefore we have $(7, 5) \in R$ and $(5, 3) \in 
R$.  However it is false that $(7, 3) \in R$ because $\mid7 - 3\mid = 4 > 2$.  Therefore $(7, 5, 3)$ is a 
counterexample to transitivity which asserts that if $(x, y) \in R$ and $(y, z) \in R$ then $(x, z) \in R$.  Therefore $R$ is not transitive.
 
 \bigskip
 
\S14.13 (a) Give an example of a relation that on a set that is neither reflexive nor irreflexive.
 
$S = \{g, h\}.  R = \{(g, g), (g, h)\}$.  The relation $R$ is not reflexive because $(h, h) \notin R$.  The relation $R$ is not irreflexive because $(g, g) \in R$. 

\S14.13 (b) Give an example of a relation that on a set that is both reflexive and irreflexive.

$S = \emptyset, R = \emptyset$.  Universal conditions (such as reflexive and irreflexive) are vacuously true on the empty set $S$.

\pagebreak

\S14.16 Give an example of a relation on a set that is both symmetric and transitive but not reflexive. 
 \[S = \{p, q, r\}, R = \{(p, q), (q, p), (p, p), (q, q)\} \]
$R$ is symmetric because whenever something of the form $(a, b) \in R$ we have $(b, a) \in R$, and it is transitive, whenever we have something of the form $(a, b)$ and $(b, c) \in R$ we also have $(a, 
c) \in R$.  But, $R$ is not reflexive because $(r, r) \notin R$.
 
Explain what is wrong with the following �proof�: 

If $R$ is symmetric and transitive then $R$ is reflexive. 
Suppose $R$ is symmetric and transitive.  Symmetric means that $x R y$ implies $y R x$.  We apply transitivity to $x R y$ and $y R x$ to give $x R x$.  Therefore $R$ is reflexive.
 
In the third sentence he states �we apply transitivity to $x R y$ and $y R x$� as if we somehow knew that $x R y$ and $y R x$.  We do not know these things.  The fictional author of the incorrect proof is apparently confusing the 
statement of symmetry, $\forall x, \forall y, (x R y) \Rightarrow (y R x)$ with a more strong statement                           $\forall x, \forall y, (x R y) \wedge (y R x)$.  This second statement would yield his argument, but is an absurdly 
strong statement, as it says that any two elements are related, hence reducing $R$ to the trivial �everything is related� equivalence relation.  Certainly this is not true for most relations we 
consider. 

\bigskip

\S15.6 Prove that congruence modulo $n$ is transitive.
 
Suppose that $a \equiv b \mod n$ and $b \equiv c \mod n$.  Translating this means that $n \mid a - b$ and         
$n \mid b - c$.  We have proven elsewhere that if $n \mid x$ and $n \mid y$ then $n \mid x + y$.  So, here                           
$n \mid(a - b) + (b - c)$, or $n\mid a - c$.  Translating again yields, $a \equiv c \mod n$.

 \bigskip
 
EXTRA \S15.10  Prove $\bigcup_{a\in A} [a] = A$.  To do this we must prove subsethood in both directions.  First we will prove $\bigcup_{a\in A} [a] \supset A$.  Suppose $x \in A$.  Because our relation is reflexive, $xRx$, and so $x \in [x]$.  Because $x \in A$, $[x] \subset \bigcup_{a\in A} [a]$, therefore $x \in [x] \subset \bigcup_{a\in A} [a]$ or $x \in \bigcup_{a\in A} [a]$, as desired.
 
Next we will prove $\bigcup_{a\in A} [a] \subset A$.  Suppose $x \in \bigcup_{a\in A} [a]$.  So, there exists an $a\in A$ such that $x \in [a]$.  Recall $[a] = \{y \in A \mid yRa\}$.  From this we see that since $x \in [a]$, it must be that $x \in A$, which was our goal.  

Since we have proven subsets in both directions, we have $\bigcup_{a\in A} [a] = A$.

\bigskip 
  
EXTRA \S15.11 Let $R$ be an equivalence relation on a set $A$ and let $a, b \in A$.  Prove that if $a \in [b]$, then $b \in [a]$.
  
Suppose that $a \in [b]$.  By definition we have $a R b$.  By symmetry we have $b R a$.  Because we have $b R a$ we have $b \in [a]$, as desired. As there is nothing distinctive about $a$ and $b$, the converse may be proven by switching letters.  

\bigskip

\S15.12 Let $R$ be an equivalence relation on a set $A$ and let $a,x,y \in A$.  If $x, y \in [a]$, prove $xRy$.  

Suppose $R$ is an equivalence relation on a set $A$ and $a,x,y \in A$.  Suppose $x, y \in [a]$.  Recall $[a] = \{e \in A \mid eRa\}$.  Since $x, y \in [a]$ we have $x Ra$ and $yRa$.  Because $R$ is an equivalence relation it is symmetric.  Since $yRa$, by symmetry $aRy$.    As $R$ is an equivalence relation it is transitive.  Since $xRa$ and $aRy$, by transitivity $xRy$, which was our goal.  

\S15.15 Describe three different equivalence relations on $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ and draw a diagram of the equivalence classes of each.  
Of course, there are many possible answers to this.  Here are two extremes:  

$R = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (10, 10)\} $

diagram:
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3&4&5&6&7&8&9&10\\
\hline 
\end{tabular} 


$R = A \times A$
diagram:
\begin{tabular}{|c|}
\hline
1 2 3 4 5 6 7 8 9 10 \\
\hline
\end{tabular} 



EXTRA \S16.10  Ok, let's start with the lineup again.  Put the numbers in an order.  There are 25! ways to do that.    Then write them down each column.  So numbers 1-5 go in the first column, down, and so on.  Then we can permute the columns and get the same answer, so there are 5! ways to permute the columns.  Therefore there are $\frac{25!}{5!}$ arrays.  Not too bad.  

\bigskip

\S16.11 Twenty people are to be divided into two teams with ten players on each team.  In how many ways can  this be done? 

Two answers: 

a.  Order all twenty people, then realize that reordering the first ten doesn't change 
anything, neither does reordering the last ten, or switching the two teams.  So, we have 
$\frac{20!}{ 10! 10! 2!} = 92,378$.


b.  (Using material from 17) Choose ten people to be on one team  
$\left( \begin{array}{c}
20 \\
10 
\end{array} \right)$, then 
divide by two because we have the same teams if we interchange all the people on both teams.  
This counts to 
$\frac{\left( \begin{array}{c}
20 \\
10 
\end{array} \right)}{2} 
 = 92,378$.
 
 \bigskip
  
\S 16.13 One hundred people are to be divided into ten discussion groups with ten people in each group.  In how many ways can this be done? 

This answer follows strategy a. from \S16.11.  Order all 100 people, then realize that neither reordering within each of the ten groups, nor reordering the sequence of the groups will change the 
group composition.  The ordering the 100 people is 100!, reordering in each group is 10! for ten groups, and then reordering the groups is 10! as well.  So we have 
$\frac{100!}{(10!)^{11}}$
 = 64,954,656,894,649,578,274,066,349,293,466,217,242,333, 
450,230,560,675,312,538,868,633, 528,911,487,364,888,307,200 $\doteq 6.49 \times 10^{85}$,  i.e. very many ways to divide these people.  (This is a great example of the point I keep making that frequently leaving the number uncomputed gives more information.) 

\bigskip

EXTRA \S16.14  For both versions, I will think about the violas leading (and I'm sure they will appreciate this).  So, I will think of the quartets as being labeled by their violists.  First I will do the bass version.  So, I have to put the rest of the musicians on quartets.  Putting violinists with violists can be done in $10!$ ways, same goes with cellists and bassists.  So, altogether there are $10!10!10! = (10!)^3$ ways to make quartet with four different instruments, but this isn't what is done in music.  

If we actually of use two violins, they become difficult (or were they already?).  We have $10!$ ways to put cellists with the violists.  And now we need to be careful.  There are $20!$ ways to line up the violinists, but switching pairs in each of the 10 quartets won't matter, so there are $\frac{20!}{2^{10}}$ ways of assigning the violinists.   Altogether this gives us $\frac{10!20!}{2^{10}}$ actual string quartets.  Using the ideas of section 17, we could also assign the first quartet it's violinists in $\left( \begin{array}{c}
20 \\
2 
\end{array} \right)$ ways and the second in 
$\left( \begin{array}{c}
18 \\
2 
\end{array} \right)$ ways and so on.  This seems messier, giving us an answer of
 \[10! \left( \begin{array}{c}
20 \\
2 
\end{array} \right)\left( \begin{array}{c}
18 \\
2 
\end{array} \right)\left( \begin{array}{c}
16 \\
2 
\end{array} \right)\left( \begin{array}{c}
14 \\
2 
\end{array} \right)\left( \begin{array}{c}
12 \\
2 
\end{array} \right)\left( \begin{array}{c}
10 \\
2 
\end{array} \right)
\left( \begin{array}{c}
8 \\
2 
\end{array} \right)\left( \begin{array}{c}
6 \\
2 
\end{array} \right)\left( \begin{array}{c}
4 \\
2 
\end{array} \right)\left( \begin{array}{c}
2 \\
2 
\end{array} \right)
\]
This is the same as the previous answer.  You might consider why.  

\bigskip

EXTRA \S16.17  Learning from 13, I hope by now we can see the partition into 20 parts of size five is given by $\frac{100!}{5!^{20}20!}$ and the partition into 5 parts of size twenty is $\frac{100!}{{20!}^55!}$.  I was going to say the second was smaller, but I keep not being so sure.  I'm sure they're not the same - the first has one 19 in the denominator and the second has five of them, so by unique prime factorisation they must be different.  But, Scheinerman says this is a time to compute, and I think I agree.  In fact, they're not even close, and my guess was right, but I'm still not precisely clear on an intuitive reason (I was thinking the smaller pieces allow for more diversity, but then the shuffling undoes some things.  In any case the 20 parts of size five can be done in over $10^{98}$ ways and the 5 parts of size twenty in under $10^{64}$ ways

\bigskip

\S 17.14 Prove that the sum of the numbers in the $n$th row of Pascal�s  triangle is $2n$.
Prove that 
\[2^n = \sum_{k = 0}^n \left( \begin{array}{c}
n \\
k 
\end{array} \right).\]
 Consider:  how many subsets are there of a set $A$ with $n$ elements?  The set of all subsets of 
$A$ is $2^A$ and has $2^{\mid A \mid} = 2^n$ elements.  Also, let�s consider this case by case, you have $\left( \begin{array}{c}
n \\
0 
\end{array} \right)$ 
0-element subsets, $\left( \begin{array}{c}
n \\
1 
\end{array} \right)$
 1-element subsets,  $\left( \begin{array}{c}
n \\
2 
\end{array} \right)$ 2-element subsets and so on, so we have a total 
of  
\[\left( \begin{array}{c}
n \\
0 
\end{array} \right) +\left( \begin{array}{c}
n \\
1 
\end{array} \right)+\left( \begin{array}{c}
n \\
2 
\end{array} \right)+ \cdots + \left( \begin{array}{c}
n \\
n 
\end{array} \right) = \sum_{k = 0}^n \left( \begin{array}{c}
n \\
k 
\end{array} \right)\] subsets.  Therefore, the number of subsets is both $2^n$ 
and $\sum_{k = 0}^n \left( \begin{array}{c}
n \\
k 
\end{array} \right)$, and so these two numbers must be equal. 

\pagebreak

\S17.23 Prove 
\[\left( \begin{array}{c}
n \\
3 
\end{array} \right) = \left( \begin{array}{c}
2 \\
2 
\end{array} \right) + \left( \begin{array}{c}
3 \\
2 
\end{array} \right) +\left( \begin{array}{c}
4 \\
2 
\end{array} \right) + \cdots + \left( \begin{array}{c}
n - 1 \\
2 
\end{array} \right).\]


$\left( \begin{array}{c}
n \\
3
\end{array} \right)$  is the number of 3-element subsets from a set of $n$ elements.  Consider grouping 
these sets by their lowest element.  There are $\left( \begin{array}{c}
n-1 \\
2 
\end{array} \right)$ 
 sets with 1 as the least element (after picking 
1, we have 2 left to choose from the remaining $(n - 1)$ elements).  There are  $\left( \begin{array}{c}
n-2 \\
2 
\end{array} \right)$ 
sets with 2 as 
the least element ($n - 2$ numbers greater than 2 for 2 spots).  There are  $\left( \begin{array}{c}
n-3 \\
2 
\end{array} \right)$ sets with 3 as the 
least element.  This continues.  There is $\left( \begin{array}{c}
n  - (n-2)\\
2 
\end{array} \right) = \left( \begin{array}{c}
2 \\
2 
\end{array} \right)$ set with $n - 2$ as the least element.  
There are  $\left( \begin{array}{c}
n-(n-1) \\
2
\end{array} \right) = \left( \begin{array}{c}
1 \\
2 
\end{array} \right) 
 = 0$ sets with $n - 1$ as the least element (this makes sense, as there is 
only one number greater than $n - 1$, so we cannot make a 3-element set with $n - 1$ as the least 
element).  There are $\left( \begin{array}{c}
n - n \\
2 
\end{array} \right) = \left( \begin{array}{c}
0 \\
2
\end{array} \right) = 0$ sets with $n$ as the least element (as above).  Since the cases 
are disjoint we can collect the numbers of sets grouped by least element and add them.  This yields: 
$\left( \begin{array}{c}
2 \\
2 
\end{array} \right) + \left( \begin{array}{c}
3 \\
2 
\end{array} \right) +\left( \begin{array}{c}
4 \\
2 
\end{array} \right) + \cdots + \left( \begin{array}{c}
n - 1 \\
2 
\end{array} \right)$ 
  but is just an alternate way of counting the number of 
3-element subsets, which is counted by  $\left( \begin{array}{c}
n \\
3 
\end{array} \right)$.  Therefore $\left( \begin{array}{c}
n \\
3 
\end{array} \right) = \left( \begin{array}{c}
2 \\
2 
\end{array} \right) + \left( \begin{array}{c}
3 \\
2 
\end{array} \right) +\left( \begin{array}{c}
4 \\
2 
\end{array} \right) + \cdots + \left( \begin{array}{c}
n - 1 \\
2 
\end{array} \right)$.

\pagebreak

\S17.24 Make a large copy of Pascal's triangle and mark the numbers $\left( \begin{array}{c}
7 \\
2 
\end{array} \right)$, 6, 5, 4, 3, 2, 
and 1.  

\[\begin{tabular}{ccccccccccccccccc} 
&&&&&&&&1&&&&&&&&\\ 
&&&&&&&1&&1&&&&&&&\\ 
&&&&&&1&&2&&1&&&&&&\\ 
&&&&&1&&3&&3&&1&&&&&\\ 
&&&&1&&4&&6&&4&&1&&&&\\
&&&1&&5&&10&&10&&5&&1&&&\\
&&1&&6&&15&&20&&15&&6&&1&&\\
&1&&7&&21&&35&&35&&21&&7&&1&\\
1&&8&&28&&56&&70&&56&&28&&8&&1\\
\end{tabular}\] 


What's the pattern?   $\left( \begin{array}{c}
7 \\
2 
\end{array} \right) =  6 + 5 + 4 + 3 + 2 + 1$.  Visually, if you add along the 
(downward right-to-left) diagonal, then take a left-turn (heading downward) you will get the resulting value. 

Mark  $\left( \begin{array}{c}
7 \\
3 
\end{array} \right),  \left( \begin{array}{c}
6 \\
2 
\end{array} \right),  \left( \begin{array}{c}
5 \\
2 
\end{array} \right),  \left( \begin{array}{c}
4 \\
2 
\end{array} \right),  \left( \begin{array}{c}
3 \\
2 
\end{array} \right)$, and  $\left( \begin{array}{c}
2 \\
2 
\end{array} \right)$.  What's the pattern?  Again,  $\left( \begin{array}{c}
7 \\
3 
\end{array} \right) =   \left( \begin{array}{c}
6 \\
2 
\end{array} \right) +  \left( \begin{array}{c}
5 \\
2 
\end{array} \right)+  \left( \begin{array}{c}
4 \\
2 
\end{array} \right)+  \left( \begin{array}{c}
3 \\
2 
\end{array} \right)+\left( \begin{array}{c}
2 \\
2 
\end{array} \right)$.  Visually, the same, add along the diagonal, take a left-turn to find the 
sum.  Generalize these formulas and prove your assertion.  In general 
\[\left( \begin{array}{c}
n \\
b 
\end{array} \right) = \sum_{i=b-1}^{n-1}  \left( \begin{array}{c}
i \\
b-1 
\end{array} \right)\] 
The proof is the same as in Prop.17.5 and in HW 17.23.  Group the subsets by least element.  In a subset with b elements, there can be least elements ranging from 1 to $n - b$ (so that 
there are room for the higher elements).  For these subsets, there are $n - 1$  down to $b - 1$ choices for the other $b - 1$ elements, after the least element.  These different cases of least element 
correspond directly to the summed coefficients on the right hand side of the above equation.  The left hand side counts the subsets directly.  Therefore, they answer the same question in two 
different ways and must be equal.



\pagebreak
 
\S17.33 There are a variety of special hands that one can be dealt in poker.  For each of the following types of hand, count the number of hand that have that type.  

\bigskip

(a) Four of a kind:  The hand contains four cards of the same numerical value and another card. 

First choose which numerical value we will have four of, there are $\left( \begin{array}{c}
13 \\
1 
\end{array} \right)$ ways to do this.  
Next pick the four cards, there is $\left( \begin{array}{c}
4 \\
4 
\end{array} \right)$ way to do this.  Then, pick the extra card.  There are 48 
cards in values not used yet, so  $\left( \begin{array}{c}
48 \\
1 
\end{array} \right)$
 ways to do this.  Altogether we have $\left( \begin{array}{c}
13 \\
1 
\end{array} \right) \left( \begin{array}{c}
4 \\
4 
\end{array} \right) \left( \begin{array}{c}
48 \\
1 
\end{array} \right)$ = 
13(48) = 624 hands of four-of-a-kind.  

\bigskip

(b)Three of a kind.  The hand contains three cards of the same numerical value and two other cards with two other numerical values.  


First choose which numerical value we will have three of, there are $\left( \begin{array}{c}
13 \\
1 
\end{array} \right)$ ways to do this.  
Next pick the three cards, there are  $\left( \begin{array}{c}
4 \\
3 
\end{array} \right)$ ways to do this.  Then, select the values of the extra 
cards, there are  $\left( \begin{array}{c}
12 \\
2 
\end{array} \right)$ ways to do this.  After that, select a suit for each of these values, there are $\left( \begin{array}{c}
4 \\
1 
\end{array} \right)^2$ ways.  Altogether we have  $\left( \begin{array}{c}
13 \\
1 
\end{array} \right) \left( \begin{array}{c}
4 \\
3 
\end{array} \right) \left( \begin{array}{c}
12 \\
2 
\end{array} \right) \left( \begin{array}{c}
4 \\
1 
\end{array} \right)^2 = 13(4)(66)(4^2)$ = 54,912. 

There are probably several ways to approach this question.  What is most important is that you are careful not to use the remaining card in the first value for one of the last two (which would 
give you four of a kind, not three) and not to have the last two the same (which would give you a full house [see (d)] not three of a kind). And, finally, not to select the last two cards as if order matters for them.  

\bigskip

(c) Flush:  The hand contains five cards all of the same suit.  

This is the easiest.  First choose a suit in $\left( \begin{array}{c}
4 \\
1 
\end{array} \right)$ ways.  Then, choose the five cards in $\left( \begin{array}{c}
13 \\
5 
\end{array} \right)$ ways.  So, we have $\left( \begin{array}{c}
4 \\
1 
\end{array} \right)\left( \begin{array}{c}
13 \\
5 
\end{array} \right)$ = 4(1287) = 5148. 

Ok, that was the easy interpretation (trusting the book literally).  More precisely we may wish to discount straight flushes [see (f)] from this.  If so, we have $5148 - 36 = 5112$ hands. 

\bigskip

(d) Full house:  The hand contains three cards of one value and two cards of another value.  

By now this should be routine.  First choose the first value $\left( \begin{array}{c}
13 \\
1 
\end{array} \right)$ then the three cards $\left( \begin{array}{c}
4 \\
3 
\end{array} \right)$ next choose the second value $\left( \begin{array}{c}
12\\
1 
\end{array} \right)$  and two cards $\left( \begin{array}{c}
4 \\
2 
\end{array} \right)$.  This gives us $\left( \begin{array}{c}
13 \\
1 
\end{array} \right) \left( \begin{array}{c}
4 \\
3 
\end{array} \right) \left( \begin{array}{c}
12\\
1 
\end{array} \right) \left( \begin{array}{c}
4 \\
2 
\end{array} \right)$  = 
13(4)(12)(6) = 3744 possible hands.  


\bigskip

(e) Straight:  The five cards have consecutive numerical values.  The suits are irrelevant.  

This one's probably the most tricky.  Look at (f) first.  We still have$\left( \begin{array}{c}
9 \\
1 
\end{array} \right)$ possibilities for 
the highest value, but now we must choose the suit for each of the five cards, each time we have 
$\left( \begin{array}{c}
4 \\
1 
\end{array} \right)$ choices.  Therefore, there are$\left( \begin{array}{c}
9 \\
1 
\end{array} \right) \left( \begin{array}{c}
4 \\
1 
\end{array} \right)^5 = 9(4^5)$ = 9216 ways to do this.  
Again, like in (c), this is trusting the book literally.  More precisely we may wish to discount straight flushes again.  If so, we have $9216 - 36 = 9180$ hands.  

\bigskip

(f) Straight flush:  The hand is both a straight and a flush.  

The two choices here are what suit to have the flush in, $\left( \begin{array}{c}
4 \\
1 
\end{array} \right)$  ways, and what the highest 
card in the straight will be.  Because there need to be five cards, the choices for highest card are A, 
K, Q, J, 10, 9, 8, 7, and 6, or 9 possibilities.  We must choose one.  Therefore, there are $\left( \begin{array}{c}
9 \\
1 
\end{array} \right)$.  
We therefore have  $\left( \begin{array}{c}
4 \\
1 
\end{array} \right) \left( \begin{array}{c}
9 \\
1 
\end{array} \right)$
 = 4(9) = 36.  

\bigskip

\underline{More Extra Problems}

\bigskip

1. Let $R$ and $S$ be the relations on $\Bbb{Z}$ defined as follows:

    $a R b$ if and only if $2a + 3b \equiv 0 \mod 5$
    
 $a S b$ if and only if $a + 3b \equiv  0 \mod 5$
    
    Are $R$ and $S$ equivalence relations?  If not, which properties do they hold.  Prove your results.\
    
    Let's start by looking at some tables for these relations. For these tables, I've computed $2a$ (left side) $+3b$ (top) $\mod 5$ for $R$, and likewise for $S$.  
    
 \begin{tabular}{|c|ccccc|}
 \hline
 R & 0 & 1 & 2 & 3 & 4\\
 \hline
 0 & 0 & 3& 1& 4& 2\\
 1 & 2& 0 &3&1&4\\
 2 &4 &2 & 0 &3 &1 \\
 3 &1&4&2&0&3\\
 4 &3&1&4&2&0\\
 \hline
 \end{tabular}  \begin{tabular}{|c|ccccc|}
 \hline
 S & 0 & 1 & 2 & 3 & 4\\
 \hline
 0 & 0 & 3& 1& 4& 2\\
 1 & 1& 4 &2&0&3\\
 2 &2 &0 & 3 &1 &4 \\
 3 &3&1&4&2&0\\
 4 &4&2&0&3&1\\
 \hline
 \end{tabular}
 
 From the $R$ table, $R$ {\em is} an equivalence relation.  In fact, $R$ is the relation ``=''.  The only things related to themselves are themselves.  Therefore this relation is RST, and not irreflexive, but it is anti-symmetric (along with being symmetric) because the only elements related each other are themselves.  
 
 From the $S$ table, $S$ is not an equivalence relation.  It isn't reflexive: 1 is not related to 1.  It's also not irreflexive, because 0 is related to 0.  It is not symmetric because 1 is related to 2, but 2 is not related to 1.  It {\em is} anti-symmetric, because the only element related in a symmetric fashion is 0 to itself, but $0=0$.  Finally, it is not transitive.  This can be seen by $1S3$ and $3S4$, but it 1 is {\em not} related to 4.  
    
\pagebreak   
    
2.  How many partitions are there of a set with $n$ elements?

This is a long and complicated question.  Here's an idea:  count onto functions from $\{1, \dots, n\}$ with the target growing larger from size 1 to $n$.  Even that part is difficult.  To do it, count all functions to the target, then uncount those that miss one, then recount those that miss two (because you uncounted them twice), and so on.  The ultimate answer from this perspective is a double sum, finally divided by $n!$ because it doesn't matter which part is which.  Ask me if you're interested in seeing the 2-page long answer to this question.  I'll happily give it to you.  The point here is to try.  And to probably not get an answer, but to make some progress and not make mistakes.  There is {\em definitely} not a nice pattern.

\bigskip

3.  Present a combinatorial proof of: 
\[\left( \begin{array}{c}
n+m \\
r 
\end{array} \right)  = \sum_{i=0}^r \left( \begin{array}{c}
n \\
i 
\end{array} \right) \left( \begin{array}{c}
m \\
r-i 
\end{array} \right) \]

This one's not so bad.  The LHS counts the number of ways to select an $r$-element subset from two sets combined which have $n$ and $m$ elements each.  The right hand side breaks this into cases, based on how many elements are from the $n$ element set.  First, $i = 0$ is the ways to select 0 elements from the $n$-element set, and then all $r$ from the $m$-element set.  Then, $i = 1$ is the ways to select 1 element from the $n$-element set, and then the remaining $r-1$ elements from the $m$-element set.  This continues up to $i = r$ where all elements are from the $n$-element set and none from the $m$-element set.  

\end{document}