%\input mathhead.tex
%\magnification=\magstep1
%\nopagenumbers
\font\bigrm=cmr17
\font\medrm=cmr12
\font\medbf=cmbx12
\def\sc{\it}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\exerciseno{\count15}
\exerciseno=0
\def\algorithmcount{\count16}
\algorithmcount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
        \item{\the\exerciseno.}
       }
\def\section#1{\advance\sectioncount by 1
     \medskip
     {\par \noindent \bf\the\sectioncount.\enskip #1.}
     \medskip
%     \headline={{\sl #1\hfil\the\pageno}}
     \theoremcount=0
     \lemmacount=0
     \corollarycount=0
    }
\long\def\longtheorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\theorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longlemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\lemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longcorollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\corollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longalgorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\algorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\figure#1#2#3{\advance\figurecount by 1
                \vbox{
                      \vskip #1
                      \special{psfile="#2"}
                      \vskip .3true in
                      \centerline{Figure\ \the\figurecount.}
                     }
                \medskip
                \figurelabel{#3}
            }
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
            {\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
            \medskip
            }
\def\exerciselabel#1{\edef#1{\the\exerciseno}}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\algorithmlabel#1{\edef#1{\the\sectioncount.\the\algorithmcount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
        \vbox{
          \smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
        }
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\Q{{\rm\bf Q}}
\def\C{{\rm\bf C}}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}

\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}

\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
                \bigskip}
\def\({\left (}
\def\){\right )}
\def\[{\left [}
\def\]{\right ]}
\def\lf{\left\lfloor}
\def\rf{\right\rfloor}
\def\lc{\left\lceil}
\def\rc{\right\rceil}

\nopagenumbers

\centerline{\bigrm A Probability Computation.}
\bigskip

Tom rolled a fair die 6 times and found that the number 3 came up twice
while the number 2 did not come up at all.  Tom thought that since each
number is equally likely, on average each number should come up exactly
once out of 6 rolls.  Therefore, it seemed to him that it would be
likely that out of six rolls of the die each number should come up
exactly once.  His sister Mary, who was studying probability at the
time, told
him that it was not likely because even if after the first 5 rolls all 5
numbers were different, the probability of getting the remaining number
on roll 6 was only $1\over 6$.

After thinking about it for a day or two, Tom agreed with Mary.  Then he
wondered what would happen if the die had more than 6 sides.  He asked
Mary what she thought the probability would be after tossing a die with
$n$ sides $n$ times that each side would come up exactly once where $n$
is a very large number.  Mary
thought that the answer would be about
$\left({1\over 2}\right)^{n}$.  She explained that for each of the first
$n\over 2$
tosses the probability that toss yields an outcome different from
all the previous tosses is more than $1\over 2$ while for each of
the last $n\over 2$
tosses the probability would be less than $1\over 2$. So, she explained,
on the average it would be like flipping a fair coin $n$ times and
computing the probability that a head comes up each time. Tom, not
wanting to appear completely at
a loss (regardless of the facts) said he thought the probability
was less than $\left({1\over 2}\right)^n$.

It is your job to settle the argument.  But before you begin,
there are a few useful
formulas which you should be aware of.

Given the numbers $1,2,3,\cdots , n$ there are exactly $n!$ ways of
arranging the numbers in a row.  For example, if $n=3$ then the $3!=6$
ways of arranging the numbers in a row are 123, 132, 213, 231, 312, and
321.

If you do an experiment $n$ times
and each time you do the experiment there are $k$ possible outcomes for
that experiment, then there are a total of $k^n$ different sequences of
outcomes from the $n$ experiments.  For example, if you flip a coin 3
times there are $2^3=8$ possible outcomes: HHH, HHT, HTH, HTT, THH, THT,
TTH, TTT.

If every outcome among $n$ possible outcomes
is equally likely and you want to know the probability
that an outcome is one of a group of say $k$ outcomes then the
probability is $k\over n$.  For example, when you flip a coin once the
probability of a head is $1\over 2$ since there are two possible
outcomes and only one is a head.  On the other hand, the probability of
getting exactly two heads when a fair coin is flipped three times is
${3\over 8}$ since there are eight possible outcomes (as listed above) and
of these three have two heads.

Now follow the steps below to settle the argument.
\medskip

\item{1.}How many different possible sequences of outcomes are possible
         when a die with $n$ sides is tossed $n$ times?
\item{2.}In how many of the sequences in part 1) do each of the $n$
         possible outcomes occur exactly once?
\item{3.}Based on 1) and 2) what is the probability that among $n$
         tosses of an $n$--sided die each toss yields a different
         number from each of the others?
         (Just write your answer as a fraction involving the
         parameter $n$.)
\item{4.}In order to settle the argument you are to compute the $n^{th}$
         root of the number you wrote in part 3).  Write this formula
         and simplify.
\item{5.}Now compute the limit of the expression you found in part 4).
         This is the most significant part of the project.  You may wish
         to follow the hints below:
 \itemitem{a.}It will simplify things to compute the limit of the
              natural log.
 \itemitem{b.}After taking log, simplify and make your expression look
              like a Riemann sum.  You may need to review what
              a Riemann sum is.  You should get an integral of some
              function evaluated between 0 and 1.
 \itemitem{c.}If the Reimann sum gives an improper integral then compute
              it by computing the appropriate limits.
\item{6.}Based on your computations, who is right?  Why?

\bye