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

	\addtolength{\topmargin}{-.35in}
	\setlength{\textheight}{9in}

%\renewcommand{\naturals}{{\bf N}}

\begin{document}

\pset{8}{October 29, 1996}{Start of Class, Tuesday, November 5, 1996}

{\bf Reading:} Sections 4.1, 4.3, 5.4--5.5 of {\it Discrete Mathematics and
its Applications} by Kenneth H. Rosen.

\bigskip
\begin{problems}

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

How many edges are possible in an undirected graph on the set
$V_n=\set{1,2,\ldots,n}$ of vertices?  How many undirected graphs are
possible on $V_n$?  Note that since the vertices are labeled and therefore
distinguishable, $G=(V_3, \{(1,2)\})$ and $G'=(V_3, \{(1,3)\})$ are
different graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem 
%{\bf [ points]}
%
%In how many ways can a rook go from the lower-left corner of
%an $m$-by-$n$ chess board to the upper-right corner by a shortest
%path, that is, a path that consists of $m+n-1$ squares?

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

How many different ways can five ordinary six-sided
distinguishable dice land?  How many ways can they land so that no
pair shows?  How many ways can they land so that a full house shows,
that is, a pair and a triple, but not five-of-a-kind?  Provide
numerical answers, but show your derivations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%4.3-42, Rosen
{\bf [10 points]} (Exercise 4.3-42 of Rosen)

Give a formula for the coefficient of $x^k$ in the expansion of 
$(x+1/x)^{100}$, where $k$ ia an integer. 

%Calculate the coefficient of 
%\begin{problemparts}
%\problempart $x^5$ in $(1+x)^{11}$;
%\problempart $a^2b^8$ in $(a+b)^{10}$;
%\problempart $a^6b^6$ in $(a^2+b^3)^5$;
%\a%problempart $x^3$ in $(3+4x)^6$.
%\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		from M&R, # 4.3.21 and 4.3.22
\problem 
{\bf [15 points]}

A computer operating system requires file names to be exactly four letters
long; uppercase and lowercase letters are distinct.
\begin{problemparts}
\problempart
How many possible file names are there?
\problempart
The operating system is changed so that uppercase and lowercase are no
longer distinct.  Figure out the new number of file names in two ways:
applying the division rule to {\bf (a)} and directly.
\problempart
The operating system is changed so that file names may be {\em up to\/}
four letters long.  Repeat {\bf (a)} and {\bf (b)}.  Can the division
rule still be used?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	from M&R, # 4.7.5

\problem \label{ball-urns}
{\bf [20 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		from M&R, # 4.7.23
%\problem
%How many ways can $b$ indistinguishable balls be placed in $u$ 
%distinguishable urns if each urn must contain at least $k$
%balls?  (Assume $k\leq b/u$ since otherwise it's impossible.)

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

How many integers in the range from 1 to 1000 are not
divisible by any of the numbers 6, 10, and 15?


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf [16 points]}

We wish to prove the identity
\[\sum_{r=0}^n{n\choose r}^2 = {2n\choose n}\ ,\]
for $n\in\naturals$.

\begin{problemparts}
\problempart Use the binomial theorem and the fact that
\[(1+x)^n(1+x^{-1})^n = x^{-n}(1+x)^{2n}\] to prove the identity.

\problempart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Use the fact that \[{n\choose r}^2 = {n\choose
r}{n\choose n-r}\] to give a combinatorial proof of the identity.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem (Inclusion-Exclusion principle and its application)
%5.4-22 and 5.5-6 of Rosen

{\bf [10 points]} (Exercises 5.4-22 and 5.5-6 of Rosen)

\bparts
\ppart Prove the principle of inclusion-exclusion using mathematical 
induction.
\ppart An integer is called {\bf squarefree} if it is not divisible 
by the square 
of a positive integer greater than $1$. Find the number of squarefree
positive integers less than $100$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}


