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

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{9}{April 29, 2003}{Start of class on Tuesday, May 6}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}

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

\problem Solve the following counting problems, and briefly explain
your reasoning.  You may express your answers in terms of factorials
and binomial coefficients.

\begin{problemparts}

\problempart How many ways are there to arrange the letters in the
word ``bookkeeper''?

\solution{If all 10 letters in the word bookkeeper were distinct, then
there would be $10!$ arrangements.  However, this overcounts by a
factor of $2!\ 2!\ 3!$, because the two o's are indistinguishable, the
two k's are indistinguishable, and the three e's are
indistinguishable.  Therefore, by the division rule, the number of
arrangements is:


\[
\frac{10!}{2!\ 2!\ 3!}
\]

Alternatively, this follows from the formula for permutations with
indistinguishable objects.
}

\problempart How many different sequences are there that consist of 99
stars and 7 bars?

\solution{We must choose 7 of the $99 + 7 = 106$ positions in the
sequence to contain bars.  Therefore, the number of such sequences is:

\[
\binom{99 + 7}{7}
\]
}

\problempart In how many different ways can $2n$ students be paired
up?

\solution{Pair up students by the following procedure.  Line up the
students and pair the first and second, the third and fourth, the
fifth and sixth, etc.  The students can be lined up in $(2n)!$ ways.
However, this overcounts by a factor of $2^n$, because we would get
the same pairing if the first and second students were swapped, the
third and fourth were swapped, etc.  Furthermore, we are still
overcounting by a factor of $n!$, because we would get the same
pairing even if pairs of students were permuted, e.g. the first and
second were swapped with the ninth and tenth.  Therefore, the number
of pairings is:

\[
\frac{(2n)!}{2^n \cdot n!}
\]
}

\problempart How many nondecreasing sequences of 7 integers in the
range from 0 to 99 are there?

\solution{There is a bijection between these nondecreasing sequences
and strings containing 7 bars and 99 stars.  In particular, the $k$-th
number in the nondecreasing sequence is the number of stars preceding
the $k$-th bar.  For example:

\[
\star \mid \star \star \star \mid \mid \star \star \mid \star \ldots
\quad \leftrightarrow \quad
(1, 4, 4, 6, \ldots)
\]

Therefore, the number of such nondecreasing sequences is:

\[
\binom{99 + 7}{7}
\]
}

\problempart How many different solutions over the natural numbers are
there to the following equation?

\beqn
x_1 + x_2 + x_3 + \ldots + x_{10} & = & 1000
\eeqn

A solution is a specification of the value of each variable $x_i$.
Two solutions are different if different values are specified for some
variable $x_i$.

\solution{There is a bijection between strings containing 1000 stars
and 9 bars and solutions to this equation.  The 9 bars divide the
stars into 10 segments.  Let $x_i$ be the number of stars in the
$i$-th segment.  Therefore, the number of solutions is:

\[
\binom{1000+9}{9}
\]
}

\problempart In how many different ways can one choose $n$ out of $2n$
objects, given that $n$ of the $2n$ objects are identical and the
other $n$ are all unique?

\solution{We can select $n$ objects as follows.  First, take a subset
of the unique objects.  Then take however many identical elements are
needed to bring the total to $n$.  The first step can be done in $2^n$
ways, and the second can be done in only 1 way.  Therefore, there are
$2^n$ ways to choose $n$ objects.}

\problempart How many different paths are there from point $(0, 0, 0)$
to point $(10, 20, 30)$ if every step increments one coordinate and
leaves the other two unchanged?

\solution{ There is a bijection between the set of all such paths and
the set of strings containing 10 X's, 20 Y's, and 30 Z's.  In
particular, we obtain a path by working through a string from left to
right.  An $X$ corresponds to a step that increments the first
coordinate, a $Y$ increments the second coordinate, and a $Z$
increments the third.  The number of such strings is:

\[
\frac{60!}{10!\ 20!\ 30!}
\]

\noindent Therefore, this is also the number of paths.
}

\problempart In how many different ways can 100 identical balls be
arranged in 10 different bins, if every bin must receive at least 2
balls?

\solution{There is a bijection between arrangements of balls and bins
and strings containing 9 bars and 80 stars.  The 9 bars partition the
sequence of stars into 10 segments.  If there are $x_i$ stars in the
$i$-th segment of a string, then there are $x_i + 2$ balls in the
$i$-th bin of the corresponding arrangment.  Therefore, the number of
arrangements is equal to the number of strings, which is:

\[
\binom{80 + 9}{9}
\]
}

\problempart How many undirected graphs without self-loops are there
with vertices $v_1, v_2, \ldots, v_n$?

