\documentstyle[12pt,xypic,macpsfig,psfig,amssymb]{article}
\input{macros-course}

%\addtolength{\topmargin}{-.2in}
%\setlength{\textheight}{9in}

\setcounter{page}{0}

\begin{document}

\handout{pqsol2}{Solutions to Review for Quiz 2}{April 22, 1997}

\long\def\comment#1{}
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem

Prove that among any set of 150 natural numbers, there must be three
numbers, $a$, $b$, and $c$, such that all the pairwise differences,
$a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70.

\bigskip

\begin{proof}
Use Pigeonhole. \\
{\bf Pigeons} The 150 numbers. \\
{\bf Holes} The natural numbers mod $70$. \\
There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, 
three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences
are equivalent to $0$ modulo $70$, therefore they are divisible by $70$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem

For each of the following sets, decide whether the set is countable or
uncountable and prove your answer.
(If an answer to one part of the question follows from an answer you
have already given to another part, then you need only show that is follows
-- you don't need to prove the second part from scratch.) \\

\bparts
\ppart The set $E$ of all the even natural numbers. \\

\bigskip
This set is countable.  The function $f(n) = 2n$ is a bijection from $\naturals$
to $E$.

\bigskip

\ppart The set of all subsets of $E$. \\
\bigskip
This set is uncountable.  The power set of any set has bigger cardinality than
the original set.  \\

\bigskip
\ppart The set of all finite subsets of $E$. \\
\bigskip
\ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } \\
Each of the $S_{i}$ is countable and the set under question  is the countable 
union of all the $S_{i}$, therefore it is countable. \\
\bigskip

\ppart The set of all even-size finite subsets of $E$. \\
\bigskip
This set is countable, being a subset of the set in part (c). \\

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%8
\problem

The CS department has just completed a revamping of its curriculum.  
The following 10 courses are now required:
6.001, 6.002, 6.003, \dots , 6.009, and 6.042.\\
In addition, for every $i,j$, 6.00$i$ is a prerequisite of 6.00$j$ or 6.0j,
if $i < j$ and $gcd(i,j) > 1$.   \\

\vspace{.01in}

\bparts
\ppart Write down all the elements of the {\em prerequisite} relation. \\
\bigskip
{\em prerequisite} $=$
\{ (6.002,6.004) , (6.002,6.006) , (6.002,6.008) , (6.002,6.0042) \\
   (6.003,6.006) , (6.003,6.009) , (6.003,6.042) , (6.004,6.006) \\
   (6.004,6.008) , (6.004,6.042) , (6.006,6.008) , (6.006,6.042) \\
   (6.007,6.042) , (6.008,6.042) , (6.009,6.042) , (6.006,6.009) \} \\

\bigskip 
\ppart State whether this relation is reflexive, symmetric, transitive,
antisymmetric. Is it an equivalence relation? \\

\bigskip
The relation is antisymmetric, but nothing else. \\


\ppart Now consider the {\em taken before} relation which is defined to be the
reflexive and transitive closure of the {\em prerequisite} relation.
Draw the Hasse Diagram for the {\em taken before} relation. \\
$$\diagram
1 & 2\dline & 3\ddline \\
  & 4\drline &   \\
5 &   & 6\dlline\dline \\
7\drline & 8\dline & 9\dlline \\
  & 42& \\
\enddiagram$$


%\vspace{2.5in}   
\ppart The new regulations place no limit on how many courses a student can 
take in one term.
What is the minimum number of terms required to complete all the required 
courses? Why? \\
\bigskip
The minimum number of terms is $5$, which is the length of the critical path
in the above Hasse diagram. \\

\bigskip
\ppart Write down a maximum-size antichain in the partial order. 
What is the meaning of an antichain in terms of a student's schedule?\\  

\bigskip
6.001, 6.002, 6.003, 6.005, 6.007. \\
An antichain is a list of subjects that a student can take at the same term. \\

\eparts

\problem An {\em independent set} in a graph is a subset $S$ of the
vertices such that no edge connects two vertices in $S$.  Consider the
following algorithm on a graph with vertices $v_1,\ldots,v_n$:

\begin{tabbing}
else \= else \= else \= else\kill
initially no vertex is marked\\
{\bf for} $i=1$ to $n$\\
\> {\bf if} no neighbor of $v_i$ is marked {\bf then}\\
\> \> mark $v_i$\\
\end{tabbing}

\begin{problemparts}

\ppart Prove that when this algorithm terminates, the set of marked vertices
is an independent set.


By induction on $i$:

