Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have $n$ sets and $k$ elements with $k\gt n$. Each elements has the same probability $\left(\frac1n\right)$ to be inserted in a set. All the elements have to be inserted in one single set.

I need to calculate the probability the difference of number of elements between the fuller set and the emptier one is at least $X\%$.

For example, given $10$ sets and $100$ elements I need to calculate the probability one sets has at least the $10\%$ of elements more than another.

share|cite|improve this question
OK, this is what you need. And what did you try to do that? – Did Aug 3 '12 at 10:55
I thought in the beginning find all the possible combination of n number which the sum of all of them is equal to k. After that I should to enumerate all the sequence where min{Sn}/max{Sn}>=0.9. After that it's easy. But my mathematics lacks and I don't know how to go further.. I can solve it only by computational brute force but it is not good for my analytical purpose. – cesare Aug 3 '12 at 12:05
I don't think that this problem has a simple solution. Approximate formulations (Poisson approximations) would only be useful for large $n$,$k$, and still the formulas would be quite complex. Even computing the probabilities for the maximum alone is difficult, see eg – leonbloy Dec 16 '14 at 17:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.