2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.