## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Colored balls in a bag

Best Answer plasmid, 11 May 2014 - 06:02 PM

Spoiler for atrocious but verified answer

Spoiler for this agrees with simulation - perl code
Go to the full post

10 replies to this topic

Senior Member

• Members
• 1837 posts
• Gender:Female

Posted 06 May 2014 - 02:12 PM

There are N balls in the bag. Each one has a distinct color. You draw one ball randomly from the bag, record its color and put it back. Calculate the probability that after T draws you've seen M distinct colors.

(T > 0, M > 0, M <= min(T, N) )

• 0

### #2 m00li

m00li

Junior Member

• Members
• 71 posts

Posted 06 May 2014 - 03:51 PM

Spoiler for solution attempt

• 0

### #3 bonanova

bonanova

bonanova

• Moderator
• 6161 posts
• Gender:Male
• Location:New York

Posted 09 May 2014 - 09:13 AM

Spoiler for Looks like

• 0

Vidi vici veni.

### #4 bonanova

bonanova

bonanova

• Moderator
• 6161 posts
• Gender:Male
• Location:New York

Posted 10 May 2014 - 02:09 PM

M different colors means: exactly M different colors, not: at least M colors, right?

• 0

Vidi vici veni.

### #5 plasmid

plasmid

Senior Lolcat

• VIP
• 1484 posts
• Gender:Male

Posted 10 May 2014 - 06:23 PM

Bonanova: using that formula with 3 balls being drawn 3 times...

probability of drawing 1 color
3! 13-1 / 33(3-1)! = 6*1 / 27*2 = 6/54

probability of drawing 2 colors
3! 23-2 / 33(3-2)! = 6*2 / 27*1 = 12/27

probability of drawing 3 colors
3! 33-3 / 33(3-3)! = 6*1 / 27*1 = 6/27

Sum of all three of those is less than 1.

I'm having trouble following m00li's logic. I got lost as soon as he started talking about selecting balls from an infinite choice of colors (which was pretty soon).
• 0

### #6 m00li

m00li

Junior Member

• Members
• 71 posts

Posted 11 May 2014 - 10:34 AM

Bonanova: using that formula with 3 balls being drawn 3 times...

probability of drawing 1 color
3! 13-1 / 33(3-1)! = 6*1 / 27*2 = 6/54

probability of drawing 2 colors
3! 23-2 / 33(3-2)! = 6*2 / 27*1 = 12/27

probability of drawing 3 colors
3! 33-3 / 33(3-3)! = 6*1 / 27*1 = 6/27

Sum of all three of those is less than 1.

I'm having trouble following m00li's logic. I got lost as soon as he started talking about selecting balls from an infinite choice of colors (which was pretty soon).

You are not alone Plasmid. I am having trouble too I must have been high on something that day
My solution is for cases where a 'selection' is being made out of n different colors. I should have calculated permutations and not selections.

• 0

### #7 plasmid

plasmid

Senior Lolcat

• VIP
• 1484 posts
• Gender:Male

Posted 11 May 2014 - 06:02 PM   Best Answer

Spoiler for atrocious but verified answer

Spoiler for this agrees with simulation - perl code

• 0

### #8 bonanova

bonanova

bonanova

• Moderator
• 6161 posts
• Gender:Male
• Location:New York

Posted 12 May 2014 - 09:37 AM

My formula made such sense to me (this is often the case until someone explains the logic that I overlook) that I posted it.  Then, embarrassingly, it did not agree with simulations.

The second part of the probability (after M colors appeared in M draws)
appeared to be incorrect by a factor of 2. I've been chasing that factor of 2
for several days, but only part time owing to preparations for a choral
performance this weekend. More, perhaps, to follow this week.

plasmid, your post #7 may have found it, since you have agreement with simulation.
I'll read it after I've given my approach another shot.

FWIW here is my simulation of 10000 cases for N = 10.
The 10 columns are for M = 1 ... 10.
The 20 rows are for T = 1 ... 20
The table entries are percent, rounded to nearest integer.

My equations agree for the major diagonal.

But they underestimate the probabilities elsewhere.

10 MNTHIST 10000
100  0  0  0  0  0  0  0  0  0
10 90  0  0  0  0  0  0  0  0
1 27 72  0  0  0  0  0  0  0
0  6 43 50  0  0  0  0  0  0
0  1 18 51 30  0  0  0  0  0
0  0  6 34 45 15  0  0  0  0
0  0  2 18 43 31  6  0  0  0
0  0  1  8 33 40 17  2  0  0
0  0  0  4 21 41 28  6  0  0
0  0  0  2 12 36 35 14  1  0
0  0  0  1  7 28 38 22  4  0
0  0  0  0  4 20 38 29  8  1
0  0  0  0  2 15 34 35 13  1
0  0  0  0  1 10 30 38 19  3
0  0  0  0  1  6 24 39 25  5
0  0  0  0  0  4 20 39 30  7
0  0  0  0  0  3 16 37 35 10
0  0  0  0  0  2 12 34 39 13
0  0  0  0  0  1  9 32 42 17
0  0  0  0  0  1  6 28 44 22

• 0

Vidi vici veni.

### #9 m00li

m00li

Junior Member

• Members
• 71 posts

Posted 25 May 2014 - 01:13 AM

More recursions:

Let f(t,m) denote the number of ways of arranging m colored balls in t slots, where t >= m and supply of each m coloured ball is infinite. Then final answer is nCmf(t,m) / nt

Here are the different recursions I have come up with for f(t,m)   (alas, no direct formula in m,n)

1) mtmC1f(t,1) - mC2f(t,2) - mC3f(t,3) .... - mCm-1f(t,m-1)

2) tC1f(t-1,m-1) + tC2f(t-2,m-1) + tC3f(t-3,m-1) + ... + tCt-m+1f(m-1,m-1)

3) mf(t-1,m-1) + m2f(t-2,m-1) + m3f(t-3,m-1) + ... + mt-m+1f(m-1,m-1)

4) m( f(t-1,m) + f(t-1,m-1) )

where f(t,1) = 1, f(t,2) = 2t-2, and f(t,t) = t!

• 0

### #10 bonanova

bonanova

bonanova

• Moderator
• 6161 posts
• Gender:Male
• Location:New York

Posted 25 May 2014 - 01:14 AM

So, I wonder. Is there no closed form solution?

• 0

Vidi vici veni.

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users