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

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

\setcounter{page}{0}

%\newcommand{\pr}{\problem}

\begin{document}

\qsol{2}{November 16, 1995}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
\bparts
\ppart Give tight ($\Theta$) bounds for 
\[{\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}}.\]
\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} \\
2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\
{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\
2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\
\end{eqnarray*}
That is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
I have $n$ one-dollar bills that I wish to donate  to $m$ charities.
\bparts
\ppart 
In how many ways can I do this if I don't care how much each charity gets?
\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$?
\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
In how many ways can $5$ indistinguishable covered wagons, $4$ indistinguishable uncovered wagons and $1$
horse be arranged in a circle?
\bigskip

This problem is just a permutation of a multiset, except that we need
to account for rotations of a circle being the same. This can be
thought of either as fixing one object, say the horse, and arranging
the wagons around it (${9\choose 5}$ ways), or counting the permutations
and dividing by $10$ to avoid overcounting the rotations
($\frac{1}{10}\frac{10!}{5!4!1!}$). Either way the answer is 126. The
most common mistake was to forget about overcounting the rotations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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 \leq i \leq \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$ when . 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 \leq i \leq \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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem 
\bparts
\ppart Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 10$.
 \[T(n) = 4T(n/2) + 6n.\]
\bigskip
\begin{eqnarray*}
T(n) & = 4T(n/2) + 6n & \\
 & = 4^2T(n/2^2) + 6(n + n/2) & \\
 & = \ldots & \\
 & = 4^iT(n/2^i) + 6(n + n/2 + \ldots + n/2^{i-1}) & \\
 & = \ldots & \\
 & = 4^{\log_2 n}T(1) + 6(n + n/2 + \ldots + n/2^{\log_2 n \ -1}) & \\
 & = n^2T(1) + O(n) & \\
 & = \Theta(n^2)
\end{eqnarray*}

\ppart
\points{10}
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}
\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). \]

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem
\bparts
\ppart 
Let $p_k$ be the number of ways to make change of $k$ cents with 
indistinguishable pennies ($1$-cent coins). Give an ordinary
generating function for $p_k$.
\bigskip
\[\frac{1}{1-x}.\]

\ppart
Let $n_k$ be the number of ways to make change of $k$ cents with 
indistinguishable nickels ($5$-cent coins). Give an ordinary
generating function for $n_k$.
\bigskip
\[\frac{1}{1-x^5}.\]

\ppart
Let $s_k$ be the number of ways to make change of $k$ cents with 
indistinguishable pennies or nickels. Give an ordinary
generating function for $s_k$.
\bigskip
\[\left( \frac{1}{1-x}\right) \left( \frac{1}{1-x^5} \right). \]

\ppart 
Give an ordinary generating function for the number of ways to 
make change of $k$ cents with at least $3$ nickels and an odd number
of pennies. (this part may be a little hard so don't knock yourself
out trying to solve it.)
\bigskip
\[\left( \frac{x^{15}}{1-x^5}\right) \left( \frac{x}{1-x^2} \right). \]

\eparts
\end{problems}

\end{document}