\solution{There are $\binom{n}{2}$ potential edges, each of which may
or may not appear in a given graph.  Therefore, the number of graphs is:

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

\end{problemparts}

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

\problem A pizza shop is having a special promotion.  Their ad reads:

\begin{quotation}

Buy 2 large pizzas at the regular price, and add any subset of our 11
delicious toppings to each pizza at no extra cost.  That's 4,194,304
different ways to design your order!
\end{quotation}

The ad writer is a former MIT student who figures that the number of
possible orders is $(2^{11})^2 = 4,194,304$.  Unfortunately, this
student got a B- in 6.042, and his solution is wrong.  What is his
mistake, and how many different orders are really possible?

\solution{The number of ways to choose different toppings for one
pizza is the number of subsets of the set of 11 toppings, which is
$2^{11}$.  However, when the student says that there are $(2^{11})^2$
different ways to choose toppings for two pizzas, he is
double-counting orders in which the two pizzas receive the same
toppings.  The right answer is:

\beqn
2^{11}+\binom{2^{11}}{2} & = & 2,098,176
\eeqn

This is the number of ways to choose the same toppings for both pizzas
plus the number of ways to choose two pizzas with different sets of
toppings.}

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

\problem Let $S$ be a set containing $n$ elements.

\begin{problemparts}

\problempart How many binary relations on the set $S$ are there?

\solution{For every ordered pair of elements of $S$, the relation
either holds or it does not.  Therefore, there are $2^{n^2}$ binary
relations.}

\problempart How many binary relations on $S$ are symmetric?

\solution{We must decide whether the relation holds for every
unordered pair of elements, of which there are $\binom{n}{2}$.  We
must also decide whether each of the $n$ elements is related to
itself.  The total number of ways to take these decisions is:

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

\problempart How many binary relations on $S$ are reflexive?

\solution{If the relation is reflexive, then the relation may or may
not hold for every ordered pair of distinct elements, of which there
are $n^2 - n$.  Thus, the number of reflexive relations is:

\[
2^{n^2 - n}
\]
}

\problempart How many binary relations on $S$ are both symmetric and reflexive?

\solution{Now the relation may or may not hold for every unordered
pair of distinct elements, of which there are $\binom{n}{2}$.  Thus,
the number of symmetric, reflexive relations is:

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

\problempart How many binary relations on $S$ are symmetric or reflexive?

\solution{
By inclusion exclusion, we have:

\beqn
\lefteqn{\text{\# symmetric or reflexive}} \hspace{1in} \\
	& = &	\text{\# symmetric} + \text{\# reflexive} -
		\text{\# symmetric and reflexive} \\
	& = &	2^{\binom{n}{2} + n} + 2^{n^2 - n} - 2^{\binom{n}{2}}
\eeqn
}

\end{problemparts}

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

\problem Give combinatorial proofs of the identities below.  Use the
following structure for each proof.  First, define an appropriate set
$S$.  Next, show that the left side of the equation counts the number
of elements in $S$.  Then show that, from another perspective, the
right side of the equation also counts the number of elements in set
$S$.  Conclude that the left side must be equal to the right, since
both are equal to $|S|$.

\begin{problemparts}

\problempart
\beqn
\binom{2n}{n} & = & \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k}
\eeqn

\solution{We are counting the number of $2n$-bit strings with an equal
number of zeros and ones.  One one hand, the number of such strings is
equal to $\binom{2n}{n}$, since we must choose $n$ of the $2n$ bits to
be 1's.  This gives the expression on the left side of the equation.
On the other hand, the number of 1's in the first half of the string
must be equal to some number $k$ between 0 and $n$.  The number of
$2n$-bit strings with exactly $k$ ones in the first half and,
consequently, $n-k$ ones in the second half is equal to $\binom{n}{k}
\cdot \binom{n}{n-k}$.  Summing over all possible values of $k$ gives
the expression on the right side of the equation above.  Since the two
sides of this equation count the elements of the same set in two
different ways, the two sides must be equal.  }

\problempart
\beqn
\binom{n+1}{m+1} & = & \sum_{k=m}^n \binom{k}{m}
\eeqn

\solution{Let $S$ be the set of $(m+1)$-combinations of the set $\{ 1,
2, 3, \ldots, n+1 \}$.  On one hand, $|S| = \binom{n+1}{m+1}$ by the
standard formula for combinations.  On the other hand, we can select
each $(m+1)$-combination by an alternative procedure.  First, choose
the largest element of the combination, and call this $k+1$.  Thus,
$k$ must be in the range from $m$ to $n$.  Now we can choose the
remaining elements in $\binom{k}{m}$ ways, since we must select $m$
elemens in the range $\{ 1, 2, 3, \ldots, k \}$.  This shows that the
expression on the right side of the equation above is also equal to
$|S|$.  Since both sides are equal to $|S|$, they must be equal to
each other.}

\end{problemparts}

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

\problem The ``engineering primes'' are 2, 3, 5, 7, and all larger
natural numbers that are not divisible by 2, 3, 5, or 7.

\begin{problemparts}

\problempart What is the smallest engineering prime that is not a real
prime?

\solution{
\beqn
11 \cdot 11 & = & 121
\eeqn
}

\problempart Use inclusion-exclusion to count the number of
engineering primes that are less than a million.

\solution{We can use inclusion-exclusion to count numbers in the range
from 1 to million that are multiples of 2, 3, 5, or 7:

\beqn
\left\lfloor\frac{10^6}{2}\right\rfloor
+ \left\lfloor\frac{10^6}{3}\right\rfloor
+ \left\lfloor\frac{10^6}{5}\right\rfloor
+ \left\lfloor\frac{10^6}{7}\right\rfloor \\
- \left\lfloor\frac{10^6}{2 \cdot 3}\right\rfloor
- \left\lfloor\frac{10^6}{2 \cdot 5}\right\rfloor
- \left\lfloor\frac{10^6}{2 \cdot 7}\right\rfloor
- \left\lfloor\frac{10^6}{3 \cdot 5}\right\rfloor
- \left\lfloor\frac{10^6}{3 \cdot 7}\right\rfloor
- \left\lfloor\frac{10^6}{5 \cdot 7}\right\rfloor \\
+ \left\lfloor\frac{10^6}{3 \cdot 5 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 5 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 7}\right\rfloor
+ \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 5}\right\rfloor \\
- \left\lfloor\frac{10^6}{2 \cdot 3 \cdot 5 \cdot 7}\right\rfloor
& = & 771429
\eeqn

Therefore, there are $1000000 - 771429 - 228571$ numbers from 1 to a
million that are not multiples of 2, 3, 5, or 7.  Adding in the
numbers 2, 3, 5, and 7, we find that the number of engineering primes
less than a million is $228571 + 4 = 228575$.
}

\end{problemparts}

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


\problem A {\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 :
\{0,1\}^n \to \{0,1\}$.

\begin{problemparts}

\problempart 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}
\]
}

\problempart 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 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}}
\]
}

