\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%twang
%FALL01 - last used on tutorial 8
%Learning objectives:  7 (calculate numbers of possible outcomes)
%Newly added
% source: http://www.math.ucla.edu/~burchard/113.2.00s/midterm1.pdf
% sum/product rule

\problem In each case, state whether the argument is correct or incorrect,
and explain why.  If incorrect, try to fix it.
\begin{problemparts}

\problempart Since there are 26 letters in the English alphabet, the
Product Rule implies that the number of four-letter English words is
$26^4$.

\solnospace{Incorrect.  Not every four letter sequence is an English word,
\eg ``xxxx'' is not English.  In fact, there are considerably fewer
four-letter English words than $26^4$.  There is no fix to this mistaken
application of the Product Rule.}

\problempart The number of 4-digit (decimal whole) numbers which have a
digit 7 somewhere is $4 * 10^3$, since by the sum rule, we must add the
counts for each position the 7 could be in; and since for each such
position, there are $10^3$ possible numbers by the product rule.  (Assume
numbers can have leading zeros)

\solnospace{Incorrect, since it double counts numbers containing more than
one 7 (for example 7707 is counted 3 times).  The sum rule does not apply.
Correct answer is the number of all possible 4-digit number minus the
number of those which do \emph{not} contain 7, namely, $10^4 - 9^4$.}

\end{problemparts}

%twang
%FALL01 - last used on tutorial 8
%Learning objectives:  7 (calculate numbers of possible outcomes)
%		       4 (graph theory)
%revised with newer graphic and edited solutions
%%Fall 99, Tutorial 9
\problem \textbf{Counting Numbered Trees.}  A \emph{numbered tree} is a
tree whose vertex set is $\set{1,2,\dots,n}$ for some $n \geq 2$.  We
define the \emph{code} of the numbered tree to be a sequence of $n-2$
integers from 1 to $n$ obtained by the following recursive process:
\begin{quotation}\noindent
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf, delete this \emph{leaf}, and
continue the process on the resulting smaller tree.
\end{quotation}
For example, the codes of a couple of numbered trees are shown in

Figure~(\ref{fig:n-2}).
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/n-2}
\end{center}
\caption{Coding Numbered Trees}
\label{fig:n-2}
\end{figure}

\bparts

\ppart Describe a procedure for reconstructing a numbered tree from its
code.

\solnospace{
The key observation is that, given a code of length $n-2$, the numbers
between 1 and $n$ which \emph{do not appear} in the code must be leaves of
the tree.  Hence, the largest missing number is a leaf attached to the
first number of the code.  The rest of the tree can now be reconstructed
by deleting the first number in the code, henceforth ignoring the largest
leaf, and proceeding recursively on the rest of the code.  (We're using
the obvious fact that what's left after deleting a leaf from a tree is
another tree.)

More precisely, the reconstruction procedure applies to any finite tree
whose vertex set is totally ordered.  The procedure takes \emph{two}
parameters: the vertex set, $V$, and a length $\card{V}-2$ ``code''
sequence, $S$, of elements in $V$.  If $l$ is the largest element in $V$
which does not appear in $S$, and $f$ is the first element of $S$, then
the reconstructed tree is obtained by adding edge $(l,f)$ to the tree
reconstructed by calling the procedure recursively with first argument
$V-\set{l}$ and second argument equal to the code obtained by erasing the
initial $f$ from $S$.  The procedure terminates when $\card{V}=2$,
returning the edge between the two numbers in $V$.

To justify the key observation, note that any vertex that gets deleted by
the process and was not a leaf to begin with, must have been the father of
a previously deleted leaf, which means it would appear in the code.  So
the missing integers must have been leaves to begin with or must be one of
the two undeleted vertices left when the coding process terminates.  But
by the end of the process the two remaining vertices are leaves, and if
they weren't leaves to begin with, they must have become leaves by having
their sons deleted, which means they would not have been missing from the
code.  So the two vertices remaining at the end must also have been leaves
of the original tree.
}

\ppart How many numbered trees with $n$ vertices are there?

\solnospace{There are exactly as many $n$-vertex numbered trees a there
are length $n-2$ sequences of numbers between 1 and $n$.  So there are
$n^{n-2}$ numbered trees.

The reason there are the same number is that the tree reconstruction
procedure takes any such length $n-2$ sequence and returns an $n$-vertex
numbered tree whose code it is.  But the explanation above of why the
recursive reconstruction procedure is correct actually shows more: the
reconstructed tree is the \emph{unique} one with that code.

Now since every such length $n-2$ sequence is the code of some $n$-vertex
numbered tree, the coding procedure defines a surjection.  Since the tree
with that code is unique, the coding coding procedure also defines an
injection.  So the tree-coding function is a bijection.  Therefore the
number of numbered trees with $n$ vertices is the same as the number of
length $n-2$ sequences of integers between 1 and $n$.}

\eparts




%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 8    *
%**************


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

\problem {\bf (15 points)} Solve the following counting problems.
Simplifying expressions is unnecessary.

\begin{problemparts}

\problempart Find the number of 5-card hands with consecutive values,
e. g. $8\clubsuit \ 9\heartsuit \ 10\diamondsuit \ J\diamondsuit \
Q\spadesuit$.  (Assume that the value of an ace is just above the
value of a king.)

\solution{There are 9 possible sequences of five consecutive values.
For each sequence, there are $4^5$ hands, since each value can be
represented by one of four different suits.  Therefore, there are a
total of $9 \cdot 4^5$ such hands.}

\problempart Find the number of 5-card hands with exactly three aces.

\solution{ We can choose the three aces in $\binom{4}{3}$ ways, and
we can choose the remaining two cards in $\binom{48}{2}$ ways.  Thus,
there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\problempart Find the number of 5-card hands in which every suit
appears at most twice.

\solution{There are two cases.  Either one suit appears twice or else
two suits appear twice.  The number of hands in which one suit appears
twice is $\binom{13}{2} \cdot 13^3 \cdot 4$.  The number of hands in
which two suits appear twice is $\binom{13}{2}^2 \cdot 13 \cdot 12$.
Therefore, there are a total of

\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot 12
\]

such hands.}

\problempart There are 15 sidewalk squares in front of the Lab for
Computer Science.  Suppose that Theory Pig can be thrown so that he
bounces on 0, 1, 2, or 3 distinct sidewalk squares.  How many
different throws are possible?

\solution{
\[
\binom{15}{0} + \binom{15}{1} + \binom{15}{2} + \binom{15}{3}
\]
}

\problempart In how many different ways can the numbers shown on a red
die, a green die, and a blue die total up to 15?  Assume that these
are ordinary, 6-sided dice.

\solution{We fall back on explicit enumeration.  Let $R$, $G$, and $B$
be the values shown on the three dice.

\begin{eqnarray*}
R = 1, B + G = 14 & \rightarrow & 0 \ \text{ways} \\
R = 2, B + G = 13 & \rightarrow & 0 \ \text{ways} \\
R = 3, B + G = 12 & \rightarrow & 1 \ \text{way} \\
R = 4, B + G = 11 & \rightarrow & 2 \ \text{ways} \\
R = 5, B + G = 10 & \rightarrow & 3 \ \text{ways} \\
R = 6, B + G = 9 & \rightarrow & 4 \ \text{ways} \\
\end{eqnarray*}

Thus there are 10 ways in total.
}

\problempart How many permutations are there of the letters
$MISSISSIPPI$?

\solution{
\begin{eqnarray*}
\frac{11!}{4! \ 4! \ 2!}	& = &	34650
\end{eqnarray*}
}

\problempart Find the number of squences of $k$ non-negative integers
with sum equal to $n$.  For example, if $k = 2$ and $n = 3$, then
there are four sequences: $0 + 3$, $1 + 2$, $2 + 1$, and $3 + 0$.

\solution{This is equal to the number of strings with $n$ stars and
$k-1$ bars.  The sizes of the $k$ groups of stars are the values of
the $k$ integers in the sequence.  Thus, there are

\[
\binom{n+k-1}{n}
\]

such sequences.
}

\problempart Find the number of squences of $k$ positive integers with
sum equal to $n$.  For example, if $k = 2$ and $n = 4$, then there are
three sequences: $1 + 3$, $2 + 2$, and $3 + 1$.

\solution{This is equal to the number of strings with $n-k$ stars and
$k-1$ bars.  Numbers in the sequence are one greater than the sizes of
the groups of stars.  Thus, there are

\[
\binom{n-1}{k-1}
\]

sequences.}

\end{problemparts}

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

\problem {\bf (10 points)} Solve the following counting problems.

\begin{problemparts}
\problempart Suppose that Theory Pig starts at position $(0, 0)$.  At
any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).  In how many different
ways can he reach position $(n, n)$, where $n$ is a non-negative
integer?

\solution{Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $N$ to be north steps.  This gives $\binom{2n}{n}$
different ways to reach $(n, n)$.}

\problempart How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{ There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are

\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}

\end{problemparts}

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

\problem {\bf (20 points)} Suppose that every two people either know
one another or else are strangers.  How many people must there be in a
room to guarantee that there are either 6 people who all know each
other or 6 people who are all strangers to one another?

The solution to this problem is a number called $R(6, 6)$.  The
solution to the simpler problem involving groups of only 5 people is
called $R(5, 5)$.  Earlier in the course, we solved a still-simpler
version of this problem involving groups of just 3 people in about ten
minutes.  Finding $R(5, 5)$ and $R(6, 6)$ is a bit more tricky.  The
following is taken from a well-known text, {\em Ten Lectures on the
Probabilistic Method}, by Joel Spencer:

