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

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

\begin{document}

\pset{9}{Novemeber 7, 1995}{November 14, 1995}

%{\bf Reading:} Sections 4.6, 4.7, 5.4 and 5.5 of {\it
%Discrete Mathematics and its Applications} by Kenneth H. Rosen.

\bigskip

\begin{problems}

\problem 
A function is said to be {\em non-decreasing} if $x\leq y \Rightarrow
f(x) \leq f(y)$. How many non-decreasing functions are there from
$\{1\ldots n\}$ to $\{1\ldots n\}$? (Hint: Think $*$'s and $|$'s) 

\problem
How many $n$-bit sequences have more $1$'s than $0$'s?

\problem
Let $f(m,n)$ denote the number of different shortest paths from
$(0,0)$ to $(m,n)$. 
\bparts
\ppart Find a closed form for $f(m,n)$.
\ppart Prove that ${\displaystyle \sum_{m=0}^\infty
\sum_{n=0}^\infty} f(m,n)x^my^n = \frac{1}{1-x-y}$.
\eparts

\problem
Prove that 
\bparts
\ppart ${\displaystyle \sum_{i=1}^\infty}\frac{1}{9i^2 - 3i -2} =
\frac{1}{3}$
\ppart ${\displaystyle \sum_{i=1}^n}i\log i = \Theta(n^2\log n)$
\eparts

\problem
Prove by induction on $n$ that $\sum_{i=0}^n {n\choose i}2^i =
3^n$. (Hint: use Pascal's identity)

\problem
Prove that 
\bparts
\ppart $f(n) = O(g(n))$ implies $g(n) = \Omega(f(n))$.
\ppart $f(n) + o(f(n)) = \Theta(f(n))$.
\eparts

\problem
Two numbers are said to be {\em coprime} if their greatest common
divisor is $1$. Find the number of numbers between $1$ and $1728$
coprime to $1728$.

\problem
Give tight ($\Theta$) bounds for the following recurrences:
\bparts
\ppart $T(n) = T(n/4) + T(4n/9) + 5n; T(n) = O(1), n \leq 10$.
\ppart $T(n) = 2T(n-1) + 3T(n-2); \ \ T(0) = T(1) = 1$.
\eparts

\problem
Rank the following functions by order of growth; that is, find an
arrangement $g_1,g_2,\ldots,g_5$ of the functions satisfying $g_i =
O(g_{i+1})$. If $g_i = o(g_{i+1})$ or if $g_i = \Theta(g_{i+1})$ then
mention that also.
\bparts
\ppart $\log n!$
\ppart $n^{\log n}$
\ppart $2^{\log n}$
\ppart $2^{\sqrt{\log n}}$
\ppart $n^3$.
\eparts

\problem
A balloon-shop sells party balloons in different colours, called
imaginatively $C_1,C_2,\ldots$. Balloons of colour $C_i$ are sold only
in packets of size $2^i$. What's more, the store you go to is down to
its last packet of each colour i.e. if you want colour $C_4$ you can
buy $0$ or $16$ balloons. 
\bparts
\ppart Prove that the generating function for the number of ways to have an assortment of $n$ coloured balloons is $(1+x)(1+x^2)\ldots(1+x^{2^i})\ldots$.
\ppart Show that $f(n)$ - the coefficient of $x^n$ in the generating function of part a) - is $1$ for all $n$.
\ppart Conclude that $\frac{1}{1-x} = (1+x)(1+x^2)\ldots(1+x^{2^i})\ldots$.
\eparts
\end{problems}

\end{document}




