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

\begin{document}

\pset{7}{March 31, 1998}{April 7}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%binomial coefficients and product rule
\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$.]



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


A positive integer is called {\em square-free} if it is not
divisible by the square of any 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.)






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%from M&R, # 4.7.5
%Problem 4
\problem{\mbox{}}

How many ways can 4 balls be placed in 4 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 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

\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{\mbox{}} 

Six women and nine men are on the faculty of a school's
EECS department.  The individuals are distinguishable.
How many ways are there to select a committee of 5
members if at least 1 woman must be on the committee?



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%pigeonhole subset sum
\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 \ . \]


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

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



\end{problems}

\end{document}