\begin{quotation}
Erdos [possibly the 20th century's top mathematician] asks us to
imagine an alien force, vastly more powerful than us, landing on Earth
and demanding the value of $R(5, 5)$ or they will destroy our planet.
In that case, he claims, we should marshall all our computers and all
our mathematicians and attempt to find the value.  But suppose,
instead, that they ask for $R(6, 6)$.  In that case, he believes, we
should attempt to destroy the aliens.
\end{quotation}

Given rumors that a new fleet is forming on Xoros 19, we had better
take a stab at $R(6, 6)$.  For now, however, we will only try to prove
that $R(6, 6) > 17$.

\begin{problemparts}
\problempart If there are $n$ people in a room, then how many
different pairs of people are there?

\solution{
\[
\binom{n}{2}
\]
}

\problempart A {\em configuration} of a group of people is a setting
of who-knows-who.  For example, there are two possible configurations
of a group of just two people: either they know each other or they are
strangers.  How many different configurations are possible in a room
with $n$ people?

\solution{Since every two people either know each other or are
strangers, the number of configurations is

\[
2^{\binom{n}{2}}.
\]
}

\problempart Suppose that there is a specific group of six people who
all know each other.  How many configurations are possible with this
restriction?

\solution{
\[
2^{\binom{n}{2} - \binom{6}{2}}
\]
}

\problempart In a set of $n$ people, how many different subsets of six
people are there?

\solution{
\[
\binom{n}{6}
\]
}

\problempart Use your answers to the preceding two parts to find an
upper bound on the number of configurations in which there exists some
group of six people who all know each other.

\solution{There are $\binom{n}{6}$ different sets of six people.  For
each set of six people, there are $2^{\binom{n}{2} - \binom{6}{2}}$
configurations in which these people all know each other.  Therefore,
there are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some set of six people all know each other.
}

\problempart Give an upper bound on the number of configurations in
which there exist either six people who all know each other or six
people who are all strangers.

\solution{
There are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people all know each other.  By the
same argument, there are at most this many configurations of six
people that are all strangers.  Therefore, there are at most

\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people either all know each other or
are all strangers.}

\problempart Use your answers to parts (b) and (f) to prove that there
exists a configuration of $17$ people such that no set of six people
all know each other or are all strangers.  This implies that $R(6, 6)
> 17$.

\solution{
By part (a), there are

\[
2^{\binom{17}{2}}
\]

configurations of 17 people.  By part (f) there are at most

\[
2 \cdot \binom{17}{6} \cdot 2^{\binom{17}{2} - \binom{6}{2}}
\]

configurations in which some set of six people either all know each
other or are all strangers.  If the first quantity is greater than the
second, then there must exist a configuration of 17 people such that
there is no set of six people that all know each other or are all
strangers.  The second quantity divided by the first is

\begin{eqnarray}
2 \cdot \binom{17}{6} \cdot 2^{- \binom{6}{2}} & \approx & 0.75.
\end{eqnarray}

Therefore, the first quantity is greater than the second, as desired.

The best known bounds are $102 \leq R(6, 6) \leq 165$.
Asymptotically, the simple technique outlined above gives a lower
bound on $R(k, k)$ that is within a factor of 2 of the best known.}

\end{problemparts}

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

\problem {\bf (20 points)} A string of parentheses is called
``balanced'' if the number of ('s is equal to the number of )'s and
the number of )'s never exeeds the number of ('s as the string is read
from left to right.  For example, (()())((())) is a balanced string,
but ())( is not.  With three pairs of parentheses, five different
balanced strings can be formed.  These five strings are listed below.

\[
((())) \quad (()()) \quad (())() \quad ()(()) \quad ()()()
\]

In general, the number of balanced strings increases rapidly with the
number of pairs of parentheses.  Your diligent TA stayed up until
dawn, slaving away with a dull pencil stub, working out the following
table:\footnote{This is a lie; he cranked it out with a C program in
about six minutes.}

\bigskip

\centerline{
\begin{tabular}{ccc}
Pairs of Parentheses & \quad & Number of Balanced Strings \\
0 & & 1 \\
1 & & 1 \\
2 & & 2 \\
3 & & 5 \\
4 & & 14 \\
5 & & 42 \\
6 & & 132 \\
7 & & 429 \\
8 & & 1430 \\
9 & & 4862 \\
10 & & 16796 \\
11 & & 58786 \\
12 & & 208012
\end{tabular}
}

\bigskip

In an apparently unrelated calculation, your exhausted TA then used
his final drops of energy and the last nubbin of his pencil to
evaluate $500000 - 1000 \sqrt{249999}$ out to 72 decimal
places:\footnote{This is also a lie; he plugged the thing into Maple.}

\[
1.000001000002000005000014000042000132000429001430004862016796058786208012\ldots
\]

Compare the table to the irrational number.  The goal of this problem
is to explain the apparently miraculous correspondence.

\begin{problemparts}

\problempart Let $p_n$ be the number of balanced strings containing
$n$ pairs of parentheses.  Express $p_n$ with a recurrence equation
and sufficient base cases.

\solution{ Note that every balanced string with $n \geq 1$ pairs of
parentheses consists of a balanced string with $k$ pairs, all enclosed
in parentheses, followed by a balanced string with $n-k-1$ pairs:

\[
\text{string with $n$ pairs} = ( \ \text{string with $k$ pairs} \ ) \ 
	\text{string with $n-k-1$ pairs}
\]

This observation suggests the following recurrence equation:

\begin{eqnarray*}
p_0	& = &	1 \\
p_n	& = &	\sum_{k=0}^{n-1} p_k \cdot p_{n-k-1} \quad (n \geq 1)
\end{eqnarray*}
}

\problempart Let $P(x)$ be the generating function for the number of
balanced strings; that is,

\begin{eqnarray*}
P(x) & = & p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots.
\end{eqnarray*}

Using the recurrence relation as a guide, find a (non-trivial)
equation relating and $P(x)$ and the square of $P(x)$.

\solution{
The summation in the recurrence equation suggests

\begin{eqnarray*}
P(x) & = & x P(x)^2 + 1.
\end{eqnarray*}

We can verify this equation using the recurrence relation.

\begin{eqnarray*}
x P(x)^2 + 1
	& = &	x (p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots)^2 + 1 \\
	& = &	x (p_0^2 + (p_0 p_1 + p_1 p_ 0) x + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^2 + \ldots) + 1 \\
	& = &	1 + p_0^2 x + (p_0 p_1 + p_1 p_ 0) x^2 + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^3 + \ldots \\
	& = &	1 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots \\
	& = &	P(x)
\end{eqnarray*}
}

\problempart Apply the quadratic formula to obtain a closed-form
expression for the generating function $P(x)$.

\solution{
Given that $P(x) = x P(x)^2 + 1$, the quadratic formula implies that

\begin{eqnarray*}
P(x)	& = & \frac{1 \pm \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}

If $x$ is small, then $P(x)$ should be about $p_0 = 1$.  Therefore,
the correct choice of sign is

\begin{eqnarray*}
P(x)	& = & \frac{1 - \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}
}

\problempart Show that $P(1/1000000) = 500000 - 1000 \sqrt{249999}$.

\solution{
\begin{eqnarray*}
P(1/1000000)
	& = &	\frac{1 - \sqrt{1 - \frac{4}{1000000}}}
		{\left(\frac{2}{1000000}\right)} \\
	& = &	500000 - 500000 \sqrt{\frac{249999}{250000}} \\
	& = &	500000 - 1000 \sqrt{249999}
\end{eqnarray*}
}

\problempart Explain why the digits of this irrational number encode
the number of balanced strings of parentheses.

\solution{Suppose that we symbolically carry out the substitution done
in the preceding problem part.

\begin{eqnarray*}
P(x)		& = &	p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots \\
P(10^{-6})	& = &	p_0 + p_1 10^{-6} + p_2 10^{-12}
				+ p_3 10^{-18} + \ldots
\end{eqnarray*}

Thus, $p_0$ appears in the units position, $p_1$ appears in the
millionths position, $p_2$ appears in the trillionths position, and so
forth.
}
\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps6
\textbf{Counting Using Functions}

Determine the cardinality of the following: 
\begin{problemparts}
\vspace{-\baselineskip}
\problempart %
The number of binary relations on a set $A$ of $n$ elements.

\solution{%
  [[[I get $2^{(n^2)}$, using bijection with Boolean matrices.]]]
  }

\vspace{-\baselineskip}
\problempart %
The number of different digraphs without self-loops for a set $V$ of
$n$ vertices.

\solution{%
  [[[I get $2^{(n^2 - n)}$, thinking of Boolean matrices without the
  diagonal elements.]]]
}

\vspace{-\baselineskip}
\problempart %
The number of functions from $A$ to $B$, where $|A| = n$ and $|B| =
m$.

\solution{%
  }
\end{problemparts}

\problem %source: spring00 ps7
  \problem Fourteen hackers and eight theoreticians are on the faculty
  of a school's EECS department.  The individuals are distinguishable.
  How many ways are there to select a committee of six members if at
  least 1 hacker must be on the committee?  You may express this in
  terms of binomial coefficients.
  
  \omitsolution{We need to count all possible combinations of people such
    that there is at least one hacker in every combination, but we must
    remember not to count any combinations multiple times.
    
    We can have committees with
    
    1 hacker, 5 theoreticians: $ { 14 \choose 1} {8 \choose 5}$\\
    2 hackers, 4 theoreticians: $ { 14 \choose 2} {8 \choose 4}$\\
    3 hackers, 3 theoreticians: $ { 14 \choose 3} {8 \choose 3}$\\
    4 hackers, 2 theoreticians: $ { 14 \choose 4} {8 \choose 2}$\\
    5 hackers, 1 theoretician: $ { 14 \choose 5} {8 \choose 1}$\\
    6 hackers, 0 theoreticians: $ { 14 \choose 6} {8 \choose 0}$\\
    
    So there are $ { 14 \choose 1} {8 \choose 5} + { 14 \choose 2} {8
      \choose 4} + { 14 \choose 3} {8 \choose 3} + { 14 \choose 4} {8
      \choose 2} + { 14 \choose 5} {8 \choose 1} + { 14 \choose 6} {8
      \choose 9}$ different possibilities for committees.
    
    Another way to solve this problem is to say that there are ${22
      \choose 6}$ different committees, and ${8 \choose 6}$ committees
    of just theoreticians.  So there are ${22 \choose 6} - {8 \choose
      6}$ different possibilities for committees.
}




\iffalse {
% new version for fall 2001

\problem %source: spring00 ps7
Consider the Towers of Hanoi game with $n$ disks and $3$
  distinct poles.  An arrangement of the disks on the poles is said to
  be legal if no disk rests on a smaller disk. How many different legal
  arrangements of the $n$ disks on the $3$ poles are there?
  
  \omitsolution{ Since each disk is different (and therefore
    distinguishable), we have at least $3^n$ different configurations
    by the product rule: 3 choices for the largest disk, 3 choices for
    the second largest disk, and so on.  Furthermore, since the disks
    on a particular pole must be in order from largest on the bottom
    to smallest on the top, there is a unique way to order the disks
    given a particular assignment to the poles; hence, there are
    exactly $3^n$ different configurations.}
}


\problem %source: spring00 ps7
% Incl/excl
% ps7 : f94 : 9
How many integers in the range from 1 to 1000 are not
  divisible by any of the numbers 6, 10, and 15?
  
  \omitsolution{Here we use inclusion-exclusion to count the number of
    integers from 1 to 1000 not divisible by 6, 10, or 15.  Make a
    table, and add the numbers with appropriate signs:
    
    \begin{tabular}{|c|r|r|c|}
      \hline
      divisible by & least common multiple & number of integers & include/exclude \\
      each of      & of divisors           &from 1 to 1000     & $+/-$\\
      \hline
      \hline
      &   1 & 1000 & $+$ \\
      6         &   6 & 166 & $-$ \\
      10        &  10 & 100 & $-$ \\
      15        &  15 &  66 & $-$ \\
      6, 10     &  30 &  33 & $+$ \\
      6, 15     &  30 &  33 & $+$ \\
      10, 15    &  30 &  33 & $+$ \\
      6, 10, 15 &  30 &  33 & $-$ \\
      \hline
    \end{tabular}
    
    \hspace{3in} These add up to 734.}

\problem %source: spring00 ps7
% ps7 : s98 : 3
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.  Use inclusion-exclusion to find the
  number of square-free positive integers strictly less than 151.
  
  \omitsolution{We use inclusion-exclusion as done in lecture for the case
    of prime numbers. We first compute the number of positive integers
    less than 150 that are not square free.
    
    Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set
    of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
    less than 150. The cardinality of the union of these sets is given
    by
    
    \begin {eqnarray*}
      |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
      |A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
      - |A_2 \cap A_3 | - |A_2 \cap A_5|\\
      & = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
      + \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
      & &  - \lfloor 150/(2^23^2) \rfloor
      - \lfloor 150/(2^25^2 \rfloor\\
      & = & 37 + 16 + 6 + 3 + 1 -4-1\\
      & = & 58
    \end {eqnarray*}
    Therefore the number of square-free positive integers less than
    150 is
    
    \[ 150 - 58 = 92 \ . \]}

\problem %source: spring00 ps7
% Permutations/counting
% ps8 : f99 : 1
Enumeration and permutations

\bparts

\ppart Kyle is manager of the MIT Chess Club.  After a long and
grueling match, the players have gone home, leaving Kyle to put the
players' unlabeled chess sets back in their lockers.  If there are
$n$ players/lockers and $n$ chess sets, how many ways could Kyle
place chess sets in lockers such that there is exactly one chess set
in each locker, disregarding the correctness of such placement?

\omitsolution{We can formulate this as a function-counting problem.  Since
  there are $n$ chess sets and $n$ lockers, we can assign each chess
  set a unique number between 1 and $n$ inclusive, and do the same for
  the lockers.  Then, we are looking for an injective function from
  $\set{1,\ldots,n}\rightarrow \set{1,\ldots,n}$.
  
  Note that the first element of the domain has $n$ possible mappings;
  the second has $n-1$ possible mappings (i.e., all but the first
  element); the third has $n-2$ possible mappings (i.e., all but the
  first two); and so on, for all $n$ elements of the domain.  This is
  simply $n!$, the number of permutations of $\set{1,\ldots,n}$.}

\remove{
\ppart This begs the question: how many ways can Kyle achieve the feat
of placing every chess set in the wrong locker?  Give an expression
for general $n$ and then approximate the value for $n=10$.

\omitsolution{This is the number of \textit{derangements} of the set of
  $n$ elements.  We do not know a closed form for this number, so we
  denote it by $D_n$ as derived in Rosen, \S 5.6.  To approximate
  $D_{10}$ we will use Stirling's approximation, $D_{10}\approx$
  something =)} }

\ppart Say Kyle recognizes Josh's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Kyle place chess sets in lockers assuming he at
least gets Josh's right?

\omitsolution{We function count, as before.  Without loss of generality,
  assign Josh's chess set and locker the number 1, and set $f(1)=1$
  in our function.  We can now create an injective function on the
  remaining elements; by part (a), this is simply $(n-1)!$.  }

\ppart Say Kyle really resents Josh's brainpower, and decides to get
even by putting Josh's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Josh's chess set into Josh's locker?

\omitsolution{Again, we function count.  (Notice a pattern?)  Without loss
  of generality, assign Josh's chess set and locker the number 1,
  as before.  We can first choose an element $j\not=1$ from the domain
  to map to $1$ ($(n-1)$ ways).  Then, we note that we have $n-1$
  elements of the domain and $n-1$ elements of the codomain in which
  we want an injection, which we can choose in $(n-1)!$ ways from part
  (a).  This gives us $(n-1)(n-1)!$, which makes sense since, from
  part (b), $(n-1)(n-1)!+(n-1)!=n!$.}

\ppart Kyle has a sudden change of heart and decides to be nice to
Josh.  At this time, he also realizes that Shishir has
conscientiously written his name on the outside of his chess set, so
now Kyle knows the correct destinations of two chess sets.  How many
arrangements are there now?

\omitsolution{As in part (b), we can simply create an injective function
  on the remaining elements, which gives us $(n-2)!$.}

\ppart Say Kyle is taking mind-altering drugs and has again changed
his mind about Josh.  Still being able to discern Josh's and
Shishir's chess sets---but wishing to ill-place Josh's---Kyle can
place chess sets in lockers in how many ways?

\omitsolution{Assign 1 to Josh's locker and chess set, and 2 to
  Shishir's locker and chess set.  We know that $|A\cap
  B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of functions
  with $f(2)=2$ and $B$ to be the set of functions with $f(1)\not=1$,
  then we know $|A|$ and $|A\cap\bar B|$, the latter of which is the
  solution to the previous part; so, the answer is
  $(n-1)!-(n-2)!=(n-2)(n-2)!$.  }

\eparts

\problem %source: spring00 ps7
% ps7 : f95 : 2
On a set of $n$ elements how many of the following are there
\bparts

\ppart binary relations? \omitsolution{$2^{n^2}$ since there are this many
  different $0-1$ matrices of order $n$.}

\ppart symmetric binary relations? \omitsolution{The matrix associated with a
  symmetric relation is symmetric.  Since there are $2^ {n+{n\choose
      2}}$ different symmetric matrices there are an equal number of
  symmetric relations.}

\ppart reflexive binary relations? \omitsolution{The matrix associated with a
  reflexive relation has $1$'s along the main diagonal . Hence the
  number of such matrices, and therefore reflexive relations, is
  $2^{n^2 - n}$ .}

\ppart symmetric and reflexive binary relations? \omitsolution{The matrix
  associated with a symmetric and reflexive relation is symmetric and
  ha s $1$'s along the main diagonal. Hence the number of such
  relations is $2^{{n\choose 2} }$.}

\ppart symmetric or reflexive binary relations? \omitsolution{The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+{n\choose
      2}} - 2^{{n\choose 2}}$.}

