\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln9.pdf}
{Week 9 Notes}, Optional: Rosen \S 4.3,4.6}

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{9}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}

A state Senate has fifteen Republicans and ten Democrats.  They are
creating a committee, which must have six people in it.  Since the
Republicans have a majority in the Senate, they insist on having a
majority on the committee. How many ways are there to form a committee
that satisfies the above conditions?

\solution{
We do these by breaking down the cases according to how many Democrats
are on the committee.
\begin{itemize}
\item No Democrats: There are $\binom{15}{6} = 5005$ such committees,
since we are choosing $6$ Republicans out of $15$.
\item One Democrat: There are are $\binom{15}{5}\binom{10}{1} = 30030$
committees.
\item Two Democrats: There are are $\binom{15}{4}\binom{10}{2} =
61425$ committees.
\end{itemize}

The total number of possible committees is the sum of the above three
numbers, which is $96460$.}
\end{problem}



\begin{problem}
%ROSEN 4.6 22

How many positive integers less than $1,000,000$ have exactly one
digit equal to $9$ and have a sum of digits equal to $13$.

\solution { 
  There are six choices for the position where $9$ appears.
  After that choice has been made, the problem reduces to figuring out
  how many ways are there to select a sequence of five positive
  integers summing to $4$ (since $13 - 9 = 4$).  This is the same as
  counting permutations of four stars and four bars; the first integer
  in the sequence corresponds to the number of stars before the first
  bar, the second to the number of stars between first and second
  bars, etc.  The total number of ways to permute four stars and four
  bars is $\binom{8}{4}$.  Therefore th number of positive integers
  less than $1,000,000$ that have exactly one digit equal to $9$
  and the sum of digits equal to $13$ is $6\binom{8}{4}$.
}

\end{problem}

\begin{problem}
Let $B(n)$ denote the number of equivalence relations on
$n$ elements.

\begin{problemparts}

\problempart Show that $B(n) \leq n!$.

\solution { 

Without loss of generality, we assume that the $n$-element set in
question is $\lbrace 1 \ldots n \rbrace$. 

Let's start with noticing a simpler upper bound - we can bound $B(n)$
by $2^{\frac{n^2-n}{2}}$ because an equivalence relation is reflexive
and symmetric. However $n!$ is much tighter bound.  

What else do we know about equivalence relations?  They partition a
set into "equivalence classes".  In fact every distinct partition of
the set of $n$ elements corresponds to an equivalence relation.
However it is hard to count the number of partitions exactly, there is
no simple closed form solution for this.  To deal with this, we
associate a function to each equivalence relation.  To be more precise
for any equivalence relation $\equiv$ on $\{ 1 \ldots n \}$, define a
function $f_{\equiv}$ by
\[
f_{\equiv}(i) = \min\{ j\ |\ j \equiv i\}{.}
\]

The function $f_{\equiv}$ is essentially providing a naming scheme for
the equivalence classes, where each class is named by the smallest
member. Now we can bound the number of ways this function can be
constructed. 

For any $\equiv$, given an element $i$, $f_{\equiv}(i)$ must be less
than or equal to $i$, because if $f_{\equiv}(i)$ is in the same
equivalence class as $i$, and it is the smallest element of that
equivalence class, so it cannot exceed $i$.  Hence$1\leq
f_{\equiv}(i)\leq i$, so there is at most one choice for
$f_{\equiv}(1)$, at most two choices for $f_{\equiv}(2)$,\dots, and at
most $n$ choices for $f_{\equiv}(n)$. Thus we have at most
$n(n-1)\cdots 1=n!$ possibile $f_{\equiv}$'s and therefore at most
$n!$ possibilities for a function $f_{\equiv}$.

We conclude the proof by showing that every equivalence relation
$\equiv$ yields a different function $f_{\equiv}$.  To see this,
suppose that $\equiv_1$ and $\equiv_2$ are such that $f_{\equiv_1} =
f_{\equiv_2}$. Given any $i,j$, if $i\equiv_1 j$ we have
$f_{\equiv_1}(i)=f_{\equiv_1}(j)=f_{\equiv_2}(j)=f_{\equiv_2}(i)$ so
$i\equiv_2 j$. Similarly, for any $i,j$, such that $i\equiv_2 j$, we
can conlude that $i\equiv_1 j$.  Hence $\equiv_1$ and $\equiv_2$ are
the same equivalence relation.

}

