6
$\begingroup$

My friend got 5 different books. He does not mind how many books I can select to borrow each time - even if I borrow none. How many different selections are possible?

I am thinking that this is a "combination" problem since the order of the books does not matter.

So I can make these selections: 5 books OR 4 books OR 3 books ...etc OR zero books. So there would be 6 different selections possible - but this was the wrong answer.

Where have I gone wrong?

$\endgroup$
3
  • $\begingroup$ Looks the kind of book you borrowed makes a difference even though the order doesn't. For example, you could borrow $1$ book from your friend in exactly $5$ ways, by choosing a different book each time. $\endgroup$
    – AgentS
    Commented Aug 9, 2019 at 3:01
  • $\begingroup$ There is one way to select all five books and there is one way to select no books. There are five ways to select one book and there are 5 ways to select 4 books. See the pattern? $\endgroup$
    – Vasili
    Commented Aug 9, 2019 at 3:05
  • $\begingroup$ Using the "pattern" you suggested, I could only arrive at 23 different selections (ie. 1 way to select zero + 1 way to select 5 books + 5 ways to select 4 books + 7 ways to select 2 books + 4 ways to select 3 books = 23 ways). But 23 is not the correct answer $\endgroup$
    – Tickle Me
    Commented Aug 9, 2019 at 7:09

3 Answers 3

1
$\begingroup$

What matters is which books you borrow, not how many books you borrow. Borrowing Apostol's Calculus and Munkres' Topology is different from borrowing Herstein's Algebra and Rudin's Principles of Mathematical Analysis.

There are $\binom{5}{k}$ ways for you to borrow exactly $k$ of the five books. Since you can borrow from $0$ to $5$ books, the number of different selections of books you could borrow is $$\sum_{k = 0}^{5} \binom{5}{k} = \binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 32$$ As Parcly Taxel observed, with each selection, you either choose to borrow a particular text or not borrow it. Since there are two choices for each of the five books, there are $2^5 = 32$ possible selections of books you could make.

The two approaches are related by the Binomial Theorem. $$(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k}x^{n - k}y^k$$ If we let $n = 5$, $x = 1$, and $y = 1$, we obtain $$2^5 = (1 + 1)^5 = \sum_{k = 0}^{5} \binom{5}{k}1^{n - k}1^k = \sum_{k = 0}^{5} \binom{5}{k}$$

$\endgroup$
3
  • 1
    $\begingroup$ in other words: you borrow a subset of the set $\{a,b,c,d,e \}$ and one of the definitions of the binomial coefficient $\binom{n}{m}$ is just the number of subsets of size $m$ from a set of size $n$ $\endgroup$
    – G Cab
    Commented Aug 9, 2019 at 14:55
  • $\begingroup$ This is the correct answer. Thank you for explaining your answer - although I did not fully understand the maths behind it. Please let me know if there is a more simplified explanation, mainly to help junior high school level students. $\endgroup$
    – Tickle Me
    Commented Aug 12, 2019 at 5:49
  • $\begingroup$ For junior high school students, I recommend starting with fewer books and making a tree diagram. For each book, the person either borrows the book or does not. For two books, you will have four outcomes: borrows both books, borrows the first book but not the second, borrows the second book but not the first, or borrows neither book. If you do this for one book, two books, and then three books, they should see that the number of options doubles each time, which would allow you to justify the answer $32$ as part of the pattern $2, 4, 8, 16, 32, \ldots$. $\endgroup$ Commented Aug 12, 2019 at 8:38
1
$\begingroup$

If your friend has $n$ different books, you have $2^n$ selections, since for each book you can either borrow or not borrow it. For the number of books you borrow, there are indeed $6$ possibilities here, but the correct answer is greater since two selections with the same number of books may have differing books.

$\endgroup$
2
  • $\begingroup$ Could you further clarify "but the correct answer is greater" ? So how would you arrive at the correct answer ? $\endgroup$
    – Tickle Me
    Commented Aug 9, 2019 at 7:14
  • 1
    $\begingroup$ @TickleMe I can borrow A and B, or A and C. Two different selections with the same number of books. $\endgroup$ Commented Aug 9, 2019 at 7:15
0
$\begingroup$

You are in a way right to say I can borrow 1 book but since all 5 books are different which book in particular you borrow itself can make a difference like 1 book. Can be borrowed in 5 different ways. Let us say books are A,B,C,D,E When you borrow either you will borrow A on will not borrow A hence book A can have 2 possible ways to share similarly all 5 books. Hence it will be 2^5.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .