P&C question (H2 maths)

• Mad Hat

  5 Apr 13, 00:15

  I found this nice P&C question in the book A-level H2 Maths Topical Practice by Lois Chee:

  In how many ways can 4 copies of a book be distributed among 6 people if
  (i) no one gets more than 1 copy of the book,
  (ii) each person can get any number of copies of the book?

  Part (i) is fine. The answer is ⁶C₄ = 15 ways. The books are copies, so they are indistinguishable, so we just choose any 4 people out of the 6 to receive one copy each.

  Part (ii) is harder. The author gives this answer:

  For each copy of the book, it can be distributed to any of the 6 people. Number of required ways = 6 x 6 x 6 x 6 = 6⁴ = 1296.

  But this doesn't seem right. This would be correct if the 4 books were different from each other. But the 4 books are identical copies. So if I give them to Tom, Dick, Harry, Jane (in that order), it is no different from giving them to Jane, Harry, Dick, Tom (in that order). But the author's method counts this as two different possibilities. So there is double counting in at least some cases.

  At first, I thought the correct answer must be 6⁴ ÷ 4! to eliminate the double counting. But I don't think this is right either.

  What is the correct way to do part (ii)? It seems harder than I thought 

• Mad Hat

  5 Apr 13, 02:39

  If we enumerate all the possibilities:

  All 4 copies to one person: 6 ways
  3 copies to one person, 1 to another: 6 x 5 ways
  2 copies to one person, 2 copies to another: ⁶C₂ ways
  2 copies to one person, 1 copy each to two people: 6 x ⁵C₂ ways
  1 copy each to four people: ⁶C₄ ways

  Total: 6 + 30 + 15 + 60 + 15 = 126 ways.

  But this doesn't indicate how to solve the general problem of distributing r copies of a book to n people (where r < n). It seems like a general solution should be possible for this kind of problem?

  Is there a better way?

• wee_ws

  5 Apr 13, 14:37

  Hi,

    Thanks for sharing, it's a past-year school's exam question if I remember correctly :P

    The enumeration method is the most certain approach :)

    From the book Counting by Koh Khee Meng and Tay Eng Guan, page 48:
  
    The number of ways of distributing r identical balls into n distinct boxes is given by

    (r + n - 1) C (n - 1).

    This general result is not known to students so students are to think through the cases and list them as what you have corrected done.

    Thanks again.

  Cheers,
  Wen Shih

• Mad Hat

  6 Apr 13, 01:44

  Thanks for showing the formula! I googled the problem also and found a cool explanation of how to do the question. Imagine the 4 books being split by 5 separators, e.g.:

  B||B|B||B   or   BBB|||B||   or   B|||||BBB etc. (Many ways)

  There are 6 spaces between the separators, which we can use to represent the 6 people. Depending on where you place the separators, you get different ways of distributing the 4 books among 6 people. E.g. this one:

  BB|||||BB

  means that the first and last person get two books each, while the four people in the middle get none.

  So the problem is equivalent to the number of ways of arranging 9 symbols in a line, 4 of which should be B, 5 of which should be I.

  Answer: 9C4, same as 9C5 = 126. Very nice!

  The general solution is then (r+n−1)Cr, same as (r+n−1)C(n−1), which is the formula you gave above. I agree this is beyond the A-level syllabus, but not very far beyond actually!

• wee_ws

  6 Apr 13, 07:43

  Hi,

    Thanks for sharing the explanations :)

  Cheers,
  Wen Shih