\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9.5in}

\begin{document}

\handout{ps6}{Problem Set 6}{March 15, 1994}

\pset{6}

{\bf Reading:\ }Maurer \& Ralston, Chapter 4.

\medskip

The problems are divided into oral problems (prefixed~``{\bf O}'') and
written problems (prefixed~``{\bf W}'').
The oral problems are due in tutorial on Monday, March 28.
The written problems are due at the beginning of class on March 29.

\bigskip

\begin{problems}

\oproblem 
Show that in any set of 12 integers, there are two whose difference 
is divisible by~11.  [{\em Hint:\ } First show that any set of 3 integers
has two whose difference is even.]

\oproblem
How many edges are possible in an undirected graph on $n$ nodes?
How many undirected graphs are possible on $n$ nodes?
(The nodes are labelled and therefore distinguishable, so
$G_1=(V, E_1)$ and $G_2=(V, E_2)$ where $V=\{1,2,3\}$, 
$E_1=\{(1,2)\}$ and $E_2=\{(1,3)\}$ are different graphs.)

\remove{
  \oproblem 
  Show that in any set of 10 people there are either four mutual friends
  or three mutual strangers (the ``is a friend of'' relation is symmetric).
  (\hint Recall from Problem Set 2 that in any set of 6 people
  there are either 3 mutual friends or 3 mutual strangers.)
}
%%	Ramsey Theorem:
%%  	A good written problem would be to prove Ramsey's general theorem
%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
%%	either a k-clique or an l-ind.set.
%%	Do this by induction--assume true for (k-1,l) and (k,l-1).

\oproblem 
Let $[n]$ denote the set $\{1,2,3,\ldots, n\}$ and
for any set $X$, let $2^X$ denote the set of all subsets of $X$.
(Recall that the empty set and $X$ itself are both subsets of $X$.)
How many elements does $2^{[8]}$ contain? 
How many elements does $2^{[n]}$ contain? 
How many elements does $2^{2^{[8]}}$ contain?

\oproblem 
In how many ways can we select a batting order of 9 ballplayers 
from a team of 24?

\oproblem
Evaluate $16 \choose 4$ and $17 \choose 5$.
What is the ratio between $n+1 \choose k+1$ and $n \choose k$?

\oproblem
Without using the formula for $n \choose k$,
prove the identity
\[
{s-1\choose 0} + {s\choose 1} + \cdots + {s+n-2\choose n-1}+ {s+n-1\choose n} 
= 
{s+n\choose n}.
\]
where $s$ and $n$ are positive integers.
(\hint If $X$ is an $(s+n)$-set\footnote{That is, a set containing
$s+n$ elements}
and $Y=\{ y_1, y_2, \ldots, y_n\}$ is a specific $n$-subset of $X$, 
what is the number of $n$-subsets of $X$ for which $y_r$ is the first member
of $Y$ not in the subset?)

\oproblem
How many outcomes are there when 3 distinguishable dice are thrown?
Show that there are only 56 possible outcomes
when 3 indistinguishable dice are thrown.
What is the number of possible outcomes when $n$ indistinguishable
dice are thrown?


\newpage
\oproblem
Calculate the coefficient of 
\begin{problemparts}
\problempart $x^5$ in $(1+x)^{11}$;
\problempart $a^2b^8$ in $(a+b)^{10}$;
\problempart $a^6b^6$ in $(a^2+b^3)^5$;
\problempart $x^3$ in $(3+4x)^6$.
\end{problemparts}

\remove{
  \oproblem
  Show that the number of different positions possible after four
  moves (total) in a game of tic-tac-toe is 756.
}

%%		from M&R, # 4.3.21 and 4.3.22
\oproblem 
A computer operating system requires file names to be exactly four letters
long; uppercase and lowercase letters are distinct.
\begin{problemparts}
\problempart
How many possible file names are there?
\problempart
The operating system is changed so that uppercase and lowercase are no
longer distinct.  Figure out the new number of file names in two ways:
applying the division rule to {\bf (a)} and directly.
\problempart
The operating system is changed so that file names may be {\em up to\ }
four letters long.  Repeat {\bf (a)} and {\bf (b)}.  Can the division
rule still be used?
\end{problemparts}