\problempart Show that $B(n) \geq 2^{n-1}$.

\solution { Again, we assume that the $n$-element set in question is
$U ::= \lbrace 1 \ldots n \rbrace$.  Consider a subset $S$ of $\{1
\ldots n-1 \}$.  Then the partition of $U$ into $S$ and
$U\mathrel{\backslash}S$ defines an equivalence relation.  Since
different choices of $S$ yield different partitions, and hence
different equivalence relations, we conclude that there are at least
as many equivalence relations on $U$ as subsets of $\{1 \ldots n-1
\}$.  Therefore there are at least $2^{n-1}$ distinct equivalence
relations on $U$.  }

\end{problemparts}
\end{problem}

\begin{problem}
Prove the following identity both by (a) algebraic manipulation and by
(b) giving a combinatorial argument:

\[{2n \choose 2} = 2{n \choose 2} + n^2\]

\solution{
By algebra,
\begin{eqnarray*}
{2n \choose 2} &=& \frac{2n(2n-1)}{2} \\
&=& n(2n-1)\\
&=& n(n-1) + n^2 \\
&=& 2{n \choose 2} + n^2
\end{eqnarray*}

The left hand side is the number of ways to choose two elements out of
$2n$.  Counting in another way, we first divide the $2n$ elements into
two sets of $n$ elements.  Either we choose both elements out of first
$n$ element set, both out of the second $n$ elements set, or one
element out of each set.  The number of ways we can do this is: ${n
\choose 2}$, ${n \choose 2}$, and $n^2$, respectively.  The sum of
these is the right hand side.  
}

\end{problem}


% Spring 01, pset 7, problem 3

\begin{problem}
George's 6.042 table has 12 students, who are supposed to break up
into 4 groups of 3 students each.  George has observed that the
students waste too much time trying to form balanced groups, so he
decided to pre-assign students to groups and email the group
assignments to his students.

How many \emph{different} group assignments are possible?
(Clarification: There is no ``numbering" of the groups. All that
matters is who ends up with whom. Two group assignments are different
if they differ in at least one group.)

\solution{ First note that given a list of $12$ names, there is a
simple way to break it up into four groups of three students each;
namely take first three names as first group, next three as second,
and so on.

For instance, say the list is ABCDEFGHIJKL. The above method gives the
following grouping: \fbox{ABC}\fbox{DEF}\fbox{GHI}\fbox{JKL}. There
are $12!$ different permutations of the list. However, not all
permutations result in a different group assignment. For example, if B
and C change places, the list is different but the assignment is the
same. We will try to see how many different lists represent the
\emph{same} group assignment.

There are $3!$ ways to move the people in \fbox{ABC} around without
changing the assignment. The same holds for all other groups. This
means that there are $(3!)^4$ ways to move people around within their
group.
 
Then, if \fbox{ABC} switches places with \fbox{JKL} we still get the
same assignment. There are $4!$ ways to permute the groups without
actually affecting the assignment.

So, there are $4! (3!)^4$ different lists that end up producing the
same assignment.

There are $12!$ possible lists, and each assignment is represented by
\emph{exactly} $4! (3!)^4$ different lists so according to the
\emph{division rule} there are
\[
\frac{12!}{4!\cdot(3!)^4}=15400
\]
 different assignments.

\paragraph{Alternative solution} Another way to see this is as follows:

We need to compute the number of partitions of a set of 12~students
into 4~groups of 3~students each. We first compute the number of
partitions given that the groups are numbered. The first group can be
selected in $\binom{12}{3}$ ways, the second in $\binom{9}{3}$ ways,
the third in $\binom{6}{3}$ ways, and the fourth in $\binom{3}{3}$
ways. Therefore, the number of different partitions is
\begin{displaymath}
  \binom{12}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}
  =
  \frac{12!}{(3!)^4}= 369600.
\end{displaymath}
Now, to account for the fact that the groups are not numbered, we need
to divide $369600$ by the number of permutations of the numbered
groups, $4! = 24$. To conclude, the number of tutorials we can have in
6.042 is at most $369600 / 24 = 15400$.
}

\end{problem}



