Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Having a little bit of trouble with this question, but I don't necessarily want the answer, I'm looking for an explanation on how to do it, and if my theory is correct.

How many ways are there to place 25 different books on 10 number shelves in the following scenarios:

a) Order of books on a shelf matters b) Order of books on a shelf doesn't matter c) Order matters, but each shelf must have at least one book

Firstly, I want to make sure I'm understanding the question correctly. We have 10 shelves, and for a, I want to see how many orderings of books there are, where like one shelf could have all 25 potentially?

Here's my thinking:

a) $25P25$ for the first place, as order matters and there's 25 ways the books could be arranged on that shelf, or it could be in the second place, third, etc. so $(25P25)*10$?

Or would I do it like a Stars and Bars question? Because the above answer is massive.

b) Order doesn't matter, so combinations now. Would I do $25C25 * 10$? Or is there a way to differentiate Stars and Bars between permutations and combinations?

c) Stars and Bars but with the restriction of each gap having one at least?

share|improve this question

2 Answers 2

You can divide your task in steps, count the ways that you can conduct each step and then use the multiplication principle to count the total number of ways that you can conduct your task.

a) You can do it in two steps.

1.Step. Order your books. You can do it in $25!$ ways.

2.Step. Decide on how many books will be placed on each shelf. That is equivalent to writing on piece of paper 10 nonnegative (zeros are here allowed in c they are not!) integers $x_1,x_2,\dots,x_{10}$ so that they add up to 25. For $i=1,2,\ldots,10$, $x_i$ represents the number of books that will be placed on the $i$-th shelf. The total number of ways that you can conduct this step is equal to the number of solutions to the equation $$x_1+x_2+\ldots+x_{10}=25,$$ with $0\leq x_i, i=1,2,\ldots,10$. This is a typical stars and bars problem with $n=10$ and $k=25$. Then (according to the Wikipedia page, Stars and Bars, Theorem two) you can do that in $$\dbinom{n+k-1}{k-1}=\dbinom{10+25-1}{10-1}=\dbinom{34}{9}$$ So in sum the task in (a) can be conducted in $25!\times\dbinom{34}{9}$ ways.

c). Based on a) the answer is straightforward by allowing in Step 2. only positive values for the $x_i, i=1,2,\ldots,10$. The total number of ways that you can conduct this step is equal to the number of solutions to the equation $$x_1+x_2+\ldots+x_{10}=25,$$ with $1\leq x_i, i=1,2,\ldots,10$. Then (according to the Wikipedia page, Stars and Bars, Theorem one) you can do it in $\dbinom{k-1}{n-1}=\dbinom{25-1}{10-1}$ ways.

So in sum the task in (c) can be conducted in $25!\times\dbinom{24}{9}$ ways.

b) 25C25 is equal to 1 so, your approach here is not correct. Here you can think it as follows. Write on each book a number from 1 to 10 (this number indicates the shelf that it will be placed). So you can do it $10\times10\times\ldots\times10=10^{25}$ ways. (With steps as in the previous questions: 1.Step Choose a shelf for book Nr1. You can do it in 10 ways. 2.Step Choose a shelf for book Nr2. You can do it in 10 ways and so on until 25.Step Choose a shelf for book Nr25. You can do it in 10 ways. So by multiplication rule you can do it in $10^{25}$ ways.)

share|improve this answer
    
I think for $\dbinom{n+k-1}{k-1}$ you meant to write $\dbinom{n+k-1}{n-1}$. But nicely done. –  David K Jun 29 at 15:19

For a), you can think of ordering the books in one order, which gives $25!$ ways. Then we have to choose how many of them go on the first shelf. You can think of putting $9$ dividers into the $26$ spaces before, between, and after the books allowing repetition. This is the number of weak compositions of $9$ into $26$ parts, which is ${26+9-1 \choose 9-1}$. Yes, the answer is massive.

Presumably in b) you still care which book(s) are on each shelf. Then take the books in order and put each one on a shelf. It has $10$ places to go.

For c) you can take your answer from b) and use the inclusion-exclusion principle to deduct those with an empty shelf or more.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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