\magnification=\magstep1
\input pdfsync
\centerline{\bf Solutions to Problem Assignment \#1}
\centerline{\bf Math 501--1, Spring 2006}
\centerline{\bf University of Utah}\bigskip\bigskip

\noindent{\bf Problems:}\medskip

\item{\bf 1.} {\it Twenty workers are to be assigned to $20$ different
	jobs, one to each job. How many different assignments are possible?}
	\medskip
	\itemitem{\bf Solution:} $20!\approx 2.43 \times 10^{18}.$\medskip
	
\item{\bf 2.} {\it Consider a group of $20$ people. If everyone shakes hands
	with everyone else, then how many handshakes take place?}
	\medskip
	\itemitem{\bf Solution:} ${20\choose 2}={20!\over 2! \times 18!}={20\times
	19\over 2!}=190.$\medskip
	
\item{\bf 3.} {\it Five separate awards (best scholarship, best leadership qualities,
	and so on ) are to be presented to selected students from a class of $30$.
	How many different outcomes are possible if:}
	\itemitem{\bf (a)} {\it a student can receive any number of awards;}\medskip
	\itemitem{\bf Solution:} $30^5=24,300,000$.\medskip
	\itemitem{\bf (b)} {\it each student can receive at most $1$ award?}\medskip
	\itemitem{\bf Solution:} $30\times 29\times 28\times 27\times 26
		= 17,100,720.$
	\medskip
	
\item{\bf 4.} {\it A person has $8$ friends, of whom $5$ will be 
	invited to a party.}
	\itemitem{\bf (a)} {\it How many choices are there if $2$ of the friends
		are feuding and will not attend together?}\medskip
	\itemitem{\bf Solution:} There are a total of ${8\choose 5}={8!\over
		3!\times 5!}=56$ ways to form invitations. But many of them
		contain the feuding duo. The number of possible invitations
		that contain the feuding duo is, in fact, ${6\choose 3}=20$.
		Therefore, there are $56-20=36$ possible invitations that do not
		include both of the fighting pair.\medskip
		
	\itemitem{\bf (b)} {\it How many choices if $2$ of the friends will
		only attend together?}\medskip
	\itemitem{\bf Solution:} There are $20$ possible ways for inviting
	the two. Also, there are ${6\choose 5}=6$ ways of not inviting them.
	Thus, there are $26$ many possible invitations of this type.\bigskip\bigskip
		
\noindent{\bf Theoretical Problems:}\medskip

\item{\bf 1.} {\it Verify that ${n\choose k}={n\choose n-k}$.
	Use this to prove that}
	$$
		{2n \choose n} =\sum_{k=0}^n {n\choose k}^2.
	$$
	It is easy to see that ${n\choose k}={n!\over k!\times (n-k)!}
	={n!\over (n-k)!\times k!}={n\choose n-k}$.
	Now, $2n\choose n$ is the number of ways of forming a team of $n$
	people from $2n$. Now concentrate on the $2n$ people. Our team
	could be formed by either choosing:
	\itemitem{\#1.} $0$ people from the first $n$ and $n$ people from the
		second $n$; or
	\itemitem{\#2.} $1$ person from the first $n$ and $n-1$ people from
		the second $n$; or $\cdots$
	\itemitem{$\vdots$}
	\itemitem{\#$n$.} $n$ people from the first $n$ and $0$ people
		from the second $n$.
	\medskip
	Items \#$1$ through \#$n$ cannot be done simultaneously. So they
	represent different ways in total.
	For \#$k$, the number of choices are ${n\choose k}{n\choose n-k}
	={n\choose k}^2$. Therefore, there are $\sum_{k=0}^n  {n\choose k}^2$-many
	ways of creating our team. But this must be equal to $2n\choose n$.
\end