\eparts

\problem %source: spring00 ps7-5
% source: spring96 ps7
% topic: combinatorics, balls in boxes, stars and bars

\bparts

% add a new simpler part without the restriction of ``with the first two 
% boxes having collectively at most four balls''?

\ppart the balls are identical?

\solution{
\noindent
Let us consider placing $n$ balls into $k$ boxes so that exactly $r$
balls are placed in the first two boxes. This can be done in
\[
{r+2-1 \choose 2-1}{(n-r)+(k-2)-1 \choose (k-2)-1}
\]
ways, since there are ${\rm BP}(r,2) = {r+2-1 \choose 2-1}$ ways to
place $r$ balls into first two boxes and ${\rm BP}(n-r,k-2) =
{(n-r)+(k-2)-1 \choose (k-2)-1}$ ways to place the remaining $n-r$
balls into the other $k-2$ boxes. We can place the balls into boxes,
so that {\em at most} $r$ balls go into the first two boxes, in
\[
\sum_{i=0}^r{{i+2-1 \choose 2-1}{(n-i)+(k-2)-1 \choose (k-2)-1}}
\]
ways. In particular for $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{i+2-1 \choose 2-1}{(8-i)+(6-2)-1 \choose (6-2)-1}} = 1056{.}
\]
}

\ppart the balls are distinct?

\solution{
\noindent
As in the part (a), we compute the number of ways $n$ balls can be
placed into $k$ boxes so that exactly $r$ of them are placed in the
first two boxes. Since the balls are distinct, we have ${n \choose r}$
ways to choose which balls to place in the first two boxes, and then
we have $2^r$ ways to place the balls into first two boxes, and
$(k-2)^{n-r}$ ways to place the rest of the balls into the remaining
$k-2$ boxes. Thus the total number of posibilities is
\[
{n \choose r}2^r(k-2)^{n-r}{.}
\]
If we require that {\em at most} $r$ balls go into the first two boxes
we compute that the number of posibilities is
\[
\sum_{i=0}^r{{n \choose i}2^i(k-2)^{n-i}}{.}
\]
For $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{8 \choose i}2^i(6-2)^{8-i}} = 1531904{.}
\]
}

\eparts

\problem %source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars
A pizza house is having a promotional sale. Their commercial reads:\\
``\ldots buy $2$ large pizzas at regular price, get up to $11$ different 
toppings for 
each pizza absolutely free. That's $4,194,304$ different ways to design your
order! \ldots''
\newline
\emph{Note:} $\displaystyle \left( \sum_{k=0}^{11}{11 \choose k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$

\bparts %

\ppart Show that $4,194,304$ is actually wrong and give the right
answer for the number of ways that you can choose toppings for the two
pizzas.

\solution{
The number of ways to choose different toppings for one pizza is
clearly $A \equiv \displaystyle \sum_{k=0}^{11}{11 \choose k} = 2^{11}
= 2,048$.  However, when they say there are $A^2$ different ways to
choose toppings for two pizzas, they are making the mistake of
counting the combination ``one mushroom pizza, and one cheese pizza"
as different from the combination ``one cheese pizza, and one mushroom
pizza."

The right solution is $ \displaystyle A+{A \choose 2} = \frac{1}{2}
(A^2+A) = 2,098,176 $, where $A$ is the number of ways to choose $2$
pizzas with the same toppings, and ${A \choose 2} $ is the number of
ways to choose $2$ different pizzas.
}

%To clarify, a valid choice of 2 pizzas
%does not allow multiple copies of the same topping on the same pizza, and does
%not require that the two pizzas themselves be distinct.
%comment on the fact that ordering of the 2 pizzas obviously doesn't matter???
%\solution{
%The problem double counts some pairs of pizzas, as ordering does not matter.
%For instance, a ``pepperoni pizza and a mushroom pizza'' is counted 
%differently from a ``mushroom pizza and a pepperoni pizza.''
%\newline
%Once you have your total number of possible single pizza types, you must 
%choose any two of them, allowing repition.
%\newline
%The correct formula is $\displaystyle { {\left( \sum_{k=0}^{11}{11 \choose k} 
%\right) + 2 - 1} \choose 2}$, which gives \bf{NEED TO FILL IN} combinations.
%}

\ppart  Now assume that you can choose any number of the same 
topping as long as the total number of toppings is no more than $11$.
(That is, you can have $2$ meatball, $4$ ham and $5$ sausage toppings if 
you are truly a meat lover.) How many different ways can you now choose
toppings for your two pizzas?

\solution{
For a single pizza, this is the ``stars and bars'' problem in disguised
form.  If $k$ is the total number of toppings you want on a pizza then
the number of ways of throwing $k$ identical balls into $11$ bins is
identical to choosing a total of $k$ toppings out a total of $11$
different topping-possibilities.  

Hence the number of ways to order one pizza is $B \equiv \displaystyle
\sum_{k=0}^{11}{10+k \choose k} = {22 \choose 11} = 705,432$.  
Using the same argument as in part
(a), we see that the number of ways to order two pizzas is
$\displaystyle B+ {B \choose 2}=\frac{B^2+B}{2} = 248,817,506,028$.
}

\eparts


\problem %source: spring00 ps7-5
% source: fall94 ps7, adapted
% topic: combinatorics; easy confidence builder
%%              from M&R, # 4.3.21 and 4.3.22
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?
\solution{
%\newline
$52^4 = 7311616$.
}
\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.
\solution{
%\newline
$52^4 \div 2^4 = 456976 = 26^4$.
}
\problempart
The operating system is changed so that file names may be {\em at least} one 
letter and {\em up to\/}
four letters long.  Repeat {\bf (a)} and {\bf (b)}.  Can the division
rule still be used?
\solution{
%\newline
$\sum_{i=1}^4 52^i = (52^5-52)/(52-1) = 7454980$; $\sum_{i=1}^4
26^i = (26^5-26)/(26-1) = 475254$.  The division rule can be applied only to
the individual terms of the summation.
}
\end{problemparts}

\problem %source: spring00 ps7-5
% source: spring95, ps7
% topic: basic combinatorics

\bparts
\ppart How many ways can $2n$ people be divided into $n$ pairs?

\solution{
$\displaystyle (2n)!/ n! 2^n$.

Consider all the ways of ordering the $2n$ people in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are ${2n \choose n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
${2n \choose n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle {2n \choose n} n! /2^n$.

\fi
}

\ppart How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solution{
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}

\eparts

\problem %source: spring00 ps7-5
% source: parts from fall95 ps7, parts from fall94 ps7
% topic: binomial coefficients in large polynomials

Find the coefficients of 
\begin{problemparts}
\problempart $x^5$ in $(1+x)^{11}$
\solution{
%\newline
${11\choose 5} = 462$
}
\problempart $a^2b^8$ in $(a+b)^{10}$
\solution{
%\newline
${10 \choose 2} = 45$
}
\problempart $a^6b^6$ in $(a^2+b^3)^5$
\solution{
%\newline
  $a^6b^6 = (a^2)^3 (b^3)^2$, so the coefficient is ${5 \choose 3} =
  10$
}
\problempart $x^3$ in $(3+4x)^6$
\solution{
%\newline
${6 \choose 3}3^3 4^3 = 34560$
}
\problempart $x^{10}$ in $(x+(1/x))^{100}$
\solution{
%\newline
${100 \choose 55}$
}
\problempart $x^8y^9$ in $(3x+2y)^{17}$
\solution{
%\newline
${17 \choose 8}3^82^9$
}
\problempart $x^k$ in $(x^2 - (1/x))^{100}$
\solution{
%\newline
$x^k$ has a nonzero coefficient iff $-100 \leq k \leq  200$ and $k = 2$ mod $3$. In such a case the coefficient is ${100\choose (100 + k)/3}(-1)^{(200 - k)/3}$.
}
\end{problemparts}

\problem %source: spring00 ps7-5
% source: fall94 ps7
% topic: combinatorics, binomial theorem
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.
%\newline
\solution{
\begin{eqnarray*}
x^{-n}(1+x)^n x^n (1+x^{-1})^n &=& x^{-n}(1+x)^n (x+1)^n \\
(1+x)^n (1+x^{-1})^n &=& x^{-n}(1+x)^{2n}\\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^{-j} &=& x^{-n}\sum_{i=0}^{2n} {2n\choose i}x^i\\
\sum_{i=0}^n {n\choose i}^2 &=& {2n\choose n}
\end{eqnarray*}
by equating the coefficients of $x^0$.
}

\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.
%\newline
\solution{
Suppose we have $2n$ objects, $n$ of which are red, and $n$ of which are blue.
How many ways can we pick $r$ red ones and $n-r$ blue ones?  Clearly this is
$${n \choose r} {n \choose n-r} = {n \choose r}^2.$$  How many ways can we choose $n$ objects
total, regardless of how many are of each color?  This is just 
$$ \sum_{r=0}^n {n \choose r}^2.$$  But there are  ${2n \choose n}$ ways to
choose $n$ objects, so these must be the same number.
}
\end{problemparts}

\problem %source: spring00 ps7-5
% source: fall94 ps7 bonus problem
% topic: combinatorics, geometry
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?

\solution{
If two chords intersect in the interior of the circle, then their endpoints
must be four distinct points.  Since no three chords intersect, any
intersection in the interior corresponds to precisely one set of four points on
the circle.  Furthermore, for any set of four points on the circle, there
is precisly one way to draw a pair of chords which intersect in the interior.
Hence there is a bijection between the intersections in the interior and the
set of four-tuples of points, so there are ${n \choose 4}$ intersections in the
interior.
}


\problem %source: spring00 ps7-5
% source: fall95 ps7
% topic: combinatorics, summations
Prove that 
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts
\ppart using a combinatorial argument.
\ppart by finding a closed form for $ {\displaystyle \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and evaluating it at $x=1$.
\eparts

\problem %source: spring00 ps7-5
% source: spring96 ps7
% topic: combinatorics, algebraic manipulation
Prove the following identities both by algebraic manipulation and
by giving a combinatorial argument:
\bparts
\ppart \[{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}\]
\ppart \[{2n \choose 2} = 2{n \choose 2} + n^2\]
\ppart \[ \sum_{k=0}^n 2^k {n \choose k} = 3^n\]
\eparts

\problem %source: spring00 ps7-5
% source: fall95 ps7
% topic: combinatorics, morse code
\ppart Given that two dots in a row can get confused with a dash, how many 
different characters can you represent with $k$ dots/dashes that have no consecutive dots?
\ppart Suppose a dot takes 1 seconds, a dash takes 3 seconds, and each must
be followed by a 1 second interval of silence.  How many morse symbol
sequences have sending times less than k seconds (including the last
interval of silence)? 
\eparts
Hint: For parts c) and d) determine and solve a recurrence
conditioning on the value of the first symbol.

\problem %source: spring00 ps7-5
% source: fall94 ps7
% topic: combinatorics
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 %source: spring00 ps7-5
% source: fall95 ps7
% topic: combinatorics, counting relations
On a set of $n$ elements how many of the following are there
\bparts
\ppart relations?
\ppart symmetric relations?
\ppart reflexive relations?
\ppart symmetric and reflexive relations?
\ppart symmetric or reflexive relations?
\ppart equivalence relations (this problem is for extra credit)?
\eparts

%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%  S99 ps5


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

\problem {\bf (10 points)} The expression $\binom{n}{k}$ is read ``$n$
choose $k$'' and represents the quantity
\[\frac{n!}{k! \ (n-k)!}.\]
This expression comes up frequently in probability and combinatorics
and will be used extensively later in this course.  Suppose that $n$
is even.  Prove that

\begin{eqnarray*}
\binom{n}{n/2}
	& = &	\Theta(2^n / \sqrt{n}).
\end{eqnarray*}

Use the following form of Stirling's formula:

\begin{eqnarray*}
n!	& \sim &	\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\end{eqnarray*}

\solution{Though substituting in Stirling's formula initially gives a
complicated expression, most of the square roots and the exponentials
cancel.  For simplicity, let $m = n/2$.

\begin{eqnarray*}
\binom{n}{n/2}
	& = &	\binom{2m}{m} \\
	& = &	\frac{(2m)!}{m! \ m!} \\
	&\sim&	\frac{\sqrt{4 \pi m} \cdot \left(\frac{2m}{e}\right)^{2m}}
		{\left(\sqrt{2 \pi m} \cdot
			\left(\frac{m}{e}\right)^m\right)^2} \\
	& = &	\frac{2^{2m}}{\sqrt{\pi m}} \\
	& = &	\frac{2^n}{\sqrt{\frac{1}{2} \pi n}} \\
	& = &	\Theta\left(\frac{2^n}{\sqrt{n}}\right)
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%% S99 ps8


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

\problem{\bf (10 points)}

How many zeroes does the decimal representation of $100!$ end with?

\solution{ $100!$ ends in $k$ zeros where $k$ is the largest number
s.t. $10^k$ divides $100!$.  Since $10 = 2\cdot 5$, we know that
$10^k=2^k\cdot5^k$, and so we are looking for the largest $k$ such that
$2^k\cdot5^k\, |\, 100!$.  Clearly, $2^k$ divides $100!$ for larger $k$
than $5^k$ divides $100!$, since multiples of two are more common in
$100!$ than multiples of five.  So, we just need to determine the largest
$k$ such that $5^k$ divides $100!$, in other words the number of multiples
of $5$ contained in $100!= 1 \cdot 2 \cdot 3 \cdots 100$.  Each multiple
of $5$ less than or equal to $100$ will contribute one to this $k$.  There
are $20$ such multiples: $5, 10, 15, ..., 95, 100$.  Each multiple of $25$
will contribute two to this $k$, since $25^n = 5^n\cdot5^n$.  There are
four of these: $25, 50, 75, 100$.  So, multiples of $25$ contribute a
total of $8$.  However, the set of multiples of $25$ is a subset of the
set of multiples of $5$, and so we have double counted some elements, and
we must substract one double-counted contribution to $k$ from each
multiple of $25$, i.e. $4$.  This gives the total of $20+8-4=24$ zeroes in
$100!$.}

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

\problem {\bf (10 Points)}

Using the principle of inclusion-exclusion, show that there are fewer than 
50,000 prime numbers less than or equal to 210,000.

\solution{
Since natural numbers are either composite or prime, we can instead
show that there are at least $210,000 - 50,000 = 160,000$ composite
numbers less than or equal to $210,000$.  Let's count composite
numbers by counting the multiples of $2, 3, 5$, and $7$:

\[\begin{array}{llr}
\mbox{multiples of }2: &210,000/2 &= 105,000\\
\mbox{multiples of }3: &210,000/3 &= 70,000\\
\mbox{multiples of }5: &210,000/5 &= 42,000\\
\mbox{multiples of }7: &210,000/7 &= 30,000\\
\hline
  &&+ 247,000
\end{array}\]

However, we have double counted the numbers which are multiples of two
of $\{2, 3, 5, 7\}$.  So, using inclusion/exclusion, we subtract these
back out:

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3\}: & 210,000/6   &= &  35,000\\
\mbox{multiples of }\{2,5\}: & 210,000/10  &= &  21,000\\
\mbox{multiples of }\{2,7\}: & 210,000/14  &= &  15,000\\
\mbox{multiples of }\{3,5\}: & 210,000/15  &= &  14,000\\
\mbox{multiples of }\{3,7\}: & 210,000/21  &= &  10,000\\
\mbox{multiples of }\{5,7\}: & 210,000/35  &= &   6,000\\
\hline
  &&& - 101,000
\end{array}\]

Now, we must add back in the numbers which are multiples of three of
$\set{2, 3, 5, 7}$:

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3,5\}: & 210,000/30  &=& 7,000\\
\mbox{multiples of }\{2,3,7\}: & 210,000/42  &=& 5,000\\
\mbox{multiples of }\{2,5,7\}: & 210,000/70  &=& 3,000\\
\mbox{multiples of }\{3,5,7\}: & 210,000/105 &=& 2,000\\
\hline
 &&& +  17,000
\end{array}\]

And subtract out the multiples of $2\cdot3\cdot5\cdot7 = 210$:

\[\begin{array}{llr}
\mbox{multiples of }\{2,3,5,7\}: & 210,000/210 &=  1,000\\
\hline
 &&-  1,000
\end{array}\]

Totaling, we get $247,000 - 101,000 + 17,000 - 1,000 = 162,000$, which is
more than the $160,000$ composite numbers whose existence we needed to
establish.

}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 Points)}
% STAS: change of exercise 23 from Rosen 4.3 to r-permutations

