\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, final} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).





\begin{problem} 
We are going to classify different counting problems by figuring
out which ones have the same formula.  Here are a set of six formula.
\begin{center}
\begin{tabular}{rl}
$n^m$:       &\brule{1in}\\
$m^n$:       &\brule{1in}\\
$P(n,m)$:    &\brule{1in}\\
$C(n-1+m,m)$:&\brule{1in}\\
$C(n-1+m,n)$:&\brule{1in}\\
$2^{mn}$:      &\brule{1in}\\
\end{tabular}
\end{center}
For each problem part below, write its label---(a),(b),\dots---on the line
next to the corresponding formula above.
\bparts

\ppart
Number of ways of putting $m$ indistinguishable balls into $n$
distinguishable urns.

\ppart Number of ways of putting $m$ distinguishable balls into $n$
distinguishable urns.

\ppart
Number of ways of creating $m$ letter words from an alphabet of size $n$,
with no letter used more than once ($m \leq n$).

\ppart
Number of ways of creating $m$ letter words from an alphabet of size $n$,
where any letter can be repeated any number of times.

\ppart Number of permutations of $m$ indistinguishable stars and
$n-1$ indistinguishable bars.

\ppart Number of matrices of size $\sqrt{n} \times \sqrt{n}$ with $m$
possible values for each entry.  (Assume $n$ is a perfect square.)

\ppart
Number of possible subsets of A, where $|A|=nm$.

\ppart
Number of possible functions from set $A$ to $B$ where $|A|=n$ and $|B|=m$.

\ppart
Number of relations from set $A$ to $B$ where $|A|=n$ and $|B|=m$.

\ppart Number of injections from set $A$ to $B$ where $\card{A}=m$ and
$\card{B}=n$, and $m \leq n$.

\ppart 
Number of natural number solutions of the equation $x_1 + x_2 + x_3
\cdots x_n = m$, where $m$ is a non-negative integer.  (A solution is
a non-negative integer vector of values for $x_1,x_2,\cdots x_n$.)

\ppart
Number of ways of lining up $n$ red balls and $m-1$ blue balls

\solution{
\begin{center}
\begin{tabular}{rl}
$n^m$: & b d\\
$m^n$: & f h \\
$P(n,m)$: & c j \\
$C(n-1+m,m)$: & a e k \\
$C(n-1+m,n)$: & l \\
$2^{mn}$: &  g i\\
\end{tabular}
\end{center}

\iffalse
\begin{enumerate}

\item
Number of ways of putting $m$ indistinguishable balls into $n$
distinguishable urns. $C(n-1+m,m)$

\item Number of ways of putting $m$ distinguishable balls into $n$
distinguishable urns. $n^m$

\item
Number of ways of creating $m$ letter words from an alphabet of size $n$,
with no letter used more than once ($m \leq n$). $P(n,m)$

\item
Number of ways of creating $m$ letter words from an alphabet of size $n$,
where any letter can be repeated any number of times. $n^m$

\item Number of ways of permutations of $m$ indistinguishable stars and
$n-1$ indistinguishable bars. $C(n-1+m,m)$

\item
Number of matrices of size $\sqrt{n} \times \sqrt{n}$ with
$m$ possible values for each entry. $m^n$

\item
Number of possible subsets of A, where $|A|=nm$. $2^{mn}$

\item
Number of possible functions from set $A$ to $B$ where $|A|=n$ and
$|B|=m$. $m^n$

\item
Number of binary relations between set $A$ and set $B$ where $\card{A}=n$ and
$\card{B}=m$. $2^{mn}$

\item
Number of injections from set $A$ to $B$ where $|A|=m$ and $|B|=n$,
and $m \leq n$. $P(n.m)$

\item 
Number of natural number solutions of the equation $x_1 + x_2 + x_3
\cdots x_n = m$, where $m$ is a non-negative integer.  (A solution is
a non-negative integer vector of values for $x_1,x_2,\cdots x_n$.)
$C(n-1+m,m)$

\item
Number of ways of lining up $n$ red balls and $m-1$ blue balls. $C(n-1+m,n)$

\end{enumerate}
\fi
}

\eparts
\end{problem}