# Combinations - Permutations

Find the number of ways in which 5 books can be distributed between three people A,B and C, if the books are a)indistinguishable, b)all different.

a) $\displaystyle \frac{5!}{3!(5-3)!} = 10$

b)$5\times 4 \times 3 = 60$

Could you check my solutions?

• Your answer $a$ seems to be answering "how many ways can you pick exactly 3 books out of five distinguishable books" (without distributing). Your answer $b$ assumes that each person gets exactly one book. – JMoravitz Feb 20 '15 at 19:39
• I am practicing solving many similar problems, but it takes time to decided what method to choose. For instance, I was thinking of using a formula for combinations, repetition is allowed, so that I am quite confused. Would you be able to state the most important rules? Thank you. – ORIGIN Feb 20 '15 at 19:50
• Some basic problem types and answers added below. – JMoravitz Feb 20 '15 at 20:07

## 1 Answer

I recommend you think of this problem using the Stars and Bars approach.

Let $\star$ represent a book, and let $\mid$ represent a divider between people. Represent an outcome of who gets how many books in the following way: All $\star$'s to the left of the first bar will be given to the first person. All $\star$'s between the first bar and the second bar are given to the second person. All $\star$'s after the second bar are given to the third person. E.g. $\star \star \mid \star \mid \star \star$ corresponds to person $A$ getting two books, person $B$ getting one book, and person $C$ getting two books, whereas $\mid \mid \star \star \star\star\star$ corresponds to person $C$ getting all the books and $A$ and $B$ not getting any.

How many ways are there to arrange the stars and bars? Think combinations.

For part b, consider multiplication principle. Who gets book 1? Who gets book 2? Who gets book 3?...

To reply to the question in the comments above: A lot of it comes with practice in being able to reword a problem to match a different problem you have already seen.

• $n^r$ You have $n$ distinguishable objects, all of which being distributed to $r$ distinguishable people. "How many ways can you distribute 5 different books to 3 different people"
• $\left(\!\!\binom{n}{r}\!\!\right) = \binom{n+r-1}{r-1}$ You have $n$ indistinguishable objects, all of which being distributed to $r$ distinguishable people. "How many ways can you give 5 identical whole cookies to 3 children"
• $\binom{n}{r}$ You split $n$ objects into two partitions. One of size $r$ and one of size $n-r$. "How many ways can you choose 3 people out of a total of 5"
• $\binom{n}{r_1,r_2,r_3,\dots,r_k} = \frac{n!}{r_1!r_2!\dots r_k!}$ You split $n$ objects into $k$ partitions, of size $r_1, r_2,\dots, r_k$ respectively. "How many ways can you rearrange the letters of the word MISSISSIPPI"
• $\frac{n!}{(n-r)!}$ The number of arrangements of $r$ objects from a collection of $n$ distinguishable objects. "How many ways can first second and third place trophies be given in a race of 10 people"

Many counting problems can fall into one of these categories, though perhaps with a different flavor or may require multiple steps involving multiplication principle, addition principle, or inclusion-exclusion to account for further complexities. A big part of practice and understanding is trying to reword a problem you are given into one of these forms.

For examples, "How many ways can you rearrange the letters of the word MISSISSIPPI" is just a different flavor of the question "In a room of 11 people, how many ways can you split them into four distinguishable teams of sizes 1,2,4, and 4 respectively"

The "How many ways can you give 5 identical whole cookies to 3 children" is just a different flavor of "How many Diophantine (integer) solutions exist for $x_1+x_2+x_3 = 5$ subject to $x_i\geq 0$ for all $i$"