# put 24 different books on 4 shelves, each shelf has at least one book. why my answer is wrong?

put 24 different books on 4 shelves, each shelf has at least one book(The books are put next to each other). How many ways?

The right answer is C(23,20)*24!, meaning the first divide the 24 slots into 4 groups and each group has 1 slot, we get C(23,20), then put 24 books into these 24 slots in order we get 24!. Therefore the result is C(23,20)*24!.

My answer is C(24,4)*4^20. I first choose 4 books and put them onto each shelf, I get C(24,4), then just put the rest 20 books which ever shelf, it should be 4^20. So my answer is C(24,4)*4^20.

Can anyone tell why my answer is wrong?

• One way to see the right answer: Order all of the books, of which there are $24!$ ways. Then put the first four books on each of the shelves, so that each shelf has a book. Then use stars and bars on the remaining $20$ books, of which there are $\binom{20+4-1}{20}=\binom{23}{20}$ ways. – Aweygan Jan 25 '17 at 20:57

You are overcounting. Cases where the first shelf get books $a,b$ are counted once with $a$ among the first four and again with $b$ among the first four. You are also undercounting by not accounting for the order of books on each shelf

After the first four books are chosen, your way doesn't take into account in which order the rest of the books are in each shelf. Also, you don't distinguish which of the first four books go on which shelf. So, for instance, you count

1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22
23 24

as indistinguishable from

11 10 9  8  7  6  5  4  3  2
21 20 19 18 17 16 15 14 13 12
23 22
1  24

This is an example of stars and bars. Assume that the books are numbered from $1$ to $24$: $$1\;2\;3\;4\;5\;6\;7\;8\;9\;10\;11\;12\;13\;14\;15\;16\;17\;18\;19\;20\;21\;22\;23\;24$$ and put three separators between them (we have $23$ distinct places for positioning such separators) $$1\;2\;3\;4\;5\;6\;7\;8\,\color{red}{\perp}\,9\;10\;11\;12\,\color{red}{\perp}\,13\;14\;15\;16\;17\;18\;19\,\color{red}{\perp}\,20\;21\;22\;23\;24$$ then choose a random permutation from $S_{24}$ $$12\;2\;16\;4\;5\;6\;23\;8\,\color{red}{\perp}\,9\;18\;11\;1\,\color{red}{\perp}\,13\;15\;14\;3\;17\;10\;19\,\color{red}{\perp}\,20\;21\;22\;7\;24$$ getting four non-empty shelves. Every arrangement can be generated this way and the single steps are independent, hence we have $\binom{23}{3}\cdot 24!$ ways for accomplishing our task.

This is classic stars and bars. Here is a general formula. If the order of the books doesn't matter we treat our $n$ shelves as bars and our $k$ books as stars. Then we have $n-1$ bars and $k$ stars. Thus if order of the books doesn't matter a general formula (where we may have a shelf with zero books on it) is $${n - 1 + k \choose k}.$$ If we need to put at least one book on a shelf then we have $n$ shelves and we put $1$ book on each leaving us $k-n$ books (stars). Then we again have $${n - 1 + k - n \choose k -n }$$ where the order of the books on the shelves doesn't matter.

Alternatively if order matters we proceed in a similar fashion but first impose the ordering $k!$ on our $k$ books. So then we have $$k! \cdot {n - 1 + k \choose k}$$ with no restrictions (i.e. a shelf can be empty). And $$k! \cdot {n - 1 + k - n \choose k - n}$$ for at least one book per shelf.

• This concludes everything I need to know, thank you! – Di Wang Jan 25 '17 at 22:47
• @DiWang no problem! Feel free to upvote/accept answer if you desire! – ClownInTheMoon Jan 26 '17 at 1:34