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

\begin{document}

\pset{8}{October 30, 1997}{November 4}

{\bf Reading: 4.1, 4.3, 4.6, 5.4, 5.5, 9.1-9.3 of Rosen} 

\bigskip
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5.4-22
%Problem 1
\problem{\bf [10 points]} 

Calculate the number of ways to place 10 indistinguishable balls in four 
boxes with at least one in each box and at most four in each box.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%tree diagram
\problem{\bf [10 points]} 

\bparts

\ppart

Show that 

$$
\sum_{i=0}^r {n+i \choose i} = {n+r+1 \choose r}
$$

\ppart

Find a formula for the number of ways a $2n+1$ game world series can be played,
that terminates after one team wins $n+1$ games.  The two teams are
distinguishable.  Use part (a) to write your answer in closed-form.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%from M&R, # 4.7.5
%Problem 3
\problem{\bf [10 points]}

How many ways can 4 balls be placed in 3 urns if 
\begin{problemparts}
\problempart both the balls and the urns are distinguishable;
\problempart the balls are distinguishable but the urns are not;
\problempart the urns are distinguishable but the balls are not;
\problempart neither the balls nor the urns are distinguishable.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem{\bf [10 points]}

\bparts

\ppart
Design a huffman code for the following
8-letter alphabet with frequency counts as follows:

A .45\\
B .01\\
C .16\\
D .03\\
E .05\\
F .07\\
G .06\\
H .17

\ppart
Give the code for the string ``AHAACDEB''.

\ppart
How many bits are needed to encode a message with 100 letters, 
containing 45 A's, 1 B, 16 C's, 3 D's, 5 E's, 7 F's, 6 G's and 17 H's
using this code?

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem{\bf [10 points]} 

How many ways can a photographer at a wedding arrange 6
people in a row from a group of 10 people that includes the bride and
groom if

\bparts

\ppart The bride must be in the picture?
\ppart The bride and the groom must be in the picture?
\ppart Exactly one of the bride and groom must be in the picture?

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 6
\problem{\bf [10 points]} 

Seven women and nine men are on the faculty of a school's
math department.  The individuals are distinguishable.
How many ways are there to select a committee of 5
members if

\bparts

\ppart at least 1 woman must be on the committee?

\ppart at least 1 man and 1 woman must be on the committee?

\ppart there must be more men than women on the committee?

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%card problem
\problem{\bf [10 points]}

\bparts
\ppart
Describe a method for guessing 2 cards when 7 out of 9 are revealed.

\ppart
Prove that you cannot guess 2 cards when 4 out of 6 are revealed.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%Do Exercise $4.6-42$ of Rosen.

\problem{\bf [10 points]}

A shelf holds 12 books in a row.  How many ways are there to choose 
five books so that no two adjacent books are chosen?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem{\bf [10 points]}

Compute the (ordinary) generating function for each of the
following sequences.

\bparts
\ppart
$\displaystyle \ang{1,1,1,1,1,\ldots}$
\ppart
$\displaystyle \ang{1,1,1,0,0,0,0,0,0,\ldots}$
\ppart
$\displaystyle \ang{0,0,1,1,1,1,1,\ldots }$
\ppart
$\displaystyle \ang{0,0,0,1,1,1,1,1,\ldots }$
\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,0,1,0,0,1,0,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{3^k+5^k+7^k}$
\ppart
$\displaystyle \ang{a_k}=\ang{1/k!}$
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Stolen from Brualdi, p. 246
%Problem 10
\problem{\bf [10 points]}

Let $S$ be the multiset $\set{\infty\cdot a_1,\infty\cdot
a_2, \infty\cdot a_3,\infty\cdot a_4}$.  For each of the following
problem parts, determine the generating function for the sequence
$\ang{g_0,g_1,\ldots}$, where $g_r$ is the number of $r$-combinations
of $S$ with the specified added restriction.

\bparts
\ppart Each $a_k$ occurs an odd number of times.
\ppart Each $a_k$ occurs a multiple of 3 times.
\ppart The element $a_1$ does not occur, and $a_2$ occurs at most once.
\ppart The element $a_1$ occurs 1, 3, or 11 times, and the element $a_2$ occurs 2, 4, or 5 times.
%\ppart Each $a_k$ occurs at least 10 times.
\eparts

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

\end{problems}

\end{document}
