# K distinct items into N distinct containers

I am fairly new to the field of combinatorics and was solving a problem from our text book which wanted us to find in how many ways we could arrange 15 books on two different shelves, where each shelf has to have at least one book on it. The solution to the problem was rather simple as there are 15! ways that the books could be arranged, multiplied by the number of ways 15 books could be distributed on those two shelves: $15!{n+k-1-2 \choose k-2} = 15!{14 \choose 13}$

However I know that by definition, the number of ways to distribute K distinct items into N distinct containers is determined by $N^K$

Therefore my question is: Why isn't $N^K$ applicable in this case? Aren't the books considered as distinct items?

• You haven't defined n and haven't even stated the problem clearly. You're more likely to get an answer if you type out the question instead of vaguely paraphrasing. – Jerry Guern Sep 18 '15 at 3:00

The $N^K$ answer is the correct one in the case that order does not matter. An example of a problem that would use this is "In how many ways can the answer key of a multiple choice test be filled out?" In this case, each question is distinct (there is question 1, question 2, etc...) and each answer is distinct (answer a, answer b, etc...). With a $20$ question test and $4$ answers available for each, there are $4^{20}$ possible answer keys. Here, the questions are treated as the "objects" and the answers are treated as the "containers" (you can keep them separate in your mind by noting that you can have multiple questions in one answer category but you cannot have multiple answers in one question category).
That does not seem to be the case for the way this problem is phrased however, being "how many ways can you arrange books onto shelves" which implies that the order that the books appear on the shelves matter. I.e., not only is it important which shelf each book is on, but where on the shelf it is. As a result, we have to approach differently. As the solution key suggested, first arrange the books in $15!$ number of ways, and then looking at the spaces between the books, place a "divider" which signifies that those books to the left go to the first shelf, and those books to the right go to the second shelf. Since the problem specifies that we require at least one book on each shelf, we ignore the space on the far left and the far right, for a total of $14$ spaces available to place the divider. By multiplication principle, we multiply these together to get the total number of $15!\cdot 14$.
The other answer of $2^{15}-2$ (minus two is to avoid the scenario of either shelf being empty) could be correct if the problem were phrased a bit differently, such as "How many ways can fifteen distinctly named books be arranged on two shelves if the books must appear in alphabetical order(from left to right) on the shelf they are on (such that neither shelf is empty)."