# A permutation and combination question (plus summation of a series)

A student is browsing in a second-hand bookshop and finds $n$ books of interest. The shop has $m$ copies of each of these $n$ books. Assuming he never wants duplicate copies of any book, and that he selects at least one book, how many ways can he make a selection? For example, if there is one book of interest with two copies, then he can make a selection in 2 ways.

So how I'm solving this is as follows: If he has to chose 1 book, he can do hat in $m$ ways. If he has to chose 2 books, he can do it in $m^2$ ways. Simialrly he choses $n$ books in $m^n$ ways. The total number of ways he can make this selection is $$\sum m + m^2 +..... m^n$$ which is a geometric series with sum $$\frac {(m) (1-m^n)} {1-m}$$ The answer however is apparently $(m+1)^n -1$ . Where am I going wrong?

## 2 Answers

The basic idea is fine, but it needs to be modified.

If he chooses $1$ book, there are $\binom{n}{1}$ ways to choose the title, and for each of these choices there are $m$ ways to choose the actual copy. Similarly, if he decides to choose $2$ books, there are $\binom{n}{2}$ ways to choose the $2$ titles, and for each of these ways there are $m^2$ ways to choose the actual copies, and so on. If he decides to choose $k$ books, there are $\binom{n}{k}$ ways to choose the $k$ titles, and for each way there are $m^k$ ways to choose the actual copies.

An easier way to solve the problem is to imagine that he stops beside each title, and then has $m+1$ choices. He can choose $1$ of the $m$ copies, or decide to skip that title. That gives a total of $(m+1)^n$ choices, from which we subtract $1$, since he cannot skip every title.

Remark: Let us temporarily allow the possibility of choosing no books. Then with your approach, as modified in the first paragraph of this answer, the number of choices is $$\sum_{k=0}^n \binom{n}{k}m^k.$$ By the binomial theorem, this is $(m+1)^n$.

For each kind of books, the person can choose $m$ copies, plus not to choose any of the kind. Since there are $n$ kinds, there are $(m+1)^n$ outcomes. Because the person chooses at least 1 book, this excludes the outcome that none are chosen, so there are $(m+1)^n - 1$ outcomes.