1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jerry Guern Sep 18 '15 at 3:00
1
$\begingroup$

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)."

$\endgroup$
  • $\begingroup$ The only thing that still somewhat confuses me, is that in your last example where the books are arranged in alphabetical order, the order matters as well and yet, the way we are counting is different. Could you elaborate why they are different? $\endgroup$ – O.A. Sep 18 '15 at 4:05
  • $\begingroup$ In that example, yes there is an ordering, but only one ordering. Think of it like you can take the books and throw them into two bins, one labeled "shelf one" and the other labeled "shelf two." Regardless what order you tossed them into the bins, the librarian will come by once you are done and put the books on each shelf in a very specific way, but still respecting your decision as to which shelf each book should go to. In that sense, order doesn't matter (which is similar as I show here to there being only one order possible). $\endgroup$ – JMoravitz Sep 18 '15 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.