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


\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln8.pdf}
{Week 8 Notes}, Rosen \S4.3, 4.6}
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{8}

% SOURCE:  Counting.tex in problemrepository
% Prepared by Eric Ho

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1

\begin{problem}
{\bf Fun with Counting.}
\begin{problemparts}

\problempart
How many permutations of the word \emph{statistics} are there?
\solution{
There are 10 letters. The frequency of each letter is: $s=3,t=3,a=1,i=2,c=1$. 

By theorem 6.2, there are $\frac{(r_1+r_2+...+r_n)!}{r_{1}!r_{2}!...r_{n}!}$
permutations of the set $A$ where each element $a_i$ is repeated exactly $r_i$
times.  As a result, the number of permutations of the word \emph{statistics}
= $\frac{10!}{3!3!2!} = 50400$.
}

\problempart
A juggler plans to juggle 15 rings for his final\'e---more than any other
circus performer has ever managed.  In his bag are 9 red rings, 11 blue
rings, 13 white rings, and 15 rings striped with all three colors.  He
must select at least two of each kind of ring to be patriotic.  An example
of a patriotic choice of 15 rings would be: 2 red, 6 white, 3 blue and 4
striped.  How many different patriotic choices are there for the 15 rings?

\solution{
This is a ``stars and bars'' problem: the same as asking how many ways
there are to arrange 15 stars (the rings) and three bars such that there
are at least two stars in each of the four groups (the kinds of rings)
delimited by the bars.  Reserving eight stars for this purpose leaves 7
stars, so there are
\[
\binom{3 + 7}{3} = \binom{10}{3}.
\]
Note that the initial number of each kind of ring available to
the juggler is irrelevant as long as there are at least 9 of each.
}


\problempart
How many ways are there to distribute eight balls into six distinct
boxes with the first two boxes having collectively at most four balls
if the balls are identical?

\solution{
Let us consider placing $n$ balls into $k$ boxes so that exactly $r$
balls are placed in the first two boxes. This can be done in
\[
\binom{r+2-1}{2-1}\binom{(n-r)+(k-2)-1}{(k-2)-1}
\]
ways, since there are $\binom{r+2-1}{2-1}$ ways to
place $r$ balls into first two boxes (by stars and bars)
and $\binom{(n-r)+(k-2)-1}{(k-2)-1}$ ways to place the remaining $n-r$
balls into the other $k-2$ boxes. We can place the balls into boxes,
so that {\em at most} $r$ balls go into the first two boxes, in
\[
\sum_{i=0}^r{\binom{i+2-1}{2-1}\binom{(n-i)+(k-2)-1}{(k-2)-1}}
\]
ways. In particular for $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{\binom{i+2-1}{2-1}\binom{(8-i)+(6-2)-1}{(6-2)-1}} = 1056{.}
\]
}



\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\begin{problem} %source: spring00 ps7-5
% source: spring96 ps7
% topic: combinatorics, algebraic manipulation
Prove the following identity by algebraic manipulation and
by giving a combinatorial argument:


