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

%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{7}

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

\begin{problem}
Here are some basic problems to help you practice your counting
technique.  Make sure that {\em everyone} on your team fully
understands the solutions to all these problems before you proceed!

\begin{problemparts}

\ppart How many distinct positive factors does the number $3^4 \cdot
5^2 \cdot 7^3 \cdot 11$ have?

\solution{
A factor is a product of between zero and four 3's, between zero and
two 5's, between zero and three 7's and either zero or one 11.
Therefore, by the product rule, the answer is:

\begin{eqnarray*}
5 \cdot 3 \cdot 4 \cdot 2  & = & 120
\end{eqnarray*}
}

\ppart In how many ways can 20 copies of Rosen (5th edition) be
arranged on 5 different shelves?

\solution{This is equivalent to asking how many ways there are to
arrange 20 stars (representing books) and 4 bars (representing
dividers between shelves) in a string.  The answer is:

\[
\frac{24!}{20!\ 4!}
\]
}

\ppart In how many ways can 15 copies of Rosen (5th edition) and 5
copies of Rosen (4th edition) be arranged on 8 different shelves?

\solution{This is equal to the number of ways to arrange 15 X's
(representing 5th editions), 5 Y's (representing 4th editions), and 7
bars (representing dividers between shelves).  This is equal to:

\[
\frac{27!}{5!\ 15!\ 7!}
\]
}

\ppart In how many ways can 20 different books be placed on 5
different shelves?

\solution{
This is equivalent to asking how many ways there are to arrange the
symbols $b_1, b_2, \ldots, b_{20}$ together with four bars in a
string.  The answer is:
\[
\frac{24!}{4!}
\]
}

\ppart A cube is {\em colorful} if every face is painted either red,
orange, yellow, green, blue, or violet and no two faces are painted
the same color.  Two colorful cubes are considered the same if one can
be obtained from the other by rotation.  How many different colorful
cubes are possible?

\solution{There are 5 ways to select the face opposite the red face.
The number of ways to color the remaining four faces is equal to the
number of ways to seat four people at a circular table, which is $3!$.
Therefore, the number of different colorful cubes is:
\[
5 \cdot 3!  =  30.
\]
}

\ppart A FRIDAY consists of 12 scoops of ice cream topped with whipped
cream, nuts, chocolate syrup, and a cherry.  There are 24 flavors of
ice cream available (including half-baked, chocolate, and cookie
dough).  Multiple scoops of the same flavor are permitted.  Order does
not matter, because the scoops are all lumped into a big bowl.  How
many different FRIDAYs are possible?

\solution{This is equal to the number of strings with 12 stars and 23
bars, which is:

\[
\frac{35!}{12!\ 13!}
\]
}

\eparts

\end{problem}

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

\begin{problem}
On problem set 7, we saw that there is no reversible procedure that
compresses all 5-megabyte files down to 1-megabyte files.  Real data
compression programs work by exploiting patterns or special properties
of the input file.  For example, let's try to compress only those
$n$-bit files such that exactly $\alpha n$ of the bits are 1's, where
$0 < \alpha < 1$ and $\alpha n$ is an integer.  Such files might
represent black-and-white images where $\alpha$ is the fraction of
white pixels.

\bparts

\ppart How many different $n$-bit files with exactly $\alpha n$ 1's
are there?

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

We must choose $\alpha n$ of the $n$ bits to make 1's and the
remaining bits are 0's.
}

\ppart Give an approximation to your answer of the form:

\[
2^{n H(\alpha)}
\]

where $H$ is a nasty-looking function involving logarithms.  Use the
following crude version of Stirling's formula:

\begin{eqnarray*}
n! & \approx & \left( \frac{n}{e} \right)^n
\end{eqnarray*}

($H$ is called the {\em entropy function} and plays a central role in
the field of Information Theory.)

