\documentstyle[amstex]{article}
\input{macros-course}

\begin{document}

\pset{10}{April 17, 1997}{April 29, 1997}

{\bf Reading:} Rosen 4.1--4.3, 5.4-5.5

{\bf Warning:} Many of these problems ask ``how many.''  You should
always justify your answers using the counting principles given in class.

\begin{problems}


\problem Binomial Theorem
\begin{problemparts}

\ppart What is the coefficient of $x^k$ in $(x^2 + \frac{1}{x^2})^{50}$?


\ppart Let $a,n \in \naturals$. Show that the expression
$$
\frac{1}{\sqrt{a}}[(1+\sqrt{a})^n - (1-\sqrt{a})^n]
$$
is an integer.
\end{problemparts}


%inclusion/exclusion


\problem Inclusion-Exclusion
\begin{problemparts}

\ppart Prove the principle of inclusion-exclusion using mathematical 
induction.

\ppart An integer is called {\bf square free} if it is not divisible 
by the square 
of a positive integer greater than $1$. Find the number of square-free
positive integers less than $100$.
\end{problemparts}


\problem Use a tree diagram to determine the number of ways that the
world series can occur, where the first team to win four games out of
7 wins the series.

\problem 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?
\ppart The bride and the groom must be in the picture?
\ppart Exactly one of the bride and groom must be in the picture?

\end{problemparts}

\newpage

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

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

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

\end{problemparts}

\problem
Five ordinary distinguishable six-sided dice are rolled.
\begin{problemparts}
\ppart How many possible ways can they land?
\ppart How many possible ways where the sum of the first two equals the
sum of the other three?
\ppart How many possible ways where there are an even number of dice coming up
even?
\ppart How many ways where the dice have a full house (that is, two of
one number plus three of a different number)?
\ppart How many ways such that no pair shows?
\ppart How many ways with no two dice showing consecutive numbers?
\end{problemparts}

\problem Prove that
\[
{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}
\]
\begin{problemparts}

\ppart algebraically.

\ppart using a combinatorial argument.

\end{problemparts}

\problem Give a combinatorial proof that 
\[
\sum_{k=1}^n k{n \choose k}^2 = n{{2n - 1} \choose {n-1}}.
\]
Hint: count the number of ways to build a committee of $n$ people from
among $n$ math and $n$ computer science professors, assuming the chair
is a math prof.  Consider two committees different if they have different
chairs.

\problem How many relations are there on the set $\{1,\ldots,n\}$?  How
many reflexive ones?  How many symmetric ones?  How many that are
reflexive and symmetric?

\problem
How many graphs are there on 4 distinguishable vertices that do not
contain any cycles of length exactly 3?



\problemopt Evaluate the following summation:
\[
\sum_{k=0}^m {m \choose k}/{n \choose k}
\]

\end{problems}

\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