The English alphabet contains $21$ consonants and five vowels.
Suppose that all strings of six English alphabet characters with no
repetitions were English words.  How many such words contain:

\bparts

\ppart exactly $1$ vowel?
\ppart exactly $2$ vowels?
\ppart at least $1$ vowel?
\ppart at least $2$ vowels?

\eparts

\solution{
\begin{enumerate}
\item[{\bf (a):\ }]

$P(21,5)\cdot5\cdot6=(21\cdot20\cdot19\cdot18\cdot17)\cdot30=73,256,400$:
A choice of $5$ consonants with no repetition, a choice of a vowel,
and a choice of vowel's position.

\item[{\bf (b):\ }]
 
$P(21,4)\cdot(5\cdot4)\cdot(6\cdot5/2)=
(21\cdot20\cdot19\cdot18)\cdot20\cdot15=
43,092,000$: A choice of $5$ consonants with no repetition, a choice
of $2$ vowels, and a choice of the vowels' positions.

\item[{\bf (c):\ }]

$P(21+5,6)-P(21,6)=21\cdot6,033,120=126,695,520$: All words minus
words with no vowels.

\item[{\bf (d):\ }]

$P(21+5,6)-P(21,6)-P(21,5)\cdot5\cdot6=
126,695,520-73,256,400=53,439,120$: As above minus part (a).

\end{enumerate}
}




%%%%%%%%%%%%%%%%%%%% S99 ps9


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

\problem {\bf (15 points)} Solve the following counting problems.
Please leave factorials and binomial coefficients in your answers rather
than evaluate them.

\begin{problemparts}

\problempart How many poker hands contain no diamonds?

\solution{
\[
\binom{39}{5}
\]
}

\problempart How many different ways are there to arrange the letters
in the word BOOKKEEPER?

\solution{
\[
\frac{10!}{2! \ 2! \ 3!}
\]
}

\problempart A bug starts at position $(0, 0)$ and wants to reach
position $(4, 6)$ in 10 steps.  Each step is either north, south,
east, or west; that is, each step either increments or decrements one
coordinate.  How many different paths can the bug choose from?

\solution{
\[
\binom{10}{4}
\]
}

\problempart How many poker hands have cards with consecutive values?
(The possible values of a card, from lowest to highest, are $2, 3, 4,
\ldots, 10, J, Q, K, A$.)

\solution{There are 9 ways to choose the lowest value, and $4^5$ ways
to choose the suits.  Therefore, there are $9 \cdot 4^5$ such hands.}

\end{problemparts}

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

\problem {\bf (10 points)} An adequately-prepared 6.042 student has
the following texts:

\begin{itemize}
\item 5 copies of Cupillari
\item 2 copies of Rosen, 3rd edition
\item 6 copies of Rosen, 4th edition
\item 4 copies of the Fall 97 lecture notes
\end{itemize}

Copies of the same text are indistinguishable.  The student also has
a bookshelf with four distinguishable shelves.  In how many different
ways can the student arrange his texts on his bookshelf?  Assume that
each shelf has enough space to hold all of the texts and that two
arrangements are different if the texts appear in a different order on
a shelf.

\solution{Each arrangement of the texts on the bookshelf corresponds
to a sequence of the texts together with three ``dividers''.  The
texts on the first shelf appear in the sequence before the first
divider, the texts on the second shelf appear between the first and
second dividers, etc.  Thus, the number of different arrangements is

\[
\frac{20!}{5! \ 2! \ 6! \ 4! \ 3!}.
\]
}

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

\problem {\bf (15 points)} Before he formed the legendary Knights of
the Round Table, King Arthur experimented with some other
organizations.

\begin{problemparts}

\problempart After Arthur first selected his knights, he lined them up
for review.  Four of the knights were armored from head to toe and
were consequently indistinguishable from one another.  The other eight
knights were unarmored and could be distinguished.  In how many
different ways could Arthur line up the knights for review?

\solution{If all of the knights were distinguishable, then there would
be $12!$ ways to line them up.  However, since the order of the four
armored knights is irrelevant, there are $12! / 4!$ ways to line all
the knights up for review.}

\problempart In the early days, Arthur's 12 knights simply traveled
about on horseback in single file.  By now, Arthur could distinguish
all his knights, armored or not.  However, Sir Lancelot insisted that
he ride somewhere ahead of Sir Gawain and somewhere behind Sir
Percival.  In how many different ways could Arthur arrange his mounted
knights in single file?

\solution{There are $12!$ arrangements, neglecting the special rule
involving Lancelot, Gawain, and Percival.  Among these $12!$
arrangements, these three knights appear in each of the $3!$ possible
orders an equal number of times.  In particular, there are $12! / 3!$
arrangements with Percival ahead of Lancelot ahead of Gawain.}

\problempart While Camelot was under construction, Arthur seated his
band of 12 knights around a hexagonal table, with two knights on each
side.  Two seatings were considered equivalent if one could be
obtained from the other by rotating the table.  In how many different
ways could Arthur seat the Knights of the Hexagonal Table?

\solution{Ignoring rotations, there are $12!$ possible seatings.
Since there are 6 possible ways to rotate the table, the number of
seatings is $12! / 6$.
}

\end{problemparts}

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

\problem {\bf (10 points)} Solve the following counting problems, and
explain your answers.

\begin{problemparts}

\problempart Determine the number of solutions to the equation $x_1 +
x_2 + \ldots + x_n = r$, where all variables are non-negative
integers.

\solution{Each solution to the equation corresponds to a string of $r$
stars and $n-1$ bars.  The correspondence is illustrated by the
example below, where $n = 4$ and $r = 6$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star \\
3 & + & 1 & + & 0 & + & 2 & = & 6
\end{array}
\]

Therefore, the number of solutions is
\[
\binom{n + r - 1}{r}.
\]
}

\problempart Determine the number of sequences of $k$ integers in the
range $0$ to $n$ that are {\em increasing}; that is, each integer in
the sequence is greater than or equal to the one before.

\solution{Each sequence corresponds to a string of $n$ stars and $k$
bars.  The correspondence is illustrated below, where $k = 4$ and $n =
7$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star & \mid & \star\\
3 &,& 4 &,& 4 &,& 6
\end{array}
\]

As the example illustrates, the $k$-th number in the sequence is equal
to the total number of stars preceding the $k$-th bar.  Therefore, the
number of sequences is
\[
\binom{n + k}{k}.
\]
}

\end{problemparts}



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem1 spring98, 5.4-22 (Rosen?)
\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.

\solution{
First place one ball in each box.  Then we must distribute 7 balls in four
boxes in such a way that no more than three balls are in the same box.

We use inclusion/exclusion

Number of ways to place 7 balls in 4 boxes:
${7+4-1 \choose 7} = {10 \choose 7}$.

Number of ways to place 7 balls in 4 boxes such that there are four balls
in a box =  number of ways to choose box with four balls * number of ways
to place remaining three balls in remaining three boxes =
$4 \cdot {5 \choose 3}$.

Number of ways to place 7 balls in 4 boxes such that there are five balls
in a box = $4 \cdot {4 \choose 2}$.

Number of ways to place 7 balls in 4 boxes such that there are six balls
in a box = $4 \cdot {3 \choose 1}$.

Number of ways to place 7 balls in 4 boxes such there are seven
balls in a box = 4.



So the total number of ways is

${10 \choose 7} - 4 \left({5 \choose 3} +
{4 \choose 2}+{3 \choose 1} +1 \right) = 40$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem2 spring98
%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$.]

