# Tagged Questions

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

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 ...
324 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 ...
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 ...
289 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 ...
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 ...
947 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 ...
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 ...
456 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% ...
188 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 ...
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 ...
93 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 ...
78 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 ...
431 views

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 ...
310 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 ...
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 ...
846 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 ...
665 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 ...
390 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 ...
964 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 ...
36 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$ ...
1k 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 ...
44 views

393 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 ...
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$. ...
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 ...