P&C question

change e world SG

hi, any kind soul out there to help me solve this question?

How many ways can 4 copies of the same book be distributed among 10 people if each person can take any number of books?

Answer is 715 and I could not get it no matter how hard I try.

quailmaster SG

consider case 1: books are distributed to 4 people, each person gets 1 book

10C4 = 210

consider case 2: books are distributed to 3 people , one person gets 2 books and the rest gets 1 book

10C3 X 3= 360

say A, B and C are chosen . Either A, B or C can get the 2 books

case 3: books are distributed to 2 person, one person gets 3 books, the other get 1 book

10C2 X 2= 90

case 4: 1 person gets all 4 books

10 C1 = 10

case 5: 2 person each gets 2 books

10C2 = 45

Adding up all 5 cases should yield 715

wishboy SG

there's another method to do this question

look at it as each person has a tray to collect the book, where each tray can only hold 1 book (easier to visualise if you draw out each 'tray' as a circle)

after distributing the first book, the person who got the book will get a new tray as each person can get more than 1 book.
in total, there are 11 trays now.

after distributing all 4 books, there will be a total of 13 trays
in these 13 trays, there will be 4 trays each holding a book
so it's like choosing 4 trays out of these 13 trays

hence, the answer is just 13C4 = 715

pardon me if this sounds confusing haha

Mad Hat SG

wishboy, wow, that's a totally ingenious way of approaching the question. i've never seen anything like that before. still trying to persuade myself that the method is sound ... but gosh thanks for sharing!

wee_ws SG

Hi,

It is correct. Combinatorically speaking, a general result is the following:

The number of ways of distributing r identical items into n distinct boxes is given by

(r + n - 1) C r.

Students will not know this result, so they are expected to consider different cases. Anyhow, it is stated in the syllabus that students will solve unfamiliar problems, of which some are classic problems like this one we have discussed.

Thanks!

Cheers,
Wen Shih

wee_ws SG

Hi,

Another general result is the following:

The number of ways of distributing r different items into n distinct boxes is given by

n^r.

Btw, the distribution problem involving diplomats came out as a question in 2008.

Thanks.

Cheers,
Wen Shih

Mad Hat SG

Wen Shih, thanks a lot. The second result you mentioned is easy to see, but the first result is not obvious at all. I would have used quailmaster's method but, clearly, if the numbers are large, e.g., distribute 100 identical books to 200 people, the method is not practical, so the general result is really useful. I think it is also very beautiful!

change e world SG

wow, im totally in awe. thanks for the help..