\solution{
\begin{eqnarray*}
\binom{n}{\alpha n}
	& = &	\frac{n!}{(\alpha n)! \ ((1 - \alpha) n)!} \\
	& \approx & \frac{\left( \frac{n}{e} \right)^n}
		{\left( \frac{\alpha n}{e} \right)^{\alpha n} \cdot
		 \left( \frac{(1 - \alpha) n}{e} \right)^{(1 - \alpha)n}} \\
	& = &	\left(\frac{1}{\alpha^{\alpha} \cdot (1 - \alpha)^{1 - \alpha}}
		\right)^n \\
	& = &	2^{n \cdot \left(\alpha \log\left(\frac{1}{\alpha}\right)
		+ (1-\alpha) \log\left(\frac{1}{1-\alpha}\right)\right)}
\end{eqnarray*}

The first step uses the definition of binomial notation.  The second
step uses Stirling's formula.  In the third step, we cancel lots of
$n$'s and $e$'s.  The final step uses the rules $u = 2^{\log u}$ and
$\log x^y = y \log x$.  (All logarithms here are base 2.)  }

\ppart Describe a reversible procedure that compresses each $n$-bit
file with exactly $\alpha n$ 1's down to an (approximately) $n
H(\alpha)$-bit file.  Your procedure can be incredibly inefficient; it
just has to work!

\solution{Index all the possible files $0, 1, 2, \ldots, \approx 2^{n
H(\alpha)}$ in any order.  The compressed form of a file is its index.
Each index is a number representable with $n H(\alpha)$ bits.}

(Intuitively, a random bit that is 1 with probability $\alpha$
contains $H(\alpha)$ bits of information.  On this intuitive basis, an
$n$-bit file with $\alpha n$ randomly-distributed 1's should contain
about $n H(\alpha)$ bits of information and therefore should be
representable with an $n H(\alpha)$-bit file.)

\ppart (Requires a calculator.)  Suppose that you have a 5-megabyte
file and 90\% of the bits are 1's.  Using the procedure you described
above, how large is the compressed file?

\solution{In this case, the file has $n = 5 \cdot 2^23$ bits and
$\alpha = 0.9$.  Therefore, the size of the compressed file is about:

\begin{eqnarray*}
n H(\alpha)
	& = &	19.7 \text{ megabits} \\
	& = &	2.45 \text{ megabytes}
\end{eqnarray*}

 }

\eparts

\end{problem}

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

\begin{problem}
An {\em $n$-bit boolean function} maps each $n$-bit string to a single
bit; that is, a $n$-bit boolean function has the form $f : \set{0,1}^n
\to \set{0,1}$.

\bparts

\ppart How many $n$-bit boolean functions are there?

\solution{We can map each of the $2^n$ elements of the domain to
either 0 or 1.  Therefore, the number of such functions is:
\[
2^{2^n}.
\]
}

