# combinatorics - product rule: the number of ways to stack books

I have difficulty understanding what order means in this task (and in general).

The problem I have:

There are five books on the shelf. How many ways you can stack several of them (a stack can also consist of one book) if (a) The order of the books in the stack is not important (b) the order of the books in the stack is important

Solution for point (a):
we have 5 places in the stack, the book may or may not be lying in it, we'll mark it as 0 and 1. Then, the number of all possible combinations of these $$2^5$$, and we still need to subtract one case when all zeros, so that $$2^5 - 1$$.

Does this solution take into account the order or not? If not, why not? I tried to draw for a couple of cases, for example 01010 and 10100. Both these stacks have two books, if the order was not important, it would be one case, not two, right?

For point (b) the correct solution is through the sum of $$5 + 5 * 4 + 5 * 4 * 3 + ... + 5!$$, where each term is a number of ways to select n books out of 5. But how does it differ from the first one? Why are there so many more cases here than in the first case? Haven't we considered all the possible combinations in (a)?

Shortly, I'm confused.

• If you want to find the number of stacks where order matters, then the number of subset permutations of a set is given by $$e\Gamma(n+1,1)$$ where $\Gamma$ is the incomplete Gamma function. Plugging in 5 and subtracting for the empty set, you have: $$e\Gamma(6,1)-1 = 325$$ Wolframalpha Apr 2, 2019 at 13:34

Does this solution take into account the order or not? If not, why not?

It does not. The reason is that the only thing you have taken into account here are which books to include in the stack. You've gone to each book in order, asked "Do I want this book to be in the stack or not?", gotten a yes / no answer, and that's it. There are $$2^5$$ different ways that this question round can go, one of those ways does not result in a stack, so there are $$2^5 - 1$$ different stacks you could make.

Why are there so many more cases here than in the first case? Haven't we considered all the possible combinations in (a)?

Yes, you considered all possible combinations, but not the fact that a stack could be ordered in many different ways. So while in (a), "a stack of all the books" only made for a single possibility, namely "a stack of all the books", this time there are $$5! = 120$$ different orders to stack those five books. And similarily for four, three or two books. This naturally leads to more possibilities.

• So, in the first case, I answer the question of how many different possibilities I have to take a few books and put them in a stack, considering that they are different, and in the second case the same, but I have to consider the possibility to take the books in different order? Apr 2, 2019 at 13:39
• @AlexanterNikolin Yes, that's it. Apr 2, 2019 at 13:41

If order matters, then we want to find the number of orders of books in the stack. I am not sure what notation you are familiar with. I will use the binomial coefficient notation. So, depending on which notation you are familiar with:

$$\dbinom{n}{r} = \dfrac{n!}{r!(n-r)!} = {_n}C_r = {^n}C_r$$

The number of orders is given by:

$$\sum_{i=1}^5 i!\dbinom{5}{i}$$

What this means is that there are $$\dbinom{5}{1}$$ way of choosing one book, and $$1!$$ ways of permuting them. There are $$\dbinom{5}{2}$$ ways of choosing two books, and $$2!$$ ways of permuting them. Etc.

So, $$1!\dbinom{5}{1}+2!\dbinom{5}{2}+3!\dbinom{5}{3}+4!\dbinom{5}{4}+5!\dbinom{5}{5} = 325$$.

• Oh, well, that's a lot easier to think about. Perhaps I've confused myself with the way I approached the first point, it's harder to imagine. That is, in the first case we simply divide by the number of permutations (it is in the formula, like r!), and in the second case we multiply? Apr 2, 2019 at 13:48
• $$\dbinom{n}{r} = {_n}C_r$$ is the number of ways to choose $r$ distinct items from a set containing $n$ distinct items (order does not matter). $${_n}P_r = \dfrac{n!}{(n-r)!}$$ is the number of ways of permuting $r$ items from a set containing $n$ items. It is the difference between combinations and permutations. Apr 2, 2019 at 13:55