%%		from M&R, # 4.7.23
\oproblem
How many ways can $b$ indistinguishable balls be placed in $u$ 
distinguishable urns if each urn must contain at least $k$
balls?  (Assume $k\leq b/u$; otherwise it's impossible.)

%%		adapted from M&R, # 4.8.1 & 4.8.3
\oproblem
In 6.042, 10 students are taking 6.002, 15 are taking 6.003
and 19 of the 44 students are taking neither.
Also, 18 are taking 6.170, 3 of whom are also taking 6.002
and 6 of whom are also taking 6.003 
(but none of whom is taking all~3.)\footnote{These are the actual numbers!}
%%	=> 9 students taking just 6.170
\begin{problemparts}
\problempart
How many 6.042 students aren't taking any of these other three classes? % 10
\problempart 
How many are taking both 6.002 and 6.003?	% 0
\problempart 
How many are taking 6.002 but not 6.003?	% 10
\problempart
How many are taking 6.003 but not 6.002?	% 15
\problempart 
How many are taking 6.003 but neither of the other two?		% 9
\problempart 
How many are taking 6.002, possibly 6.003, but not 6.170?	% 7
\problempart
How many are taking 6.002 and/or 6.170 but not 6.003?		% 19
\end{problemparts}


%%		from M&R, # 4.8.9
\oproblem
Explain why an integer between 2 and 100 is prime if and only if either
(a) it is a prime less than 10, or 
(b) no prime less than 10 divides it.
Now use the Inclusion-Exclusion Principle to compute the number
of primes less than 100. 
(You may know other methods that will answer this question faster,
but if we replaced 100 by 1,000,000, this method would win.)


\newpage
%%		from M&R, # 4.7.5
\wproblem	
How many ways can 4 balls be placed in 3 urns if 
\begin{problemparts}
\problempart both the balls and the urns are distinguishable;
\problempart the balls are distinguishable but the urns are not;
\problempart the urns are distinguishable but the balls are not;
\problempart neither the balls nor the urns are distinguishable.
\end{problemparts}


%	inclusion-exclusion
\wproblem {\bf Derangements.}	% taken from Biggs, p. 73.

An inefficient secretary has $n$ letters and $n$ addressed envelopes
for them.  In how many ways can the secretary achieve the feat of 
putting every letter in the wrong envelope?
This number is called the number of \defi{derangements}, $D_n$.
\begin{problemparts}
\problempart 
How many ways are there of achieving the feat with $n=4$?
Write down each of the different ways as a permutation of $\{1,2,3,4\}$.
(For example, $2341$ represents putting letter number 2 in envelope number 1,
letter 3 in envelope 2, letter 4 in envelope 3, and letter 1 in envelope~4.)
\problempart 
The number of derangements $D_n$ is 
the number of permutations of $n$ elements that leave no element fixed.
That is, it is the number of permutations $\pi$ of $\{1,2,\ldots,n\}$
such that $\pi(i)\neq i$ for all~$i$.
Let $A_i$ denote the subset of permutations that leave $i$ fixed.
What is $D_n$ in terms of $n$ and the sets $A_i$?
\problempart 
Let $\alpha_r$ be the cardinality of the intersection of the $A_i$
taken $r$ at a time, so
\[
\alpha_r =  \sum_{i_1<i_2<\cdots<i_r} 
			|A_{i_1}\cap A_{i_2} \cap \cdots \cap A_{i_r}|,
\]
where the $i_j$ are (distinct) integers between 1 and~$n$.
(Writing ``sum over $i_1<i_2<\cdots<i_r$'' is a slick way of saying 
``sum over all the different $r$-subsets $\{i_1,\ldots,i_r\}$''.)
\\
\remove{
  \begin{eqnarray*}
  \alpha_1 & =& \sum_{i=1}^n |A_i|,\\
  \alpha_2 & =& \sum_{i<j} |A_i\cap A_j|,\\
  \vdots \\
  \alpha_r & = & \sum_{i_1<i_2<\cdots<i_r} 
			  |A_{i_1}\cap A_{i_2} \cap \cdots \cap A_{i_r}|,
  \end{eqnarray*}
  so $\alpha_r$ is the cardinality of the intersection of the $A_i$
  taken $r$ at a time.
}
Express $D_n$ in terms of $n$ and the $\alpha_1,\ldots,\alpha_n$.
\problempart 
Show 
\[
D_n = n! \left( 1 - {1\over 1!} + {1\over 2!} -\cdots +(-1)^n {1\over n!}
\right)
\]
by computing $\alpha_r$ as the number of ways to choose the $r$ integers
times the number of ways of permuting the rest.
%	\problempart
%	Give a tight asymptotic ($\Theta$) bound on $D_n$.
\end{problemparts}

%	\wproblem 
%	Compute the Bell number.

\newpage
\wproblem {\bf Catalan numbers.}

In Problem Set 3, we saw a definition of well-formed strings of parentheses
and brackets. 
We say a string of parentheses is well-formed if it is either
$(\,)$, $(\,w\,)$, or $w\,v$, where $w$ and $v$ are well-formed.
In this problem, you will count the number $C(n)$ of well-formed strings
of parentheses containing $n$ left-parentheses and $n$ right-parentheses.
The numbers $C(n)$ are called the \defi{Catalan numbers}.
\begin{problemparts}
\problempart 
What is the total number of strings (well-formed or not) containing
$n$ left-parentheses and $n$ right-parentheses?
\problempart 
There is a very clever argument for calculating $C(n)$ 
using something called \defn{the reflection principle}.
We will illustrate graphically the application 
of the reflection principle to this problem.
Consider counting the number of ways of walking from the origin $(0,0)$
of the $x,y$-plane to the point $(2n,0)$.
The walk must consist of exactly $2n$ steps, where each step
goes right one unit and either up or down one unit.
The figure below shows such a walk that happens not to go above $y=1$
for the first 7 steps.
What is the number of ways of performing such a walk?
Suppose now that you may never go below the $x$-axis. 
How is the number of such walks related to $C(n)$?
\problempart
Let us now count the number of walks that {\em do}
go (strictly) below the $x$-axis.
Argue that the number of such walks is equal to the number of walks
that start instead at $(0,-2)$ and finish at $(2n,0)$ (but may cross the 
$x$-axis many times).
Do this by finding a bijection between the two sets of walks (see figure) 
that justifies the term ``reflection principle''.


\begin{figure}[htb]
\setlength{\unitlength}{.3in}

\begin{picture}(14,5)(-7,-3.5)

\put(-2,0){\vector(1,0){9}}
\multiput(-1,-0.1)(1,0){8}{\line(0,1){.2}}
\put(0,-3.5){\vector(0,1){5}}
\multiput(-0.1,-3)(0,1){5}{\line(1,0){.2}}

\multiput(-1,-1)(.2,0){37}{\line(1,0){.1}}

{\thicklines
\put(0,0){\line(1,1){1}}
\put(1,1){\line(1,-1){1}}
\put(2,0){\line(1,1){1}}
\put(3,1){\line(1,-1){1}}
\put(4,0){\line(1,-1){1}}
\put(5,-1){\line(1,1){1}}
\put(6,0){\line(1,1){1}}
}
\put(0,-2){\line(1,-1){1}}
\put(1,-3){\line(1,1){1}}
\put(2,-2){\line(1,-1){1}}
\put(3,-3){\line(1,1){1}}
\put(4,-2){\line(1,1){1}}


\put(0,0){\circle*{.2}}
\put(1,1){\circle*{.2}}
\put(2,0){\circle*{.2}}
\put(3,1){\circle*{.2}}
\put(4,0){\circle*{.2}}
\put(5,-1){\circle*{.2}}
\put(0,-2){\circle*{.2}}
\put(1,-3){\circle*{.2}}
\put(2,-2){\circle*{.2}}
\put(3,-3){\circle*{.2}}
\put(4,-2){\circle*{.2}}
\put(6,0){\circle*{.2}}

\end{picture}
\end{figure}

\problempart
What is the number of walks 
that start at $(0,-2)$ and finish at $(2n,0)$ (but may cross the 
$x$-axis many times)?\\
Conclude that $C(n)$ is ${1\over n+1}{2n\choose n}$.

\problempart
Let $B(n)$ be the number of binary trees on $n$ nodes.
(Having only one child as a left child is different from having only 
one child as a right child, so for example there are
5 binary trees on 3 nodes.)
It turns out that $B(n)=C(n)$.
Show that this is true either by (a) giving a bijection between the
set of well-formed strings of parentheses ($n$ left and $n$ right)
or (b) by showing that both $B(n)$ and $C(n)$ satisfy the recurrence
\[  T(n) = \sum_{k=0}^{n-1} T(k)\cdot T(n-1-k)
\]
where $n\geq 1$ and $T(0)=1$.
\end{problemparts}


\end{problems}


\end{document}


