Number of ways of sorting distinct elements into 4 sets This was on a test I just had. The first part says:
"A person donates nine antique clocks to four different museums. Supposing all clocks are identical and he can distribute them in any way he chooses, how many ways are there of donating the clocks"?
This is choosing elements with replacement which has a well known formula of $n+r-1\choose r$ where $n=9$ and $r=3$ in our case. The next part is what has me stumped:
"Now suppose each clock is different. In how many ways can they be donated"?
He can still distribute them any way he chooses, so the first museum could get 8, the second 1 and the others none. I still can't figure out how to do this. I thought one would first want to choose an arrangement of the 9 objects of which there are 9! such arrangements. But then I'm not sure how to account for all the possible number of elements that each museum could get.

Every clock goes to one of four museums, so there are $4$ choices for the first clock, $4$ for the second,... for a total of $4^9$ in all by the rule of product for combinatorics.
