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

Question

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.

Answer 1

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.

Answer 2

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$.