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

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

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

\begin{document}

\pset{7}{October 27, 1994}{In lecture, Thursday, November 3, 1994}

{\bf Reading:\ } [MR], Chapter 4.

\bigskip
\begin{problems}

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

\problem

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$?  Since the vertices are labeled and therefore
distinguishable, $G=(V_3, \{(1,2)\})$ and $G'=(V_3, \{(1,3)\})$ are
different graphs.

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

\remove{
  \problem
  Without using the formula for $n \choose k$,
  give a combinatorial argument to prove that the identity
  \[
  {s-1\choose 0} + {s\choose 1} + \cdots + {s+n-2\choose n-1}+ {s+n-1\choose n} 
  = 
  {s+n\choose n}
  \]
  holds, where $s$ and $n$ are positive integers.
  (\hint If $X$ is an $(s+n)$-set\footnote{That is, a set containing
  $s+n$ elements}
  and $Y=\{ y_1, y_2, \ldots, y_n\}$ is a specific $n$-subset of $X$, 
  what is the number of $n$-subsets of $X$ for which $y_r$ is the first member
  of $Y$ not in the subset?)
}

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

\problem 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 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
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$;
\problempart $x^3$ in $(3+4x)^6$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
  \oproblem
  Show that the number of different positions possible after four
  moves (total) in a game of tic-tac-toe is 756.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		from M&R, # 4.3.21 and 4.3.22
\problem 
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}
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}

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

\problem \mbox{}

\bparts \ppart Generalize your answers to \ref{ball-urns}, parts {\bf (a)} 
and {\bf (c)}, to $n$ balls and $k$ urns.
\eparts

You cannot generalize your answer to part {\bf (b)} or {\bf (d)}
of \ref{ball-urns}, however, because there is no closed-form
solution.  Let us now examine these two difficult problems more
closely.

\bparts \ppart Define the \defi{Stirling numbers of the second kind}
as the number of ways to put $n>0$ distinguishable balls into {\em
exactly} $k>0$ indistinguishable urns, which we denote by $S(n,k)$.
Alternatively, we can view $S(n,k)$ as the number of ways to partition
an $n$-set into exactly $k$ subsets.  For example, $S(n,1)=1$;
$S(n,n)=1$; and $S(n,k)=0$ if $k>n$.  We can see that the answer to
part {\bf (b)} of \ref{ball-urns} is $S(4,1)+S(4,2)+S(4,3)$.

What is $S(n,n-1)$?

Show that $S(n,k)$ satisfies the following recurrence
\[ S(n,k) = 
\cases{	0 & \cif{k>n;}\\
	1 & \cif{k=1\mbox{ or }k=n};\\
	k\cdot S(n-1, k) + S(n-1, k-1) & \mbox{otherwise.}
}
\]

Use this recurrence to compute $S(4,1)+S(4,2)+S(4,3)$, and check your
answer with that for part {\bf (b)} of \ref{ball-urns}.

\ppart Define $p(n,k)$ to be the number of ways to put $n>0$
indistinguishable balls into {\em exactly} $k>0$ indistinguishable
urns.  Alternatively, we can view $p(n,k)$ as the number of ways to
write $n\in\nats$ as the sum of exactly $k$ positive integers:
$n=a_1+a_2+\cdots+a_k$, where $a_1\geq a_2\geq\cdots\geq a_k\geq 1$.
For example, $p(n,1)=1$; $p(n,n)=1$; $p(n, n-1) = 1$ if $n>1$; and
$p(n,k)=0$ if $k>n$.  We can see that the answer to part {\bf (d)} of
\ref{ball-urns} is $p(4,1)+p(4,2)+p(4,3)$.

What is $p(n,2)$?

Show that $p(n,k)$ satisfies the following recurrence
\[ p(n,k) =
\cases{	0 & \cif{k>n;}\\
	1 & \cif{k=1\mbox{ or }k=n};\\
	p(n-1, k-1) + p(n-k, k)& \mbox{otherwise.}
}
\]

Use this recurrence to compute $p(4,1)+p(4,2)+p(4,3)$, and check your
answer with that for part {\bf
(d)} of \ref{ball-urns}.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		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.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		adapted from M&R, # 4.8.1 & 4.8.3
\remove{
\problem
In 6.042, 49 students are taking 6.002, 20 are taking 6.034,
and 18 of the 78 students are taking neither.
Also, 28 are taking 6.035, 15 of whom are also taking 6.002
and 1 of whom is also taking 6.034, 
but none of whom is taking all three courses.
%%	=> 9 students taking just 6.035
\begin{problemparts}
\problempart
How many 6.042 students aren't taking any of these other three classes? % 6
\problempart 
How many are taking both 6.002 and 6.034?	% 9
\problempart 
How many are taking 6.002 but not 6.034?	% 40
\problempart
How many are taking 6.034 but not 6.002?	% 11
\problempart 
How many are taking 6.034 but neither of the other two?		% 10
\problempart 
How many are taking 6.002 but not 6.035?	% 34
\problempart
How many are taking 6.002 and/or 6.035 but not 6.034?		% 52
\end{problemparts}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%		from M&R, # 4.8.9
\remove{
\problem
Explain why an integer between 2 and 100 is prime if and only if either
(a) it is a prime less than 10, or 
(b) no prime less than 10 divides it.
Now use the Inclusion-Exclusion Principle to compute the number
of primes less than 100. 
(You may know other methods that will answer this question faster,
but if we replaced 100 by 1,000,000, this method would win.)
}

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

\remove{
\problem Let $n, r\in\naturals$.
Use the binomial theorem to evaluate the expressions
\[\sum_{k=0}^{n}{n\choose k}r^k 
\;\;\mbox{ and }\;\;
\sum_{k=0}^{n}{n\choose k}(-r)^k\ .\]
%	(\hint $(-1)^k = \pm (-1)^{n-k}$.)
Use your analysis to conclude that if $r$ is odd, then
\[\left. 2^{n-1} \;\right| \sum_{\stackrel{\scriptstyle k=0}{k {\mathrm{\ even}}}}^{n}{n\choose k}r^{k}\ .\]

Note that if $r=1$, this sum simply counts the number of even-sized
subsets of an $n$-set, which we know is exactly $2^{n-1}$.

}

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

\problem 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 
One thousand freshmen conspire to randomly flip the seats of 26-100.
There are one thousand seats, and initially each seat is in
the up position.  The first student enters 26-100 and flips all
the seats to the down position.  The second student enters and flips
seats $2, 4, 6, \ldots, 1000$ back up.  The third student enters and
flips seats $3, 6, 9, \ldots, 999$---flipping each one up if it was
down and down if it was up.  This process continues for all 1000
freshmen, where the $k$th student toggles the position of every seat
that is a multiple of~$k$.  Show these silly freshmen that this
doesn't leave the seats in a very random state by telling them exactly
which seats will finish in the down position.

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

\problem ({\bf Extra credit}---simple when you see it.) Consider $n$
points located on a circle, and consider the $n\choose 2$ chords
connecting the points.  Assuming that no three chords with distinct
endpoints intersect at a single point, how many points of intersection
among the chords are there in the interior of the circle?

\end{problems}

\end{document}