\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\]
\solution{ 
Algebraic:
\begin{eqnarray*}
\binom{n}{k}\binom{n-k}{r-k} &= &\frac{n!}{k!(n-k)!}\frac{(n-k)!}{(r-k)!(n-r)!}\\
&= &\frac{n!}{(n-r)!k!(r-k)!}\\
&= &\frac{n!r!}{r!(n-r)!k!(r-k)!}\\
&= &\frac{n!}{r!(n-r)}\frac{r!}{k!(r-k)!}\\
&= &\binom{n}{r}\binom{r}{k}\\\
\end{eqnarray*}

Combinatoric:
With a group of $n$ balls, I wish to pick a group of $k$ balls and another group of 
$r-k$ balls.  I could do it by picking a group of $r$ balls and then partition it
into sets of $k$ and $r-k$.  On the other hand, I can first pick $k$ balls and then pick $r-k$ balls
from the remaining $n-k$ balls. 
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem 3
\begin{problem} {\bf Do you know this person?}

Suppose that every two people either know one another or else are
strangers.  How many people must there be in a room to guarantee that
there are either 6 people who all know each other or 6 people who are all
strangers to one another?

The solution to this problem is a number called the Ramsey number $R(6, 6)$.  
The solution to the simpler problem involving groups of only 5 people is 
called $R(5,5)$.  Last week, we solved a still simpler version of this
problem involving groups of just 3 people using the pigeonhole principle.  
Finding $R(5, 5)$ and $R(6, 6)$ is a bit more tricky.  The following is taken
from, \emph{Ten Lectures on the Probabilistic Method}, by Joel Spencer:

\begin{quotation}\noindent
Erd\"os [possibly the 20th century's top mathematician] asks us to
imagine an alien force, vastly more powerful than us, landing on Earth
and demanding the value of $R(5, 5)$ or they will destroy our planet.
In that case, he claims, we should marshall all our computers and all
our mathematicians and attempt to find the value.  But suppose,
instead, that they ask for $R(6, 6)$.  In that case, he believes, we
should attempt to destroy the aliens.
\end{quotation}

Given rumors that a new fleet is forming on Xoros 19, we had better
take a stab at $R(6, 6)$.  For now, however, we will only try to prove
that $R(6, 6) > 17$.

\begin{problemparts}
\problempart If there are $n$ people in a room, then how many
different groups of two people are there?

\solution{
\[
\binom{n}{2}
\]
}

\problempart A {\em configuration} of a group of people is a setting
of who-knows-who.  For example, there are two possible configurations
of a group of just two people: either they know each other or they are
strangers.  How many different configurations are possible in a room
with $n$ people?

\solution{Since every two people either know each other or are
strangers, the number of configurations is

\[
2^{\binom{n}{2}}.
\]
}

\problempart Suppose that there is a specific group of six people who
all know each other.  How many configurations are possible with this
restriction?

\solution{
\[
2^{\binom{n}{2} - \binom{6}{2}}
\]
}

\problempart In a set of $n$ people, how many different subsets of six
people are there?

\solution{
\[
\binom{n}{6}
\]
}

\problempart 
There are at most
\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]
configurations in which some set of six people all know each other.  
Give an explanation to justify this answer.


\solution{There are $\dbinom{n}{6}$ different sets of six people.  For
each set of six people, there are $2^{\binom{n}{2} - \binom{6}{2}}$
configurations in which these people all know each other.  Therefore,
there are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some set of six people all know each other.
}

\problempart 
There are at most
\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]
configurations in which some six people either all know each other or
are all strangers.  Give an explanation to justify this answer.


\solution{
There are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people all know each other.  By the
same argument, there are at most this many configurations of six
people that are all strangers.  Therefore, there are at most

\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people either all know each other or
are all strangers.}

\problempart Use your answers to parts (b) and (f) to prove that there
exists a configuration of $17$ people such that no set of six people
all know each other or are all strangers.  This implies that $R(6, 6)
> 17$.

\solution{
By part (a), there are

\[
2^{\binom{17}{2}}
\]

configurations of 17 people.  By part (f) there are at most

\[
2 \cdot \binom{17}{6} \cdot 2^{\binom{17}{2} - \binom{6}{2}}
\]

configurations in which some set of six people either all know each
other or are all strangers.  If the first quantity is greater than the
second, then there must exist a configuration of 17 people such that
there is no set of six people that all know each other or are all
strangers.  The second quantity divided by the first is

\begin{eqnarray}
2 \cdot \binom{17}{6} \cdot 2^{- \binom{6}{2}} & \approx & 0.75.
\end{eqnarray}

Therefore, the first quantity is greater than the second, as desired.

The best known bounds are $102 \leq R(6, 6) \leq 165$.
Asymptotically, the simple technique outlined above gives a lower
bound on $R(k, k)$ that is within a factor of 2 of the best known.}

\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4

\begin{problem}
%Created by Eric Ho
%This is Lucas' theorem
%Reference: http://www.math.hmc.edu/funfacts/ffiles/30002.4-5.shtml

In this problem, we will prove
\begin{theorem*}[Lucas]

For all $n,k$ and prime number $p$, let the base $p$ representation of
$n$ be $(a_0,a_1,...,a_j)$ and the base $p$ representation of $k$ be
$(b_0,b_1,...,b_j)$.  Then
\[
\binom{n}{k} \equiv \binom{a_0}{b_0}\binom{a_1}{b_1}\cdots\binom{a_j}{b_j} \pmod{p}.
\]
\end{theorem*}

For example, if $n = 588, k=277, p=5$, then in base $p$, $n = 4323$ and
$k=2102$, and the theorem states that
\[
\binom{588}{277} = \binom{4}{2} \binom{3}{1} \binom{2}{0}
\binom{3}{2}\pmod{5}.
\]
We can use a
computer to verify that both sides yield a remainder of $4$ when divided
by $5$.

This is an interesting theorem because it tells us there are exactly
$(1+a_0)(1+a_1)(1+a_2)...(1+a_j)$ values of non-multiples of $p$ in the
$n^{th}$ row of Pascal's triangle.  The following steps will help you prove
this theorem.

\begin{problemparts}

