% 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}[15]
Suppose we have a length $k$ sequence of integers, where each integer
is in the range $1$ to $n$ (inclusive). The sequence is \emph{weakly
increasing} if each integer in the sequence is greater than or equal
to the one before. For example if $k = 4$ and $n = 7$, then the
sequences $1127$ and $1247$ are weakly increasing but the sequence
$1427$ is not. We want to determine the number of such weakly
increasing sequences.

\begin{problemparts}

\problempart[5] Define a bijection between weakly increasing length
$k$ sequences of integers in the range $1$ to $n$, and arrangements of
stars and bars (no proof necessary). Give the stars-and-bars
representation of the sequence 3 4 4 6, where $k = 4$ and $n = 7$.

\solution[\vspace*{3.5in}]{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 is more than one way 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 don't help derive the
answer\dots.
}

\problempart[3] Write a simple formula in terms of $n$ and $k$ for the
total number of such weakly increasing sequences. Your answer may be
expressed in terms of binomial coefficients and/or factorials.

\solution[\vspace*{2in}]{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}.
\]
}

\instatements{\newpage}
\problempart[2] Suppose that all length $k$ sequences of integers,
where each integer is from the range $1$ to $n$, are equally likely,
and I choose one at random. Write another simple formula for the
probability that I get a weakly increasing sequence.

\solution[\vspace*{3in}]{The total number of possible sequences is
$n^k$ and all sequences are equally likely. Therefore
\[
\frac{\binom{n-1 + k}{k}}{{n}^k}
\]
}
\eparts

Now instead consider length $k$ sequences of integers, where each
integer is again in the range $1$ to $n$, that are \emph{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 weakly increasing sequence but not strictly
increasing; the sequence $1247$ is strictly increasing.

\bparts \problempart[5] Suppose that all length $k$ sequences of
integers, where each integer is from the range $1$ to $n$, are equally
likely, and I choose one at random. Write a simple formula for 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 at most
one 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}

\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