The inductive hypothesis is: \\
$P(i):$ after the completion of the $i$th loop, the marked nodes form and
independent set.

Base Case: \\
$P(1)$: Since only $v_1$ is marked, it forms an independent set since it
isn't connected to any other marked nodes.

Inductive Step: $P(i) \rightarrow P(i+1)$ \\
At the beginning of the $i+1$st iteration, we know by the inductive hypothesis that the 
marked nodes form an independent set of $v_1 \ldots v_i$.  We add $v_{i+1}$,
only if it is not connected to any other $v_k$ that's marked,
so the marked vertices of $v_1 \ldots v_{i+1}$ remain an independent set.

Hence after completion of the $n$th iteration of the for loop, the marked
vertices of $v_1 \ldots v_n$ form an independent set.

\ppart {\bf (Optional)} Prove that the set of marked vertices is a
{\em maximal} (under containment) independent set, in that adding any
other vertex will make it not-independent.


Assume for contradiction that there exists some vertex, $v_k$ that is not 
marked, yet is not connected to any marked vertex.  When $i=k$ in the
for loop, however, this vertex would have to have been
marked since it wasn't connected to any marked vertex.
So we have a contradiction, and there be no unmarked vertices with all unmarked
neighbors.

Therefore the marked vertices are a maximal independent set (note maximal,
not maximum since we're not claiming that this set is the largest independent
set).

\end{problemparts}

\problem We know that trees are bipartite because they contain no odd
cycles.  Give a direct proof that trees are bipartite by induction on
the number of tree vertices.

Base case: clearly a 1 vertex tree is bipartite.

Inductive step: Suppose all $n$-vertex trees are bipartite---that is,
can be legally colored with two colors red and green.  Consider any
$n+1$ vertex tree $T$.  It has a leaf vertex $v$.  If we remove $v$,
we are left with an $n$-vertex tree that is bipartite by the IH.  So
we can legally color the remaining $n$ tree vertices red and green.  Now
put $v$ back.  It is adjacent to only 1 node.  If that node is red,
make $v$ green, otherwise make $v$ red.  This extends the legal
coloring to $v$, so we have successfully colored $T$ with 2 colors,
proving it is bipartite.


\problem Sums.
\bparts
\ppart Give tight ($\Theta$) bounds for 
\[{\displaystyle \sum_{i=1}^n i^{1/2}}.\]

\bigskip
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq  {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
\sqrt{n}\leq 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \leq 2\sqrt{n}\\
\end{eqnarray*}
for all $n\geq 4$, that is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} \in \Theta(\sqrt{n}).\]

\ppart Express the following in closed form 
\[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\]
(Note that the lower indices are not constants.)

\bigskip
\begin{eqnarray*}
{\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\
 & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\
 & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p  \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\
 & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right).
\end{eqnarray*}

\eparts