\solution{
We can write $(x+y+z)^n$ as follows:

\begin {equation} 
 \label{eq1} \begin {array}{lcr}
 (x+y+z)^n & =& (x+y+z) (x+y+z) \cdots
(x+y+z)\\ &=& \displaystyle
\sum_{  \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} C_{a,b,c} x^a y^b z^c 
\end {array} \ . \end {equation}
where $C_{a,b,c}$ is the number of ways to partition a set
of $a+b+c$  elements into three 
subsets of size, respectively, $a$, $b$, and $c$. 

We compute $C_{a,b,c}$ using the product rule. A
partition can be obtained by first choosing $a$ elements
out of $a+b+c$ ones, and then choosing $b$ elements out of the remaining
$b+c$ ones. The number of ways to make such choices is

\begin {equation} \label{eq2}
 C_{a,b,c} = {a +b +c \choose a} \cdot {b+c \choose b} = 
\frac{ (a+b+c)!}{a!(b+c)!} \cdot \frac{(b+c)!}{b!c!} = \frac {(a+b+c)!}{a!
b!c!}\ .  \end {equation}
% We could have found the same expression using the division rule.
Substituting Equation~(\ref{eq2}) into Equation~(\ref{eq1}) we
have

\begin{eqnarray*} 
(x+y+z)^n & = &  \sum_{ \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, 
b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} \frac {n!}{a!b!c!}
x^a y^b z^{c} \\
& = & \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
x^a y^b z^{n-a-b} \ .
\end {eqnarray*}

If we set  $x=y=z=1$
we derive

\[ 3^n = (1+1+1)^n = \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
1^a 1^b 1^{n-a-b}\ . \]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem3 spring98
%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.)

\solution{
We use inclusion-exclusion as done in lecture for the case
of prime numbers. We first compute the number of positive
integers less than 150 that are not square free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) 
be the set of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
less than 150. The cardinality of the union of these sets is given by

\begin {eqnarray*}
 |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/(2^23^2) \rfloor
- \lfloor 150/(2^25^2 \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 -4-1\\
& = & 58
\end {eqnarray*}
Therefore the number of square-free positive integers less than
150 is

\[ 150 - 58 = 92 \ . \]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem4 spring98, from M&R, # 4.7.5
\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;

\solution{
$4\cdot 4\cdot 4\cdot 4 =256$.
}

\problempart the balls are distinguishable but the urns are not;

\solution{
15.
We can put either all 4 balls in one urn; or
3 in one, 1 in another; or 2 in one, 2 in another;
or 2 in one, 1 in one and 1 in another;
or 1 ball in each urn.
The balls are distinguishable, so there are $4\choose 3$ ways of
putting 3 in one urn.  There are $4\choose 2$ ways of putting 2 in one and 1 in
each of the other two.  There are ${4\choose 2}/2$ ways of putting 2 in one and
2 in another. Since the urns are indistinguishable, the case where
all the balls are placed in the same urn and the case where each
ball is places in a different urn are unique.
So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} + 1 = 15.
\]
}

\problempart the urns are distinguishable but the balls are not;

\solution{
35.
This is a stars and bars problem with the balls being stars and the 
urns bars.  The answer is
${4+4-1 \choose 4} = {7 \choose 4} = 35$.
}

\problempart neither the balls nor the urns are distinguishable.

\solution{
5.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 4 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset, \emptyset$ or
$\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or
$\{1,1\}, \{1,1\},\emptyset,\emptyset$, or
$\{1,1\}, \{1\}, \{1\}, \emptyset$, or
$\{1\},\{1\},\{1\},\{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem5 spring98
\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?

\solution{
There are $5$ ways to position the bride, $P(9,4)$ ways to choose 
and arrange the others.  This gives a total 
of ${5\cdot 9! \over 5!}$ ways.
}

\ppart The bride and the groom must be in the picture?

\solution{
There are $5$ ways to place the bride and $4$ to place the groom.  There are
$P(8,3)$ ways to choose and arrange the people.  
Total : $5 \cdot 4 \cdot {8! \over 3!}$ ways.
}

\ppart Exactly one of the bride and groom must be in the picture?

\solution{
$2$ ways to choose between bride or groom, $5$ ways to place whichever one is chosen, and 
$P(8,4)$ to choose and arrange the remaining people.
Total : $2 \cdot 5 {8! \over 4!}$ ways.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem6 spring98
\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?

\solution{
We need to count all possible combinations of people such that there
is at least one woman in every combination, but we must remember not
to count any combinations multiple times.  

We can have committees with 

1 woman, 4 men: $ { 6 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 6 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 6 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 6 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 6 \choose 5} {9 \choose 0}$\\

So there are 
$ { 6 \choose 1} {9 \choose 4} 
+ { 6 \choose 2} {9 \choose 3}
+ { 6 \choose 3} {9 \choose 2}
+ { 6 \choose 4} {9 \choose 1}
+ { 6 \choose 5} {9 \choose 0} = 2877$ different possibilities for
committees.

Another way to solve this problem is to say that there are ${15 \choose 5}$
different committees, and ${9 \choose 5}$ committees of just men.  So there
are ${15 \choose 5} - {9 \choose 5}$ different possibilities for committees.

Note that $6 \cdot { 14 \choose 4} =6006$ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of $4$ chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A, \{BCDE\}$ as well as $B, \{ACDE\}$.  
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem8 spring98, 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?

\solution{
There are 5 bars (chosen books), and therefore there are
6 places where the 8 stars (non-chosen books) can fit (before the first 
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one star 
in it, so that adjacent books are not chosen. Once we have placed these
4 stars, there are 4 stars left to be placed in 6 slots. The number of
ways to do this is therefore ${{6+4-1}\choose{4}}={9\choose 4}=126$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem1 spring98
\problem 
{\bf [11 points]}
A donut shop carries just four flavors of donuts: glazed, chocolate,
Boston creme, and strawberry. How many ways can we choose a box of 12
donuts so that we have at least one of each flavor?

\solution{
First buy one donut of each flavor. Then the problem is reduced to
choosing eight donuts without constraints. This is an
8-combination with repetition from a 4-element set, so the answer is 
\[{4+8-1 \choose 8}={11 \choose 8}=165.\]

Alternatively, we can use the formula given in lecture for an
$r$-combination with at least one of each item. Then we have
\[{12-1 \choose 4-1}={11 \choose 3}=165.\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 problem2 spring98
\problem 
{\bf [10 points]}
How many eleven-letter strings can be formed by permuting the letters
in ABRACADABRA?

\solution{
The string is eleven letters long, and there are five A's, two B's, two
R's, one C, and one D. The multinomial coefficient is 
\[ {11 \choose {5,2,2,1,1}} = {{11!} \over {5! 2! 2! 1! 1!}}=83,160.\]
}

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS8    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem %(5 points)
% Inclusion-exclusion

In a survey of 270 college students, it is found that:
\begin{itemize}
\item 64 like brussels sprouts
\item 94 like broccoli
\item 58 like cauliflower
\item 26 like both brussels sprouts and broccoli
\item 28 like both brussels sprouts and cauliflower
\item 22 like both broccoli and cauliflower
\item 14 like all three vegetables
\end{itemize}

How many students do not like ANY of the aforementioned vegetables?

\solution{
\medskip
\textbf{Solution:}
\medskip
By the direct application of the Principle of Inclusion-Exclusion, the union of sprouts-lovers, cauliflower-lovers, and broccoli-lovers will be of size:
$64+94+58-26-28-22+14=154$
Therefore, the remaining $270-154=116$ students don't like any of the three vegetables.
}

%%%%%%%%%%%%%%  Fall 2000  PS8   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem %(15 points)
% Inclusion-exclusion
% Modified from Rosen 5.6, number 17 and the preceding problems on
% derangements.

\ppart
In how many ways can the natural numbers $0,1,2,3,4,5,6,7,8,9,10,11$
be arranged in a sequence so that no number is in its original position?

\solution{
\medskip
\textbf{Solution:}
\medskip

We need to determine the number of \textbf{derangements} of a set of 12 elements. 
\smallskip
\[
\displaystyle 
D_{12}=12! \left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}+\frac{1}{8!}-\frac{1}{9!}+\frac{1}{10!}-\frac{1}{11!}+\frac{1}{12!} \right]=176,214,841
\]

}


\ppart
In how many ways can the natural numbers $0,1,2,3,4,5,6,7,8,9,10,11$
be arranged in a sequence so that no \emph{even} number is in its original
position?

\solution{
\medskip
\textbf{Solution:}
\medskip

We can derive this answer by mimicking the derivation of the formula for the number of derangements, but worrying only about the even numbers. What we want is the size of the union of all those undesirable permutations that keep one or more of the even numbers in their place, so that we can subtract it from the sum of all permutations.


There are $12!$ permutations altogether. Let $e$ be one of the 6 even numbers. The number of permutations in which $e$ is in its original position is $11!$ (since $e$ remains in its place while the other $11$ numbers are free to move around however they like.)
\medskip

So, there are $11!\binom{6}{1}$ permutations which force $1$ of the even numbers stays in its place. Similarly, there are $10!\binom{6}{2}$ permutations which keep $2$ of the even numbers in their original positions, $9!\binom{6}{3}$ permutations that force $3$ of them to remain where they were,  $8!\binom{6}{4}$ permutations that keep $4$ even numbers fixed, $7!\binom{6}{5}$ permutations that guarantee that $5$ even numbers will stay put, and finally $6!\binom{6}{6}$, that is $6!$ permutations in which all $6$ even numbers will remain where they were.
\medskip

We want to know how many permutations there are where \textbf{at least} one number remains in its place. The inclusion-exclusion principle comes to our rescue, and says that the size of the union of these undesirable permutations is:
\[
\displaystyle
11!\binom{6}{1}-10!\binom{6}{2}+9!\binom{6}{3}-8!\binom{6}{4}+7!\binom{6}{5}-6!\binom{6}{6} = 191,751,120
\]

There are $12!$ permutations in total, $191,751,120$ of which are undesirable, which leaves us with $12!-191,751,120=287,250,480$ permutations where no number appears in its original position.
}

 
%%%%%%%%%%%%%%  Fall 2000 PS8    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem %(10 points)
% Product rule, trees

How many bit strings of length 10 contain either five consecutive $0$s
or five consecutive $1$s?

\solution{
\medskip
\textbf{Solution:}
\medskip

There are $2^{10}$ bit strings of length 10. First, let's see how many of those contain five consecutive $0$'s. The sequence of the 5 $0$'s can start at position $1,2,3,4,5$ or $6$. In each case, the remaining $5$ bits are allowed to be anything, so, as a ``first approximation'', we can say that there are $6*2^5$ different strings of consecutive $0$'s. \par However, if we do this, we are \emph{overcounting} since, for example, the string that has its first $8$ bits equal to $0$ and the last $2$ equal to $1$ (that is, $0000000011$) will be counted as a valid string \emph{four times} by our method:  \underline{00000}00011, 0\underline{00000}0011, 00\underline{00000}011 and 000\underline{00000}11. We need to eliminate these duplicates, which occur whenever we are dealing with strings that have more than 5 consecutive $0$'s. \par

We can do this by calculating the number of strings with $6$ or more consecutive $0$'s using the same method as above. This will give us $5*2^4$ such strings, and for each sequence of $0$'s, we will be overcounting exactly one time less than we overcounted above: for example, going back to the string of $8$ consecutive $0$'s that was counted 4 times above, we see that this method will count it exactly $3$ times \underline{000000}0011, 0\underline{000000}011, 00\underline{000000}11.  The same will hold for all strings of length $\geq 6$ because the number of allowed starting positions for a sequence of $6$ $0$'s is exactly one less than the number of allowed starting positions for a sequence of $5$ consecutive $0$'s. Thus, it suffices to subtract this number from  the number we got before to get rid of duplicates. Therefore, the number of strings containing 5 or more consecutive $0$'s is  
\[
6*2^5-5*2^4=112\]
By symmetry, there are another 112 strings which contain five consecutive $1$'s. The question was to determine the number of strings that have either 5 $0$'s or 5 $1$'s. So, we are looking for the size of the union of those two sets (the bit strings with 5 $0$'s and the bit strings with 5 $1$'s). The intersection of the 2 sets (i.e, sequences that contain \emph{both} 5 $0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and $1111100000$. Therefore, by the inclusion-exclusion principle, the size of the union of the two sets is $112+112-2=222$

}

%%%%%%%%%%%%%%  Fall 2000  PS8   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem %(20 points)
% Binomial coefficient calculations, playing with the definition.
% Also Fibonacci numbers, induction

\ppart %(5 points)
Recall the double induction example from Lecture 3, which involved a
function $f: \nat \times \nat \Rightarrow \nat$ defined by:  $f(n,0) =
1$ for all $n$, $f(0,k) = 1$ for all $k$, and $f(n+1,k+1) = f(n+1,k) +
f(n,k+1)$ for all $n$ and $k$.
We proved by double induction that $f(n,k) = \frac{(n+k)!}{n!k!}$
for all $n$ and $k$. \\
Recall the definition of binomial coefficients: $\binom{a}{b}=\frac{a!}{(a-b)!b!}$. Express $f(n,k)$ in terms of binomial coefficients.

\solution{
\medskip
\textbf{Solution:}
\medskip

Since \[\frac{(n+k)!}{n!k!}=\frac{(n+k)!}{(n+k-k)!k!}=\binom{n+k}{k}\] we see that 
$f(n,k)=\binom{n+k}{k}$
}


% A:  \binom{n+k}{n}

\ppart %(5 points)
What identity about binomial coefficients arises from what we proved
in Lecture 3? Hint: how can you express $\binom{n+1}{k+1}$ in terms of smaller binomial coefficients? 

\solution{
\medskip
\textbf{Solution:}
\medskip

By direct substitution from part (a) we get:
 \[\binom{n+k+2}{k+1} = \binom{n+k+1}{k+1} + \binom{n+k+1}{k}\]
This is usually written as: \[\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}\]
}

\ppart %(15 points)
% From Velleman p. 278, problem 5(e)
Recall the definition of Fibonacci numbers:
\[
F_{0}=0;
F_{1}=1;
\text{for every }n\geq 2, F_{n}=F_{n-2}+F_{n-1}\]
Prove that for all $n\geq 0$
\[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]

Hint: use induction, and the formula you derived above

%Should be a proof using strong induction, either directly from the
%defintions or using some version of the sum identity above.
%Give a hint?
%I found it useful to try small cases, and to look at where the
%corresponding entries were in the array from lecture 3.
\solution{
\medskip
\textbf{Solution:}
\medskip
We can prove this by induction on $n$. Let $P(n)$ be the statement that \[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]
\subparagraph{Base Case:}For $n=0$, $\sum_{i=0}^{-1}{\binom{2n-i-1}{i}}=0$ since the summation basically has no terms. Indeed $F_{0}=0$ so the first half of what we need to show holds. $\sum_{i=0}^{0}{\binom{2n-i}{i}}=1$ and $F_{1}=1$ so the second half also holds.
\subparagraph{Induction Step:} Assume $P(n)$. We want to prove $P(n+1)$. We need to show 2 things:
\[
F_{2n+2} = \sum_{i=0}^{n}{\binom{2n-i+1}{i}}\qquad  \text{and}\qquad
F_{2n+3}=\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}
\]
First, let's see what $\sum_{i=0}^{n}{\binom{2n-i+1}{i}}$ is equal to. The first term of the summation, i.e, when $i=0$ is $1$, therefore, we can write this as \[
1+ \sum_{i=1}^{n}{\binom{2n-i+1}{i}}\]Now, using the identity from part (b), we can write this as
\[
1+ \sum_{i=1}^{n}{\left[ \binom{2n-i}{i}+ \binom{2n-i}{i-1}\right] } 
\] 
which is, of course, equal to 
\[
1+\sum_{i=1}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
We notice that if we let $i=0$, $\binom{2n-i}{i}=1$, so we can ``absorb'' that 1 into the first summation and write
 \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
 Things are starting to look good since we recognize that first sum to be $F_{2n+1}$. In order to attack the second sum, we make a substitution: let $k=i-1$ (which means, wherever we see $i$, we put $k+1$. So the above becomes \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{k=0}^{n-1}{\binom{2n-k-1}{k}}\]
From our induction hypothesis, this equals $F_{2n+1}+F_{2n}$ so this does indeed equal $F_{2n+2}$. (For those who are confused about what I proved: if you want to prove that $a=b$, you can just prove that $b=a$).
\medskip

Now, let's see what $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}$ is equal to. 
For $i=n+1$, $\binom{2n-i+2}{i}=\binom{n+1}{n+1}=1$. For  $i=0$, $\binom{2n-i+2}{i}=1$. Therefore, we can write this thing as
\[
1+1 +\sum_{i=1}^{n}{\binom{2n+-i+2}{i}}
\] 
which, using the same identity again, can be written as
\[
1+1+\sum_{i=1}^{n}{\left[ \binom{2n-i+1}{i}+\binom{2n-i+1}{i-1}\right]}
\]which is equal to
\[
1+1+\sum_{i=1}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n}{\binom{2n-i+1}{i-1}}
\]Since for $i=0$, $\binom{2n-i+1}{i}=1$ and for $i=n+1$, $\binom{2n-i+1}{i-1}=\binom{n}{n}=1$, we can ``absorb'' one of the $1$'s into the first sum and the other into the second sum and write
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n+1}{\binom{2n-i+1}{i-1}}
\]and making the substitution $i-1=k$ into the second sum, we get
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{k=0}^{n}{\binom{2n-k}{k}}
\] By what we proved before, the first sum equals $F_{2n+2}$ and by our induction hypothesis, the second sum equals $F_{2n+1}$. Therefore, $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}=F_{2n+2}+F_{2n+1}=F_{2n+3}$ as desired.
 


}
%%%%%%%%%%%%%%  Fall 2000   PS8  %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
On a set of $n$ elements how many of the following are there?

