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

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


\begin{document}

\psol{7}{April 7, 1997}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem{\mbox{}}

Calculate the number of ways to place 11 {\em indistinguishable} balls in four 
{\em distinguishable} boxes so that each box contains at least one,
but no more than four, balls.



\bigskip

First place one ball in each box.  Then we must distribute 7 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 7 balls in 4 boxes:
${7+4-1 \choose 7} = {10 \choose 7}$.

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

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

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

Number of ways to place 7 balls in 4 boxes such there are seven
balls in a box = 4.



So the total number of ways is

${10 \choose 7} - 4 \left({5 \choose 3} +
{4 \choose 2}+{3 \choose 1} +1 \right) = 40$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem{\mbox{}} 


Prove that

\[ \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!} = 3^n  \ .\]

\medskip

[Hint: find a formula for $(x+y+z)^n$ and then set $x=y=z=1$.]


\bigskip

We can write $(x+y+z)^n$ as follows:

\begin {equation} 
 \label{eq1} \begin {array}{lcr}
 (x+y+z)^n & =& (x+y+z) (x+y+z) \cdots
(x+y+z)\\ &=& \displaystyle
\sum_{  \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} C_{a,b,c} x^a y^b z^c 
\end {array} \ . \end {equation}
where $C_{a,b,c}$ is the number of ways to partition a set
of $a+b+c$  elements into three 
subsets of size, respectively, $a$, $b$, and $c$. 

We compute $C_{a,b,c}$ using the product rule. A
partition can be obtained by first choosing $a$ elements
out of $a+b+c$ ones, and then choosing $b$ elements out of the remaining
$b+c$ ones. The number of ways to make such choices is

\begin {equation} \label{eq2}
 C_{a,b,c} = {a +b +c \choose a} \cdot {b+c \choose b} = 
\frac{ (a+b+c)!}{a!(b+c)!} \cdot \frac{(b+c)!}{b!c!} = \frac {(a+b+c)!}{a!
b!c!}\ .  \end {equation}
% We could have found the same expression using the division rule.
Substituting Equation~(\ref{eq2}) into Equation~(\ref{eq1}) we
have

\begin{eqnarray*} 
(x+y+z)^n & = &  \sum_{ \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, 
b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} \frac {n!}{a!b!c!}
x^a y^b z^{c} \\
& = & \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
x^a y^b z^{n-a-b} \ .
\end {eqnarray*}

If we set  $x=y=z=1$
we derive

\[ 3^n = (1+1+1)^n = \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
1^a 1^b 1^{n-a-b}\ . \]



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 3
%inclusion-exclusion
\problem{\mbox{}}

A positive integer is called {\em square-free} if it is not
divisible by the square of a positive integer greater than 1.
For example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$
is not. $1$ is square-free.
Find the number of square-free positive integers less than
150 (150 included.)


\bigskip

We use inclusion-exclusion as done in lecture for the case
of prime numbers. We first compute the number of positive
integers less than 150 that are not square free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) 
be the set of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
less than 150. The cardinality of the union of these sets is given by

\begin {eqnarray*}
 |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/(2^23^2) \rfloor
- \lfloor 150/(2^25^2 \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 -4-1\\
& = & 58
\end {eqnarray*}
Therefore the number of square-free positive integers less than
150 is

\[ 150 - 58 = 92 \ . \]




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem{\mbox{}}

\begin{problemparts}
\problempart $4\cdot 4\cdot 4\cdot 4 =256$.
\problempart 15.
We can put either all 4 balls in one urn; or
3 in one, 1 in another; or 2 in one, 2 in another;
or 2 in one, 1 in one and 1 in another;
or 1 ball in each urn.
The balls are distinguishable, so there are $4\choose 3$ ways of
putting 3 in one urn.  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$ ways of putting 2 in one and
2 in another. Since the urns are indistinguishable, the case where
all the balls are placed in the same urn and the case where each
ball is places in a different urn are unique.
So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} + 1 = 15.
\]
\problempart 35.
This is a stars and bars problem with the balls being stars and the 
urns bars.  The answer is
${4+4-1 \choose 4} = {7 \choose 4} = 35$.

\problempart 
5.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 4 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset, \emptyset$ or
$\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or
$\{1,1\}, \{1,1\},\emptyset,\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 5
\problem{\mbox{}} 

How many ways can a photographer at a wedding arrange 5
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 $5$ ways to position the bride, $P(9,4)$ ways to choose 
and arrange the others.  This gives a total 
of ${5\cdot 9! \over 5!}$ ways.

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

\bigskip

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

\bigskip

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

\end{problemparts}

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

Six women and nine men are on the faculty of a school's
EECS department.  How many ways are there to select a committee of 5
members if 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: $ { 6 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 6 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 6 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 6 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 6 \choose 5} {9 \choose 0}$\\

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

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

Note that $6 \cdot { 14 \choose 4} =6006$ 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\}$.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem{\mbox{}}




Let $a_1,\ldots,a_n$ be $n$ positive integers  ($n \geq 2$)
such that $1 \leq a_i \leq  \lfloor (2^n-2)/n \rfloor$ for all $i =1,\ldots,n$.
Prove that there are two disjoint non-empty  subsets $S,T \subseteq 
\{1,\ldots,n\}$ such that
\[ \sum_{i \in S} a_i= \sum_{i \in T} a_i \ . \]


\bigskip


There are $2^n -1$ non-empty subsets $S$ of $\{1,\ldots,n\}$.
Consider, for each such subset, the sum $sum(S) = \sum_{i \in S} a_i$.
Since $1 \leq sum(S) \leq 2^n-2$, it follows that there are two different
sets $S_1$ and $S_2$ such that $sum(S_1) = sum(S_2)$ (we
use the pigeonhole principle: the pigeons are the sets $S$ and
the holes are the numbers $sum(S)$; there are $2^n-1$ pigeons
and $2^n-2$ holes.) We now define $S_1' = S_1 - (S_1 \cap S_2)$ and
$S_2' = S_2 - (S_1 \cap S_2$). We now have
 \[ sum (S'_1) = sum(S_1) - sum(S_1 \cap S_2) = sum(S_2) - sum(S_1 \cap S_2)
= sum(S'_2) \]
and $S'_1$ and $S'_2$ are disjoint. Therefore, $S'_1$ and $S'_2$
are the desired solution.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\mbox{}}

A shelf holds 13 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 8 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 4 stars left to be placed in 6 slots. The number of
ways to do this is therefore ${{6+4-1}\choose{4}}={9\choose 4}=126$.

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


\end{problems}

\end{document}





