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

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


\begin{document}

\psol{8}{November 14 1997}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem{\bf [10 points]}
222z
Calculate the number of ways to place 10 balls in four boxes with at 
least one in each box and at most four in each box.

\bigskip

First place one ball in each box.  Then we must distribute six balls in four
boxes in such a way that no more than three balls are in the same box.

We use inclusion/exclusion

Number of ways to place six balls in 4 boxes:
${6+4-1 \choose 6} = {9 \choose 6}$

Number of ways to place six balls in 4 boxes such that there are four balls
in a box =  number of ways to choose box with three balls * number of ways
to place two balls in three boxes =
$4 \cdot {4 \choose 2}$.

Number of ways to place six balls in 4 boxes such that there are five balls
in a box = $4 \cdot {3 \choose 1}$.

Number of ways to place six balls in 4 boxes such that there are six balls
in a box = $4$.

So the total number of ways is

${9 \choose 6} - 4 \left({4 \choose 2}+{3 \choose 1} +1 \right) = 44$


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

\bparts

\ppart

Show that 

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

\bigskip

We will prove it by induction on $r$.
Let $P(r): \sum_{i=0}^r {n+i \choose i} = {n+r+1 \choose r}$.

{\bf Base case:} n  = 0;

$1 = {n \choose 0} = {n+1 \choose 0} = 1$

{\bf Inductive step:}

\begin{eqnarray*}
\sum_{i=0}^{r+1} {n+i \choose i} & = &\sum_{i=0}^{r} {n+i \choose i}
+{n+r+1 \choose r+1} \\
& = & { n+r+1 \choose r} + {n+r+1 \choose r+1}\\
& = & { n+r+2 \choose r+1}
\end{eqnarray*}

where in the last step we used Pascal's identity.

\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.

\bigskip

Fix a winning team, say team $1$.  The game can terminate in any day
from the $(n+1)$st day to the $(2n+1)$st day.  If the game terminates on the
$i$th day, then there are ${i-1 \choose n}$ ways to arrange the $n$ victories
of team $1$ in the past $i-1$ days.  Therefore the total
number of ways that team $1$ can win is

$$
\sum_{i=n+1}^{2n+1} {i-1 \choose n}
$$

By symmetry, this is also the number of ways that team $2$ can win, 
therefore the total number of ways the world series can occur
is 
$$
2\sum_{i=n+1}^{2n+1} {i-1 \choose n} = 
2\sum_{i=0}^{n} {n+i \choose n} =
2\sum_{i=0}^{n} {n+i \choose i} =
= 2 {2n+1 \choose n}
$$

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem{\bf [10 points]}

\begin{problemparts}
\problempart $3\cdot 3\cdot 3\cdot 3=81$.
\problempart 14.
We can put either all 4 balls in one urn,
3 in one, 2 in one and 2 in another, or 2 in one and 1 in each of the other
two.  The balls are distinguishable, so there are $4\choose 3$ ways of
putting 3 in one.  There are $4\choose 2$ ways of putting 2 in one and 1 in
each of the other two.  There are ${4\choose 2}/2$ of putting 2 in one and
2 in another.
So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} = 14.
\]
\problempart 15.

This is a stars and bars problem with the balls being stars and the 
urns bars.  The answer is
${4+3-1 \choose 4} = {6 \choose 4} = 15$.

