How many ways are there to arrange $n$ books on $k$ shelves assuming the following conditions?
1) The books are indistinguishable, the shelves are distinguishable
Answer: There are $n$ books and $k-1$ dividers, so this is a sequence of $n+k-1$ stars that we will choose $k-1$ of the stars to turn into dividers, resulting in $n$ stars representing books and $k-1$ dividers. The answer is:
$$n+k-1 \choose k-1$$
2) The books are indistinguishable, the shelves are indistinguishable
Answer: This is just the number of ways in case 1 divide by k! because case 1 counted distinguishable shelves, which implicitly counted the permutation of the shelves. So we explicit divide by the permutation of the shelves for indistinguishable shelves. The answer is:
$$\frac{n+k-1 \choose k-1}{k!}$$
3) the books are distinguishable, the shelves are distinguishable, and the order of the books on each shelf matters
Answer: do this 2 stages. First, there are $n!$ ways of arranging the books. Then, for each arrangement, use the stars and dividers method in case 1 to place $k-1$ dividers, which there are $n+k-1 \choose k-1$ ways. The anwser is:
$$n! \times {n+k-1 \choose k-1}$$
4) the books are distinguishable, the shelves are indistinguishable, and the order of the books on each shelf matters
Answer: this is just like the relationship between case 1 and case 2, so we divide by the result from case 3 by $k!$. The answer is:
$$\frac{n! \times {n+k-1 \choose k-1}}{k!} $$
Is my logic correct in these answers?
Best Answer
Case 1 and 3 are correct but the rest aren't.
Note when $n=1$ and $k = 3$ your answer for 2 gives:
$$ \frac{\binom{3}{2}}{3!} = \frac{1}{2} $$
This should tell you that something is wrong. (Hint permutations don't act freely on your objects from Case 1).
Note that some of these questions don't have nice closed forms.