\ppart binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip

    $2^{n^2}$ since there are this many different $0-1$ matrices of order $n$.
}   
\ppart symmetric binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix associated with a symmetric relation is symmetric.  Since there are $2^{n+\binom{n}{2}}$ different symmetric matrices there are an equal number of symmetric relations.
}

\ppart reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix associated with a reflexive relation has $1$'s along the main diagonal . Hence the
number of such matrices, and therefore reflexive relations, is $2^{n^2 - n}$.
}
\ppart symmetric and reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix
  associated with a symmetric and reflexive relation is symmetric and
  has $1$'s along the main diagonal. Hence the number of such
  relations is $2^{\binom{n}{2} }$.}

\ppart symmetric or reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}$.
}

%%%%%%%%%%%%%%  Fall 2000 PS 8.5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% new
% combinatorics, stars and bars, symmetry

\textbf{Vote today } $6N$ voters show up to vote for one of three 
candidates: Bush, Gore and Nader.

\ppart Assuming that voters are indistinguishable, what is the number of
possible vote counts?

\solution{\textbf{Solution: }
We can model this problem using $6N$ stars, each representing a vote,
and two bars, to separate Gore's, Bush's and Nader's votes.  Each
election result corresponds to a unique placement of the stars and
bars.  Therefore, the number of possible election results is 
$\binom{6N + 2}{2}$.}

\ppart What is the number of possible vote counts in which Nader wins 
the popular vote?

\solution{\textbf{Solution: }
Let $T$ be the number of vote counts for which the election is
a tied race.  By symmetry, Nader can win the election in 
$\frac{1}{3} (\binom{6N + 2}{2} - T)$ ways.

To compute $T$, we use a similar trick.  A tie happens either if two
candidates tie for first place or all three candidates tie for first
place.  By symmetry, we only need to consider the case when Bush and
Gore tie for first (but Nader doesn't).  For this to happen, Bush and
Gore must each get at least $2N + 1$ votes, but no more than $3N$
votes.  This is a total of $N$ possible outcomes.  It follows that 
$T = 3N + 1$, as there is one way in which all candidates tie for first.

It follows that Nader can win the election in 
$\frac{1}{3} (\binom{6N + 2}{2} - 3N - 1) = 2N(3N + 1)$ ways.
}
 
%%%%%%%%%%%%%%  Fall 2000  PS 8.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% spring96 ps7
% combinatorics, balls and bins, stars and bars

How many ways are there to distribute eight balls into six distinct
boxes with the first two boxes having collectively at most four balls
if

\ppart the balls are identical?

\solution{\textbf{Solution: }
Let us consider placing $n$ balls into $k$ boxes so that exactly $r$
balls are placed in the first two boxes. This can be done in
\[
{r+2-1 \choose 2-1}{(n-r)+(k-2)-1 \choose (k-2)-1}
\]
ways, since there are ${\rm BP}(r,2) = {r+2-1 \choose 2-1}$ ways to
place $r$ balls into first two boxes and ${\rm BP}(n-r,k-2) =
{(n-r)+(k-2)-1 \choose (k-2)-1}$ ways to place the remaining $n-r$
balls into the other $k-2$ boxes. We can place the balls into boxes,
so that {\em at most} $r$ balls go into the first two boxes, in
\[
\sum_{i=0}^r{{i+2-1 \choose 2-1}{(n-i)+(k-2)-1 \choose (k-2)-1}}
\]
ways. In particular for $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{i+2-1 \choose 2-1}{(8-i)+(6-2)-1 \choose (6-2)-1}} = 1056{.}
\]
}

\ppart the balls are distinct?

\solution{\textbf{Solution: }
As in the part (a), we compute the number of ways $n$ balls can be
placed into $k$ boxes so that exactly $r$ of them are placed in the
first two boxes. Since the balls are distinct, we have ${n \choose r}$
ways to choose which balls to place in the first two boxes, and then
we have $2^r$ ways to place the balls into first two boxes, and
$(k-2)^{n-r}$ ways to place the rest of the balls into the remaining
$k-2$ boxes. Thus the total number of posibilities is
\[
{n \choose r}2^r(k-2)^{n-r}{.}
\]
If we require that {\em at most} $r$ balls go into the first two boxes
we compute that the number of posibilities is
\[
\sum_{i=0}^r{{n \choose i}2^i(k-2)^{n-i}}{.}
\]
For $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{8 \choose i}2^i(6-2)^{8-i}} = 1531904{.}
\]
}
  
%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% spring95, ps7
% basic combinatorics

% \ppart How many ways can $2n$ objects be divided into $n$ pairs?
%
%\solution{\textbf{Solution: }
%Consider all the ways of ordering the $2n$ objects in a line. There are
%$(2n)!$ ways of doing this. Now group them into pairs based on the
%linear order, i.e. group the first and second object, group the third
%and fourth object,..., group the $(2n-1)$th and $2n$th object. Thus
%each linear order gives us a unique grouping into pairs. But observe
%that two different linear orders could give rise to the same grouping
%into pairs. So let us now count the number of linear orders that give
%rise to the same grouping into pairs. Given a grouping into pairs, to
%generate a linear order we need to order each pair (there are $2^n$
%ways to do this) and then order the $n$ pairs (there are $n!$ ways to
%do this). Hence $n! 2^n$ linear orders give the same grouping into
%pairs. Thus the total number of ways $2n$ objects can be divided into
%$n$ pairs is $\frac{(2n)!}{n! 2^n}$.
%}

%\ppart 
How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solution{\textbf{Solution: }
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}
 
%%%%%%%%%%%%%%  Fall 2000  PS 8.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem 
% spring98 ps8
% combinatorics, some stars and bars

How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{\textbf{Solution: }
There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are
\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}


%%%%%%%%%%%%%%  Fall 2000 PS 8.5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% fall94 ps7
% combinatorics, binomial theorem

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

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

\solution{\textbf{Solution: }
\begin{eqnarray*}
(1+x)^n (1+x)^n &=& (1+x)^{2n} \\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^j &=&
    \sum_{i=0}^{2n} {2n\choose i}x^i
\end{eqnarray*}

Equating the coefficients of $x^n$ on both sides yields
\begin{eqnarray*}
\sum_{i+j=n} {n\choose i}{n\choose j} &=& {2n\choose n} \\
\sum_{i=0}^n {n\choose i}{n\choose n-i} &=& {2n\choose n}
\end{eqnarray*}
From where we obtain the identity using the substitution 
${n\choose n-i} = {n\choose i}$.
}

\ppart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Give a combinatorial proof of the identity.

\solution{\textbf{Solution: }
Suppose we have $2n$ objects, $n$ of which are red, and $n$ of which are blue.
How many ways can we pick $r$ red ones and $n-r$ blue ones?  Clearly this is
$${n \choose r} {n \choose n-r} = {n \choose r}^2.$$  
How many ways can we choose $n$ objects total, regardless of how many
are of each color?  This is just 
$$ \sum_{r=0}^n {n \choose r}^2.$$  
But there are  ${2n \choose n}$ ways to
choose $n$ objects, so these must be the same number.
}    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%FALL 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem set 3, #1
\problem \textbf{Countable and Uncountable Sets}

{\bf (a)} Do \S 1.7, Exercise 32 (a,b,d) from the Rosen textbook.

