\problemdata      
        {counting-10} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {M\&R \#4.7.5} % Source (if known)
        {S02 CP8F; F01, TU9} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
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$. For each ball, we can choose
one of 4 urns to put it in. We can think of this problem as a string
of 4 boxes (balls) from an alphabet of urns, or as a function from a
set of balls to a set of urns. The fact that all the balls are
different is important.}

\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$. Note, there is a fundamental difference between
balls and urns - an urn can hold many balls, but a ball can go into
only one urn. So having urns indistinguishable is not the same as
having balls be indistinguishable.} 

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