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

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

\begin{document}

\pset{8}{October 31, 1995}{November 07, 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 
{\bf Multinomial Theorem.} Prove that for any variables $x_i$ and positive integer n
\[ 
\left (\sum_{i=1}^k x_i \right)^n = \sum_{n_1+n_2+\cdots+n_k =
    n} { n \choose n_1,n_2,\ldots,n_k} x_1^{n_1}x_2^{n_2}\cdots
  x_k^{n_k}
\]
\bparts
\ppart algebraically and
\ppart combinatorially.
\eparts

\problem {\bf Submultisets.}
\bparts
\ppart
How many distinguishable submultisets of the multiset
$\{n_1\cdot a_1,n_2\cdot a_2,\ldots,n_k\cdot a_k\}$ are there?
\ppart
How many different divisors of 75600 are there? 
\eparts

\iffalse
\problem
Consider the Towers of Hanoi game with $n$ disks and $3$ distinct poles.
\bparts
\ppart
An arrangement of the disks on the poles is said to be legal if no
disk rests on a smaller disk. How many different legal arrangements of
the $n$ disks on the $3$ poles are there?
\ppart 
Construct a graph that has one vertex for each legal configuration of
the Towers of Hanoi game and an edge between two vertices if the
corresponding two configurations are a move apart. Since the moves are
reversible we can see that the graph is undirected. Show that this
graph contains a connected component of size less than that of part a)
and hence there is a configuration that is not reached during legal
play. 
\eparts
\fi

\problem 
\bparts
\ppart 
Consider the Towers of Hanoi game with $n$ disks and $3$ distinct
poles.  An arrangement of the disks on the poles is said to be legal
if no disk rests on a smaller disk. How many different legal
arrangements of the $n$ disks on the $3$ poles are there? 
\ppart
How many distinguishable ways are there to put $n$ books on
$r$ shelves (order on the shelf matters)?
\eparts

\problem
$11$ scientists are working on a secret project. They want to lock
the documents in a cabinet so that the cabinet cannot be opened by any
subset of five scientists. But every subset of six scientists should
be able to open it. 
\bparts
\ppart 
Prove that a minimum of ${11\choose 5}$ different locks is needed on
the cabinet.
\ppart
Prove that each scientist must carry at least ${10\choose 5}$ keys.
\eparts


\problem Compute the (ordinary) generating function for each of the
following sequences.
\bparts
\ppart
$\displaystyle \ang{0,0,0,1,1,2,1,1,1,1,1\ldots }$
\ppart
$\displaystyle \ang{0,0,0,1,2,3,4,5,6,7,8,9\ldots }$
\ppart
$\displaystyle \ang{1,0,1,0,1,0,1,\ldots}$
\ppart
$\displaystyle \ang{1,4,9,16,25,\ldots}$
\ppart
$\displaystyle \ang{2,6,12,20,30,42,56,\ldots}$
\ppart
$\displaystyle \ang{a_k} = \ang{k(k+2)}$
\ppart
$\displaystyle \ang{a_k}=\ang{2^k+3^k}$
\ppart
$\displaystyle \ang{a_k}=\ang{1/k!}$
\ppart
$\displaystyle \ang{a_k}=\ang{\sum_{i=0}^k {1\over i!}}$
\ppart
$\displaystyle \ang{1,1/2,1/3,1/4,\ldots}$
\eparts
%\end{multicols}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find partial fraction decompositions for the following functions.
\bparts
\ppart
$\displaystyle \frac{x^4 + x^3 + 3x^2 + 6x + 7}{x^2 + 3x + 2}$
\ppart
$\displaystyle \frac{x-6}{x^3 + x^2 - x - 1}$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Use generating functions to solve the recurrence
\[
a_n = \cases{n & \mbox{if } 0 \leq n<3 \\
2a_{n-2}+a_{n-3} & \mbox{if } n\geq 3}
\]
Use induction to check your answer.

\iffalse

\problem
using only the fact that there are 60 different permutations of
PEPPER, count the number of permutations of PEPPERMILL.

\problem
Prove 
\[{a choose k} - {a choose k-1} + {a choose k-2} + \ldots = {a-1
choose k}.\]


\problem
How many bit strings of length $n$, where $n \geq 4$, contain exactly
two occurrences of $01$?


\problem
Prove that the number of ways to write $n$ as a sum of $r$ numbers is
equal to the number of ways to write $n$ as a sum of numbers each at
most $r$.


rosen 4.6-40 but without hint.


Prove that every integer $n$ can be written uniquely in the form
\[
\sum a_k k!
\]
where $0 \le a_k \le k$.

How many ways can we go up n stairs if we take one or two steps at a
time?  

\fi



\end{problems}

\end{document}