\comment{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem (10 points)\\
Unbeknownst to many, Leonardo Fibonacci had a brother Eduardo who
invented the following sequence of numbers that he called {\em Eduardo}
numbers:

$$e_0 = 1$$
$$e_1 = 3$$
$$ \forall i \geq 2: e_i = e_{i-1} + e_{i-2}$$

Eduardo (who was not so good at math) made 2 conjectures about his numbers:

$$C1: \forall i \geq 0: e_i = f_{i+1} + 2f_i$$
$$C2: \forall i \geq 0: e_i = f_{i+2} - f_i$$

where $f_i$ is the $i^{th}$ Fibonacci number ($f_0 = 0$, $f_1 = 1$, $f_n =
f_{n-1}+f_{n-2}$ for all $n \geq 2$).\\
 
\def\longdash{\rule[.04in]{.1in}{.5pt}}

Decide whether or not Eduardo's conjectures are true.  Prove your
answers.  (Hint: do not repeat Eduardo's mistake by trying to solve
the recurrence exactly $\longdash$ there is a much faster way to
determine if each conjecture is true.)\\

\comment{
The first conjecture can be proven true by induction as follows:\\

{\em Base cases:} $e_o = 1 = f_1+2f_0, \,\,e_1 = 3 = 1+ 2 = f_2+2f_1$\\

{\em Induction step:} Suppose $e_i = f_{i+1}+2f_i$ for $i<k$, where $k
\geq 2$. We then have that\\
\begin{displaymath}
e_k = e_{k-1}+e_{k-2} = f_k+2f_{k-1} + f_{k-1}+2f_{k-2} = f_{k+1} +
2f_k
\end{displaymath}\\
\vspace{1.5in}
The second conjecture is false. A counterexample is $e_1 = 3 \neq f_3
- f_1 = 1$.
}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem  Consider the following recurrence:
 \[T(n) = 2T(\lfloor n/2 \rfloor) + n\log\log n, \qquad T(1)=1\]
\begin{problemparts}

  \ppart Assume that $n$ is a power of 2 so that the floor operation
  can be ignored.  Give tight ($\Theta$) bounds for $T(n)$.  Show your
  derivation, but don't bother proving the result correct.  (Hint: you
  might use Stirling's approximation to asymptotically bound $\log
  ((\log n)!)$.

\bigskip
  
  Plug and chug gives
\begin{eqnarray*}
T(n) &= & \sum_{k=0}^{i-1}2^k(n/2^k)\log\log(n/2^k) + 2^iT(n/2^i) \\
     &= &n \sum_{k=0}^{\log n -1} \log \log n/2^k + 2^{\log n}T(1)\\
     &= &n \sum_{k=0}^{\log n -1} \log (\log n - k) + n\\
     &= &n \sum_{k=1}^{\log n } \log k  + n\\
     &= &n \log \prod_{k=1}^{\log n} k + n\\
     &= &n (\log ((\log n)!) + 1)\\
     &\in &\Theta(n\log n\log\log n)
\end{eqnarray*}

  \ppart Prove that $T(n)$ is an increasing function of $n$ (that is,
  that $T(n+1) \geq T(n)$).
\bigskip

By strong induction.  We know that
$T(n+1) = 2T(\lfloor (n+1)/2 \rfloor)+(n+1)\log\log (n+1).$  We also know
that $\lfloor (n+1)/2 \rfloor \ge \lfloor n/2\rfloor$.  It follow from
the inductive hypothesis that $T(\lfloor (n+1)/2 \rfloor) \ge
T(\lfloor n/2\rfloor)$.  Thus,
\begin{eqnarray*}
T(n+1) &= &2T(\lfloor (n+1)/2 \rfloor)+(n+1)\log\log (n+1)\\
       &\ge &2T(\lfloor n/2 \rfloor)+n\log\log n\\
       &= &T(n)
\end{eqnarray*}

  \ppart From the previous two parts, deduce tight ($\Theta$) bounds
  on $T(n)$ when $n$ is an arbitrary natural number.

\bigskip

Let $k = \lceil \log_2 n \rceil$.  It follows that $2^{k-1} \le n
\le 2^k$.  Therefore, $T(2^{k-1}) \le T(n) \le T(2^k)$.  In other
words,
\[
2^{k-1} (\log (k-1)!+1) \le T(n) \le 2^k (\log k!+1)
\]
However,
\begin{eqnarray*}
2^{k-1}(\log(k-1)!+1) &= & \frac12 2^k ((\log k)!- \log k+1)\\
                  &= &\Omega(n(\log n \log\log n -\log \log n))\\
                  &= &\Omega(n\log n\log\log n)\\
\end{eqnarray*}
Also, $2^k(\log k!+1)=O(n\log n\log\log n)$, which implies that
$T(n)=\Theta (n\log n \log \log n)$ for all $n$.

\end{problemparts}

\problem
Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step.
\begin{itemize}
\item $n(\log_2 n)^5$
\item $n^3$
\item $n!$
\item $(n!)^2$
\item $n^n$
\item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$
\end{itemize}
\comment{\bigskip
\[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \]
}

\[n(\log_2 n)^5 < n^3 \leq 3\cdot 8^{\log_2 n} + 4^{\log_2 n}
 < n! < n^n < (n!)^2\]  
where $<$ means ``is $o(\cdot)$'' and $\leq$ means
``is $\Theta(\cdot)$''. 

\comment{

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem \\

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending
on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) =
\Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is
more than one relation between $f(n)$ and $g(n)$, write only the
strongest one (a relation $X$ is stronger than another relation $Y$ if
$X$ implies $Y$ but the converse does not hold). The first line is an
example solution. Note: $\lg n = \log_2 n$.\\ 
\
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\begin{array}{rcrl}
2n         &=& \stackrel{\textstyle \Theta}{\blank} & (n) \\
&&&\\
\lg (n^3)  &=& \stackrel{\textstyle \Theta}{\blank} & (\lg n)\\
&&&\\
n!         &=& \stackrel{\textstyle \omega}{\blank} & (4^n)\\
&&&\\
2^{\log_3 n} &=& \stackrel{\textstyle o}{\blank} & (n^2)\\
&&&\\
\sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle \omega}{\blank} & (1)\\
&&&\\
n^{4.01}   &=& \stackrel{\textstyle \omega}{\blank} & (n^4 \lg n)\\
&&&\\
\sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle o}{\blank} & (1)\\
&&&\\
{n \choose 10}&=& \stackrel{\textstyle \Theta}{\blank} & (n^{10}) \\
&&&\\
8^{\lg n}  &=& \stackrel{\textstyle \Theta}{\blank} & (n^3)
\end{array}
\]
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem Recurrences.


