It's about distribution or arrangement of $m$ distinct or identical balls into $n$ distinct or identical bins with all possible combinations.

learn more… | top users | synonyms

5
votes
1answer
1k views

$n$ balls are thrown randomly into $k$ bins - how many are empty?

A large number of variants of this question were already asked here, including these - one, two, which are close, but none seem to answer my question. Assume that $n$ balls are thrown randomly and ...
5
votes
1answer
308 views

How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?

Assume all balls with the same color are indistinguishable. The order in which balls are put in a bin does not matter. No bins are allowed to have the same distribution of balls! For example, this ...
7
votes
4answers
6k views

If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?

If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what ...
0
votes
2answers
287 views

How many positive integer solutions are there to the inequality $x_1+x_2+…+x_r\le n$?

The original problem is there are $r$ identical boxes and $n$ identical balls. Every box is nonempty. Then how many ways of putting balls in boxes? It is equivalent to the problem of finding ...
5
votes
3answers
6k views

How can I solve bins-and-balls problems?

Below is the problem that I wanted to solve When there are $m$ balls and $n$ bins, balls are thrown into bins where each ball is thrown into a bin uniformly at random. What is the expected number ...
11
votes
3answers
927 views

Probability $k$ bins are non-empty

The following problem arises in the analysis of Bloom filters. Consider $m$ bins and $N=nk$ balls placed uniformly and independently at random into the bins. A query chooses $k$ bins uniformly and ...
8
votes
3answers
2k views

Expected max load with $n$ balls in $n$ bins?

If you throw $n$ balls into $n$ bins uniformly and independently at random, let $X$ be the number of balls in the bin with the largest number of balls in it. Is there an elementary way to ...
6
votes
3answers
450 views

Second pair of matching birthdays

The "birthday problem" is well-known and well-studied. There are many versions of it and many questions one might ask. For example, "how many people do we need in a room to obtain at least a 50% ...
5
votes
1answer
184 views

Probability of drawing a run of a specific color from an urn with two colors of balls

I was sent a puzzle involving an urn with 128 white balls and 288 black. If the balls are drawn without replacement until the urn is exhausted, what is the probability that a sequence of 10 or more ...
2
votes
2answers
1k views

Probability of having $k$ empty urns after putting $n$ balls into $n$ urns

Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn. Balls are randomly thrown into urns: Each ball is ...
0
votes
1answer
74 views

Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?

I have n objects and k boxes, each box has its own size. The arrangement of objects in a box doesn't matter. How many combinations are there, respectively the formula? Say we have 7 objects and 3 ...
0
votes
1answer
91 views

Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$

Let $n,k,r$ be positive integers. The number of all nonnegative solutions of the Diophantine Equation $x_1+x_2+\dots+x_k=n$ is $\binom{n+k-1}{n}$. Is there a general formula for the number of ...
2
votes
2answers
427 views

Probability of number of unique numbers in $37$ Roulette Wheel spins.

I was wondering if someone could help me answer the following question: Calculate the probability that in $37 $ consecutive spins of a roulette wheel (using an European Roulette wheel) you will have $...
2
votes
3answers
704 views

We throwing $m$ balls to $n$ cells…

We throwing $m$ balls to $n$ cells randomly... At each cell can be more then one ball, or (of course) it can still empty. What is the expectation of the empty cells? I'd like to get any help! Thank ...
1
vote
2answers
465 views

Throwing $k$ balls into $n$ bins.

I have the following question: Throwing $k$ balls into $n$ bins. What is the probability that exactly $z$ bins are not empty? I thought about something like: $$\Pr(z)=\frac{n! z^{k-z}}{n^k (n-z)!},$...
35
votes
3answers
6k views

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

I have a very simple simulation program, the sequence is: Create an array of 400k elements Use a PRNG to pick an index, and mark the element (repeat 400k times) Count number of marked elements. An ...
9
votes
1answer
298 views

How many expected people needed until 3 share a birthday?

I asked a somewhat related question recently and then became interested in this one: how many people are required, on average, until 3 share a birthday? More generally, if we have $M$ bins, what is ...
9
votes
4answers
1k views

Probability that all bins contain strictly more than one ball?

Here's the problem I'm working on: Given that I'm distributing $N$ balls into $K$ bins, what is the probability that all bins contain at least two (strictly more than 1) balls? This seems like a very ...
8
votes
2answers
838 views

Find: The expected number of urns that are empty

A total of $n$ balls, numbered $1$ through $n$, are put into $n$ urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the urns $1, 2, . . . , i$. Find ...
6
votes
1answer
661 views

$m$ balls into $n$ urns

Assume that there are $m$ balls and $n$ urns with $m\gt n$. Each ball is thrown randomly and uniformly into urns. That is, each ball goes into each urn with probability $\dfrac1n$. What is the ...
3
votes
1answer
382 views

$k$ balls into $n$ bins — Number of occupied bins

Suppose we throw $k$ balls into $n$ bins. Assume that $\log^2n\le k\le n$. Is there a high probability bound (preferably exponential) on the number of occupied (i.e., non-empty) bins? Something ...
2
votes
1answer
954 views

Distribution of distinct balls in identical boxes

how can I derive a formula for the number of distributions of $n$ different balls in $k$ identical boxes. Where $\mathbf{empty\ box}$ is allowed. I know this is equivalent to finding the number of ...
5
votes
0answers
35 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
1
vote
0answers
115 views

Balls and Bins- Hash Table: a Concrete Example

My question is related to this: http://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030 In [1,2], it is said that if we throw $n$ balls into $...
1
vote
1answer
986 views

Expectation of throwing $n$ balls into $n$ bins [duplicate]

Suppose we throw $n$ indistinguishable balls in $n$ bins at random. The throws are independent. What is the expected number of empty bins? What is the expected number of bins with one ball. Using ...
0
votes
1answer
390 views

$N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls.

This is an extension to question 821984: Given $N$ balls independently distributed randomly among $m$ bins, what is the probability that at least one bin gets exactly $k$ balls? And is this ...
0
votes
1answer
318 views

Expected number of bins with more than one ball [duplicate]

Suppose that $n$ balls are randomly thrown into $N$ bins. We can compute the expected number of bins that contain at least one ball as $E(X) = N(1 - (1 - 1/N)^n)$. Now, suppose that instead we are ...
0
votes
1answer
659 views

r identical objects into n distinct boxes

The question says that there are r identical balls to be placed in n boxes s.t. $r\geq n$ .How many ways are there such that each box contains atleast one object?The solution is $n+r-n-1\choose n-1$. ...