% substantially rewrote christos's orginal problem
% maybe should have put in new file but instead just commented his
% version out at the bottom.


\begin{problem}[20]
We want to determine the number of sequences of $k$ integers in the
range $1$ to $n$ that are {\em increasing}; that is, each integer in
the sequence is greater than or equal to the one before. For example
if $k = 4$ and $n = 7$, then the sequence $1127$ is increasing whereas
the sequence $1427$ is not.

\begin{problemparts}

\problempart[5] Describe a mapping between the set of increasing sequence
of $k$ integers and a set of arrangments of stars and bars, such that
the mapping is a bijection.

\solution[\vspace*{4cm}]{Each sequence corresponds to a string of $n-1$
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}
\]

Note there are many different ways of creating this mapping, for
example consider having $n$ bins ($n-1$ bars) with values $1$ through
$n$ and $k$ balls representing the $k$ integers that can be placed
inside the bins.

It is also possible to describe mappings that dont help derive the
answer...  
}


\problempart[3] What is the total number of such sequences?

\solution[\vspace*{2cm}]{
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-1 + k}{k}.
\]
} 

\problempart[6] Suppose that I randomly choose $k$ integers from the
range $1$ to $n$ uniformly and independently. What is the probability
that I get an increasing sequence?

\solution[\vspace*{3.5cm}]{The total number of possible sequences is
$n^k$ and all seuqnces are equally likely. Therefore

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

Now instead consider sequences of $k$ integers that are that are {\em
strictly} increasing, in other words each integer in the sequence is
strictly greater than the one before. For example if $k = 4$ and $n =
7$, then the sequence $1127$ is not strictly inscreasing but $1237$
is.

\problempart[6] Suppose that I randomly choose $k$ integers from the
range $1$ to $n$ uniformly and independently (where $k < n$). What is
the probability that I get a strictly increasing sequence?

\solution[\vspace*{2cm}]{ 

The number of strictly increasing sequences can be thought of as
having $n$ bins and $k$ balls but a bin can hold only one
or zero ball. Therefore, the number of ways in which you can choose k bins is
$\binom{n}{k}$.

\[
\frac{\binom{n}{k}}{n^{k}}
\]
}

\end{problemparts}
\end{problem} 

\comment{Eric}{bug in solution (d) fixed}
\comment{Radhika}{Check for bugs, ambiguous wording}


\iffalse
\begin{problem}
\begin{problemparts}

\iffalse
\problempart
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$. 
}
\fi

\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{problem} 

\comment{jack}{looks like it's
from tutorial but i believe it's a good exam problem.}
\fi