5 books in 3 bundles

Question

5 distinct books can be tied in 3 indistinct bundles in how many ways, if order of book within a bundle does not matter?

I have counted in following way, and I saw another person counting in a different way, which also seem correct to me, but our results do not tally. Can anyone point out why?

My way :

$5$ books can be tied in $3$ bundles in two different ways 1 + 1 + 3 or 1+2+2.

$1+1+3\rightarrow \binom{5}{3} = 10$ ways

$1+2+2\rightarrow \binom{5}{1} \binom{4}{2}=5.6=30$ ways.

Total 10+30 = 40 ways.

Another person's way :

5 distinct books can be divided in 3 distinct bundles (empty allowed) in $3^5$ ways. Subtracting the cases where one bundle is empty $\binom{3}{1} 2^5$, adding the cases where 2 bundles are empty $\binom{3}{1} 1^5$. Total $3^5-3.2^5+3=243-96+3=150$. Since the bundles are indistinguishable, all 3! permutations among the bundles are to be counted only once. So total number of ways = $150/6=25$

Answer 1

You have a mistake in your $1+2+2$ case.

You begin by choosing the one book that gets bundled by itself. This can be accomplished in $5$ ways.

The next step, in presumably what you are thinking, is to "pick which two books go into the first 2-bundle" and then the remaining books go into the second 2-bundle. This can be done in $\binom{4}{2}$ ways.

However... we can't tell after the fact which of the two 2-bundles was the "first" or the "second"! You have double counted these outcomes.

You can correct this by recognizing that you counted each outcome twice and dividing by symmetry... giving $\binom{5}{1}\cdot \binom{4}{2}\cdot \frac{1}{2}=15$ ways for this case.

I dislike "division by symmetry arguments" and so instead prefer to think of this as after having chosen the book for the 1-bundle, among those four remaining books one has the smallest ISBN number (or other distinguishable feature). We then choose which book gets paired with that book. The remaining books get paired together. Choosing which book gets paired with that book with the smallest ISBN number can be done in $3$ ways, giving a total of $5\cdot 3 = 15$ ways for this case.

Answer 2

Okay, if you allow an empty bundle, then you can have the following situations:

A: $\{5,0,0\}$. There is one way to do this.

B: $\{4,1,0\}$. There are five ways to do this (select the one that is in its own bundle.

C: $\{3,2,0\}$. There are $\pmatrix{5\\3}=\frac{5!}{3!2!}=10$ ways.

D: $\{3,1,1\}$. There are $\pmatrix{5\\3} = 10 $ ways.

E: $\{2,2,1\}$. There are $\frac{1}{2} \cdot \pmatrix{5\\2} \cdot \pmatrix{3\\2}=10\cdot 3 /2=15$ ways.

That is it. Adding them up: $1+5+10+10+15=41.$

The comments are correct! We've got duplicates in E and need to divide by two. (Bundle 1 and bundle 3 are exchangeable).