\solution{(a) This is countable. The integers in the set are
$\pm 1,\pm 2, \pm 4, \pm 5, \pm 7$, and so on. We can list these
numbers in the order $1, -1, 2, -2, 4, -4, 5, -5, 7, -7,\ldots$, thereby
establishing the desired correspondence. In other words, the correspondence
is given by $1 \leftrightarrow 1, 2 \leftrightarrow -1, 3 \leftrightarrow 2,
4 \leftrightarrow -2, 5 \leftrightarrow 4, 6 \leftrightarrow -4$, and so on.  

%Since $S$ is a subset of a countable set, namely,
%$\naturals$, $S$ is countable.  Here's an explicit bijection $f: S
%\rightarrow N$:
%
%\hspace{6mm}
%if $x > 0, f(x) = 2 ( \abs x - \abs {\lfloor \frac{x}{3} \rfloor})-1 $
%
%\hspace{6mm}
%if $x < 0, f(x) = 2 ( \abs x - \abs {\lfloor \frac{x}{3} \rfloor}) $

(b) This is similar to part (a); we can simply list the elements of the set in
order of increasing absolute value, l;isting each positive term before its
corrsponding negative:\\ 
$5, -5, 10, -10, 15, -15, 20, -20, 25, -25, 30, -30, 
40, -40, 45, -45, 50, -50,\ldots$.

%Let $S$ denote the set of numbers divisible by 5 but not by 7.
%There is a bijection $f: S \rightarrow N$.
%
%\hspace{6mm}
%if $x > 0, f(x) = \frac{ 2 ( \abs x - \abs {\lfloor \frac{x}{7} \rfloor})-1}{5} $
%
%\hspace{6mm}
%if $x < 0, f(x) = \frac{ 2 ( \abs x - \abs {\lfloor
%\frac{x}{7} \rfloor})} {5} $

(d) The set is not countable. We can prove by the same diagonalization 
argument that was used to prove that the set of all reals is uncountable
in Example 17, \S 1.7 of Rosen. All we need to do is choose
$d_i=1$ when $d_{ii}=9$ and choose $d_i=9$ when $d_{ii}=1$ or $d_{ii}=$blank
(if the decimal expansion is finite).}

%Not countable, with a similar argument to that for all the real
%numbers between 0 and 1 in \S 1.7.}
%
{\bf (b)} Show that the set of all functions from $\naturals$ to
$\{0,1\}$ is uncountable.

\iffalse GIVEN IN HANDOUT 16:
Hence, conclude that the set of all subsets 
of $\naturals$ is uncountable.
\fi


\solution{Rework the proof of uncountability of the reals in base 2.
Then, referring to example 17 in \S 1.7, note that we can define the
$i^{\textit{\tiny th}}$ function $f_i$ as $f_i(j)=d_{ij}$, which puts
the functions from $\naturals$ to $\{0,1\}$ in one-to-one correlation
with the real numbers; thus, this set of functions is uncountable.\\
If we take a function $f_i$ to be the characteristic
function of a subset $S_i\subseteq\naturals$ (i.e., $f(x)=1\iff x\in
S$), then the set of subsets of the natural numbers is in one-to-one
correspondence with the set of functions from $\naturals$ to $\{0,1\}$
and is therefore also uncountable.}

{\bf (c)} Show that the set of all finite strings constructed from 0's and 1's
is countable.

\solution{There are a finite number, namely, $2^m$, bit strings of length
$m$. The set of all bit strings is the union of the bit strings of length $m$
over $m=0,1,2,\ldots$. Since the union of a countable number of countable
sets is countable, there are a countable number of bit strings.}

%
%We can consider an integer in big-endian binary format,
%in which case there always exists an integer $i=1b_{n-1}b_{n-2}\cdots
%b_0$ that maps to the bit string bit $1b_{n-1}b_{n-2}\cdots b_0$.
%Clearly, if we can also add the strings $0b_{n-1}b_{n-2}\cdots
%b_0$ for every integer $i$, then we will have covered all bit
%strings.  We can therefore make our map
%\begin{center}
%\begin{tabular}{rcl}
%$1b_{n-1}b_{n-2}\cdots b_{1}1$ & $\mapsto$ &
%$1b_{n-1}b_{n-2}\cdots b_{1}$ \\
%$1b_{n-1}b_{n-2}\cdots b_{1}0$ & $\mapsto$ &
%$0b_{n-1}b_{n-2}\cdots b_{1}$ \\
%\end{tabular}
%\end{center}
%Note that we are excluding $0$ from our domain; if you like, you can
%add $1$ to $x$ before looking at the binary representation.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem set 3, #2
\ppart \textbf{Counting}

{\bf (a)} Do \S 4.1, Exercise 20 from the Rosen textbook.

\solution{
\begin{enumerate}
\item[(a)] 1000.
\item[(b)] 4500.
\item[(c)] $9\cdot 9\cdot 8\cdot 7=4536$.  Note that the first digit
doesn't have 10 choices, since it cannot be $0$.
\item[(d)] 3000 are divisible by 3, so it follows that 6000 are not.
\item[(e)] 1800 are divisible by 5 and 1286 are divisible by 7.  There 
are 257 numbers divisible by both 5 and 7 (i.e., divisible by 35).
So, by inclusion/exclusion, the answer is $1800+1286-257=2829$.
\item[(f)] $9000-2829=6171$.
\item[(g)] 1800 divisible by 5 and 257 divisible by both, so
$1800-257=1543$ divisible by 5 but not 7.
\item[(h)] 257, as above.
\end{enumerate}
}

{\bf (b)} Do \S 4.1, Exercise 52 from the Rosen textbook.

\solution{There are $2^n$ lines (assignments) in the truth table for a
formula with $n$ variables, since each of the variables can take on
one of two values.  For a given truth assignment to the $n$ variables,
the proposition can be either true or false; hence, there are
$2^{2^n}$ possibilities.}

\iffalse
\ppart \textbf{Induction and Counting}

Do \S 4.1, Exercise 54 from the Rosen textbook.

\solution{We want to show that a procedure consisting of $M$ tasks
can be done in $n_1n_2\cdots n_M$ ways if the $i\kth$ task can be done
in $n_i$ ways.  The product rule stated in the text is the base case,
$M=2$.  Assume the induction hypothesis for $M=m$ and prove it for
$M=m+1$.  Then, to do the procedure we have to do each of the first
$m$ tasks, which by the IH can be done in $n_1n_2\cdots n_m$ ways, and
then do the $(m+1)\kth$ task, so there are $(n_1n_2\cdots n_m)n_{m+1}$
ways.}
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem set 3, #6.
\problem \textbf{Countability}  %F97 H19-Pset7

A real number is {\em algebraic} if it is the root of a
polynomial with rational number coefficients.  Algebraic numbers form
an important part in the study of (what else) modern algebra.  A
number that is not algebraic is called {\em transcendental}.

\bparts

\ppart Prove that for any particular $d$, the set of degree $d$
polynomials with rational coefficients is countable.

\solution{
Let $P_d$ be the set of degree $d$ polynomials with rational 
coefficients.
The function 
\[f\colon (q_0,q_1,\ldots, q_d)\mapsto q_0x^d+q_1x^{d-1}+\cdots+q_d\]
is a surjection from $(\rationals - \{0\}) \times \rationals^d$ 
to $P_d$.
Since the set $(\rationals - \{0\}) \times \rationals^d$ is countable 
(the Cartesian product of finitely many countable sets is countable),
then also the set $P_d$ is countable.}

\ppart Prove that the set of all roots of degree $d$ polynomials with
rational coefficients is countable (you may use the fact that a degree
$d$ polynomial has at most $d$ roots).

\solution{
Since each degree $d$ polynomial has at most $d$ roots we can give a 
surjection from $P_d\times\{1,\ldots, d\}$ to the set of all 
roots of degree $d$ polynomials with rational coefficients.
For example we can define $f(p(x),i) = x_i$,
where $x_1,\ldots, x_d$ are the roots of $p(x)$
(if $p(x)$ has less then $d$ roots, just repeat the last 
one many times).}

\ppart Prove that the set of algebraic numbers (which is just the
union of the sets in the previous part) is countable.

\solution{
The set of algebraic numbers is the union of the sets 
of the roots of polynomials with rational coefficients
of degree $d$, for all $d$.
This is a countable union of countable sets,
which we know it is countable.
}

\ppart Conclude that there is a transcendental number.

\solution{
If there were no transcendental numbers, all numbers would be 
algebraic, i.e., the set of algebraic numbers equals $\reals$.
But this is not possible because the reals are not countable.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  The following are some inclusion/exclusion problems...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%PROBLEM SET 3
\ppart \textbf{Inclusion-Exclusion Principle}

\noindent

There are 49 students in a class at MIT who either understand mathematical 
equations, exercise regularly, or love school. Of these:

\noindent
20 students understand mathematical equations.

\noindent
20 students exercise regularly.

\noindent
26 students love school.

\noindent
36 students understand mathematical equations or exercise regularly.

\noindent
38 students understand mathematical equations or love school.

\noindent
40 students exercise regularly or love school.

\vspace{1mm}

\noindent
How many students understand mathematical equations AND exercise
regularly AND love school?

\solution{
Let $A$ denote the set of students who understand mathematical
equations, $B$ denote the set of students who exercise
regularly, and $C$ denote the set of students who love school.
Then we are given that $ | A\cup B\cup C | = 49$, 
$| A |=20$, $| B |=20$, $| C |=26$, 
$| A\cup B |=36$, $| A\cup C |=38$, and $| B\cup C |=40$.
\begin{eqnarray*}
| A\cap B\cap C | & = & 
      | A\cap B | +| C | - | (A\cap B)\cup C |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) \cap (B\cup C) |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) | - | (B\cup C) | + | (A\cup B \cup C) |\\
& = & 20 + 20 - 36 + 26 - 38 - 40 + 49\\
& = & 1
\end{eqnarray*}
In line 1 we apply inclusion-exclusion, in line 2 we apply inclusion-exclusion
and distributive laws, and in line 3 we apply inclusion-exclusion.
}

\problem \textbf{Sieving}

Consider the {\it medieval puzzle} of the woman and the eggs. On her
way to the market to sell her eggs, a horseman knocks the old woman
down by accident, causing all the eggs to be broken. He offers to
pay the damages and wants to know how many eggs she had. She says she
does not remember the exact number, but when she took them 2 at a
time, 1 was left over. One was also left over when she took them
3,4,5,6, at a time; however when they were taken 7 at a time, it came
out even.

\bparts

\ppart
If the woman had less than 1000 eggs, how many
possibilities are there for the exact number of eggs she had?

{\bf Solution:}

We first realize that the woman could have N eggs if and only if N was
simultaneously $1\bmod k$ for $k=2,3,4,5,6$ and $0\bmod 7$. But this
is equivalent to saying that $k | (N-1)$ for $k=2,3,4,5,6$ and $7 |
N$. Notice that the first condition, $k | (N-1)$ for $k=2,3,4,5,6$, is
equivalent to $\lcm(2,3,4,5,6) | (N-1)$, where $\lcm$ is the least
common multiple. 
Therefore, we want to find out possible values of $N<1000$
such that $60 | (N-1)$ and $7 | N$, 
as $\lcm(2,3,4,5,6)=60$. This is the same as finding values
of $j$ such that $60 j + 1 < 1000$ and $7 | (60 j + 1)$. The latter
condition just reduces to requiring that $7 | (4 j + 1)$, and the
possible values of $j$ that satisfy the above conditions are $5$ and
$12$. Therefore $N=301$ and $721$ are the possible values for
the exact number of eggs she had.

Alternatively, set  $A_i$ to be the set of integers 
between 1 and 1000 which are congruent to
$1\bmod {(i+1)}$ for $i=1\ldots 5$  and $A_6$ be the set of integers
between 1 and 1000 congruent to $0\bmod 7$.

The number of exact eggs the woman may have had is the
intersection of all the sets $A_i$ for $i=1,\ldots,6$.
Use the formula for the inclusion-exclusion principle on page 359 of
Rosen to compute the cardinality of this intersection plugging in
numerical values for the cardinality of the above  sets and their
various intersections necessary for the computation.

A simple computer program could also be used to generate the result. A
version of C++ code is given below.

\begin{verbatim}
#include<iostream.h>

int main(){

// returns the number of possibilities for the exact number of eggs the
// woman had. It also displays those values.

  #define MAXEGGS 1000
  int temp;
  int possibleValues = 0;
  for (temp=1; temp<MAXEGGS; temp++)
    if ((temp%2 == 1) && (temp%3 == 1) && (temp%4 == 1) && 
        (temp%5 == 1) && (temp%6 == 1) && (temp%7 == 0)){
      cout<<temp<<"\n";
      possibleValues++;}
  cout<<"The "<<possibleValues<<" values above are the 
        possiblities for the exact number of eggs she had.\n";
  return possibleValues;
}
\end{verbatim}
This produces the output:
\begin{verbatim}
301
721
The 2 values above are the possiblities for the exact number of eggs she had.
\end{verbatim}

{\bf endsoln}

\ppart
Describe a procedure whereby the old woman can determine all values less than
1000 that are possibilities for the exact number of eggs she may
have had, using a sieve.

(Hint: This can be solved in a manner analogous to the {\it sieve of
  Eratosthenes} for enumerating all primes upto
$N^2$ in which we remove all numbers $k$ between $1$ and
$N^2$ that simultaneously satisfy the following constraints:
$k\equiv 0\bmod 2, k\equiv 0\bmod 3,k\equiv 0 \bmod 5,\ldots,k\equiv
0\bmod p $ where p is the largest prime less than or equal to $N$.
Here you need to figure out a strategy for removing numbers of eggs
less than a 1000 from the list so what remains are candidates for the
exact numberof eggs.)