% Spring 99 Quiz2 Prob 6
\begin{problem} The \emph{king positioning} in an
arrangement of a deck of 52 playing cards is the sequence of numerical
positions in the deck, from one to 52, of the four successive kings.  For
example, the king positioning $(1,2,3,4)$ means all the kings come at the
beginning of the deck.  The king positioning $(1,18,35,52)$ describes the
situation in which the kings are spaced uniformly---with exactly 16 cards
between successive kings.

\begin{problemparts}
\problempart How many king positionings are there?

\solution{$\dbinom{52}{4}$.}

\problempart How many king positionings are there in which \emph{no two
kings are adjacent}?

\solution{Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\dbinom{45+4}{4}$ ways to do this.}

\problempart Of the $52!$ possible arrangements of the deck, how many
have no two kings adjacent?

\solution{Now in each of the previous patterns of stars and bars, the
kings can be permuted in $4!$ ways and the remaining cards can be permuted
in $48!$ ways, so the total number of desired arrangements is
\[
\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).
\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi
}


\end{problemparts}
\end{problem}

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% EXTRA PROBLEMS

\begin{problem}
Let us redraw Pascal's Triangle in the following way:

\begin{center}
\begin{tabular}{lcccccccc}
$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$ \\
$\cdot$ & $\cdot$ & $\cdot$ & $\cdot$ & $\cdot$& $\cdot$  & $\cdot$ & $\cdot$ \\\end{tabular}
\end{center}

Now let n be a nonnegative integer and let k be an integer with $0
\leq k \leq n$.  Define $path(n,k)$ to be the number of paths from the
top left corner (the entry $\binom{0}{0} = 1 $) to the entry
$\binom{n}{k}$, where each path is composed of only two possible types of
moves: 

type $(a)$: from any entry in the Triangle we can move to the entry immediately below the current entry (i.e. in the next row) 

type $(b)$: from any entry in the Triangle we can move to the entry
immediately below and to the right of the current entry (i.e. in the next row).

 We define $path(0,0)=1$.  Prove that the value of an entry 
$\binom{n}{k}$ of Pascal's
triangle represents $path(n,k)$, the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.

\solution {
Notice that $path(n,0)=1$, (we must move straight down to reach $\binom{n}{0}$) and $path(n,n)=1$, (we must move diagonally to reach $\binom{n}{n}$).

Observe that each path from $\binom{0}{0}$ to $\binom{n}{k}$ is either

(i) a path from $\binom{0}{0}$ to $\binom{n-1}{k}$ followed by one vertical move $(a)$, or 

(ii) a path from $\binom{0}{0}$ to $\binom{n-1}{k-1}$ followed by one diagonal move $(b)$.

So, the total number of paths 
is $path(n,k) = path(n-1,k)+path(n-1,k-1)$.
The numbers $path(n,k)$
are computed in exactly the same way as the binomial coefficients
$\binom{n}{k}$ starting with the same initial values.  Hence it
follows that for all integers n and k with $0 \leq k \leq n$, \[
path(n,k) = \binom{n}{k}\] Thus the value of an entry $\binom{n}{k}$ of
Pascal's triangle represents the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.  And, we
have derived another combinatorial interpretation of the numbers $\binom{n}{k}$.  }

\end{problem}

\begin{problem}

In a horse race with five horses, how many possible rankings are
there, assuming that ties are allowed.  What about six horses?

\solution{ 

Let $f(n)$ denote the number of possible rankings in an
$n$-horse race, where $n \in \mathbb{N}$.  Clearly $f(0) = 1$.  Let $g(n,
i)$ be the number of possible rankings in an $n$ horse race which ends
with $i$ ties for first place.  There are $\binom{n}{i}$ ways of
selecting which horses end in first place, and then $f(n-i)$ ways of
having the other horses ranked.  Therefore $g(n,i) = \binom{n}{i}
f(n-i)$.

Since $f(n) = \sum_{i=1}^{n} g(n,i)$, we conclude that $f$ satisfies
$f(n) = \sum_{i=1}^{n} \binom{n}{i} f(n-i)$.  Using this we can
easily compute the first few values of $f$, including $f(5)$ and
$f(6)$:

\begin{eqnarray}
  f(1) = \binom{1}{1} f(0) & = & 1 \nonumber \\
  f(2) = \binom{2}{1} f(1) + \binom{2}{2} f(0) & = & 3 \nonumber \\
  f(3) = \binom{3}{1} f(2) + \binom{3}{2} f(1) + \binom{3}{0} f(0) & = & 13 \nonumber \\
  f(4) = \binom{4}{1} f(3) + \binom{4}{2} f(2) + \binom{4}{1} f(1) + \binom{4}{0} f(0) & = & 75 \nonumber \\
  f(5) = \binom{5}{1} f(4) + \binom{5}{2} f(3) + \binom{5}{2} f(2) + \binom{5}{1} f(1) + \binom{5}{0} f(0)
 & = & 541 \nonumber \\
  f(6) = \binom{6}{1} f(5) + \binom{6}{2} f(4) + \binom{6}{3} f(3) + \binom{6}{2} f(2) + \binom{6}{1} f(1) + \binom{6}{0} f(0)
 & = & 4683 \nonumber 
\end{eqnarray}

}