\bparts 

\ppart Suppose that each pair of a genetically engineered species of
rabbits left on an island produces two new pairs of rabbits at the age
of one month and six new pairs of rabbits at the age of two months and
every month afterwards. None of the rabbits ever die or leave the
island.  Find a recurrence relation for the number of {\em pairs} of
rabbits on the island $n$ months after one newborn pair is left on
the island. Do not solve the recurrence relation.\\
\\

Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then
$N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\
\begin{displaymath}
N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2)
\end{displaymath}\\
\vspace{0.5in}

\ppart Solve the following inhomogeneous recurrence relation:\\
\begin{displaymath} 
f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2
\end {displaymath}
The initial conditions are $f(0) = 5, f(1) = 26$.\\


The characteristic equation $r^2-6r+9$ has a repeated root $\alpha =
3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$,
for some constants $A$ and $B$. To find a particular solution, we try
$f_p(n) = K2^n$. Plugging into the difference equation gives:\\

\begin{math}
K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\
\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\
\end{math}\\
Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$.
We now use the initial conditions to solve for $A$ and $B$:\\

\begin{math}
f(0) = 5 = A+4 \Rightarrow A = 1\\
f(1) = 26 = 3 + 3B +8 \Rightarrow B = 5\\
\end{math}\\
Hence the solution is $f(n) = 3^n + 5n3^n + 2^n, n \geq 2$.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem
Consider the following nuclear reaction. There is one particle of type
$1$ at time instant $1$. Each particle of type $i$ existing at time
$t$ undergoes fission to produce one particle of type $i+1$ and one of
type $i+2$ at time instant $t+1$.
\bparts 
\ppart 
Write and justify a recurrence for $f(i,t)$, the number of particles of type
$i$ at time $t$. (Make sure to include the base cases for your
recurrence.)

\bigskip

Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to
particles of type $i$ at time $t$ and this is the only way that
particles of type $i$ are formed at time $t$.
Hence we get the recurrence
\[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \]
The base case is  
\begin{itemize}
\item $f(1,1) = 1$.
\item $f(i,1) = 0, -\infty < i < \infty, i \not= 1$.
\end{itemize}

\ppart 
Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.)
\bigskip

(Note: Let $a$ be any nonnegative integer and $b$ be any integer. In
what follows, we use the definition that ${a\choose b} =
\frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b}
= 0$. Pascal's identity holds for this definition.)

 The proof is by induction on $t$. Let
$P(t)$ be
\[f(i,t) = {t-1\choose i-t}, \forall i.\]

