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

0
votes
0answers
22 views

Balls and Bins: Probability that every bin contains at most $O(logn)$ balls

I consider the balls and bins experiment, where we have $m=n\log n$ balls and $n$ bins. Every ball uniformly at random chooses one bin. We want to show that with probability $1-o(1)$ every bin ...
0
votes
0answers
58 views

balls in bins — waiting time until $k$ bins are occupied

Consider the classic balls in bins problem: we throw balls one by one into $n$ bins independently and uniformly. Define $\tau(k)$ for $1 \le k \le n$ to be the number of balls we have thrown until $k$ ...
0
votes
1answer
41 views

A Question on distribution numbers

This is a question from the book Combinatorics -a problem oriented approach which states: Q.1 Find the no. of distributions of a set of distinct balls into a set of distinct boxes, if no boxes can ...
0
votes
1answer
698 views

Number of ways to distribute identical balls into identical bins

I have a question which I expected to be quite famous and common, yet I haven't found much... How many ways are there to distribute $k$ identical balls into $n$ identical bins? For example $(k, ...
0
votes
0answers
31 views

Expectation Time to Pick all the colors of balls in urn

I am so jealous of those guys who are math genius.. Here is a ball in urn question. Suppose there are n different colors of balls in an urn (totally n balls with n colors). Randomly pick up one each ...
0
votes
1answer
134 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$. ...
0
votes
1answer
61 views

r distinct objects into n distinct boxes ( ordering of objects in each box matters)

I have a question and solution as well ,but I don't understand it: If r distinct objects are to be distributed into n distinct boxes each box can hold any number of objects and the ordering of objects ...
1
vote
2answers
116 views

Probability of assigning balls into buckets, where each bucket has a certain capacity.

I'll start with a specific example of what I am trying to solve: I have eight balls to be randomly placed into four buckets. Buckets #1-3 have the capacity of 2, 2, 3 respectively, while bucket #4 ...
0
votes
2answers
35 views

Probability that the first $2$ balls are white, given that the sample contains exactly $6$ white balls

An urn contains $30$ white and $15$ black balls. If $10$ balls are drawn without replacement, find the probability that the first $2$ balls are white, given that the sample contains exactly $6$ ...
2
votes
2answers
91 views

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls?

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls? I don't know how to even approach this. A rough number is also ...
1
vote
0answers
26 views

Distribution of maximum/minimum proportion in a sampling process

I am facing something that can be explained as a balls & urns problem. Suppose you have $B$ black and $W$ white balls inside an urn. They are randomly chosen, one by one, without replacement, and ...
1
vote
0answers
41 views

Occupancy distribution bounds for $k$ balls in $m$ bins

Suppose we throw $k$ (distinct) balls into $m$ (distinct) bins, and let $B$ count the number of non-empty bins. I am interested in lower bounds on $B$. More precisely, I wish to bound from above the ...
5
votes
1answer
107 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 ...
3
votes
1answer
38 views

Expected total number of balls in all bins after throwing balls uniformly randomly to bins that have limited capacity

Consider throwing $n$ balls uniformly randomly to $L$ bins. Each bin has capacity $G$, meaning that if a ball is threw to a bin that already has $G$ balls in it, the ball is discarded. Is that ...
2
votes
3answers
192 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 ...
0
votes
1answer
64 views

Expected number of bins with more than one ball

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 ...
31
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 ...
1
vote
1answer
70 views

Is there a fast, reasonably accurate estimator for multinomial PDF?

I am working on a balls in boxes kind of problem, where the probability of a ball ending up in a certain box varies by box, that is, each box has some probability P of getting any ball, all together ...
0
votes
2answers
75 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 ...
2
votes
3answers
69 views

Find the probability that the $4$th ball removed from the box is white

A box has $10$ balls, $6$ of which are black and $4$ of which are white. $3$ balls are removed from the box, their color unnoted. Find the probability that a fourth ball removed from the box is ...
1
vote
1answer
53 views

Expectation time for at least 2 balls in each bin

Given $N$ bins and an unlimited number of balls, to be assigned one ball per time unit to a uniformly random bin. What is the expected time to achieve at least 2 balls in every bin? From a previous ...
0
votes
1answer
120 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 ...
1
vote
1answer
145 views

$n$ balls into $k$ baskets, $n \geq k$, no empty baskets

I have $n$ balls and throw them into $k$ baskets. None of $k$ baskets should be empty. Which means each basket has at least one ball. Balls and baskets are not distinguishable. What is the number ...
2
votes
3answers
125 views

Constrained combinations of balls in jars

Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls. The question is how many ...
0
votes
3answers
57 views

Count all events for k distinguishable items in n distinguishable bins

I want to count all the possible cases that I can distribute k distinguishable items in n distinguishable bins, for example for 3 items and 2 bins I have the next n^k the possible cases are: I ...
1
vote
1answer
45 views