\problempart 
4.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 3 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset$, or
$\{1,1,1\}, \{1\}, \emptyset$, or
$\{1,1\}, \{1,1\},\emptyset$, or
$\{1,1\}, \{1\}, \{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.

\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

\bigskip

A: 0\\
B: 10000\\
C: 110\\
D: 10001\\
E: 1001\\
F: 1011\\
G: 1010\\
H: 111\\

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

\bigskip

01110011010001100110000

\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?

\bigskip

We use the formula 
$$
length = \sum_{i=1}^k n_i length(i)
$$

$$
length = 45 \cdot 1 + 1 \cdot 5 + 16 \cdot 3 + 3 \cdot 5 +
5 \cdot 4 + 7 \cdot 4 + 6 \cdot 4 + 17 \cdot 3 = 
236
$$

\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

\begin{problemparts}

\ppart The bride must be in the picture?

\bigskip

There are $6$ ways to position the bride, $P(9,5)$ ways to choose 
and arrange the others.  This gives a total 
of ${6\cdot 9! \over 4!}$ ways.

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

\bigskip

There are $6$ ways to place the bride and $5$ to place the groom.  There are
$P(8,4)$ ways to choose and arrange the people.  
Total : $6 \cdot 5 \cdot {8! \over 4!}$ ways.
 
\ppart Exactly one of the bride and groom must be in the picture?

\bigskip

$2$ ways to choose between bride or groom, $6$ ways to place whichever one is chosen, and 
$P(8,5)$ to choose and arrange the remaining people.
Total : $2 \cdot 8!$ ways.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem 

Seven women and nine men are on the faculty of a school's
math department.  How many ways are there to select a committee of 5
members if
\begin{problemparts}

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

We need to count all possible combinations of people such that there
is at least one woman in every combination, but we must remember not
to count any combinations multiple times.  

We can have committees with 

1 woman, 4 men: $ { 7 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 7 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 7 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 7 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 7 \choose 5} {9 \choose 0}$\\

So there are 
$ { 7 \choose 1} {9 \choose 4} 
+ { 7 \choose 2} {9 \choose 3}
+ { 7 \choose 3} {9 \choose 2}
+ { 7 \choose 4} {9 \choose 1}
+ { 7 \choose 5} {9 \choose 0} = 4242$ different possibilities for
committees.

Another way to solve this problem is to say that there are ${16 \choose 5}$
different committees, and ${9 \choose 5}$ committees of just men.  So there
are ${16 \choose 5} - {9 \choose 5}$ different possibilities for committees.

Note that $7 \cdot { 15 \choose 4} $ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of $4$ chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A, \{BCDE\}$ as well as $B, \{ACDE\}$.  


\problempart at least 1 man and 1 woman must be on the committee?
We can have committees with 

1 woman, 4 men: $ { 7 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 7 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 7 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 7 \choose 4} {9 \choose 1}$\\

So there are 
$ { 7 \choose 1} {9 \choose 4} 
+ { 7 \choose 2} {9 \choose 3}
+ { 7 \choose 3} {9 \choose 2}
+ { 7 \choose 4} {9 \choose 1} = 4221$ different possibilities for
committees.

Again, this is also equal to the number of different committees, minus
the number of committees with no men, and minus the number of committees
with no women:
${16 \choose 5} - {9 \choose 5} - {7 \choose 5}$ 

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

For there to be more men than women, we must have $3$ or more men on the
committee.

5 men, 0 women: $ { 9 \choose 5} {7 \choose 0}$\\
4 men, 1 woman $ { 9 \choose 4} {7 \choose 1}$\\
3 men, 2 women: $ { 9 \choose 3} {7 \choose 2}$\\

$ { 9 \choose 5} {7 \choose 0}
+ { 9 \choose 4} {7 \choose 1}
+ { 9 \choose 3} {7 \choose 2}= 2772$ \\

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem

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

\bigskip

There must be $\ceil{9/4} = 3$ cards with the same color, so we choose to
hide two of them.  The first card revealed fixes the color and the offset.
There are six cards to code the position.  These suffice.  For example,
the first three cards can fix the position relative to the offset fixed by the
first card, and the other three card to describe the position relative to the
position of the first hidden card.  Note that the hidden card must be chosen
so that both offsets are less than or equal to 6.


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

\bigskip

There are ${52 \choose 6}$ possible six-card hands.  There are 
$P(52,4) = {52! \over 48!}$ four-card hands that can be displayed
(with order counted), therefore by pigeonhole there are at least
$\ceil{{ {52 \choose 6} \over  {52! \over 48!}}} = 4$ six-card hands
result in the same four-card display.  Therefore, the magician cannot
correctly guess in this case since these 4 hands must have different hidden
cards.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\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?

\bigskip

There are 5 bars (chosen books), and therefore there are
6 places where the 7 stars (non-chosen books) can fit (before the first 
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one star 
in it, so that adjacent books are not chosen. Once we have placed these
4 stars, there are 3 stars left to be placed in 6 slots. The number of
ways to do this is therefore ${{6+3-1}\choose{3}}={8\choose 3}=56$.

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

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

\bparts
\ppart $1/(1-x)$.
\ppart $1+x+x^2$.
\ppart ${x^2}/(1-x)$.
\ppart ${x^3}/(1-x)$.
\ppart $x^3 + x^4 + 2x^5 + x^6/(1-x)={{x^3}\over{1-x}}+x^5$.
\ppart $\sum_{n}{x^{3n}}=1/(1-x^3)$.
\ppart $(1+x)/(1-x)^3$.
%\ppart $2/(1-x)^3$.
\ppart $\sum_{n}{n(n+2)x^n}=\sum_{n}{n^2x^n}+2\sum_{n}{n x^n}=
{x \over (1-x)^2} + {2x^2 \over (1-x)^3 }+
2 {x \over (1-x)^2} = {2x^2 \over (1-x)^3 }+ {3x \over (1-x)^2} $
\ppart $1/(1-3x) + 1/(1-5x) + 1/(1-7x)$.
\ppart $e^x$.
\eparts

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

\bparts
\ppart GF for $\ang{a_k}={x\over{1-x^2}} ~\Longrightarrow 
A(x)=({x\over{1-x^2}})^4$.
\ppart GF for $\ang{a_k}={1\over{1-x^3}} ~\Longrightarrow 
A(x)=({1\over{1-x^3}})^4$.
\ppart GF for: 
$\ang{a_1}=1,~ \ang{a_2}=1+x,~ \ang{a_3},\ang{a_4}={1\over{1-x}}
~\Longrightarrow 
A(x)={{1+x}\over{(1-x)^2}}$.
\ppart GF for: 
$\ang{a_1}=x+x^3+x^{11},~ \ang{a_2}=x^2+x^4+x^5,~ \ang{a_3},\ang{a_4}={1\over{1-x}}
~\Longrightarrow \\
A(x)={{(x+x^3+x^{11})(x^2+x^4+x^5)}\over{(1-x)^2}}$.

\eparts

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

\end{problems}

\end{document}





