Reply
Fri 20 May, 2011 01:57 pm
Hi everyone.
I last did probability about 5yrs ago(?) and I've been trying to refresh my memory of it. Here's a question that has me stumped.
How many ways are there of placing n un-identifiable letters in m mailboxes?
If you can distinguish the letters the answer is quite easy: m^n, because each letter has m possible boxes it can go into.
For this case where the letters are un-identifiable or un-distinguishable, the only way I can think of doing it is the following:
If you have 1 letter there are m ways.
If you have 2 letters there are m ways of putting them all in one box, plus m!/[2!(m-2)!] ways of putting one letter in its own box (m is clearly >= 2 otherwise the problem is trivial).
If you have 3 letters there are m ways of putting all the letters in one box, plus m(m-1) ways of putting 2 letters in one box and the other elsewhere, plus m!/[3!(m-3!)] ways of putting each letter in its own box (provided m >= 3).
Etc. on to higher numbers of letters.
Is this correct? Is there a simpler way of going about it? I ask if there is a simpler way because the case where we can distinguish the letters appears so much easier.
Thank you for any help.
@Quincy,
To the n letters, add m-1 'separators' which will divide the letters into m groups (mailboxes), and lay them all out in a row. There are C(n+m-1, m-1) ways to position the separators. If two separators are adjacent, the mailbox between them is empty.
@markr,
markr wrote:
To the n letters, add m-1 'separators' which will divide the letters into m groups (mailboxes), and lay them all out in a row. There are C(n+m-1, m-1) ways to position the separators. If two separators are adjacent, the mailbox between them is empty.
Ah yes, that seems to be correct. Simple, elegant, to the point. I like it. I thought I was doing something wrong with my answer.
Thank you for the help markr.