What is the probability of picking $4$ balls out from the two bins?

Assume there are $2$ bins (bin $a$ and bin $b$ ), and each bin contains $n$ indistinguishable balls with $n>10$. The probability of picking $k$ ball from each bin is $p_k$, ($k\ge 0$). Then what is ...
1
vote
1answer
83 views

Combinatorics with balls and bins with constraint

I have $90$ identical balls to distribute among $64$ distinguishable bins. Each must get at least 1 ball, after that the distribution over the remaining $26$ does not matter. I know I first have to ...
1
vote
2answers
70 views

probability that given n balls and 60 urns no urn has more than 1 ball

A carnival game is set up so that a ball put into play has an equal chance of landing in any of 60 different slots. The operator of the game allows you to choose any number of balls and put them all ...
1
vote
0answers
64 views

Balls and bins question with nlogn balls and n bins.

The question: Suppose we randomly drop nlogn balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin. How would this be done? I believe the answer is well ...
1
vote
2answers
57 views

Inclusion/Exclusion Principle for indistinguishable balls into two different types of boxes

The problem asks me how to distribute n balls into h boxes where each must get at least 1 n and t boxes where each can be left empty What I have, and where I seem to have stalled is how to ...
5
votes
3answers
760 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 ...
-1
votes
2answers
144 views

Balls and bins problem - expected number of balls needed to throw [closed]

Suppose we have n boxes and we start randomly and independently throwing balls into the boxes. (a) For a given box, what is the expected number of balls we need to throw before one of the balls lands ...
1
vote
1answer
270 views

Expectation of throwing $n$ balls into $n$ bins

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 ...
1
vote
0answers
65 views

How to estimate pigeonhole principle?

I was thinking about this after my professor mentioned the pigeonhole principle in class. Let's say we have $N$ items and $M$ containers. Here we assume $N > M$. We will randomly place each of the ...
0
votes
2answers
174 views

Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
7
votes
2answers
3k 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 ...
1
vote
2answers
138 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
2
votes
1answer
137 views

Bins and balls model - filling first bins [close]

We have $n$ bins and $m$ balls. I want to compute the probability that in the first $k$ bins, $q$ of them will be non-empty. I can throw $m$ balls into $n$ bins in $n^m$ ways. Using Stirling ...
0
votes
1answer
197 views

Ball and bins & Coupon collector problem

If you know a coupon collector problem, you will know what I am talking about. But if you are not familiar with I will try to explain what is the coupon collector problem. I have $n$ bins. I throw ...
1
vote
2answers
113 views

How many ways to $22$ balls in $5$ boxes problem

How many ways are there to put $22$ identical balls into $5$ boxes, with each box has at least $2$ balls? The answer is $16$ choose $4$, i.e., $_{16}C_4$, but can someone explain it to me?
0
votes
2answers
64 views

Probability and conditional?

A bag contains four red balls and four white balls. A ball is selected at random, removed and replaced by a ball of the opposite colour. A second ball is then selected at random. Calculate the ...
0
votes
1answer
64 views

probability of specific number of balls in an urn

I have $n$ balls, I distribute them between 2 urns. Each ball goes to urn 1 with probability $p$ and urn 2 with probability $1-p$. What is the probability that there are $l$ balls in urn 1 when all ...
2
votes
1answer
479 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 ...
1
vote
0answers
124 views

The probability of two balls going into the same bin

Suppose I have n bins and n balls with label on them. What would be the probability that I throw the i th ball into the same bin as the j th ball? Is it just 1/n because there is a probability of 1/n ...
0
votes
1answer
77 views

Balls and bins with 2 balls and 2 bins

I'm trying to understand a proof in a paper I'm reading. It relies on a balls and bins problem. Here is what I'm trying to figure out: We want the maximum number of balls in a bin. We have 2 balls ...
0
votes
1answer
591 views

Balls and bins probability problem

$k = \sqrt n$ balls are thrown into $n$ bins. The bins are standing in a row and numbered from 1 to $n$. What is the probability that there are no two balls in the same bin or in adjacent bins??? In ...
2
votes
0answers
70 views

Maximum bin load for $\alpha n$ balls into $n$ bins

In a paper I am reading the author writes: A standard result concerning balls and bins shows that if we throw at least $\alpha n$ balls into at most $n$ bins, then the maximum bin load is ...
0
votes
2answers
155 views

A bin and balls problem

Throw 7 balls into 7 bins. Given there are exactly 2 empty boxes, find the probability that 1 bin contains 3 balls, and thus the other 4 bins contain 1 ball each. I know I could use a multinomial ...
0
votes
1answer
1k views

Distribute distinct objects in identical boxes

Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one? $\mathbf {Is\ there\ any\ standard\ formula\ for\ these\ sums}$, as we have for ...
2
votes
1answer
123 views

Bounds for 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 a nice elementary way to ...