0
   

Basic Probability Question

 
 
Quincy
 
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.
 
View best answer, chosen by Quincy
markr
  Selected Answer
 
  3  
Reply Sat 21 May, 2011 02:30 am
@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.
Quincy
 
  1  
Reply Sat 21 May, 2011 04:59 am
@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. Very Happy
0 Replies
 
 

Related Topics

 
  1. Forums
  2. » Basic Probability Question
Copyright © 2024 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.04 seconds on 04/27/2024 at 09:43:53