\problempart
Show that
\[
k\binom{p^{r}}{k} = p^{r}\binom{p^{r}-1}{k-1},
\]
where $r=\log_p{n}$ and $0<k<p^{r}$.

\solution{ Plug $n=p^{r}$ in the right hand side of the formula yields
\begin{eqnarray*}
p^{r}\binom{p^{r}-1}{k-1} &= &n\binom{n-1}{k-1}\\
&= &k\frac{n}{k}\binom{n-1}{k-1}\\
&= &k\frac{n(n-1)!}{k(k-1)!(n-k)!}\\
&= &k\frac{n!}{k!(n-k)!}\\
&= &k\binom{n}{k}\\
&= &k\binom{p^{r}}{k}\\ 
\end{eqnarray*}
}

\problempart Argue that $p$ divides $\dbinom{p^{r}}{k}$. \hint: What are
the bounds on the number of powers of $p$ that divides the two sides of
the equation in (a)?  

\solution{ The right hand side of the equation in (a) is
$p^{r}\dbinom{p^{r}-1}{k-1}$.  \emph{At least} $r$ powers of $p$ divides
this term.  The left hand side of the equation in (a) is
$k\dbinom{p^{r}}{k}$.  \emph{At most} $r-1$ powers of $p$ divides $k$,
since $k<p^{r}$.  Therefore $p$ must divide $\dbinom{p^{r}}{k}$.}

The previous part implies that $\dbinom{p^{r}}{k}=0\pmod{p}$. 
The exception is when $k=0$ or $k=p^{r}$ in which
$\dbinom{p^{r}}{k}=1\pmod{p}$. 


\problempart
Show that $(1+x)^{p^{r}} = 1 + x^{p^{r}} \pmod{p}$. 

\solution{
Expand the left hand side of the equation using the binominal theorem.  
This yields $\binom{p^{r}}{1}1^{p^{r}} + \binom{p^{r}}{2}1^{p^{r-1}}x + ... + \binom{p^{r}}{p^{r}}x^{p^{r}}$. 
The coefficients of all middle terms are $0\pmod{p}$, whereas the coefficients for the first and last term 
is $1\pmod{p}$ (from (b)).  This yields the right hand side of the equation. 
}


\problempart
Show that $(1+x)^{588} = (1+x^{125})^{4}(1+x^{25})^{3}(1+x^{5})^{2}(1+x)^{3} \pmod{5}$
\solution{
It follows from (c): \\
\begin{eqnarray*}
(1+x)^{588} &= &(1+x)^{4(125)}(1+x)^{3(25)}(1+x)^{2(5)}(1+x)^{3}\\
            &= &(1+x^{125})^{4}(1+x^{25})^{3}(1+x^{5})^{2}(1+x)^{3} \pmod{5}   
\end{eqnarray*} 
}

\problempart
Show that
\[
\binom{588}{277}=
\binom{4}{2}\binom{3}{1}\binom{2}{0}\binom{3}{2}\pmod{5}.
\]
\hint What are the coefficients of $x^{277}$ on both sides of the equation in (d)?

\solution{
The coefficient of the $x^{277}$ term on the left hand side is $\binom{588}{277}$. 
For the right hand side, since $277 = 2*125 + 1*25 + 2*1$,  the $x^{277}$ term comes
exactly from the second term in $(1+x^{125})^{4}$, the first term in $(1+x^{25})^{3}$, 
and the second term in $(1+x)^{3}$.  Their coefficients are exactly $\binom{4}{2}$,
$\binom{3}{1}$, $\binom{2}{0}$, and $\binom{3}{2}$.  Multiplying them yields the
identity we are trying to show. 
}

\problempart
Briefly generalize parts (d) and (e) and prove the theorem. 

\solution{
Generalizing (e) yields the formula $(1+x)^{n} = (1+x^{p^{j}})^{a_0}(1+x^{p^{j-1}})^{a_1}(1+x^{p^{j-2}})^{a_2}...(1+x)^{a_j}$. 
Generalizing (f) implies that the coefficient of the $x^{k}$ term on the right hand side of the equation
comes from the $(b_0,b_1,...,b_j)^{th}$ corresponding term on the right, since 
$k={b_0}^{p^{j}}+{b_1}^{p^{j-1}}+ {b_2}^{p^{j-2}} + ... + {b_j}$.  Comparing coefficients
yields:

\\
\begin{center}
\[
\binom{n}{k} = \binom{a_0}{b_0}\binom{a_1}{b_1}...\binom{a_j}{b_j} \pmod{p}
\]
\end{center}

}

\end{problemparts}
\end{problem}



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



\end{document}                            