\end{problem}



\begin{problem}
Give the number of seven-card poker hands that contain

\begin{problemparts}

\problempart
four cards of one kind and three cards of a second kind?

\problempart
three cards of one kind and pairs of each of two different kinds?

\problempart
pairs of each of two different kinds, and three other cards all
of different kinds?

\problempart
cards of seven different kinds?

\problempart
a seven card flush?

\problempart
a seven card straight?

\problempart
a seven card straight flush?

\solution{
TO BE ADDED
}

\end{problemparts}
\end{problem}

\begin{problem}

Prove the following identity both by (a) algebraic manipulation and by
(b) giving a combinatorial argument:


\begin{problemparts}

\problempart \[{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}\]

\solution{
By algebra,
\begin{eqnarray*}
{n \choose r}{r\choose k} &= & \frac{n!}{r!(n-r)!} \cdot
\frac{r!}{ k! (r-k)!} \\
&=& \frac{n!}{k! (n-k)!} \cdot \frac{(n-k)!}{(r-k)! (n-k - (r-k))!} \\
&=& {n \choose k}{n-k \choose r-k}
\end{eqnarray*}

Combinatorially, the left hand side is the number of ways of
choosing $r$ elements out of $n$.  From those $r$, you further choose
$k$ elements.  So, we have three types of elements:  $k$ elements
which are choosen twice, $r-k$ elements which are chosen only on
the first pass, and elements that were never choosen.

In the right hand side, you first choose your $k$ elements.  Then,
from the remaining $n-k$ elements, you choose $r-k$ elements. 
}


\problempart \[{2n \choose 2} = 2{n \choose 2} + n^2\]
\solution{
By algebra,
\begin{eqnarray*}
{2n \choose 2} &=& \frac{2n(2n-1)}{2} \\
&=& n(2n-1)\\
&=& n(n-1) + n^2 \\
&=& 2{n \choose 2} + n^2
\end{eqnarray*}

The left hand side is the number of ways to choose two elements out of
$2n$.  Counting in another way, we first divide the $2n$ elements into
two sets of $n$ elements.  Either we choose both elements out of first
$n$ element set, both out of the second $n$ elements set, or one
element out of each set.  The number of ways we can do this is: ${n
\choose 2}$, ${n \choose 2}$, and $n^2$, respectively.  The sum of
these is the right hand side.  
}

\problempart \[ \sum_{k=0}^n 2^k {n \choose k} = 3^n\]
\solution{
Algebratically,
\begin{eqnarray*}
3^n &=& (2+1)^n \\
&=& \sum_{k=0}^n 2^k {n \choose k} 1^{n-k} \\
&=& \sum_{k=0}^n 2^k {n \choose k} 
\end{eqnarray*}

Given a set of $n$ elements, we want to divide it into three disjoint
subsets: $A$,$B$, $C$.  Each element can go into any of the three subsets,
so there are $3^n$ such divisions.

Another way to count the number of division is to first pick $n-k$ elements
to be put in $A$.  This can be done in ${n \choose n-k} = {n \choose k}$
ways.  Then, the remaining $k$ elements can be split
between $B$, $C$ in $2^k$ ways.  Summing over all possible values of $k$
gives us the right hand side.
}

\end{problemparts}
\end{problem}

\begin{problem}
%ROSEN 4.Supp 52

A witness to a hit-and-run accident tells the police that the license
plate of the car in the accident, which contains three letters
followed by three digits, starts with letters AS and contains both the
digits 1 and 2.  How many different license plates can fit this
description.

\solution{
TO BE ADDED.
}

\end{problem}

