Hi everyone!
I have a fun problem in combinatorics to solve. I am searching for an analytical formula for the answer. Right now I use a recursive function to solve it.
A bowl contains N balls of each of L different colors (NxL balls in total). You pick M <= NxL balls without replacement. What is the probability of having picked K balls of the same color, but less of the others?
If someone can give me reference to discussion of this problem, I'ld be glad.
Best regards,
Arni Richard
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
This should actually be
"What is the probability of having picked exactly K balls of the same arbitrary color, but less from the other colors?"
For example, a bowl contains 5 red balls, 5 blue. (N = 5, L = 2)
I pick 3 balls. (M = 3).
What is the probability of the event that I have 2 red balls and 1 blue, or 2 blue balls and 1 red. (K = 2).
I see where I misread your statement. Let me see if I have it at least partially right.
Say we have five colors each with 5 balls.
I am to pick 12 balls. 3 are to be (let us say) red.
What is the probability of doing this without getting more than two of any other color.
Clearly there are some limits on M and K. Cearly M<21, K<6, If M=1 then K=1. If M=2, then K must = 2 M cannot be < K. In your case above proability is 36 out of 100 but I do not have an analytical equation.
For the specific case you stated, which is more specific than the general solution:
number of balls B = N* L
total combinations = choose(B, M) = 10 choose 3 = 10*9*8/(3*2) = 720/6 = 120
Of those, you want the probability that you choose 2 of 5, and 1 of 5
(N/B) * (N-1)/(B-1) * (N-1)/(B-2) + (N/B) * (N-1)/(B-1) * (N-1)/(B-2)
in general, there need not be a single value for N. There could be N1 = 5, N2 = 14. The idea still works.
Limits on M and K
K<=M
Number of balls picked is less than or equal to picking K-1 of all colors, and one more of the arbitrary color.
M <= KL - L + 1
In terms of K,
K - 1 >= (M-1)/L
K >= 1 + (M-1)/L
1 + (M-1)/L <= K <= M
If L = 1 P=1
If L = 2, the problem becomes very simple. P = KCN * (M-K)CN / MC(LN)
# of ways of choosing the K balls from the designated color TIMES
# of ways of choosing the M-K remaining balls from the other color DIVIDED BY
# of ways of choosing all balls.
If L = 3, the problem becomes much harder.
P = KCN * SUM(i = MAX(0, M-K-(K-1)) to MIN(M-K,K-1)) [iCN * (M-K-i)CN] / MC(LN)
Why the restrictions on i?
i can be no greater than the balls left over (M-K) nor K-1.
the number of balls leftover after picking the i balls can not be over (M-K) nor K-1
and so forth.
If the color of the K balls do not matter, simply multiply the answer by L.
For your example: (N = 5, L = 2). (M = 3). (K = 2).
P = KCN * (M-K)CN / MC(LN)
= 2C5 * (3-2)C5 / 3C(2*5)
= 2C5 * 1C5 / 3C10
= 5 * 4 / 2 * 5 / ((10*9*8)/(3*2*1))
= 10 * 5 / 120
= 50 /120
= 5/12
~0.416667
If color does not matter, 5/12 * 2 = 10/12 = 5/6 ~ .83333
sorry i correct my post :
We suppose :
X= N * L
Answer is : Sigma ( (1/X)*(1/(X-1))*(1/(X-2))*
hint : [2.xxx] = 2
==========================
for example N = 5 , L = 2 , M = 5
you want to pick 5 ball .. you want a probility of '1 of your desire colour' , '2 of your desire colour'
answer is : 1/90 + 1/10
im really sorry for my incorrect posts ..
today i found that all my posts are incorrect ..
but i think this one is correct :D :
X = N * L
we define a function of probablity of picking a desire colour ball when we pick M Ball ..
F(N,L,M,a) = (N/X) * (N-1/X-1) * ... * (N-(a-1)/X-(a-1)) * ( X-N/X-a ) * (X-N-1/X-a-1) * ... *(X-N-(M-a-1) / X-(M-1))
For your question :
Answer = Sigma (F(N,L,M,a) , a = 1 .. [M/2])
[2.xxx] = 2
in according to that Function the answer of you Example is :
N = 5 , L = 2 , M = 3
F(5,2,3,1) = 5/10 * 5/9 * 4/8 = 10/72 // one red & 2 blue
F(5,2,3,2) = 5/10 * 4/9 * 5/8 = 10/72 // 2red & one blue
is it helpful ?
F(5,2,3,1) = 5/10 * 5/9 * 4/8 = 10/72 = 5/36 // one red & 2 blue
This is the probability of picking one blue ball, then one red ball, then another blue ball.
However, this misses,
red, blue, blue = 5/10 * 5/9 * 4/8 = 5/36
blue, blue, red = 5/10 * 4/9 * 5/8 = 5/36
Total probability for 2 blue and one red= 15/36 = 5/12
as shown easier.
I do not recommend this method, as it just seems painful to calulate and would become unmanageable with big enough M or L. Using nCr is much easier.
I think there is no simple analytical formula for that.
Notice that the number of ways to choose M balls out of N*L balls equals the binomial coefficient C(N*L,M). That's simple.
Now let's count the number of ways of "having picked K balls of the same color, but less of the others". First we need to select a color with K balls picked out of L colors, it brings a factor of L*C(N,K) (the binomial coefficient C(N,K) stands for choosing K specific balls of selected color out of N balls) to the answer and leaves us with L-1 non-selected colors. From each of these L-1 colors we need to pick at most K-1 balls, with the total amount of M-K balls. I do not see any better description than in term of generating functions. Namely, the number of ways to pick M-K balls of L-1 colors with at most K-1 balls of each color equal the coefficient of x^(M-K) in the expansion of
(1 + C(N,1)*x + C(N,2)*x^2 + ... + C(N,K-1)*x^(K-1))^(L-1)
that is denoted as follows:
[x^(M-K)] (1 + C(N,1)*x + C(N,2)*x^2 + ... + C(N,K-1)*x^(K-1))^(L-1)
Hence, the final answer for the probability you've asked is
L * C(N,K) * [x^(M-K)] (1 + C(N,1)*x + C(N,2)*x^2 + ... + C(N,K-1)*x^(K-1))^(L-1) / C(N*L,M)
This answer can be simplified in some cases:
1) If M<2K then the probability can be computed simply as
L * C(N,K) * C(N*(L-1),M-K) / C(N*L,M)
2) If K=1 then the probability is 0 unless M=1, in which case the probability is 1.
3) If K=2 then the probability is L* C(N,2) * C(L-1,M-2) * N^(M-2) / C(N*L,M)
For example, let's compute the answer in the case N=5, L=2, M=3, K=2 considered by others.
We can apply either formula 1 (since M<2*K):
F(5,2,3,2) = 2 * C(5,2) * C(5*(2-1),3-2) / C(5*2,3) = 2 * C(5,2) * C(5,1) / C(10,3) = 2 * 10 * 5 / 120 = 5/6
or formula 3 (since K=2):
F(5,2,3,2) = 2 * C(5,2) * C(1,3-2) * 5^(3-2) / C(5*2,3) = 2 * 10 * 1 * 5 / 120 = 5/6
Business Accounts
Answer for Membership
by: aburrPosted on 2006-10-06 at 11:07:44ID: 17678795
"What is the probability of having picked K balls of the same color, but less of the others?"
The import of the " but less of the others" puzzles me.
How many balls are you picking? 5? 10? K?
So you pick K. What is the probablilty that they will all be the same? (small, if K is large) but what is this "less".
Are you given a particular color? Pick K balls and find that color to be the less? If you pick K balls, the probability that one of the colors will be less (or equal) is 100%