0
$\begingroup$

From Schaum's Discrete Math:

Assuming a cell can be empty find the number of ways a set of 3 elements can be partitioned into:

a) 3 ordered cells b) 3 unordered cells

So let's say I've got the set ${a,b,c}$. So I have 1 way to choose a set of 3 and then 3 ways to arrange that set in 3 distinct cells. I then have $\binom{3}{2}=3$ ways to choose a set of 2 which then gives me a set of 2, a set of 1, and the empty set which can be arranged in $3!$ ways. I then have $3!$ ways to arrange the elements as single element sets. Thus I end up with $3+3*6+6=27$

However they just answered a) $3^3=27$ and b) 5 without any explanation.

How did they come up with $3^3$? How do you explain that?

1 Answers 1

1

OK, I get it. It's the number of functions from the set $\{a,b,c\}$ to the set of labelled cells. That's why it's $3^3$. So in the general case it would be $m^n$ to distribute $n$ elements in to $m$ labeled cells.