\ppart The $n$-bit boolean function $f$ {\em depends on bit $i$}
if there exist $n$-bit strings $b$ and $b'$ such that $b$ and $b'$
differ only in the $i$-th bit and $f(b) \neq f(b')$.  How many $n$-bit
boolean functions are there that do {\em not} depend on the $i$-th bit?

\solution{Now we can map each of the $2^{n-1}$ domain elements with a
0 in the $i$-th position to either 0 or 1.  Each of the domain
elements with a 1 in the $i$-th position must be mapped to the same
value as the corresponding element with a 0 in the $i$-th position.
Therefore, the number of boolean functions that do not depend on the
$i$-th bit is:
\[
2^{2^{n-1}}.
\]
}

\ppart How many $n$-bit boolean functions depend on {\em every}
bit?  Use inclusion-exclusion.  Your answer should be a summation.

\solution{Generalizing the argument above, the number of $n$-bit
boolean functions that do not depend on a $k$ specified bits is
$2^{2^{n-k}}$.  By the inclusion-exclusion formula, the number of
functions that depend on every bit is the total number of functions,
minus the number that depend on one bit, plus the number the depend on
two bits, minus the number that depend on three bits, etc.  This
gives:
\[
\sum_{k=0}^{n} (-1)^k \cdot \binom{n}{k} \cdot 2^{2^{n-k}}
\]
}

\eparts

\end{problem}

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

\begin{problem}
Recall the recursive definition for the set $W$ of {\em well-formed
parenthesis strings}:

\begin{enumerate}

\item The empty string, $\lambda$, is in $W$.

\item If $s$ and $t$ are in $W$, then $(s)t \in W$.

\end{enumerate}

\bparts

\ppart Let $C_i$ be the number of well-formed parenthesis strings with
exactly $i$ pairs of parentheses.  The numbers $C_0, C_1, C_2, \ldots$
are called the {\em Catalan numbers}.  They arise in many different
counting problems, as we'll see.  Compute $C_0, \ldots, C_4$.

\solution{
\[
\begin{array}{rcll}
C_0 & = & 1 & \lambda \\
C_1 & = & 1 & () \\
C_2 & = & 2 & (()) \quad ()() \\
C_3 & = & 5 & ((())) \quad (()()) \quad (())() \quad ()(()) \quad ()()() \\
c_4 & = & 14 & \ldots
\end{array}
\]
}

\ppart Translate the recursive definition of the set $W$ in to a
recurrence equation expressing $C_{n+1}$ in terms of smaller Catalan
numbers.  (Observe that every well-formed parenthesis string with
$n+1$ pairs of parentheses must be formed using rule 2 where $s$ has
$k$ pairs of parentheses and $t$ has $n - k$ pairs for some $0 \leq k
\leq n$.)

\solution{ Every well-formed parenthesis string with $n + 1$
parenthesese is of the form $(s)t$.  Let $k$ be the number of pairs of
parentheses in $s$.  This means that there are $n-k$ pairs of
parentheses in $t$.  Therefore, for a given $k$, we have $C_k$ choices
for $s$ and $C_{n-k}$ choices for $t$.  Summing over all possible
values of $k$ gives the recurrence:

\begin{eqnarray*}
C_{n+1} & = & \sum_{k=0}^n C_k \cdot C_{n-k}
\end{eqnarray*}
}

\ppart Theory Hippo wants to walk from point $A$ to point $B$ on an
$n \times n$ grid without falling into the Flaming Chasm of Hideous
Death:

\bigskip
\centerline{\includegraphics[height=2.5in]{rec7-chasm}}
\bigskip

Each step carries Theory Hippo either 1 unit north or 1 unit east.
One possible path is shown in bold.  Show that Theory Hippo has $C_n$
safe routes available by describing a bijection between well-formed
parenthesis strings and safe paths across the grid.

\solution{If $n = 0$, then $A = B$ and Theory Hippo has $C_0 = 1$ safe
paths.  In general, each safe path across an $n \times n$ grid
corresponds to a well-formed parenthesis string where we interpret
each $($ as a north step and each $)$ as an east step.  For example,
the path down in the diagram corresponds to the string:

\[
()(()())((()()))
\]

Since the number of $($'s never exceeds the number of $)$'s partway
through a well-formed string, Theory Hippo never falls into the
Flaming Chasm of Hideous Death.
}

\ppart Some examples of {\em rooted ordered binary trees} are shown
below.

\bigskip
\centerline{\includegraphics[height=2.5in]{rec7-trees}}
\bigskip

Determine the number of rooted ordered binary trees with $n$ vertices
by describing a bijection with well-formed parenthesis strings.  (As a
first step, you might try to associate each of the example trees above
with a specific parenthesis string.)

\solution{Associate the empty string $\lambda$ with the empty tree.
Associate the string $(s)t$ with a tree that has a root, a left
subtree corresponding to $s$, and a right subtree corresponding to
$t$.  (If $s$ or $t$ is the empty string, than that subtree is
missing.)

Thus, the trees in the diagram are associated with the following
strings:

\[
\begin{array}{c}
\lambda \\
() \\
(()) \\
()() \\
((())) \\
(()()) \\
(())() \\
()(()) \\
()()()
\end{array}
\]
}

\ppart (Harder) A {\em triangulation} of a convex polygon is a way of
cutting the polygon into triangles.  Some polygon triangulations are
shown below.  (The first one is a degenerate case, a triangulation of
a 2-gon.)

\bigskip
\centerline{\includegraphics[height=2.5in]{rec7-triangulate}}
\bigskip

Show that a convex $(n+2)$-gon can be triangulated in $C_n$ different
way by describing a bijection with well-formed parenthesis strings.

\eparts

\end{problem}

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

\end{document}