Base Case. $P(1)$ is true since
\begin{itemize}
\item $f(1,1) = {0\choose 0} = 1$.
\item $f(i,1) = {0\choose i-1} = 0, -\infty < i < \infty, i \not= 1$.
\end{itemize}

Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. 
\begin{eqnarray*}
f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\
         & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\
        & = {t\choose i-1-t} & \mbox{ by Pascal's identity} 
\end{eqnarray*}
Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem
How many $6$-digit decimal numbers are there that do not contain
``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem
numbers may have leading $0$'s)
\bigskip


Let
\begin{itemize}
\item $A$ be the set of all six-digit strings, using the digits
$\{0, 1, \ldots, 9\}$.
\item $B$ be the set of six-digit strings that contain the subsequence
$123$.
\item $C$ be the set of all six-digit strings that contain the subsequence
$456$.
\item $D$ be the set of all six-digit strings that do not contain 
$123$ or $456$.
\end{itemize}

We're interested in figuring out $| D |$.
Since $$D = A - (B \cup C),$$
and $B \cup C \subseteq A$,
we can use the inclusion-exclusion formula:
$$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$

First, $|A| = 10^6$, since we can put any of ten digits in each of
six places.  

Now, a string can contain $123$ in any of four positions; once this
position is chosen, we have $1000$ choices for the remaining positions.
However, this approach counts the string $123123$ twice, so 
the total size of $B$ is
$$| B | = 4(1000) - 1 = 3999.$$
By the same reasoning, we get
$$| C | = 3999.$$

Finally, there are only two strings in $B \cap C$, namely $123456$ 
and $456123$.  Thus,
$$| B \cap C | = 2.$$
Plugging this into our formula, we get
$$| D | = 10^6  - 3999 - 3999 + 2 = 992004.$$

{\em (Common Mistakes: A lot of people forgot about the double-counting
of $123123$ and $456456$, and so had $|B| = |C| = 4000$.  Some people also
argued that since $123$ can appear in one of only four places in the
string, $|B| = 4$.)}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem Binomial Coefficients.

\bparts 
\ppart Prove, by direct calculation, that the following
binomial identity is true for all $l,m,n$ such that $0 \leq l \leq m
\leq n$ :

\begin{displaymath}
{n \choose m}{m
  \choose l} = {n \choose l}{n-l \choose m-l}
\end{displaymath}\\

We just expand the binomial coefficients and cancel:\\

\begin{math}
{n \choose m}{m \choose l} = \frac{n!}{m!(n-m)!}\frac{m!}{l!(m-l)!} = \frac{n!}{(n-m)!}\frac{1}{l!(m-l)!}=
\frac{n!}{l!(n-l)!}\frac{(n-l)!}{(m-l)!(n-m)!} = {n \choose l}{n-l \choose m-l}
\end{math}\\
\vspace{0.5in}
\ppart Now prove the same identity combinatorially. Let $A$ be an
$n$-element set.  Explain how the left-hand and right-hand sides of the
identity in part a) may be interpreted as the number of ways of
choosing two subsets $B$ and $C$ of $A$, where $|B|=m$, $|C| =l$, and
$C \subseteq B$.\\
\\


The left hand side corresponds to first choosing $B$, then $C$. The
number of ways of doing this is, using the product rule, ${n \choose
  m}{n \choose l}$. The right hand side corresponds to first choosing
$C$, and then choosing $B-C$. The number of ways of doing this is,
using the product rule, ${n \choose l}{n-l \choose m-l}$. Since both
sides are equivalent to the number of ways of choosing subsets $B$ and $C$ such
that $|B|=m$, $|C| =l$, and $C \subseteq B$, the identity holds.
\eparts

\comment{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
I have $n$ dollars that I wish to donate  to $m$ charities in
whole-dollar amounts (each charity gets a natural number of dollars,
no fractions).  
\bparts
\ppart 
In how many ways can I do this if I don't care how much each charity gets?
\comment{\bigskip

Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the
$i$-th charity gets the money between bars $i-1$ and $i$. This gives you 
${n+m-1 \choose m-1 } $ ways to distribute the money.
}
\ppart 
In how many ways can I do this so that each charity gets at least \$ $10$?
\comment{\bigskip

First give 10 dollars to each charity, then distribute the remaining
 $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}=
{n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$.}
\eparts
}

\comment{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem

Four distinct children approach you on Halloween, requesting candy.
You have ten pieces of candy to distribute among them. In how many
different ways can you distribute the ten pieces if: (You must specify
your answer as an integer, or as a ratio of products of integers, or
as an integer raised to the power of an integer)\\ 

\bparts
\ppart All the pieces are the same (Reese's Peanut-butter
Cups$^{(TM)}$). No other restrictions.\\
\comment{
$${10+4-1 \choose 10} = {13 \choose 10} = \frac{13!}{3!10!}$$\\
\vspace{0.5in}}

\ppart All the pieces are the same, and each child must receive at
least one piece. No other restrictions.\\
\comment{
$${6+4-1 \choose 6} = {9 \choose 6} = \frac{9!}{3!6!}$$\\
\vspace{0.5in}}
\ppart All the ten pieces are different. No other restrictions. \\
\comment{
$$4^{10}$$
}
\comment{
\ppart Five pieces are Reese's Peanut-Butter Cups $^{(TM)}$ and the other five are
Nestle's Crunch $^{(TM)}$. No other restrictions.\\

$${5+4-1 \choose 5}^2 = {8 \choose 5}^2 = (\frac{8!}{3!5!})^2$$\\
\vspace{0.5in}
\ppart All the pieces are the same. No child gets more than $4$
pieces. No other restrictions.\\
We use the formula for $10$-combinations of $4$ elements with
repetition with each element occurring fewer than $5$ times, and get:\\

$${13 \choose 3} - {4 \choose 1}{8 \choose 3} + {4 \choose 2}{3
  \choose 3} = 68$$}
\eparts
}



\end{problems}
\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