\solution{
As above, we use the observation that
the woman could have N eggs if and only if N was
simultaneously $1\bmod k$ for k=2,3,4,5,6 and $0\bmod 7$.
This leads to the following sieving strategy.
List all numbers from 1 to 1000. First cross out all numbers which
are congruent to 0 mod 2, then cross out all those congruent to
0 or 2 mod 3, then all those congruent to 0,2 or 3 mod 4,
then all those congruent to 0,2,3,4,5 mod 6  and finally those
congruent to 1,2,3,4,5,6 mod 7.  Whats left are the choices
for the exact number of eggs the woman had. Note that 
if you write a short computer
program to implement your process, you may check your
answer to part (a) using this method.}

\eparts

\problem \textbf{Inclusion-exclusion}

A certain company wants to have security for their computer
systems.  So they have given everyone a name and password.  The 
passwords are exactly 10 letters long.

\bparts

\ppart If all the passwords must satisfy the following rules, how many
possible passwords are there :
\begin{enumerate}
\item[1.] The passwords must be permutations of the 
    letters (a, d, f, i, l, o, p, r, s, t)
\item[2.] No password can contain the sequence "fail"
\item[3.] No password can contain the sequence "drop"
\end{enumerate}

\solution{
The possible passwords = total number of permutations - permutations
containing "fail" - permutations containing "drop" + permutations
containing "fail" and "drop".

The total number of permutations of the letters is $10!$.  The number
of permutations that contain the sequence "fail" can be seen as
finding the number of permutations of the following 7 elements (d, o,
p, r, s, t, fail) which is $7!$.  The same can be seen with the number
of permutations with "drop" = $7!$.

The number of permutations with both "fail" and "drop" is
the same as finding the number of permutations of the following 4
elements (drop, fail, s, t) = $4!$

Thus possible = $10! - 7! - 7! + 4!$.
}

\ppart Bob is trying to break into the system.  He has obtained
the list of all the passwords and the list of all the names, yet he
doesnt know which passwords go with which names.  If the password file
contains 100 passwords and there are a 100 names, 
how many possible ways can those passwords be
associated with the names? Approximate your answer using Sterling's
approximation.


\solution{
There are 100 possible names for the first password, 99 for the 
second, ... and 1 possible for the last.  Multiplying these possiblities 
together gives you $100!$. By Sterling's approximation this is
approximately $9.32\times 10^{157}$.
}

\ppart Bob realizes that trying every possibility from part (b) will
take a long time.  But he is still determined to figure out which
names belong with each password.  He then realizes that names were
mapped to passwords using a single function $f$ chosen by the system manager
in advance from a set of five
functions $\set{f_1,f_2,f_3,f_4,f_5}$, i.e.,
$f(\mathrm{name}_i)=\mathrm{password}_i$.  Can Bob map names to
passwords any faster now? (Note: Bob knows the set of functions and
can compute himself $f_i$ for any $i$).

\solution{ Yes, Bob can map names to passwords faster now.
For each $1\leq i\leq 100$, Bob
goes down the list of names evaluating $f_i(name)$ and checking if the result
allows him to enter the account in question.
If for all names this works, then Bob uses $f_i$ for the mapping from now on.
This takes $500$ trials, as there are $100$ trials per function and
there are $5$ functions. }
\eparts

\problem \textbf{Inclusion-exclusion}

\bparts

\ppart Let $S$ be a set with $n$ elements.  Fix a constant $k$.  How
many sequences $(T_1,T_2,\ldots,T_k)$ of subsets of $S$ are there such
that $T_1\subseteq T_2\subseteq \cdots\subseteq T_k$?  Note that the
subset relation is not strict.

\solution{For each element $x\in S$, we can choose the set $T_i$ in
which it first appears, after which it appears in all $T_j$ for $j\geq
i$; there are $k+1$ choices for each ($k$ sets plus one for the choice
in which it never appears), so there are $(k+1)^n$ such sequences.}

\ppart Suppose Dana answers the previous question correctly, and is
feeling confident enough to tackle the variant where the subset
relations are strict (i.e., $T_1\subset T_2\subset \cdots\subset
T_k$).  She proceeds by describing an enumeration strategy.

She first chooses a $(k-1)$-sized subset $Q\subseteq S$ and permutes
those elements into a sequence $(e_2,e_3,\ldots,e_k)$ such that
$\forall i,j$ where $j\leq i$, $e_j\in T_i$ but $e_j\not\in T_{i-1}$;
then, for each of the remaining elements $x\in S-Q$, she chooses an
$i$ such that either $i=k+1$ or $x\in T_i$ but $x\not\in T_{i-1}$,
effectively introducing $x$ into the sequence of sets at position $i$.

Fox tells her that her enumeration strategy miscounts.  Who is right,
and why?

\solution{Dana is overcounting.  Suppose $n\geq k$; fix $S$ and
$Q$.  Then, $\exists x\in S-Q$, since $|S|>|Q|$.  If we place $x$ in
the same set with $e_2$ (i.e., $T_2$), then we can choose a new $Q'$
and sequence $(x,e_3,\ldots,e_k)$ with associated sets
$(T_1,T_2',T_3,\ldots,T_k)$.  Now, choose to place $e_2$ (which is not
in our sequence) into $T_2'$, so $T_2=T_2'$ with all other sets the
same; clearly, we are then counting this sequence twice.}

\eparts
}

\problem \textbf{Enumeration, permutations, and derangements}

\bparts

\ppart Lars Beefcake is manager of the MIT Chess Club.  After a long
and grueling match, the players have gone home, leaving Lars to put
the players' unlabelled chess sets back in their lockers.  If there
are $n$ players/lockers and $n$ chess sets, how many ways could Lars
place chess sets in lockers such that there is exactly one chess set
in each locker, disregarding the correctness of such placement?

\solution{We can formulate this as a function-counting problem.  Since
there are $n$ chess sets and $n$ lockers, we can assign each chess set a
\textit{unique} number between 1 and $n$ inclusive, and do the same
for the lockers.  Thus, we are looking for an injective function $f$
from $\set{1,\ldots,n}\rightarrow \set{1,\ldots,n}$, since we want
that no two chess sets are mapped to the same locker (i.e., we want
that $f(x)=f(y)\Rightarrow x=y$ for all $x,y\in\set{1,\ldots,n}$.)

Note that the first element of the codomain has $n$ possible
preimages; the second has $n-1$ possible mappings (i.e., all but the
first preimage); the third has $n-2$ possible mappings (i.e., all but
the first two preimages); and so on, for all $n$ elements of the
codomain.  This is simply $n!$, the number of permutations of
$\set{1,\ldots,n}$.}

\ppart This begs the question: how many ways can Lars achieve the feat
of placing every chess set in the wrong locker?  Give an expression
for general $n$ and then approximate the value for $n=10$.

\solution{This is the number of \textit{derangements} of the set of
$n$ elements.  We do not know a closed form for this number, so we
denote it by $D_n$ as derived in Rosen, \S 5.6.  To approximate
$D_{10}$, use Sterling's approximation. This gives us approximately 
$1.33\times 10^6$.}

\ppart Say Lars recognizes Dexter's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Lars place chess sets in lockers assuming he at
least gets Dexter's right?

\solution{We count functions, as before.  We note that since we want
Dexter's chess set (give it number $a$) to appear in Dexter's locker
(give it number $b$), it must be that $f(a)=b$ in the function we are
constructing.  The first remaining element of the codomain then has
$n-1$ choices of preimage (since Dexter's chess set can't go into more
than one locker!), the second remaining element of the codomain has
$n-2$ choices of preimage, and so forth.

This gives us $(n-1)!$ possible configurations of chess sets.  We can
also get here by employing symmetry and using part (a).  Without loss
of generality, assign Dexter's chess set and locker the number 1, and
set $f(1)=1$ in our function.  We can now create an injective function
on the remaining elements; by part (a), this is simply $(n-1)!$.  }

\ppart Say Lars really resents Dexter's brainpower, and decides to get
even by putting Dexter's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Dexter's chess set into Dexter's locker?

\solution{Again, we function count.  (Notice a pattern?)  The opposite
of the solution to part (c), we want $f(a)=c$ for some $c\not=b$; we
can therefore choose $c$ in $n-1$ ways.  Then, since we don't care
where the other chess sets go, we have $n-1$ possible preimages for
the first remaining element of the codomain, $n-2$ possible preimages
for the second remaining element of the codomain, and so forth.  This
gives us $(n-1)\times(n-1)!$ ways to arrange the chess sets.

This should make sense since, from part (c), $(n-1)(n-1)!+(n-1)!=n!$,
the total number of arrangements of $n$ chess sets into $n$ lockers.}

\ppart Lars has a sudden change of heart and decides to be
nice to Dexter.  At this time, he also realizes that Frohike has
conscientiously written his name on the outside of his chess set, so
now Lars knows the correct destinations of two chess sets.  How many
arrangements are there now?

\solution{This is basically the same as part (c).  Say Frohike's chess
set is $c$ and his locker is $d$; then, we want $f(a)=b$ and
$f(c)=d$.  The first remaining element of the codomain has $n-2$
possible preimages, the second remaining element of the codomain has
$n-3$ possible preimages, and so forth.  This gives us $(n-2)!$
possible ways to arrange chess sets in lockers.}

\ppart Say Lars is taking mind-altering drugs and has again changed
his mind about Dexter.  Still being able to discern Dexter's and
Frohike's chess sets---but wishing to ill-place Dexter's---Lars can
place chess sets in lockers in how many ways?
\solution{This is inclusion exclusion on parts (c) and (e). We know
that $|A\cap B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of
functions with $f(a)=b$ and $B$ to be the set of functions with
$f(c)\not=d$, then we know $|A|$ and $|A\cap\bar B|$, the latter of
which is the solution to part (e); so, the answer is
$(n-1)!-(n-2)!$.  }

\eparts


%END   Tina's problems


%% begin Yu-Han's problems for Fall 2001

% Towers of Hanoi, outcome 7
% Yu-Han, Fall 2001

\problem {\bf Towers of Hanoi}

The Towers of Hanoi game involves stacking $32$ disks onto three vertical
pegs, \cf Rosen \S 5.1, Example 5.  Each disk has a hole in the middle
through which a peg can slide, and all the disks have different diameters.
An arrangement of the disks on the pegs is allowed only if no disk rests
on a smaller disk.  How many different such arrangements are allowed?

\solnospace{There are $3^{32}$ different configurations by the product
rule: 3 choices of peg for the largest disk, 3 choices for the second
largest disk, and so on.}


% Bostonian Field of Dreams, outcome 7
% Yu-Han, Fall 2001

\problem {\bf In a Bostonian field of dreams...}

In some imaginary world, the Boston Red Sox are playing the New York Yankees
for the World Series Championship title.  In fact, they've already won the first
game of the series, and there is great enthusiasm in Beantown at the prospect
of winning the whole thing.  People in the sports bars talk excitedly about 
the different ways Boston could win (will they sweep it?  will they lose the 
second game but come back and take the next three? ...), but they are all a 
little too inebriated
to figure out all the possibilities.  Wielding your tree diagram method and
your smart MIT brainpower, 
calculate for them
the many many different ways the Red Sox could actually take home the title!  
(For those
of you unfamiliar with baseball, the World Series is a best of seven tournament, 
i.e. the first team to win four games wins the title.)

\solnospace{The required
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/figures/tree-psol8.jpg}{tree
diagram} is attached.

Alternatively, one can
count the number of ways the Red Sox could win using the combinatorics we have
covered since last week.  We need to choose three games out of six remaining for
the Red Sox to win.  After each third game is played in which the Red Sox win, 
the series is considered over.  Thus, there are $C(6,3) = 20$ possibilities.
}



%% Square-Free
% outcomes 7, Inclusion-Exclusion
% Yu-Han, Fall 2001


%%  Inclusion-Exclusion, s98 : ps7, prob 3; Spring '01, Tutorial 8

\problem {\bf Square-Free}

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.  Use inclusion-exclusion to find the
number of square-free positive integers strictly less than 151.

\solnospace{We use Inclusion-Exclusion as was done for
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}{rule}{count-primes}{counting
prime numbers} in Notes and Rosen.  So we compute the number of positive
integers less than 150 that are \emph{not} square-free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set of
multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$) less than
150.  The union of these sets is the set of all numbers less than 150
which are not square-free, \ie have some square divisor in them.
The reader should take a moment to think through why this assertion
is true (why only primes? why stop at 11?).

The cardinality of this set can be computed by the Inclusion-Exclusion
Principle.  Since $2^2 7^2 > 150$ and $3^25^2 > 150$, it follows that $A_i
\intersect A_j = \emptyset$ unless $\set{i,j}=\set{2,3}$ or $\set{2,5}$,
so

\begin {eqnarray*}
\card{A_2 \cup A_3 \cup A_5 \cup A_7} & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/2^23^2 \rfloor
- \lfloor 150/2^25^2 \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 - 4 - 1\\
& = & 58
\end {eqnarray*}
Therefore, the number of square-free positive integers less than
150 is
\[
150 - 58 = 92.
\]
}



%% end Yu-Han's problems for Fall 2001




\end{problems}

\end{document}