\problempart How many $n$-bit boolean functions depend on {\em every} bit?

\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}}
\]
}

\end{problemparts}


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

\problem We can obtain a crude variant of Stirling's formula by
dropping the $\sqrt{2 \pi n}$ term, which leaves:

\beqn
n! & \approx & \left( \frac{n}{e} \right)^n
\eeqn

\begin{problemparts}

\problempart Use this approximation to estimate the value of:

\beqn
\binom{n}{\alpha n}
\eeqn

where $\alpha$ is a number between 0 and 1 such that $\alpha n$ is an
integer.  Show your work, and put your answer in the form

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

where $H$ is a function of $\alpha$.  (The function $H$ is called the
{\em binary entropy function}.  Much like $e$ and $\pi$, entropy crops
up in all sorts of odd places.  Furthermore, entropy plays a central
role in the field of information theory.)

\solution{
\beqn
\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}} \\
	& = &	\frac{1}{\alpha^{\alpha n} \cdot
		(1-\alpha)^{(1 - \alpha) n}} \\
	& = &	2^{n H(\alpha)}
\eeqn

\noindent where:

\beqn
H(\alpha) & = & \alpha \log_2\left(\frac{1}{\alpha}\right) +
		(1 - \alpha) \log_2\left(\frac{1}{1 - \alpha}\right)
\eeqn
}

\problempart Using this formula, approximately how many $n$-bit
strings have exactly $n/3$ ones?  (Assume that $n/3$ is an integer.)
You answer should be of the form $2^{nc}$ where $c$ is a constant.

\solution{
Stting $\alpha = 1/3$ in the formula above gives:

\beqn
2^{n H(1/3)}
	& \approx &	2^{0.918 n}
\eeqn
}

\problempart Using the same formula, what is the approximate
probability of flipping $51\%$ heads in $n$ tosses of a fair coin?
(Assume that $0.51n$ is an integer.)  Your answer should be of the form
$2^{-nc}$ where $c$ is a constant.

\solution{
The probability is:

\beqn
\frac{\binom{n}{0.51n}}{2^n}
\	& \approx &	2^{n(H(0.51) - 1)} \\
	& \approx &	2^{-0.000289 n}
\eeqn

Thus, for example, when $n = 1000000$, the probability of flipping
$510000$ heads is about $2^{-289}$.}

\end{problemparts}

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

\end{problems}
\end{document}
